Hello,
the method "discoveryEdge" currently tells whether or not the algorithm should explore a
subtree/branch and add related vertices to the stack/queue. So I see no conflict in the implementation. Maybe
you are saying that the edge should be explored *right before* the vertex it leads to -- but why? AFAIK a
standard graph search is only concerned with *vertices*. In that sense "finishEdge" becomes
useless, as the responsibility for returning prematurely is entirely covered by "finishVertex". Am
I raving mad? :-)
yes you are right, the visit should be only concerned the vertices, but in our
implementation we added also the discoveryEdge that in a dfs has invoked like a
BFS. This in my opinion can be frustrating for the user because the edge is not
visit in depth but in breadth.
So IMHO we should visit also the edge in depth, (only in a dfs of course) or
remove the invocation of discover/finish edge that can get confused the user.
if you want to postpone the edge visit to the right time (i.e. when the
corresponding tail vertex is removed from the "waiting list") then I
guess the waiting list itself should also keep track of the edge and/or
the predecessor (vertex). The class PredecessorsList probably does that
job fairly well.
Rephrasing a bit: we are seeking a unified implementation for both
standard "graph searches" (only concerned with vertices) and more
general "graph visits" (e.g. the one needed for max flow algorithms). So
yeah, let's use our brains for something cool :)
P.S. I would not remove "discoverEdge" anyway because, as I said before,
it can help pruning the graph and avoiding to explore dead ends (e.g.
for max flow, there is no point in traversing edges with no residual
flow capacity).
Ciao
Claudio
--
Claudio Squarcella
PhD student at Roma Tre University
http://www.dia.uniroma3.it/~squarcel
http://squarcella.com/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
