jgrapht-users

[jgrapht-users] Non-determinstic getSpanningTreeEdge call

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

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()));
    }

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

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

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

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

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

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

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

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
>

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

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