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

[Idan M. <ida...@gm...>]

The graph building is done by getting the vertices and edges from a database
and creating them.
The vertices and edges may come in a different order each time because the
select query is not sorted.
Could the order difference of adding the edges may cause this to happen?

If I add edge A to the graph than edge B, will I get A and then B in the
iterator, and if I put B than A will that change to B and A in the iterator
respectively?

If so, that may be it.

Idan.

On Mon, Feb 16, 2009 at 6:11 AM, John V. Sichi <js...@gm...> wrote:

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