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 Sun, 26 Feb 2012 22:41:39 GMT
Hi,

> Simo you are right, the vertices have visited in the right way, but the edge handler
has called in the wrong way.  IMHO we have to modify the code in order to fire the edge handler
in the right way to avoid any error for the user.

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? :-)

> It's a good idea, Now we have implemented two separate methods that visit the graph for
dfs and bfs. We should do a little refactoring and implement a unique method that switches
between dfs and bfs simply changing the the type of visitedVertex. WDYT?

Yes! James' idea sounds good to me.

Ciao,
Claudio

>> I think "visitedVertices" should rather be called "seenVertices", as it is only needed
to avoid adding vertices more than once to the stack/queue. Marco (and all), please see if
the implementations look nicer with that change in mind (looks good to me).
>>
> +1

-- 
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