Opened 12 years ago

Closed 6 years ago

#8714 closed enhancement (wontfix)

add Bellman-Ford algorithm for shortest paths

Reported by: mvngu Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: graph theory Keywords:
Cc: wdj, dkrenn, dcoudert, ncohen Merged in:
Authors: David Coudert Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: u/cheuberg/8714 (Commits, GitHub, GitLab) Commit: 2c58a9bcdeab06355c52912c12d041ea143eed43
Dependencies: #12806 Stopgaps:

Status badges

Description (last modified by chapoton)

I'm using #698 as a wish list of items to add to the graph theory module of Sage. The purpose of this ticket is to implement the Bellman-Ford algorithm for finding shortest paths in a weighted graph G that may have negative weights. If G doesn't have negative weights, Dijkstra's algorithm can be used. However, if G has negative weights, we fall back on the Bellman-Ford algorithm. The Bellman-Ford algorithm is able to handle graphs with negative weights, but not graphs that have negative-weight cycles. See also the function BellmanFord in Mathematica's Combinatorica package. See this graph theory book for an algorithmic presentation of the Bellman-Ford algorithm.

See also the graph theory roadmap.

APPLY:

Attachments (3)

trac_8714.patch (6.8 KB) - added by dcoudert 9 years ago.
trac_8714.2.patch (15.3 KB) - added by dcoudert 8 years ago.
trac_8714_addon1.patch (6.5 KB) - added by chapoton 8 years ago.

Download all attachments as: .zip

Change History (37)

comment:1 Changed 12 years ago by mvngu

  • Cc wdj added
  • Description modified (diff)

Here is an implementation by David Joyner:

def bellman_ford(Gamma, s):
    """
    Computes the shortest distance from s to all other vertices in Gamma.
    If Gamma has a negative weight cycle, then return an error.

    INPUT:

    - Gamma -- a graph.
    - s -- the source vertex.

    OUTPUT:

    - (d,p) -- pair of dictionaries keyed on the list of vertices,
      which store the distance and shortest paths.

    REFERENCE:

    http://en.wikipedia.org/wiki/Bellman-Ford_algorithm
    """
    P = []
    dist = {}
    predecessor = {}
    V = Gamma.vertices()
    E = Gamma.edges()
    for v in V:
        if v == s:
            dist[v] = 0
        else:
            dist[v] = infinity
        predecessor[v] = 0
    for i in range(1, len(V)):
        for e in E:
            u = e[0]
            v = e[1]
            wt = e[2]
            if dist[u] + wt < dist[v]:
                dist[v] = dist[u] + wt
                predecessor[v] = u
    # check for negative-weight cycles
    for e in E:
	u = e[0]
        v = e[1]
        wt = e[2]
        if dist[u] + wt < dist[v]:
            raise ValueError("Graph contains a negative-weight cycle")
    return dist, predecessor

And some examples:

sage: M = matrix([[0,1,4,0], [0,0,1,5], [0,0,0,3], [0,0,0,0]])
sage: G = Graph(M, format="weighted_adjacency_matrix")
sage: bellman_ford(G, G.vertices()[0])
  {0: 0, 1: 1, 2: 2, 3: 5}

and

sage: M = matrix([[0,1,0,0],[1,0,-4,1],[1,1,0,0],[0,0,1,0]])
sage: G = DiGraph(M, format = "weighted_adjacency_matrix")
sage: bellman_ford(G, G.vertices()[0])
---------------------------------------------------------------------------
...
ValueError: Graph contains a negative-weight cycle

comment:2 Changed 10 years ago by dkrenn

  • Cc dkrenn added

comment:3 Changed 10 years ago by dkrenn

  • Dependencies set to #12806

Bellman-Ford is available in networkx 1.6. I added the dependency #12806, where the upgrade to 1.6 happens.

When #12806 is done, we can add an interface in the graph class for Bellman-Ford algorithm, which should be done with this ticket here.

comment:4 Changed 9 years ago by dcoudert

  • Cc dcoudert added

Hello,

I have checked the networkx implementation of the Bellman-Ford algorithm (See here) and we can propose a better implementation.

This is a first implementation that can certainly be improved. Its advantage is that in the best case the time complexity is in O(|V|+|E|) and in the worst case, it is O(|V|.|E|). It uses a set to maintain the set of active vertices, that is vertices for which a change has been performed during previous round.

def bellman_ford(G, s):
    """
    some documentation
    """
    from sage.rings.infinity import Infinity
    P = []
    dist = {}
    predecessor = {}
    V = G.vertices()
    N = G.num_verts()
    E = G.edges()
    for v in V:
        if v == s:
            dist[v] = 0
        else:
            dist[v] = Infinity
        predecessor[v] = 0
    W = {}
    for e in E:
        W[(e[0],e[1])] = e[2]
        W[(e[1],e[0])] = e[2]
    A = set([s])
    B = set()
    cpt = 0
    while len(A) > 0 and cpt < N:
        while len(A) > 0:
            u = A.pop()
            for v in G.neighbor_iterator(u):
                if dist[u] + W[(u,v)] < dist[v]:
                    dist[v] = dist[u] + W[u,v]
                    predecessor[v] = u
                    B.add(v)
        A = B.copy()
        B.clear()
        cpt += 1
    # check for negative-weight cycles
    for e in E:
	u = e[0]
        v = e[1]
        wt = e[2]
        if dist[u] + wt < dist[v]:
            raise ValueError("Graph contains a negative-weight cycle")
    return dist, predecessor

