Bellman-ford Shortest path Algorithm

[GoogleCodeExporter]

Bellman-ford shortest path algorithm is not working for string type nodes and 
edges. Can you add one example for Bellman-ford shortest path algorithm like 
the example of Europe where it is working fine. I have tried to use this 
algorithm on nodes like 1,2,3,4,5] then it works fine but for nodes as a string 
are not working. Can anyone help or tried this? Please share your comments.If 
possible urgently.

Original issue reported on code.google.com by annu.i...@gmail.com on 4 Feb 2011 at 1:58

[GoogleCodeExporter]

Might be a bug. Thanks for your report. 

I'll have a look at it tonight and I'll come back to you. 

Original comment by tomaz.ko...@gmail.com on 4 Feb 2011 at 2:10

• Changed state: Started

[GoogleCodeExporter]

I can't reproduce this problem and I don't see where it should fail for nodes 
represented as strings. It only uses key-value and key in dictionary lookups so 
it even works on cases where nodes are not represented by the same type: 
    G = digraph()
    G.add_nodes(['1','2','3',4])
    G.add_edge(('1','2'), 6)
    G.add_edge(('1','3'), 7)
    G.add_edge(('2',4), 2)

I'm marking this issue as CantReproduce for now. But it you could provide a 
test case (attached as a diff would be great) where it fails I'm going to open 
this issue again.

Original comment by tomaz.ko...@gmail.com on 4 Feb 2011 at 3:36

• Changed state: CantReproduce

[GoogleCodeExporter]

Hi...Now it is working fine. The same I did now was doing before also but it 
was giving key-error. I have one another doubt. Is the order of nodes and edges 
are also effect or raise the key-error? Because for me when i changed the order 
of edges it is working fine.

Original comment by annu.i...@gmail.com on 5 Feb 2011 at 5:45

[GoogleCodeExporter]

I'm having trouble with interpreting your problem. Attaching a .py file with a 
simple case of failure for the respective algorithm would make this a whole lot 
easier :)

Original comment by tomaz.ko...@gmail.com on 5 Feb 2011 at 10:23

[GoogleCodeExporter]

Oh I almost forgot ...

Please provide the following info:
- version of python you are using
- version of python graph 

Original comment by tomaz.ko...@gmail.com on 5 Feb 2011 at 10:29

[GoogleCodeExporter]

Hello...now problem has solved. I was getting key-error because in my dataset 
there was an edge which was not having connection with any other nodes of 
graph. Thanks for your reply and help.

Original comment by annu.i...@gmail.com on 5 Feb 2011 at 11:37

[GoogleCodeExporter]

I'm not sure we should be raising a KeyError in this case. I think we could 
provide a more descriptive exception object. This might be a subclass of 
KeyError but it should not actually be a KeyError. Any thoughts?

Original comment by s...@stodge.org on 5 Feb 2011 at 1:30

[GoogleCodeExporter]

@sal: Well I did bit of extra testing and now I can clearly see where the 
KeyError is being raised.  

B-F checks for negative weight cycles at the end of the main loop. If the given 
graph contains subgraphs that are not connected it should only return 
predecessors and distance costs for nodes that could be reached in that 
subgraph. 

Right now it raises a KeyError because its looking for nodes that are not 
included in distance dictionary (unconnected parts of the graph). 

I'm going to rewrite the last part of the algorithm so it'll work for 
unconnected graphs so there will be no need for extra KeyError wrappers.

Original comment by tomaz.ko...@gmail.com on 6 Feb 2011 at 2:28

[GoogleCodeExporter]

Yeah..I think this will be the case for raising key-error. Thanks.

Original comment by annu.i...@gmail.com on 7 Feb 2011 at 4:45

[GoogleCodeExporter]

See: r725

Original comment by tomaz.ko...@gmail.com on 9 Feb 2011 at 5:06

• Changed state: Fixed