Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/utils/tests/test_rcm.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 networkx.utils import reverse_cuthill_mckee_ordering | |
2 import networkx as nx | |
3 | |
4 | |
5 def test_reverse_cuthill_mckee(): | |
6 # example graph from | |
7 # http://www.boost.org/doc/libs/1_37_0/libs/graph/example/cuthill_mckee_ordering.cpp | |
8 G = nx.Graph( | |
9 [ | |
10 (0, 3), | |
11 (0, 5), | |
12 (1, 2), | |
13 (1, 4), | |
14 (1, 6), | |
15 (1, 9), | |
16 (2, 3), | |
17 (2, 4), | |
18 (3, 5), | |
19 (3, 8), | |
20 (4, 6), | |
21 (5, 6), | |
22 (5, 7), | |
23 (6, 7), | |
24 ] | |
25 ) | |
26 rcm = list(reverse_cuthill_mckee_ordering(G)) | |
27 assert rcm in [[0, 8, 5, 7, 3, 6, 2, 4, 1, 9], [0, 8, 5, 7, 3, 6, 4, 2, 1, 9]] | |
28 | |
29 | |
30 def test_rcm_alternate_heuristic(): | |
31 # example from | |
32 G = nx.Graph( | |
33 [ | |
34 (0, 0), | |
35 (0, 4), | |
36 (1, 1), | |
37 (1, 2), | |
38 (1, 5), | |
39 (1, 7), | |
40 (2, 2), | |
41 (2, 4), | |
42 (3, 3), | |
43 (3, 6), | |
44 (4, 4), | |
45 (5, 5), | |
46 (5, 7), | |
47 (6, 6), | |
48 (7, 7), | |
49 ] | |
50 ) | |
51 | |
52 answers = [ | |
53 [6, 3, 5, 7, 1, 2, 4, 0], | |
54 [6, 3, 7, 5, 1, 2, 4, 0], | |
55 [7, 5, 1, 2, 4, 0, 6, 3], | |
56 ] | |
57 | |
58 def smallest_degree(G): | |
59 deg, node = min((d, n) for n, d in G.degree()) | |
60 return node | |
61 | |
62 rcm = list(reverse_cuthill_mckee_ordering(G, heuristic=smallest_degree)) | |
63 assert rcm in answers |