The implementation can be adapted to graphs and digraphs.

Let me know if you think it is a good idea to write this patch.

Best, D.

comment:5 Changed 9 years ago by dcoudert

  • Cc ncohen added

I have a better implementation, but I don't know exactly

  • Where to place it: generic_graph.py or generic_graph_pyx.pyx for more efficiency
  • The best name: shortest_paths_BellmanFord ?
  • What to return: dictionary with distances and dictionary with predecessors or paths?

Well, some minor details ;-)

comment:6 Changed 9 years ago by ncohen

Well, it depends on whether you want to optimize it in C a bit or not.. In this case the choice is made for you as you would need a Cython file.

You could also use the "distance_all_pairs" file.

I would say that the best name would be.... no name ? A hidden function. Then function would then be accessed through the usual methods of graphs/digraphs, like "distance", "shortest path", "distances all pairs", with a special flag or just automatically if there happen to be negative weights on the edges... What do you think ? It would be weird to create a new function for that if we have many already, especially if you wonder what it should return -- in this case it would have to return what the function calling it expects...

We should be able to talk about in in a few days :-)

Nathann

comment:7 Changed 9 years ago by dcoudert

At first I can add it to generic_graph.py, and let to others to option to improve the implementation in C.

I will propose a patch over the week end.

comment:8 Changed 9 years ago by azi

Hello!

Is there anything new with this patch? BF would be a very useful algorithm to have in Sage!

comment:9 Changed 9 years ago by dcoudert

I don't have a lot of free time these days and it takes some time to write the documentation and doctests. I will try to commit soon.

Changed 9 years ago by dcoudert

comment:10 follow-up: Changed 9 years ago by dcoudert

  • Authors set to David Coudert
  • Status changed from new to needs_review

I have uploaded the first part of the patch: the hidden bellman-ford function. You can already try it (and reviewed it) via G.__bellman_ford__(source node) where G is either a graph or a digraph, with or without loops and multiple edges, with negative edge weights, etc.

It remains the long/boring part to call that function from other functions, add optional arguments and tests, etc. I don't have time to do it now, so anyone is welcome to contribute.

I set the patch to needs review, but it should be needs work.

David.

comment:11 in reply to: ↑ 10 Changed 9 years ago by ncohen

  • Status changed from needs_review to needs_work

I set the patch to needs review, but it should be needs work.

Well, then.. O_o

Nathann

comment:12 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

Changed 8 years ago by dcoudert

comment:13 Changed 8 years ago by dcoudert

  • Description modified (diff)

Finally, this patch is ready to be reviewed!

The method is now transparently called when negative weights are detected. I have also added an optional parameter that could be used e.g. in patch #13380.

apply: trac_8714.2.patch

comment:14 Changed 8 years ago by dcoudert

  • Status changed from needs_work to needs_review

Changed 8 years ago by chapoton

comment:15 Changed 8 years ago by chapoton

  • Description modified (diff)

comment:16 Changed 8 years ago by chapoton

I have made a small review patch, mainly changing minor cosmetic details.

comment:17 Changed 8 years ago by dcoudert

Hello,

I haven't received notification for the addon patch.

The addon patch is ok (install, test, etc.).

Thank you for this improvement. I let you decide for the status of the patch.

David.

comment:18 follow-ups: Changed 8 years ago by ncohen

  • Branch set to u/ncohen/8714

Yoooooooooooo !

I just reviewed this patch, and I don't see anything wrong. Several questions/remarks, though :

  • the weights dictionary is actually (in memory) a copy of the whole graph. Isn't it better to create a normalized copy of the graph and work on this only ?
  • Why __bellman_ford__ and not just _bellman_ford ? Isn't the __ only for special Python functions ?
  • You say that loops are supported, but I don't see how. Where do you detect if there is a negative loop somewhere, for instance ?
  • your function ee compares the vertices' name, and that's tricky. Sometimes the vertices of a graph are not integers, can be sets (KneserGraph? for instance) and comparing them doesn't work as expected.

Besides:

  • I modified a bit the behaviour of your modifications to shortest_paths, as this dictionary only needs to contain an entry for a target when such a path exists. I also used the fact that your Bellman Ford implementation satisfies pred[t] = [t] whenever dist[t] == Infinity.
  • From the looks of .all_pairs_shortest_path, perhaps we should create a hidden function for the code of Floyd-Warshall_Python. Not urgent, just cleaning stuff.

I added my patch as a git commit, to which the two previous hg patches belong. The new branch is u/ncohen/8714.

Have fuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuun ! ;-)

Nathann

comment:19 Changed 8 years ago by git

  • Commit set to 01521a8f176cde7159829b53274ba2cd1973ee18

