Re: Bellman-Ford Query

["Acarali, Dilara" <Dilara.Acarali AT city.ac.uk>]

I see - that does appear to make more sense now. 

It also explains why I wasn't having any unexpected issues when using the Dijsktra algorithm (I was trying to figure out if there was something wrong about my graph definition). 

Thanks again for your assistance 😊

Regards

Dilara

---

From: Yoann Pigné <yoann.pigne AT gmail.com>
Sent: 16 March 2018 11:02
To: Acarali, Dilara
Cc: graphstream-users AT litislab.fr
Subject: Re: Bellman-Ford Query

 

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