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

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

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