Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / flow / tests / test_gomory_hu.py @ 5cef0f13

History | View | Annotate | Download (4.57 KB)

1
from itertools import combinations
2
from nose.tools import assert_equal, assert_true, raises
3

    
4
import networkx as nx
5
from networkx.algorithms.flow import boykov_kolmogorov
6
from networkx.algorithms.flow import edmonds_karp
7
from networkx.algorithms.flow import preflow_push
8
from networkx.algorithms.flow import shortest_augmenting_path
9
from networkx.algorithms.flow import dinitz
10

    
11
flow_funcs = [
12
    boykov_kolmogorov,
13
    dinitz,
14
    edmonds_karp,
15
    preflow_push,
16
    shortest_augmenting_path,
17
]
18

    
19

    
20
class TestGomoryHuTree:
21

    
22
    def minimum_edge_weight(self, T, u, v):
23
        path = nx.shortest_path(T, u, v, weight='weight')
24
        return min((T[u][v]['weight'], (u, v)) for (u, v) in zip(path, path[1:]))
25

    
26
    def compute_cutset(self, G, T_orig, edge):
27
        T = T_orig.copy()
28
        T.remove_edge(*edge)
29
        U, V = list(nx.connected_components(T))
30
        cutset = set()
31
        for x, nbrs in ((n, G[n]) for n in U):
32
            cutset.update((x, y) for y in nbrs if y in V)
33
        return cutset
34

    
35
    def test_default_flow_function_karate_club_graph(self):
36
        G = nx.karate_club_graph()
37
        nx.set_edge_attributes(G, 1, 'capacity')
38
        T = nx.gomory_hu_tree(G)
39
        assert_true(nx.is_tree(T))
40
        for u, v in combinations(G, 2):
41
            cut_value, edge = self.minimum_edge_weight(T, u, v)
42
            assert_equal(nx.minimum_cut_value(G, u, v),
43
                         cut_value)
44

    
45
    def test_karate_club_graph(self):
46
        G = nx.karate_club_graph()
47
        nx.set_edge_attributes(G, 1, 'capacity')
48
        for flow_func in flow_funcs:
49
            T = nx.gomory_hu_tree(G, flow_func=flow_func)
50
            assert_true(nx.is_tree(T))
51
            for u, v in combinations(G, 2):
52
                cut_value, edge = self.minimum_edge_weight(T, u, v)
53
                assert_equal(nx.minimum_cut_value(G, u, v),
54
                             cut_value)
55

    
56
    def test_davis_southern_women_graph(self):
57
        G = nx.davis_southern_women_graph()
58
        nx.set_edge_attributes(G, 1, 'capacity')
59
        for flow_func in flow_funcs:
60
            T = nx.gomory_hu_tree(G, flow_func=flow_func)
61
            assert_true(nx.is_tree(T))
62
            for u, v in combinations(G, 2):
63
                cut_value, edge = self.minimum_edge_weight(T, u, v)
64
                assert_equal(nx.minimum_cut_value(G, u, v),
65
                             cut_value)
66

    
67
    def test_florentine_families_graph(self):
68
        G = nx.florentine_families_graph()
69
        nx.set_edge_attributes(G, 1, 'capacity')
70
        for flow_func in flow_funcs:
71
            T = nx.gomory_hu_tree(G, flow_func=flow_func)
72
            assert_true(nx.is_tree(T))
73
            for u, v in combinations(G, 2):
74
                cut_value, edge = self.minimum_edge_weight(T, u, v)
75
                assert_equal(nx.minimum_cut_value(G, u, v),
76
                             cut_value)
77

    
78
    def test_les_miserables_graph_cutset(self):
79
        G = nx.les_miserables_graph()
80
        nx.set_edge_attributes(G, 1, 'capacity')
81
        for flow_func in flow_funcs:
82
            T = nx.gomory_hu_tree(G, flow_func=flow_func)
83
            assert_true(nx.is_tree(T))
84
            for u, v in combinations(G, 2):
85
                cut_value, edge = self.minimum_edge_weight(T, u, v)
86
                assert_equal(nx.minimum_cut_value(G, u, v),
87
                             cut_value)
88

    
89
    def test_karate_club_graph_cutset(self):
90
        G = nx.karate_club_graph()
91
        nx.set_edge_attributes(G, 1, 'capacity')
92
        T = nx.gomory_hu_tree(G)
93
        assert_true(nx.is_tree(T))
94
        u, v = 0, 33
95
        cut_value, edge = self.minimum_edge_weight(T, u, v)
96
        cutset = self.compute_cutset(G, T, edge)
97
        assert_equal(cut_value, len(cutset))
98

    
99
    def test_wikipedia_example(self):
100
        # Example from https://en.wikipedia.org/wiki/Gomory%E2%80%93Hu_tree
101
        G = nx.Graph()
102
        G.add_weighted_edges_from((
103
            (0, 1, 1), (0, 2, 7), (1, 2, 1),
104
            (1, 3, 3), (1, 4, 2), (2, 4, 4),
105
            (3, 4, 1), (3, 5, 6), (4, 5, 2),
106
        ))
107
        for flow_func in flow_funcs:
108
            T = nx.gomory_hu_tree(G, capacity='weight', flow_func=flow_func)
109
            assert_true(nx.is_tree(T))
110
            for u, v in combinations(G, 2):
111
                cut_value, edge = self.minimum_edge_weight(T, u, v)
112
                assert_equal(nx.minimum_cut_value(G, u, v, capacity='weight'),
113
                             cut_value)
114

    
115
    @raises(nx.NetworkXNotImplemented)
116
    def test_directed_raises(self):
117
        G = nx.DiGraph()
118
        T = nx.gomory_hu_tree(G)
119

    
120
    @raises(nx.NetworkXError)
121
    def test_empty_raises(self):
122
        G = nx.empty_graph()
123
        T = nx.gomory_hu_tree(G)