search

wting / python-graph

Automatically exported from code.google.com/p/python-graph
Other
5 stars 4 forks source link

Bellman-Ford algorithm #49

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 
Adding Bellman-Ford algorithm (shortest path family) to the algorithms
package. 

Quote:
The Bellman–Ford algorithm, a label correcting algorithm,[1] computes
single-source shortest paths in a weighted digraph (where some of the edge
weights may be negative). 
http://en.wikipedia.org/wiki/Bellman-Ford_algorithm

Original issue reported on code.google.com by tomaz.ko...@gmail.com on 16 Nov 2009 at 4:20

GoogleCodeExporter commented 9 years ago

Original comment by pmatiello on 17 Nov 2009 at 1:17

GoogleCodeExporter commented 9 years ago 
Anyone working on this issue?? I would like to take it up next.

Original comment by anand.ib...@gmail.com on 30 Nov 2009 at 4:11

GoogleCodeExporter commented 9 years ago 
Since it's status was labelled as "started" I thought it was obvious ;) It's 
nearly
finished, but I'm very busy at he moment.

Original comment by tomaz.ko...@gmail.com on 30 Nov 2009 at 4:15

GoogleCodeExporter commented 9 years ago 
Oops..... my bad..am kinda newbie to googlecode... and the last time i was part 
of a
programming team was almost 3 years ago at guess?? IBM ..ironically enough it is
known for its process :D
i will then take up some other issue then..

Original comment by anand.ib...@gmail.com on 30 Nov 2009 at 4:22

GoogleCodeExporter commented 9 years ago 
[deleted comment]
GoogleCodeExporter commented 9 years ago 
I finally got some spare time and wrapped everything up:
- a clean implementation
- tests
- documentation
- new exceptions.py module in pygraph.algorithms 
- cleaned up the minmax.py module

(Please see the diff patch attached to this post.)

The reason I haven't committed this code yet and only attached the diff file is 
because I 
want some opinion about the pygraph.algorithms.exceptions module that I 
introduced in 
the 
attached patch. The way I see it, this could be a container for all other 
exceptions 
that 
might occur during some other not yet included algorithms. (Like the recursive 
best 
first 
search I plan to propose for inclusion after this one.)

Looking forward for your opinion and the "go code" for committing my code.

Regards, Tomaž

Original comment by tomaz.ko...@gmail.com on 24 Feb 2010 at 10:02

Attachments:

GoogleCodeExporter commented 9 years ago 
Tomaz, could move the exceptions to pygraph.classes.exceptions.py? It already 
exists. :)

Original comment by pmatiello on 24 Feb 2010 at 10:26

GoogleCodeExporter commented 9 years ago 
I'm aware of the existing  pygraph.classes.exceptions.py module. But I was 
doubtful 
about adding the exceptions for algorithms among exceptions for graph classes. 

I'm ok with moving the whole thing to pygraph.classes.exceptions.py, if you 
don't agree 
with the proposed design.

I'll commit the modified version after your final directive, ok?

Original comment by tomaz.ko...@gmail.com on 24 Feb 2010 at 10:43

GoogleCodeExporter commented 9 years ago 
The file pygraph.classes.exceptions is meant to hold all kinds of exceptions
(exceptions are classes, so they are in pygraph.classes namespace).

I'll be waiting for your commit.

Original comment by pmatiello on 24 Feb 2010 at 10:56

GoogleCodeExporter commented 9 years ago 
Committed and marked this issue as fixed, but you change the status for more 
discussion, if needed :)

Original comment by tomaz.ko...@gmail.com on 24 Feb 2010 at 11:08

GoogleCodeExporter commented 9 years ago 
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.Urgently.

Original comment by annu.i...@gmail.com on 4 Feb 2011 at 1:43

GoogleCodeExporter commented 9 years ago 
[deleted comment]
GoogleCodeExporter commented 9 years ago 
That's probably a bug. Could you open a new issue for this? I'll take a look at 
it as soon as possible.

Original comment by pmatiello on 4 Feb 2011 at 1:53

GoogleCodeExporter commented 9 years ago 
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.Urgently.

Original comment by annu.i...@gmail.com on 4 Feb 2011 at 1:57

GoogleCodeExporter commented 9 years ago 
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 
urgently.

Original comment by annu.i...@gmail.com on 4 Feb 2011 at 2:13