graph_tool.search.bellman_ford_search

graph_tool.search.bellman_ford_search(g, source, weight, visitor=<graph_tool.search.BellmanFordVisitor object>, dist_map=None, pred_map=None, combine=<function <lambda>>, compare=<function <lambda>>, zero=0, infinity=inf)

Bellman-Ford traversal of a directed or undirected graph, with negative weights.

Parameters:

gGraph

Graph to be used.

sourceVertex

Source vertex.

weightEdgePropertyMap

Edge property map with weight values.

visitorDijkstraVisitor (optional, default: DijkstraVisitor())

A visitor object that is invoked at the event points inside the algorithm. This should be a subclass of DijkstraVisitor.

dist_mapVertexPropertyMap (optional, default: None)

A vertex property map where the distances from the source will be stored.

pred_mapVertexPropertyMap (optional, default: None)

A vertex property map where the predecessor map will be stored (must have value type “int64_t”).

combinebinary function (optional, default: lambda a, b: a + b)

This function is used to combine distances to compute the distance of a path.

comparebinary function (optional, default: lambda a, b: a < b)

This function is use to compare distances to determine which vertex is closer to the source vertex.

zeroint or float (optional, default: 0)

Value assumed to correspond to a distance of zero by the combine and compare functions.

infinityint or float (optional, default: float('inf'))

Value assumed to correspond to a distance of infinity by the combine and compare functions.

Returns:

minimizedbool

True if all edges were successfully minimized, or False if there is a negative loop in the graph.

dist_mapVertexPropertyMap

A vertex property map with the computed distances from the source.

pred_mapVertexPropertyMap

A vertex property map with the predecessor tree.

See also

bfs_search

Breadth-first search

dfs_search

Depth-first search

dijkstra_search

Dijkstra search

astar_search

\(A^*\) heuristic search

Notes

The Bellman-Ford algorithm [bellman-ford] solves the single-source shortest paths problem for a graph with both positive and negative edge weights. If you only need to solve the shortest paths problem for positive edge weights, dijkstra_search() provides a more efficient alternative. If all the edge weights are all equal, then bfs_search() provides an even more efficient alternative.

The Bellman-Ford algorithm proceeds by looping through all of the edges in the graph, applying the relaxation operation to each edge. In the following pseudo-code, v is a vertex adjacent to u, w maps edges to their weight, and d is a distance map that records the length of the shortest path to each vertex seen so far. p is a predecessor map which records the parent of each vertex, which will ultimately be the parent in the shortest paths tree

RELAX(u, v, w, d, p)
  if (w(u,v) + d[u] < d[v])
    d[v] := w(u,v) + d[u]       relax edge (u,v)
    p[v] := u
  else
    ...                         edge (u,v) is not relaxed

The algorithm repeats this loop |V| times after which it is guaranteed that the distances to each vertex have been reduced to the minimum possible unless there is a negative cycle in the graph. If there is a negative cycle, then there will be edges in the graph that were not properly minimized. That is, there will be edges (u,v) such that w(u,v) + d[u] < d[v]. The algorithm loops over the edges in the graph one final time to check if all the edges were minimized, returning true if they were and returning false otherwise.

BELLMAN-FORD(G)
  for each vertex u in V
    d[u] := infinity
    p[u] := u
  end for
  for i := 1 to |V|-1
    for each edge (u,v) in E          examine edge (u,v)
      RELAX(u, v, w, d, p)
    end for
  end for
  for each edge (u,v) in E
    if (w(u,v) + d[u] < d[v])
      return (false, , )              edge (u,v) was not minimized
    else
      ...                             edge (u,v) was minimized
  end for
  return (true, p, d)

The time complexity is \(O(V E)\).

References

[bellman-ford]

R. Bellman, “On a routing problem”, Quarterly of Applied Mathematics, 16(1):87-90, 1958.

[bellman-ford-bgl]

http://www.boost.org/doc/libs/release/libs/graph/doc/bellman_ford_shortest.html

[bellman-ford-wikipedia]

http://en.wikipedia.org/wiki/Bellman-Ford_algorithm

Examples

We must define what should be done during the search by subclassing BellmanFordVisitor, and specializing the appropriate methods. In the following we will keep track of the edge minimizations.

class VisitorExample(gt.BellmanFordVisitor):

    def __init__(self, name):
        self.name = name

    def edge_minimized(self, e):
        print("edge (%s, %s) has been minimized..." % \
              (self.name[e.source()], self.name[e.target()]))

    def edge_not_minimized(self, e):
        print("edge (%s, %s) has not been minimized..." % \
              (self.name[e.source()], self.name[e.target()]))

With the above class defined, we can perform the Bellman-Ford search as follows.

>>> g = gt.load_graph("search_example.xml")
>>> name = g.vp["name"]
>>> weight = g.ep["weight"]
>>> nweight = g.copy_property(weight)
>>> nweight.a[6] *= -1   # include negative weight in edge (Carlos, Alice)
>>> minimized, dist, pred = gt.bellman_ford_search(g, g.vertex(0), nweight, VisitorExample(name))
edge (Bob, Eve) has been minimized...
edge (Bob, Chuck) has been minimized...
edge (Bob, Carlos) has been minimized...
edge (Bob, Isaac) has been minimized...
edge (Alice, Oscar) has been minimized...
edge (Alice, Dave) has been minimized...
edge (Alice, Carlos) has been minimized...
edge (Carol, Eve) has been minimized...
edge (Carol, Imothep) has been minimized...
edge (Carlos, Eve) has been minimized...
edge (Carlos, Imothep) has been minimized...
edge (Chuck, Eve) has been minimized...
edge (Chuck, Isaac) has been minimized...
edge (Chuck, Imothep) has been minimized...
edge (Dave, Oscar) has been minimized...
edge (Eve, Isaac) has been minimized...
edge (Eve, Imothep) has been minimized...
>>> print(minimized)
True
>>> print(pred.a)
[3 3 9 1 6 1 3 6 1 3]
>>> print(dist.a)
[-28.42555934 -37.34471821 -25.20438243 -41.97110592 -35.20316571
 -34.02873843 -36.58860946 -33.55645565 -35.2199616  -36.0029274 ]