#!/usr/bin/env python
from igraph import Graph
def gomory_hu_tree(graph, capacity=None, flow_attr="flow", copy_attrs=True):
"""Calculates the Gomory-Hu tree of the given graph, assuming that the edge
capacities are given in `capacity`.
This implementation uses Gusfield's algorithm.
@param capacity: the vector of edge capacities. May be a list or the name
of an edge attribute.
@param flow_attr: the name of the edge attribute in the resulting graph that
will contain the minimum flow values
@param copy_attrs: whether to copy the graph and vertex attributes of the
original graph into the returned one
@return: the Gomory-Hu tree
"""
n = graph.vcount()
# Initialize the tree: every edge points to node 0
neighbors = [0] * n
flows = [0.0] * n
# For each source vertex except vertex zero...
for s in xrange(1, n):
# Find its neighbor.
t = neighbors[s]
# Find the minimum cut between s and t
cut = graph.mincut(s, t, capacity)
flows[s] = cut.value
side_of_s = cut[cut.membership[s]]
# Update the tree
for u in side_of_s:
if u > s and neighbors[u] == t:
neighbors[u] = s
# Construct the tree
edges = [(i, neighbors[i]) for i in xrange(1, n)]
result = Graph(n, edges, directed=False, edge_attrs={flow_attr: flows[1:]})
# Copy the attributes if needed
if copy_attrs:
for attr in graph.attributes():
result[attr] = graph[attr]
for attr in graph.vertex_attributes():
result.vs[attr] = graph.vs[attr]
return result
def test():
g = Graph.Formula("0-1, 0-2, 1-2, 1-3, 1-4, 2-4, 3-4, 3-5, 4-5")
g.es["capacity"] = [1, 7, 1, 3, 2, 4, 1, 6, 2]
gh = gomory_hu_tree(g, capacity="capacity")
print gh
print gh.es["flow"]
if __name__ == "__main__":
test()