Re: [jgrapht-users] Non-determinstic getSpanningTreeEdge call

[John V. S. <js...@gm...>]

After reviewing the code, I can't find any source of non-determinism, 
but I probably missed something.

The only hash-based data structure involved is the "seen" HashMap in 
CrossComponentIterator, but that is only used for associative lookups 
(we never iterate over its keys/values).

So assuming that the way you build the input graph is deterministic, 
then the result should be also.

JVS

Idan Miller wrote:
> Hi everyone,
> 
> I'm using the ClosestFirst iterator to calculate a weighted BFS.
> The problem is, I get non-deterministic results with calling 
> getSpanningTreeEdge for the same graph.
> Any idea how I can make it deterministic? It's not mentioned in the 
> documentation.
> 
> Here's the code snippet:
> 
> private static synchronized NavigationGraph 
> findSpanningTree(NavigationGraph graph)
>     {       
>         // Run BFS starting from the root node and create a result graph
>         DirectedGraph<NavigationGraphNode, NavigationGraphEdge> tree =
>             new DefaultDirectedGraph<NavigationGraphNode, 
> NavigationGraphEdge>(NavigationGraphEdge.class);
>         tree.addVertex(graph.getRoot());
>        
>         ClosestFirstIterator<NavigationGraphNode, NavigationGraphEdge> 
> iterator =
>             new ClosestFirstIterator<NavigationGraphNode, 
> NavigationGraphEdge>(graph.getGraph(), graph.getRoot());
>        
>         while (iterator.hasNext())
>         {
>            NavigationGraphNode currVertex = iterator.next();
>            
>             // Add target vertex and edge to tree
>             tree.addVertex(currVertex);
>             NavigationGraphEdge edge = 
> iterator.getSpanningTreeEdge(currVertex);
>            
>             if (edge != null)
>             {
>                 tree.addEdge(graph.getGraph().getEdgeSource(edge), 
> currVertex, edge);
>             }
>         }
>        
>         return (new NavigationGraph(tree, graph.getRoot()));
>     }
> 
> 
> ------------------------------------------------------------------------
> 
> ------------------------------------------------------------------------------
> Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco, CA
> -OSBC tackles the biggest issue in open source: Open Sourcing the Enterprise
> -Strategies to boost innovation and cut costs with open source participation
> -Receive a $600 discount off the registration fee with the source code: SFAD
> http://p.sf.net/sfu/XcvMzF8H
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users