Hi,
On 25/02/2012 19:51, James Carman wrote:
The code shouldn't "visit" each of the connected nodes during the
iteration. It should only visit the "popped" node and then add all
un-visited, connected nodes to the stack. Hopefully we've implemented
this so that all we have to do to switch from dfs to bfs is to swap
out the collection used. If you switch to a queue rather than a
stack, it magically changes to bfs. I've done this before using the
"buffer" abstraction in commons collections.
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).
Claudio
On Sat, Feb 25, 2012 at 1:48 PM, Simone Tripodi
<simonetrip...@apache.org> wrote:
Hi Marco,
IIRC the vertex order should be guarded by the vertexStack - maybe it
is just the handler be called in the wrong way.
Do you have/can you provide please testcases?
TIA,
-SImo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
On Sat, Feb 25, 2012 at 6:47 PM, Marco Speranza
<marcospera...@apache.org> wrote:
Hi all. I've a little doubt on DFS algorithm implemented in the
DefaultVisitAlgorithmsSelector.
I think that the visit doesn't serch in depth but in a breadth way.
here is a little code snippet:
[ ... ]
while ( visitingGraph&& !vertexStack.isEmpty() )
{
V v = vertexStack.pop();
if ( handler.discoverVertex( v ) )
{
Iterator<V> connected = ( graph instanceof DirectedGraph ) ? (
(DirectedGraph<V, E>) graph ).getOutbound( v ).iterator()
: graph.getConnectedVertices( v ).iterator();
while ( connected.hasNext() )
{
V w = connected.next();
if ( !visitedVertices.contains( w ) )
{
E e = graph.getEdge( v, w );
if ( handler.discoverEdge( v, e, w ) )
{
[ ... ]
I think that the algo explores the edge, and than fires handler.discoverEdge(
v, e, w ), in breadth and not in depth, doesn't it?
best regards
--
Marco Speranza<marcospera...@apache.org>
Google Code: http://code.google.com/u/marco.speranza79/
---------------------------------------------------------------------
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
--
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
