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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
from __future__ import division, print_function, absolute_import
import numpy as np
from numpy.testing import assert_equal
from scipy.sparse.csgraph import reverse_cuthill_mckee,\
maximum_bipartite_matching
from scipy.sparse import diags, csr_matrix, coo_matrix
def test_graph_reverse_cuthill_mckee():
A = np.array([[1, 0, 0, 0, 1, 0, 0, 0],
[0, 1, 1, 0, 0, 1, 0, 1],
[0, 1, 1, 0, 1, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 1, 0],
[1, 0, 1, 0, 1, 0, 0, 0],
[0, 1, 0, 0, 0, 1, 0, 1],
[0, 0, 0, 1, 0, 0, 1, 0],
[0, 1, 0, 0, 0, 1, 0, 1]], dtype=int)
graph = csr_matrix(A)
perm = reverse_cuthill_mckee(graph)
correct_perm = np.array([6, 3, 7, 5, 1, 2, 4, 0])
assert_equal(perm, correct_perm)
# Test int64 indices input
graph.indices = graph.indices.astype('int64')
graph.indptr = graph.indptr.astype('int64')
perm = reverse_cuthill_mckee(graph, True)
assert_equal(perm, correct_perm)
def test_graph_reverse_cuthill_mckee_ordering():
data = np.ones(63,dtype=int)
rows = np.array([0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2,
2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5,
6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9,
9, 10, 10, 10, 10, 10, 11, 11, 11, 11,
12, 12, 12, 13, 13, 13, 13, 14, 14, 14,
14, 15, 15, 15, 15, 15])
cols = np.array([0, 2, 5, 8, 10, 1, 3, 9, 11, 0, 2,
7, 10, 1, 3, 11, 4, 6, 12, 14, 0, 7, 13,
15, 4, 6, 14, 2, 5, 7, 15, 0, 8, 10, 13,
1, 9, 11, 0, 2, 8, 10, 15, 1, 3, 9, 11,
4, 12, 14, 5, 8, 13, 15, 4, 6, 12, 14,
5, 7, 10, 13, 15])
graph = coo_matrix((data, (rows,cols))).tocsr()
perm = reverse_cuthill_mckee(graph)
correct_perm = np.array([12, 14, 4, 6, 10, 8, 2, 15,
0, 13, 7, 5, 9, 11, 1, 3])
assert_equal(perm, correct_perm)
def test_graph_maximum_bipartite_matching():
A = diags(np.ones(25), offsets=0, format='csc')
rand_perm = np.random.permutation(25)
rand_perm2 = np.random.permutation(25)
Rrow = np.arange(25)
Rcol = rand_perm
Rdata = np.ones(25,dtype=int)
Rmat = coo_matrix((Rdata,(Rrow,Rcol))).tocsc()
Crow = rand_perm2
Ccol = np.arange(25)
Cdata = np.ones(25,dtype=int)
Cmat = coo_matrix((Cdata,(Crow,Ccol))).tocsc()
# Randomly permute identity matrix
B = Rmat*A*Cmat
# Row permute
perm = maximum_bipartite_matching(B,perm_type='row')
Rrow = np.arange(25)
Rcol = perm
Rdata = np.ones(25,dtype=int)
Rmat = coo_matrix((Rdata,(Rrow,Rcol))).tocsc()
C1 = Rmat*B
# Column permute
perm2 = maximum_bipartite_matching(B,perm_type='column')
Crow = perm2
Ccol = np.arange(25)
Cdata = np.ones(25,dtype=int)
Cmat = coo_matrix((Cdata,(Crow,Ccol))).tocsc()
C2 = B*Cmat
# Should get identity matrix back
assert_equal(any(C1.diagonal() == 0), False)
assert_equal(any(C2.diagonal() == 0), False)
# Test int64 indices input
B.indices = B.indices.astype('int64')
B.indptr = B.indptr.astype('int64')
perm = maximum_bipartite_matching(B,perm_type='row')
Rrow = np.arange(25)
Rcol = perm
Rdata = np.ones(25,dtype=int)
Rmat = coo_matrix((Rdata,(Rrow,Rcol))).tocsc()
C3 = Rmat*B
assert_equal(any(C3.diagonal() == 0), False)
|
