Re: Bellman-Ford Query

[Yoann Pigné <yoann.pigne AT gmail.com>]

The thing is Bellman-Ford is a weighted digraph algorithm. By definition, it 
can only work with directed edges (arcs). 

Now, what we do in GraphStream, since you are free to define directed or 
undirected edges, is to consider undirected edges as directed ones. So in 
your example, edge « 1-2 » will actually be considered as a directed arc. 
That would explain, I hope, the obtained results. 

Should we explain this behaviour clearly in the documentation? Sure!

Should we adopt another behaviour like (throw an exception, duplicate 
undirected edges, …) ? I don’t know.

> Le 16 mars 2018 à 11:25, Acarali, Dilara 
> <Dilara.Acarali AT city.ac.uk>
>  a écrit :
> 
> I should also add that the graph is meant to be undirected:
> 
> //populate graph with nodes & edges
> graph.addNode("1");
> graph.addNode("2");
> graph.addNode("3");
> graph.addNode("4");
> graph.addNode("5");
> graph.addNode("6");
> graph.addEdge("1-2", "1", "2", false);
> graph.addEdge("1-4", "1", "4", false);
> graph.addEdge("1-6", "1", "6", false);
> graph.addEdge("2-3", "2", "3", false);
> graph.addEdge("2-6", "2", "6", false);
> graph.addEdge("3-5", "3", "5", false);
> graph.addEdge("3-6", "3", "6", false);
> graph.addEdge("4-5", "4", "5", false);
> graph.addEdge("5-6", "5", "6", false);
> 
> Regards
> 
> Dilara
> 
> From: Acarali, Dilara
> Sent: 16 March 2018 10:20
> To: Yoann Pigné; 
> graphstream-users AT litislab.fr
> Subject: Re: Bellman-Ford Query
>  
> Hi - Thanks for the quick reply. 
> 
> I have attached a PNG of the graph I was playing with. 
> 
> Also, just wanted to clarify a couple of things I've noticed I 
> misrepresented:
> 
> 1- > 
> for (Node srcNode : graph.getEachNode()) {
>   BellmanFord presimBellman = new BellmanFord("hops", srcNode.getId());
>   presimBellman.init(graph);
>   presimBellman.compute();
>   for (Node dstNode : graph.getEachNode()) {
>      String connection = "" + srcNode.getId() + "->" + dstNode.getId();
>      double pathLength = 
> presimBellman.getShortestPath(dstNode).getNodeCount();
>      Path path = presimBellman.getShortestPath(dstNode)
>      if (pathLength != 0) { //this is added to actually get the no. of hops 
> from the shortest path
>             pathLength -= 1;
>      }
>    }
> }
> 
> I had added the "-1" to pathLength to try to get hop count instead of total 
> node count. This is what is shown in the output.
> 
> 2 ->
> 
> BellmanFord testBellman = new BellmanFord("hops", "2");
> testBellman.init(graph);
> testBellman.compute();
> System.out.println(testBellman.getSource() + "->1 = " + 
> testBellman.getShortestPathValue(1));
> 
> This code returns Infinity for the shortest path value. 
> 
> Regards
> 
> Dilara
> 
> From: Yoann Pigné 
> <yoann.pigne AT gmail.com>
> Sent: 16 March 2018 10:09
> To: 
> graphstream-users AT litislab.fr;
>  Acarali, Dilara
> Subject: Re: Bellman-Ford Query
>  
> Hi, 
> 
> I don’t know what your graph looks like. Would you mind sharing that graph 
> too?
> 
> My guess is nodes 1 and 2 are connected through a directed edge (an arc) 
> from 1 to 2, so that a path from 1 to 2 exists but not from 2 to 1. The 
> cost of the path from 2 to 1 must be infinity but the length of the path is 
> zero because their is no path. Again, just a guess.
> 
> Yoann 
> 
> > Le 16 mars 2018 à 10:52, Acarali, Dilara 
> > <Dilara.Acarali AT city.ac.uk>
> >  a écrit :
> > 
> > Hello, 
> > 
> > I've been using GraphStream, and specifically exploring the Bellman-Ford 
> > algorithm implementation to find distance between nodes on a simple 
> > graph.  I run the algorithm and print the results as follows:
> > 
> > connection  length  path      
> > 1->1        0.0     []        
> > 1->2        1.0     [2, 1]    
> > 1->3        2.0     [3, 2, 1] 
> > 1->4        1.0     [4, 1]    
> > 1->5        2.0     [5, 4, 1] 
> > 1->6        1.0     [6, 1]    
> >  
> > 2->1        0.0     []        
> > 2->2        0.0     []        
> > 2->3        1.0     [3, 2]    
> > 2->4        1.0     [4, 1]    
> > 2->5        2.0     [5, 3, 2] 
> > 2->6        1.0     [6, 2]    
> > 
> > 3->1        0.0     []        
> > 3->2        1.0     [2, 1]    
> > 3->3        0.0     []        
> > 3->4        1.0     [4, 1]    
> > 3->5        1.0     [5, 3]    
> > 3->6        1.0     [6, 3]    
> > 
> > The code I use looks like this:
> > 
> > for (Node srcNode : graph.getEachNode()) {
> >    BellmanFord presimBellman = new BellmanFord("hops", srcNode.getId());
> >    presimBellman.init(graph);
> >    presimBellman.compute();
> > for (Node dstNode : graph.getEachNode()) {
> > String connection = "" + srcNode.getId() + "->" + dstNode.getId();
> > double pathLength = presimBellman.getShortestPath(dstNode).getNodeCount();
> > Path path = presimBellman.getShortestPath(dstNode);
> >           }
> > }
> > 
> > My question is, why does 1->2 return the correct hop count of 1, but 2->1 
> > does not? I tried setting both node1 and node2 as the source node in the 
> > Bellman-Ford constructor (on alternative runs) and still get the same 
> > result. I am aware that this is a stub implementation but don't think 
> > this should be happening? 
> > 
> > I also get the same result when I run:
> > 
> > BellmanFord testBellman = new BellmanFord("hops", "2");
> > testBellman.init(graph);
> > testBellman.compute();
> > System.out.println(testBellman.getSource() + "->1 = " + 
> > testBellman.getShortestPathValue(1));
> > 
> > Any feedback would be much appreciated.
> > 
> > Regards
> > 
> > Dilara