Re: Bellman-Ford Query

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

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