/usr/lib/python2.7/dist-packages/networkx/utils/tests/test_rcm.py is in python-networkx 1.9+dfsg1-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | from nose.tools import *
from networkx.utils import reverse_cuthill_mckee_ordering
import networkx as nx
def test_reverse_cuthill_mckee():
# example graph from
# http://www.boost.org/doc/libs/1_37_0/libs/graph/example/cuthill_mckee_ordering.cpp
G = nx.Graph([(0,3),(0,5),(1,2),(1,4),(1,6),(1,9),(2,3),
(2,4),(3,5),(3,8),(4,6),(5,6),(5,7),(6,7)])
rcm = list(reverse_cuthill_mckee_ordering(G))
assert_equal(rcm,[0, 8, 5, 7, 3, 6, 4, 2, 1, 9])
def test_rcm_alternate_heuristic():
# example from
G = nx.Graph([(0, 0),
(0, 4),
(1, 1),
(1, 2),
(1, 5),
(1, 7),
(2, 2),
(2, 4),
(3, 3),
(3, 6),
(4, 4),
(5, 5),
(5, 7),
(6, 6),
(7, 7)])
answer = [6,3,7,5,1,2,4,0]
def smallest_degree(G):
node,deg = sorted(G.degree().items(), key = lambda x:x[1])[0]
return node
rcm = list(reverse_cuthill_mckee_ordering(G, heuristic=smallest_degree))
assert_equal(rcm, answer)
|