commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Simone Tripodi <>
Subject Re: [graph] Doubts on DFS algorithm implementation
Date Mon, 27 Feb 2012 19:57:15 GMT
+1 to Claudio!

On Mon, Feb 27, 2012 at 7:35 PM, Claudio Squarcella
<> wrote:
> 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
> ---------------------------------------------------------------------
> To unsubscribe, e-mail:
> For additional commands, e-mail:

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message