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

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

Let me know if you find something specific in JGraphT that you think is 
behaving unexpectedly.

JVS

Idan Miller wrote:
> I tested create a simple graph differently (different vertex addition, 
> different edge addition) and the results were always the same.
> I always got the 2-4 edge and not the 3-4 edge.
> So maybe there is something else that is a problem here?
> 
> Here's the code:
> 
> public static void main(String[] args)
>     {
>         DefaultDirectedWeightedGraph<Integer, String> graph =
>             new DefaultDirectedWeightedGraph<Integer, String>(String.class);
>        
>         int vertex1 = 1;
>         int vertex2 = 2;
>         int vertex3 = 3;
>         int vertex4 = 4;
>        
>         graph.addVertex(vertex1);
>         graph.addVertex(vertex4);
>         graph.addVertex(vertex3);
>         graph.addVertex(vertex2);
>        
>         graph.addEdge(vertex1, vertex2, "1-2");
>         graph.addEdge(vertex1, vertex3, "1-3");
>         graph.addEdge(vertex3, vertex4, "3-4");
>         graph.addEdge(vertex2, vertex4, "2-4");
>              
>         // Run BFS starting from the root node and create a result graph
>         DefaultDirectedWeightedGraph<Integer, String> tree =
>             new DefaultDirectedWeightedGraph<Integer, String>(String.class);
>        
>         tree.addVertex(vertex1);
>        
>         ClosestFirstIterator<Integer, String> iterator =
>             new ClosestFirstIterator<Integer, String>(graph, vertex1);
>            
>         while (iterator.hasNext())
>         {
>            int currVertex = iterator.next();
>            
>             // Add target vertex and edge to tree
>             tree.addVertex(currVertex);
>             String edge = iterator.getSpanningTreeEdge(currVertex);
>            
>             if (edge != null)
>             {
>                 tree.addEdge(graph.getEdgeSource(edge), currVertex, edge);
>             }
>         }
>     }
> 
> On Mon, Feb 16, 2009 at 10:58 AM, Idan Miller <ida...@gm... 
> <mailto:ida...@gm...>> wrote:
> 
>     I'm trying to reproduce the behaviour in a simple graph and check
>     the theory.
>     Sounds like that is the problem.
> 
>     Thanks,
>     Idan.
> 
> 
>     On Mon, Feb 16, 2009 at 10:22 AM, John V. Sichi <js...@gm...
>     <mailto:js...@gm...>> wrote:
> 
>         Idan Miller wrote:
> 
>             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.
> 
> 
>         Yes, sounds like that is your problem.  You may be able to solve
>         it by adding an ORDER BY to your database queries.
> 
>         JVS
> 
> 
>