Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/tests/test_steinertree.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 import pytest | |
2 import networkx as nx | |
3 from networkx.algorithms.approximation.steinertree import metric_closure | |
4 from networkx.algorithms.approximation.steinertree import steiner_tree | |
5 from networkx.testing.utils import assert_edges_equal | |
6 | |
7 | |
8 class TestSteinerTree: | |
9 @classmethod | |
10 def setup_class(cls): | |
11 G = nx.Graph() | |
12 G.add_edge(1, 2, weight=10) | |
13 G.add_edge(2, 3, weight=10) | |
14 G.add_edge(3, 4, weight=10) | |
15 G.add_edge(4, 5, weight=10) | |
16 G.add_edge(5, 6, weight=10) | |
17 G.add_edge(2, 7, weight=1) | |
18 G.add_edge(7, 5, weight=1) | |
19 cls.G = G | |
20 cls.term_nodes = [1, 2, 3, 4, 5] | |
21 | |
22 def test_connected_metric_closure(self): | |
23 G = self.G.copy() | |
24 G.add_node(100) | |
25 pytest.raises(nx.NetworkXError, metric_closure, G) | |
26 | |
27 def test_metric_closure(self): | |
28 M = metric_closure(self.G) | |
29 mc = [ | |
30 (1, 2, {"distance": 10, "path": [1, 2]}), | |
31 (1, 3, {"distance": 20, "path": [1, 2, 3]}), | |
32 (1, 4, {"distance": 22, "path": [1, 2, 7, 5, 4]}), | |
33 (1, 5, {"distance": 12, "path": [1, 2, 7, 5]}), | |
34 (1, 6, {"distance": 22, "path": [1, 2, 7, 5, 6]}), | |
35 (1, 7, {"distance": 11, "path": [1, 2, 7]}), | |
36 (2, 3, {"distance": 10, "path": [2, 3]}), | |
37 (2, 4, {"distance": 12, "path": [2, 7, 5, 4]}), | |
38 (2, 5, {"distance": 2, "path": [2, 7, 5]}), | |
39 (2, 6, {"distance": 12, "path": [2, 7, 5, 6]}), | |
40 (2, 7, {"distance": 1, "path": [2, 7]}), | |
41 (3, 4, {"distance": 10, "path": [3, 4]}), | |
42 (3, 5, {"distance": 12, "path": [3, 2, 7, 5]}), | |
43 (3, 6, {"distance": 22, "path": [3, 2, 7, 5, 6]}), | |
44 (3, 7, {"distance": 11, "path": [3, 2, 7]}), | |
45 (4, 5, {"distance": 10, "path": [4, 5]}), | |
46 (4, 6, {"distance": 20, "path": [4, 5, 6]}), | |
47 (4, 7, {"distance": 11, "path": [4, 5, 7]}), | |
48 (5, 6, {"distance": 10, "path": [5, 6]}), | |
49 (5, 7, {"distance": 1, "path": [5, 7]}), | |
50 (6, 7, {"distance": 11, "path": [6, 5, 7]}), | |
51 ] | |
52 assert_edges_equal(list(M.edges(data=True)), mc) | |
53 | |
54 def test_steiner_tree(self): | |
55 S = steiner_tree(self.G, self.term_nodes) | |
56 expected_steiner_tree = [ | |
57 (1, 2, {"weight": 10}), | |
58 (2, 3, {"weight": 10}), | |
59 (2, 7, {"weight": 1}), | |
60 (3, 4, {"weight": 10}), | |
61 (5, 7, {"weight": 1}), | |
62 ] | |
63 assert_edges_equal(list(S.edges(data=True)), expected_steiner_tree) | |
64 | |
65 def test_multigraph_steiner_tree(self): | |
66 G = nx.MultiGraph() | |
67 G.add_edges_from( | |
68 [ | |
69 (1, 2, 0, {"weight": 1}), | |
70 (2, 3, 0, {"weight": 999}), | |
71 (2, 3, 1, {"weight": 1}), | |
72 (3, 4, 0, {"weight": 1}), | |
73 (3, 5, 0, {"weight": 1}), | |
74 ] | |
75 ) | |
76 terminal_nodes = [2, 4, 5] | |
77 expected_edges = [ | |
78 (2, 3, 1, {"weight": 1}), # edge with key 1 has lower weight | |
79 (3, 4, 0, {"weight": 1}), | |
80 (3, 5, 0, {"weight": 1}), | |
81 ] | |
82 T = steiner_tree(G, terminal_nodes) | |
83 assert_edges_equal(T.edges(data=True, keys=True), expected_edges) |