Hello,
Attached is a quick implementation of the Gomory-Hu tree calculation in Python.
I haven't tested it too much (only with the example in Wikipedia), but I think
it should be okay. Let me know if you run into any issues; if not, chances are
that this will be converted into C at some point and then merged into the next
igraph release.
All the best,
Tamas
#!/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()
On 10 Jul 2013, at 11:45, Raphael C <[email protected]> wrote:
> I am interested in the Gomory-Hu tree (
> http://en.wikipedia.org/wiki/Gomory%E2%80%93Hu_tree ) of a graph.
> There are a few algorithms with the one by Gusfield apparently being
> very simple if you already have a max flow implementation. There is
> also source code here http://www.cs.princeton.edu/~kt/cut-tree/ .
>
> Would it be possible to add an implementation to python igraph by any
> chance please? I hope I haven't just missed it in the documentation.
>
> The full paper is at http://epubs.siam.org/doi/abs/10.1137/0219009
> but seems to need a subscription unfortunately.
>
> Raphael
>
> _______________________________________________
> igraph-help mailing list
> [email protected]
> https://lists.nongnu.org/mailman/listinfo/igraph-help
_______________________________________________
igraph-help mailing list
[email protected]
https://lists.nongnu.org/mailman/listinfo/igraph-help
