Should undirected DFS raise BackEdge event on source edge?

Jul 21, 2009 at 10:46 PM
Edited Jul 21, 2009 at 11:04 PM

UndirectedDepthFirstSearchAlgorithm examines all edges on the current vertex and raises a BackEdge event on the edge from which it arrived. In my opinion this is undesirable behavior. BackEdge events are useful for detecting cycles but this event creates a 'false positive' at every vertex. Conversely, I don't see the utility of the event being raised on the 'arriving from' edge - I'd be curious to hear about applications in which this event is actually interesting to the listener.

Proposed change: add a TEdge source member to SearchFrame; then in v's edge iteration when the current edge equals source either skip all processing whatsoever or else only raise an ExamineEdge event on it (but no BackEdge event).

Coordinator
Jul 22, 2009 at 5:42 AM

I foolisheled ported the directed algorithm to undirected. I need to look into that.

Jul 22, 2009 at 4:50 PM

I've uploaded a .diff file with the proposed change.