Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/connectivity/tests/test_stoer_wagner.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 from itertools import chain | |
2 import networkx as nx | |
3 import pytest | |
4 | |
5 | |
6 def _check_partition(G, cut_value, partition, weight): | |
7 assert isinstance(partition, tuple) | |
8 assert len(partition) == 2 | |
9 assert isinstance(partition[0], list) | |
10 assert isinstance(partition[1], list) | |
11 assert len(partition[0]) > 0 | |
12 assert len(partition[1]) > 0 | |
13 assert sum(map(len, partition)) == len(G) | |
14 assert 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 w == cut_value | |
21 | |
22 | |
23 def _test_stoer_wagner(G, answer, weight="weight"): | |
24 cut_value, partition = nx.stoer_wagner(G, weight, heap=nx.utils.PairingHeap) | |
25 assert cut_value == answer | |
26 _check_partition(G, cut_value, partition, weight) | |
27 cut_value, partition = nx.stoer_wagner(G, weight, heap=nx.utils.BinaryHeap) | |
28 assert cut_value == answer | |
29 _check_partition(G, cut_value, partition, weight) | |
30 | |
31 | |
32 def test_graph1(): | |
33 G = nx.Graph() | |
34 G.add_edge("x", "a", weight=3) | |
35 G.add_edge("x", "b", weight=1) | |
36 G.add_edge("a", "c", weight=3) | |
37 G.add_edge("b", "c", weight=5) | |
38 G.add_edge("b", "d", weight=4) | |
39 G.add_edge("d", "e", weight=2) | |
40 G.add_edge("c", "y", weight=2) | |
41 G.add_edge("e", "y", weight=3) | |
42 _test_stoer_wagner(G, 4) | |
43 | |
44 | |
45 def test_graph2(): | |
46 G = nx.Graph() | |
47 G.add_edge("x", "a") | |
48 G.add_edge("x", "b") | |
49 G.add_edge("a", "c") | |
50 G.add_edge("b", "c") | |
51 G.add_edge("b", "d") | |
52 G.add_edge("d", "e") | |
53 G.add_edge("c", "y") | |
54 G.add_edge("e", "y") | |
55 _test_stoer_wagner(G, 2) | |
56 | |
57 | |
58 def test_graph3(): | |
59 # Source: | |
60 # Stoer, M. and Wagner, F. (1997). "A simple min-cut algorithm". Journal of | |
61 # the ACM 44 (4), 585-591. | |
62 G = nx.Graph() | |
63 G.add_edge(1, 2, weight=2) | |
64 G.add_edge(1, 5, weight=3) | |
65 G.add_edge(2, 3, weight=3) | |
66 G.add_edge(2, 5, weight=2) | |
67 G.add_edge(2, 6, weight=2) | |
68 G.add_edge(3, 4, weight=4) | |
69 G.add_edge(3, 7, weight=2) | |
70 G.add_edge(4, 7, weight=2) | |
71 G.add_edge(4, 8, weight=2) | |
72 G.add_edge(5, 6, weight=3) | |
73 G.add_edge(6, 7, weight=1) | |
74 G.add_edge(7, 8, weight=3) | |
75 _test_stoer_wagner(G, 4) | |
76 | |
77 | |
78 def test_weight_name(): | |
79 G = nx.Graph() | |
80 G.add_edge(1, 2, weight=1, cost=8) | |
81 G.add_edge(1, 3, cost=2) | |
82 G.add_edge(2, 3, cost=4) | |
83 _test_stoer_wagner(G, 6, weight="cost") | |
84 | |
85 | |
86 def test_exceptions(): | |
87 G = nx.Graph() | |
88 pytest.raises(nx.NetworkXError, nx.stoer_wagner, G) | |
89 G.add_node(1) | |
90 pytest.raises(nx.NetworkXError, nx.stoer_wagner, G) | |
91 G.add_node(2) | |
92 pytest.raises(nx.NetworkXError, nx.stoer_wagner, G) | |
93 G.add_edge(1, 2, weight=-2) | |
94 pytest.raises(nx.NetworkXError, nx.stoer_wagner, G) | |
95 G = nx.DiGraph() | |
96 pytest.raises(nx.NetworkXNotImplemented, nx.stoer_wagner, G) | |
97 G = nx.MultiGraph() | |
98 pytest.raises(nx.NetworkXNotImplemented, nx.stoer_wagner, G) | |
99 G = nx.MultiDiGraph() | |
100 pytest.raises(nx.NetworkXNotImplemented, nx.stoer_wagner, G) |