Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / connectivity / tests / test_stoer_wagner.py @ 5cef0f13

History | View | Annotate | Download (3.05 KB)

1
from itertools import chain
2
import networkx as nx
3
from nose.tools import *
4

    
5

    
6
def _check_partition(G, cut_value, partition, weight):
7
    ok_(isinstance(partition, tuple))
8
    assert_equal(len(partition), 2)
9
    ok_(isinstance(partition[0], list))
10
    ok_(isinstance(partition[1], list))
11
    ok_(len(partition[0]) > 0)
12
    ok_(len(partition[1]) > 0)
13
    assert_equal(sum(map(len, partition)), len(G))
14
    assert_equal(set(chain.from_iterable(partition)), set(G))
15
    partition = tuple(map(set, partition))
16
    w = 0
17
    for u, v, e in G.edges(data=True):
18
        if (u in partition[0]) == (v in partition[1]):
19
            w += e.get(weight, 1)
20
    assert_equal(w, cut_value)
21

    
22

    
23
def _test_stoer_wagner(G, answer, weight='weight'):
24
    cut_value, partition = nx.stoer_wagner(G, weight,
25
                                           heap=nx.utils.PairingHeap)
26
    assert_equal(cut_value, answer)
27
    _check_partition(G, cut_value, partition, weight)
28
    cut_value, partition = nx.stoer_wagner(G, weight,
29
                                           heap=nx.utils.BinaryHeap)
30
    assert_equal(cut_value, answer)
31
    _check_partition(G, cut_value, partition, weight)
32

    
33

    
34
def test_graph1():
35
    G = nx.Graph()
36
    G.add_edge('x', 'a', weight=3)
37
    G.add_edge('x', 'b', weight=1)
38
    G.add_edge('a', 'c', weight=3)
39
    G.add_edge('b', 'c', weight=5)
40
    G.add_edge('b', 'd', weight=4)
41
    G.add_edge('d', 'e', weight=2)
42
    G.add_edge('c', 'y', weight=2)
43
    G.add_edge('e', 'y', weight=3)
44
    _test_stoer_wagner(G, 4)
45

    
46

    
47
def test_graph2():
48
    G = nx.Graph()
49
    G.add_edge('x', 'a')
50
    G.add_edge('x', 'b')
51
    G.add_edge('a', 'c')
52
    G.add_edge('b', 'c')
53
    G.add_edge('b', 'd')
54
    G.add_edge('d', 'e')
55
    G.add_edge('c', 'y')
56
    G.add_edge('e', 'y')
57
    _test_stoer_wagner(G, 2)
58

    
59

    
60
def test_graph3():
61
    # Source:
62
    # Stoer, M. and Wagner, F. (1997). "A simple min-cut algorithm". Journal of
63
    # the ACM 44 (4), 585-591.
64
    G = nx.Graph()
65
    G.add_edge(1, 2, weight=2)
66
    G.add_edge(1, 5, weight=3)
67
    G.add_edge(2, 3, weight=3)
68
    G.add_edge(2, 5, weight=2)
69
    G.add_edge(2, 6, weight=2)
70
    G.add_edge(3, 4, weight=4)
71
    G.add_edge(3, 7, weight=2)
72
    G.add_edge(4, 7, weight=2)
73
    G.add_edge(4, 8, weight=2)
74
    G.add_edge(5, 6, weight=3)
75
    G.add_edge(6, 7, weight=1)
76
    G.add_edge(7, 8, weight=3)
77
    _test_stoer_wagner(G, 4)
78

    
79

    
80
def test_weight_name():
81
    G = nx.Graph()
82
    G.add_edge(1, 2, weight=1, cost=8)
83
    G.add_edge(1, 3, cost=2)
84
    G.add_edge(2, 3, cost=4)
85
    _test_stoer_wagner(G, 6, weight='cost')
86

    
87

    
88
def test_exceptions():
89
    G = nx.Graph()
90
    assert_raises(nx.NetworkXError, nx.stoer_wagner, G)
91
    G.add_node(1)
92
    assert_raises(nx.NetworkXError, nx.stoer_wagner, G)
93
    G.add_node(2)
94
    assert_raises(nx.NetworkXError, nx.stoer_wagner, G)
95
    G.add_edge(1, 2, weight=-2)
96
    assert_raises(nx.NetworkXError, nx.stoer_wagner, G)
97
    G = nx.DiGraph()
98
    assert_raises(nx.NetworkXNotImplemented, nx.stoer_wagner, G)
99
    G = nx.MultiGraph()
100
    assert_raises(nx.NetworkXNotImplemented, nx.stoer_wagner, G)
101
    G = nx.MultiDiGraph()
102
    assert_raises(nx.NetworkXNotImplemented, nx.stoer_wagner, G)