### view env/lib/python3.9/site-packages/networkx/algorithms/connectivity/tests/test_stoer_wagner.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
line wrap: on
line source
```
from itertools import chain
import networkx as nx
import pytest

def _check_partition(G, cut_value, partition, weight):
assert isinstance(partition, tuple)
assert len(partition) == 2
assert isinstance(partition[0], list)
assert isinstance(partition[1], list)
assert len(partition[0]) > 0
assert len(partition[1]) > 0
assert sum(map(len, partition)) == len(G)
assert set(chain.from_iterable(partition)) == set(G)
partition = tuple(map(set, partition))
w = 0
for u, v, e in G.edges(data=True):
if (u in partition[0]) == (v in partition[1]):
w += e.get(weight, 1)
assert w == cut_value

cut_value, partition = nx.stoer_wagner(G, weight, heap=nx.utils.PairingHeap)
_check_partition(G, cut_value, partition, weight)
cut_value, partition = nx.stoer_wagner(G, weight, heap=nx.utils.BinaryHeap)
_check_partition(G, cut_value, partition, weight)

def test_graph1():
G = nx.Graph()
_test_stoer_wagner(G, 4)

def test_graph2():
G = nx.Graph()
_test_stoer_wagner(G, 2)

def test_graph3():
# Source:
# Stoer, M. and Wagner, F. (1997). "A simple min-cut algorithm". Journal of
# the ACM 44 (4), 585-591.
G = nx.Graph()
_test_stoer_wagner(G, 4)

def test_weight_name():
G = nx.Graph()
_test_stoer_wagner(G, 6, weight="cost")

def test_exceptions():
G = nx.Graph()
pytest.raises(nx.NetworkXError, nx.stoer_wagner, G)