+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 <squar...@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-unsubscr...@commons.apache.org > For additional commands, e-mail: dev-h...@commons.apache.org > --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