Branch pushed to git repo; I updated commit sha1. New commits:

01521a8trac #8714: review of code and doc
e31e05ctrac #8714 minor details, cleanup
8259b18trac #8714 -- Implements Bellman-Ford shortest path algorithm

comment:20 Changed 8 years ago by ncohen

  • Status changed from needs_review to needs_info

comment:21 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:22 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:23 Changed 8 years ago by cheuberg

  • Branch changed from u/ncohen/8714 to u/cheuberg/8714

comment:24 in reply to: ↑ 18 Changed 8 years ago by cheuberg

  • Commit changed from 01521a8f176cde7159829b53274ba2cd1973ee18 to a27064f6972402144b7fd5748f6e524d30194870

I had a short look at this patch and corrected a few obvious typos.

Replying to ncohen:

  • You say that loops are supported, but I don't see how. Where do you detect if there is a negative loop somewhere, for instance ?

If there is a negative loop somewhere, max_number_of_loops is reached and the code raises a ValueError.


New commits:

8259b18trac #8714 -- Implements Bellman-Ford shortest path algorithm
e31e05ctrac #8714 minor details, cleanup
01521a8trac #8714: review of code and doc
a27064ftrac #8714: corrected minor typos

comment:25 Changed 8 years ago by git

  • Commit changed from a27064f6972402144b7fd5748f6e524d30194870 to 6762f7e4f71ccc4fc8a0ce281bd51e7b673c266a

Branch pushed to git repo; I updated commit sha1. New commits:

6762f7etrac #8714: fixed failing doctest

comment:26 follow-up: Changed 8 years ago by dcoudert

Thank you for pushing this patch. I had no time to do it in the last months, and I still don't know how to use git...

I had a quick look at proposed changes.

typo: algorith -> algorithm

- INPUTS:
+ For more information on the Bellman-Ford algorith, see the

I have some doubt about the recursive function def build_paths(v):. I suggest to have a loop instead of recursive calls. You never know how long will be the path, and its never a good idea to have 1000 or more recursive calls...

Thanks.

comment:27 in reply to: ↑ 18 Changed 8 years ago by cheuberg

Replying to ncohen:

  • your function ee compares the vertices' name, and that's tricky. Sometimes the vertices of a graph are not integers, can be sets (KneserGraph? for instance) and comparing them doesn't work as expected.

Apparently, the function ee serves to orient an undirected graph. One could probably replace the comparison of the labels by a comparison of the id which would serve the same purpose (have a unique orientation).

However: is there any advantage of using the Bellman-Ford algorithm (as compared to Dijkstra) in the undirected case? If all edges have non-negative weight, Dijkstra should be more efficient. If there is an edge with negative weight (and this edge is reachable from the start vertex), then Bellman-Ford will detect it as a negative circuit (just take this edge in both directions repeatedly) and fail anyway.

There is a method for computing shortest paths in undirected graphs with conservative weights (negative edge weights allowed, but no undirected cycle (different vertices!) of negative weight), cf. Corollary 12.13 in Korte and Vygen, Combinatorial Optimization (5th edition). But this has nothing to do with Bellman-Ford.

My proposal would be to remove the code for undirected graphs in this proposed patch, which would increase readability IMHO, remove the problem with this ee function and would, in my opinion, not loose any useful functionality. I do not know whether this would still belong to generic_graph, though.

comment:28 in reply to: ↑ 26 Changed 8 years ago by cheuberg

Replying to dcoudert:

typo: algorith -> algorithm

- INPUTS:
+ For more information on the Bellman-Ford algorith, see the

I do not understand your comment, I corrected a typo algorith -> algorithm in a27064f and cannot find another occurrence of "algorith,"

comment:29 Changed 8 years ago by git

  • Commit changed from 6762f7e4f71ccc4fc8a0ce281bd51e7b673c266a to 2c58a9bcdeab06355c52912c12d041ea143eed43

Branch pushed to git repo; I updated commit sha1. New commits:

7b62388trac #8714: allow edges of weight 0
2c58a9btrac 8714: shortest_paths was broken

comment:30 Changed 8 years ago by cheuberg

I fixed two issues with the code. This includes a simple doctest for the (previously broken for negative edge weights) function shortest_paths. IMHO, doctests should be included for the other changed functions, too.

comment:31 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:32 Changed 6 years ago by cheuberg

  • Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
  • Status changed from needs_info to needs_review

Bellman-Ford has now been implemented in #18931. As discussed in #18931 comment 15, the performance has not yet been compared with the code here.

However, the branch attached to this ticket no longer merges with develop and very much work would be needed. Moreover, this ticket has not had any activity for 15 months. My suggestion is to close this ticket here as a duplicate.

comment:33 Changed 6 years ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

Actually I tried this patch a few days ago and I fully agree that it has to be fully rewritten. Moreover, to be competitive with respect to #18931, the algorithm has to be cythonized. So let's close this ticket, and if later we decide to give a try to a fresh cython implementation, we can do it in another ticket. Best, David.

comment:34 Changed 6 years ago by vbraun

  • Resolution set to wontfix
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.