Ticket #4127 (closed defect: fixed)

Opened 6 years ago

Last modified 6 years ago

Update BFS interface to filter before anything else

Reported by: gemacke Owned by: gemacke
Priority: normal Milestone: 1.2
Version: 1.1.1 Severity: normal
Keywords: Cc:

Description

The current BFS interface does filtering of the graph via visit_test(), but the filtering is done after incrementing the color array and examining the edge. This is incorrect behavior; the filtering should be done before anything else. The color array should only be incremented if the filter is passed.

To accomplish this, I am separating checking the color array from filtering. The visit_test() function will be renamed to filter(), and it will return if the next edge / vertex passes the filter and should be considered by the algorithm. I am adding the function color_test() to the BFS visitor that will perform the incrementing on the color array and return true if the vertex hadn't been accessed before and false otherwise. filter() will be called first, and color_test() will only be called if the edge passes the filter.

These changes allow the user to ignore the color array completely by redefining color_test() to just return true. The user can also pass in a NULL pointer for the color array after redefining color_test() to return true since that value is only used inside color_test().

Change History

comment:1 Changed 6 years ago by gemacke

  • Status changed from new to accepted

comment:2 Changed 6 years ago by gemacke

  • Status changed from accepted to closed
  • Resolution set to fixed

Fixed in r3826 and r3827.

Note: See TracTickets for help on using tickets.