commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Marco Speranza <marcospera...@apache.org>
Subject Re: [graph] Doubts on DFS algorithm implementation
Date Mon, 27 Feb 2012 08:05:35 GMT
Hi Claudio

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

have a nice day 

--
Marco Speranza <marcosperanza@apache.org>
Google Code: http://code.google.com/u/marco.speranza79/

Il giorno 26/feb/2012, alle ore 23:41, Claudio Squarcella ha scritto:

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


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


Mime
View raw message