1import numpy as np
2from numpy.testing import assert_equal
3from scipy.sparse.csgraph import reverse_cuthill_mckee, structural_rank
4from scipy.sparse import csc_matrix, csr_matrix, coo_matrix
5
6
7def test_graph_reverse_cuthill_mckee():
8    A = np.array([[1, 0, 0, 0, 1, 0, 0, 0],
9                [0, 1, 1, 0, 0, 1, 0, 1],
10                [0, 1, 1, 0, 1, 0, 0, 0],
11                [0, 0, 0, 1, 0, 0, 1, 0],
12                [1, 0, 1, 0, 1, 0, 0, 0],
13                [0, 1, 0, 0, 0, 1, 0, 1],
14                [0, 0, 0, 1, 0, 0, 1, 0],
15                [0, 1, 0, 0, 0, 1, 0, 1]], dtype=int)
16
17    graph = csr_matrix(A)
18    perm = reverse_cuthill_mckee(graph)
19    correct_perm = np.array([6, 3, 7, 5, 1, 2, 4, 0])
20    assert_equal(perm, correct_perm)
21
22    # Test int64 indices input
23    graph.indices = graph.indices.astype('int64')
24    graph.indptr = graph.indptr.astype('int64')
25    perm = reverse_cuthill_mckee(graph, True)
26    assert_equal(perm, correct_perm)
27
28
29def test_graph_reverse_cuthill_mckee_ordering():
30    data = np.ones(63,dtype=int)
31    rows = np.array([0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2,
32                2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5,
33                6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9,
34                9, 10, 10, 10, 10, 10, 11, 11, 11, 11,
35                12, 12, 12, 13, 13, 13, 13, 14, 14, 14,
36                14, 15, 15, 15, 15, 15])
37    cols = np.array([0, 2, 5, 8, 10, 1, 3, 9, 11, 0, 2,
38                7, 10, 1, 3, 11, 4, 6, 12, 14, 0, 7, 13,
39                15, 4, 6, 14, 2, 5, 7, 15, 0, 8, 10, 13,
40                1, 9, 11, 0, 2, 8, 10, 15, 1, 3, 9, 11,
41                4, 12, 14, 5, 8, 13, 15, 4, 6, 12, 14,
42                5, 7, 10, 13, 15])
43    graph = coo_matrix((data, (rows,cols))).tocsr()
44    perm = reverse_cuthill_mckee(graph)
45    correct_perm = np.array([12, 14, 4, 6, 10, 8, 2, 15,
46                0, 13, 7, 5, 9, 11, 1, 3])
47    assert_equal(perm, correct_perm)
48
49
50def test_graph_structural_rank():
51    # Test square matrix #1
52    A = csc_matrix([[1, 1, 0],
53                    [1, 0, 1],
54                    [0, 1, 0]])
55    assert_equal(structural_rank(A), 3)
56
57    # Test square matrix #2
58    rows = np.array([0,0,0,0,0,1,1,2,2,3,3,3,3,3,3,4,4,5,5,6,6,7,7])
59    cols = np.array([0,1,2,3,4,2,5,2,6,0,1,3,5,6,7,4,5,5,6,2,6,2,4])
60    data = np.ones_like(rows)
61    B = coo_matrix((data,(rows,cols)), shape=(8,8))
62    assert_equal(structural_rank(B), 6)
63
64    #Test non-square matrix
65    C = csc_matrix([[1, 0, 2, 0],
66                    [2, 0, 4, 0]])
67    assert_equal(structural_rank(C), 2)
68
69    #Test tall matrix
70    assert_equal(structural_rank(C.T), 2)
71