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