commons-dev mailing list archives

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

http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/



On Mon, Feb 27, 2012 at 7:35 PM, Claudio Squarcella
<squarcel@dia.uniroma3.it> 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
> 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
>

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message