#!/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()