commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Claudio Squarcella <squar...@dia.uniroma3.it>
Subject Re: [graph] Doubts on DFS algorithm implementation
Date Mon, 27 Feb 2012 18:35:19 GMT
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-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message