### annotate env/lib/python3.9/site-packages/networkx/algorithms/centrality/flow_matrix.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
shellac
parents:
diff changeset
1 # Helpers for current-flow betweenness and current-flow closness
shellac
parents:
diff changeset
2 # Lazy computations for inverse Laplacian and flow-matrix rows.
shellac
parents:
diff changeset
3 import networkx as nx
shellac
parents:
diff changeset
4
shellac
parents:
diff changeset
5
shellac
parents:
diff changeset
6 def flow_matrix_row(G, weight=None, dtype=float, solver="lu"):
shellac
parents:
diff changeset
7 # Generate a row of the current-flow matrix
shellac
parents:
diff changeset
8 import numpy as np
shellac
parents:
diff changeset
9
shellac
parents:
diff changeset
10 solvername = {
shellac
parents:
diff changeset
11 "full": FullInverseLaplacian,
shellac
parents:
diff changeset
12 "lu": SuperLUInverseLaplacian,
shellac
parents:
diff changeset
13 "cg": CGInverseLaplacian,
shellac
parents:
diff changeset
14 }
shellac
parents:
diff changeset
15 n = G.number_of_nodes()
shellac
parents:
diff changeset
16 L = laplacian_sparse_matrix(
shellac
parents:
diff changeset
17 G, nodelist=range(n), weight=weight, dtype=dtype, format="csc"
shellac
parents:
diff changeset
18 )
shellac
parents:
diff changeset
19 C = solvername[solver](L, dtype=dtype) # initialize solver
shellac
parents:
diff changeset
20 w = C.w # w is the Laplacian matrix width
shellac
parents:
diff changeset
21 # row-by-row flow matrix
shellac
parents:
diff changeset
22 for u, v in sorted(sorted((u, v)) for u, v in G.edges()):
shellac
parents:
diff changeset
23 B = np.zeros(w, dtype=dtype)
shellac
parents:
diff changeset
24 c = G[u][v].get(weight, 1.0)
shellac
parents:
diff changeset
25 B[u % w] = c
shellac
parents:
diff changeset
26 B[v % w] = -c
shellac
parents:
diff changeset
27 # get only the rows needed in the inverse laplacian
shellac
parents:
diff changeset
28 # and multiply to get the flow matrix row
shellac
parents:
diff changeset
29 row = np.dot(B, C.get_rows(u, v))
shellac
parents:
diff changeset
30 yield row, (u, v)
shellac
parents:
diff changeset
31
shellac
parents:
diff changeset
32
shellac
parents:
diff changeset
33 # Class to compute the inverse laplacian only for specified rows
shellac
parents:
diff changeset
34 # Allows computation of the current-flow matrix without storing entire
shellac
parents:
diff changeset
35 # inverse laplacian matrix
shellac
parents:
diff changeset
36 class InverseLaplacian:
shellac
parents:
diff changeset
37 def __init__(self, L, width=None, dtype=None):
shellac
parents:
diff changeset
38 global np
shellac
parents:
diff changeset
39 import numpy as np
shellac
parents:
diff changeset
40
shellac
parents:
diff changeset
41 (n, n) = L.shape
shellac
parents:
diff changeset
42 self.dtype = dtype
shellac
parents:
diff changeset
43 self.n = n
shellac
parents:
diff changeset
44 if width is None:
shellac
parents:
diff changeset
45 self.w = self.width(L)
shellac
parents:
diff changeset
46 else:
shellac
parents:
diff changeset
47 self.w = width
shellac
parents:
diff changeset
48 self.C = np.zeros((self.w, n), dtype=dtype)
shellac
parents:
diff changeset
49 self.L1 = L[1:, 1:]
shellac
parents:
diff changeset
50 self.init_solver(L)
shellac
parents:
diff changeset
51
shellac
parents:
diff changeset
52 def init_solver(self, L):
shellac
parents:
diff changeset
53 pass
shellac
parents:
diff changeset
54
shellac
parents:
diff changeset
55 def solve(self, r):
shellac
parents:
diff changeset
56 raise nx.NetworkXError("Implement solver")
shellac
parents:
diff changeset
57
shellac
parents:
diff changeset
58 def solve_inverse(self, r):
shellac
parents:
diff changeset
59 raise nx.NetworkXError("Implement solver")
shellac
parents:
diff changeset
60
shellac
parents:
diff changeset
61 def get_rows(self, r1, r2):
shellac
parents:
diff changeset
62 for r in range(r1, r2 + 1):
shellac
parents:
diff changeset
63 self.C[r % self.w, 1:] = self.solve_inverse(r)
shellac
parents:
diff changeset
64 return self.C
shellac
parents:
diff changeset
65
shellac
parents:
diff changeset
66 def get_row(self, r):
shellac
parents:
diff changeset
67 self.C[r % self.w, 1:] = self.solve_inverse(r)
shellac
parents:
diff changeset
68 return self.C[r % self.w]
shellac
parents:
diff changeset
69
shellac
parents:
diff changeset
70 def width(self, L):
shellac
parents:
diff changeset
71 m = 0
shellac
parents:
diff changeset
72 for i, row in enumerate(L):
shellac
parents:
diff changeset
73 w = 0
shellac
parents:
diff changeset
74 x, y = np.nonzero(row)
shellac
parents:
diff changeset
75 if len(y) > 0:
shellac
parents:
diff changeset
76 v = y - i
shellac
parents:
diff changeset
77 w = v.max() - v.min() + 1
shellac
parents:
diff changeset
78 m = max(w, m)
shellac
parents:
diff changeset
79 return m
shellac
parents:
diff changeset
80
shellac
parents:
diff changeset
81
shellac
parents:
diff changeset
82 class FullInverseLaplacian(InverseLaplacian):
shellac
parents:
diff changeset
83 def init_solver(self, L):
shellac
parents:
diff changeset
84 self.IL = np.zeros(L.shape, dtype=self.dtype)
shellac
parents:
diff changeset
85 self.IL[1:, 1:] = np.linalg.inv(self.L1.todense())
shellac
parents:
diff changeset
86
shellac
parents:
diff changeset
87 def solve(self, rhs):
shellac
parents:
diff changeset
88 s = np.zeros(rhs.shape, dtype=self.dtype)
shellac
parents:
diff changeset
89 s = np.dot(self.IL, rhs)
shellac
parents:
diff changeset
90 return s
shellac
parents:
diff changeset
91
shellac
parents:
diff changeset
92 def solve_inverse(self, r):
shellac
parents:
diff changeset
93 return self.IL[r, 1:]
shellac
parents:
diff changeset
94
shellac
parents:
diff changeset
95
shellac
parents:
diff changeset
96 class SuperLUInverseLaplacian(InverseLaplacian):
shellac
parents:
diff changeset
97 def init_solver(self, L):
shellac
parents:
diff changeset
98 from scipy.sparse import linalg
shellac
parents:
diff changeset
99
shellac
parents:
diff changeset
100 self.lusolve = linalg.factorized(self.L1.tocsc())
shellac
parents:
diff changeset
101
shellac
parents:
diff changeset
102 def solve_inverse(self, r):
shellac
parents:
diff changeset
103 rhs = np.zeros(self.n, dtype=self.dtype)
shellac
parents:
diff changeset
104 rhs[r] = 1
shellac
parents:
diff changeset
105 return self.lusolve(rhs[1:])
shellac
parents:
diff changeset
106
shellac
parents:
diff changeset
107 def solve(self, rhs):
shellac
parents:
diff changeset
108 s = np.zeros(rhs.shape, dtype=self.dtype)
shellac
parents:
diff changeset
109 s[1:] = self.lusolve(rhs[1:])
shellac
parents:
diff changeset
110 return s
shellac
parents:
diff changeset
111
shellac
parents:
diff changeset
112
shellac
parents:
diff changeset
113 class CGInverseLaplacian(InverseLaplacian):
shellac
parents:
diff changeset
114 def init_solver(self, L):
shellac
parents:
diff changeset
115 global linalg
shellac
parents:
diff changeset
116 from scipy.sparse import linalg
shellac
parents:
diff changeset
117
shellac
parents:
diff changeset
118 ilu = linalg.spilu(self.L1.tocsc())
shellac
parents:
diff changeset
119 n = self.n - 1
shellac
parents:
diff changeset
120 self.M = linalg.LinearOperator(shape=(n, n), matvec=ilu.solve)
shellac
parents:
diff changeset
121
shellac
parents:
diff changeset
122 def solve(self, rhs):
shellac
parents:
diff changeset
123 s = np.zeros(rhs.shape, dtype=self.dtype)
shellac
parents:
diff changeset
124 s[1:] = linalg.cg(self.L1, rhs[1:], M=self.M, atol=0)[0]
shellac
parents:
diff changeset
125 return s
shellac
parents:
diff changeset
126
shellac
parents:
diff changeset
127 def solve_inverse(self, r):
shellac
parents:
diff changeset
128 rhs = np.zeros(self.n, self.dtype)
shellac
parents:
diff changeset
129 rhs[r] = 1
shellac
parents:
diff changeset
130 return linalg.cg(self.L1, rhs[1:], M=self.M, atol=0)[0]
shellac
parents:
diff changeset
131
shellac
parents:
diff changeset
132
shellac
parents:
diff changeset
133 # graph laplacian, sparse version, will move to linalg/laplacianmatrix.py
shellac
parents:
diff changeset
134 def laplacian_sparse_matrix(G, nodelist=None, weight=None, dtype=None, format="csr"):
shellac
parents:
diff changeset
135 import numpy as np
shellac
parents:
diff changeset
136 import scipy.sparse
shellac
parents:
diff changeset
137
shellac
parents:
diff changeset
138 A = nx.to_scipy_sparse_matrix(
shellac
parents:
diff changeset
139 G, nodelist=nodelist, weight=weight, dtype=dtype, format=format
shellac
parents:
diff changeset
140 )
shellac
parents:
diff changeset
141 (n, n) = A.shape
shellac
parents:
diff changeset
142 data = np.asarray(A.sum(axis=1).T)