annotate env/lib/python3.9/site-packages/networkx/linalg/algebraicconnectivity.py @ 0:4f3585e2f14b draft default tip

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author shellac
date Mon, 22 Mar 2021 18:12:50 +0000
parents
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
1 """
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
2 Algebraic connectivity and Fiedler vectors of undirected graphs.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
3 """
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
4 from functools import partial
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
5 import networkx as nx
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
6 from networkx.utils import not_implemented_for
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
7 from networkx.utils import reverse_cuthill_mckee_ordering
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
8 from networkx.utils import random_state
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
9
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
10 try:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
11 from numpy import array, asarray, dot, ndarray, ones, sqrt, zeros, atleast_2d
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
12 from numpy.linalg import norm, qr
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
13 from scipy.linalg import eigh, inv
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
14 from scipy.sparse import csc_matrix, spdiags
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
15 from scipy.sparse.linalg import eigsh, lobpcg
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
16
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
17 __all__ = ["algebraic_connectivity", "fiedler_vector", "spectral_ordering"]
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
18 except ImportError:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
19 __all__ = []
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
20
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
21 try:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
22 from scipy.linalg.blas import dasum, daxpy, ddot
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
23 except ImportError:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
24 if __all__:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
25 # Make sure the imports succeeded.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
26 # Use minimal replacements if BLAS is unavailable from SciPy.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
27 dasum = partial(norm, ord=1)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
28 ddot = dot
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
29
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
30 def daxpy(x, y, a):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
31 y += a * x
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
32 return y
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
33
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
34
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
35 class _PCGSolver:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
36 """Preconditioned conjugate gradient method.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
37
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
38 To solve Ax = b:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
39 M = A.diagonal() # or some other preconditioner
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
40 solver = _PCGSolver(lambda x: A * x, lambda x: M * x)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
41 x = solver.solve(b)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
42
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
43 The inputs A and M are functions which compute
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
44 matrix multiplication on the argument.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
45 A - multiply by the matrix A in Ax=b
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
46 M - multiply by M, the preconditioner surragate for A
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
47
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
48 Warning: There is no limit on number of iterations.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
49 """
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
50
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
51 def __init__(self, A, M):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
52 self._A = A
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
53 self._M = M or (lambda x: x.copy())
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
54
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
55 def solve(self, B, tol):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
56 B = asarray(B)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
57 X = ndarray(B.shape, order="F")
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
58 for j in range(B.shape[1]):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
59 X[:, j] = self._solve(B[:, j], tol)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
60 return X
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
61
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
62 def _solve(self, b, tol):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
63 A = self._A
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
64 M = self._M
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
65 tol *= dasum(b)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
66 # Initialize.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
67 x = zeros(b.shape)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
68 r = b.copy()
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
69 z = M(r)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
70 rz = ddot(r, z)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
71 p = z.copy()
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
72 # Iterate.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
73 while True:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
74 Ap = A(p)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
75 alpha = rz / ddot(p, Ap)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
76 x = daxpy(p, x, a=alpha)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
77 r = daxpy(Ap, r, a=-alpha)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
78 if dasum(r) < tol:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
79 return x
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
80 z = M(r)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
81 beta = ddot(r, z)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
82 beta, rz = beta / rz, beta
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
83 p = daxpy(p, z, a=beta)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
84
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
85
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
86 class _CholeskySolver:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
87 """Cholesky factorization.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
88
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
89 To solve Ax = b:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
90 solver = _CholeskySolver(A)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
91 x = solver.solve(b)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
92
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
93 optional argument `tol` on solve method is ignored but included
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
94 to match _PCGsolver API.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
95 """
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
96
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
97 def __init__(self, A):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
98 if not self._cholesky:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
99 raise nx.NetworkXError("Cholesky solver unavailable.")
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
100 self._chol = self._cholesky(A)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
101
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
102 def solve(self, B, tol=None):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
103 return self._chol(B)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
104
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
105 try:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
106 from scikits.sparse.cholmod import cholesky
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
107
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
108 _cholesky = cholesky
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
109 except ImportError:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
110 _cholesky = None
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
111
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
112
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
113 class _LUSolver:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
114 """LU factorization.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
115
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
116 To solve Ax = b:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
117 solver = _LUSolver(A)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
118 x = solver.solve(b)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
119
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
120 optional argument `tol` on solve method is ignored but included
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
121 to match _PCGsolver API.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
122 """
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
123
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
124 def __init__(self, A):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
125 if not self._splu:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
126 raise nx.NetworkXError("LU solver unavailable.")
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
127 self._LU = self._splu(A)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
128
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
129 def solve(self, B, tol=None):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
130 B = asarray(B)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
131 X = ndarray(B.shape, order="F")
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
132 for j in range(B.shape[1]):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
133 X[:, j] = self._LU.solve(B[:, j])
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
134 return X
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
135
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
136 try:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
137 from scipy.sparse.linalg import splu
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
138
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
139 _splu = partial(
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
140 splu,
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
141 permc_spec="MMD_AT_PLUS_A",
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
142 diag_pivot_thresh=0.0,
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
143 options={"Equil": True, "SymmetricMode": True},
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
144 )
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
145 except ImportError:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
146 _splu = None
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
147
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
148
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
149 def _preprocess_graph(G, weight):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
150 """Compute edge weights and eliminate zero-weight edges.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
151 """
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
152 if G.is_directed():
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
153 H = nx.MultiGraph()
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
154 H.add_nodes_from(G)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
155 H.add_weighted_edges_from(
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
156 ((u, v, e.get(weight, 1.0)) for u, v, e in G.edges(data=True) if u != v),
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
157 weight=weight,
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
158 )
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
159 G = H
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
160 if not G.is_multigraph():
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
161 edges = (
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
162 (u, v, abs(e.get(weight, 1.0))) for u, v, e in G.edges(data=True) if u != v
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
163 )
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
164 else:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
165 edges = (
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
166 (u, v, sum(abs(e.get(weight, 1.0)) for e in G[u][v].values()))
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
167 for u, v in G.edges()
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
168 if u != v
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
169 )
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
170 H = nx.Graph()
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
171 H.add_nodes_from(G)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
172 H.add_weighted_edges_from((u, v, e) for u, v, e in edges if e != 0)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
173 return H
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
174
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
175
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
176 def _rcm_estimate(G, nodelist):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
177 """Estimate the Fiedler vector using the reverse Cuthill-McKee ordering.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
178 """
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
179 G = G.subgraph(nodelist)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
180 order = reverse_cuthill_mckee_ordering(G)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
181 n = len(nodelist)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
182 index = dict(zip(nodelist, range(n)))
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
183 x = ndarray(n, dtype=float)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
184 for i, u in enumerate(order):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
185 x[index[u]] = i
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
186 x -= (n - 1) / 2.0
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
187 return x
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
188
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
189
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
190 def _tracemin_fiedler(L, X, normalized, tol, method):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
191 """Compute the Fiedler vector of L using the TraceMIN-Fiedler algorithm.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
192
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
193 The Fiedler vector of a connected undirected graph is the eigenvector
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
194 corresponding to the second smallest eigenvalue of the Laplacian matrix of
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
195 of the graph. This function starts with the Laplacian L, not the Graph.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
196
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
197 Parameters
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
198 ----------
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
199 L : Laplacian of a possibly weighted or normalized, but undirected graph
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
200
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
201 X : Initial guess for a solution. Usually a matrix of random numbers.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
202 This function allows more than one column in X to identify more than
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
203 one eigenvector if desired.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
204
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
205 normalized : bool
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
206 Whether the normalized Laplacian matrix is used.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
207
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
208 tol : float
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
209 Tolerance of relative residual in eigenvalue computation.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
210 Warning: There is no limit on number of iterations.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
211
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
212 method : string
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
213 Should be 'tracemin_pcg', 'tracemin_chol' or 'tracemin_lu'.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
214 Otherwise exception is raised.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
215
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
216 Returns
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
217 -------
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
218 sigma, X : Two NumPy arrays of floats.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
219 The lowest eigenvalues and corresponding eigenvectors of L.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
220 The size of input X determines the size of these outputs.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
221 As this is for Fiedler vectors, the zero eigenvalue (and
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
222 constant eigenvector) are avoided.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
223 """
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
224 n = X.shape[0]
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
225
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
226 if normalized:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
227 # Form the normalized Laplacian matrix and determine the eigenvector of
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
228 # its nullspace.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
229 e = sqrt(L.diagonal())
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
230 D = spdiags(1.0 / e, [0], n, n, format="csr")
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
231 L = D * L * D
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
232 e *= 1.0 / norm(e, 2)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
233
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
234 if normalized:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
235
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
236 def project(X):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
237 """Make X orthogonal to the nullspace of L.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
238 """
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
239 X = asarray(X)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
240 for j in range(X.shape[1]):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
241 X[:, j] -= dot(X[:, j], e) * e
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
242
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
243 else:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
244
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
245 def project(X):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
246 """Make X orthogonal to the nullspace of L.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
247 """
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
248 X = asarray(X)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
249 for j in range(X.shape[1]):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
250 X[:, j] -= X[:, j].sum() / n
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
251
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
252 if method == "tracemin_pcg":
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
253 D = L.diagonal().astype(float)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
254 solver = _PCGSolver(lambda x: L * x, lambda x: D * x)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
255 elif method == "tracemin_chol" or method == "tracemin_lu":
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
256 # Convert A to CSC to suppress SparseEfficiencyWarning.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
257 A = csc_matrix(L, dtype=float, copy=True)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
258 # Force A to be nonsingular. Since A is the Laplacian matrix of a
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
259 # connected graph, its rank deficiency is one, and thus one diagonal
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
260 # element needs to modified. Changing to infinity forces a zero in the
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
261 # corresponding element in the solution.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
262 i = (A.indptr[1:] - A.indptr[:-1]).argmax()
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
263 A[i, i] = float("inf")
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
264 if method == "tracemin_chol":
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
265 solver = _CholeskySolver(A)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
266 else:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
267 solver = _LUSolver(A)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
268 else:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
269 raise nx.NetworkXError("Unknown linear system solver: " + method)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
270
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
271 # Initialize.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
272 Lnorm = abs(L).sum(axis=1).flatten().max()
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
273 project(X)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
274 W = ndarray(X.shape, order="F")
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
275
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
276 while True:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
277 # Orthonormalize X.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
278 X = qr(X)[0]
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
279 # Compute iteration matrix H.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
280 W[:, :] = L @ X
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
281 H = X.T @ W
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
282 sigma, Y = eigh(H, overwrite_a=True)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
283 # Compute the Ritz vectors.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
284 X = X @ Y
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
285 # Test for convergence exploiting the fact that L * X == W * Y.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
286 res = dasum(W @ Y[:, 0] - sigma[0] * X[:, 0]) / Lnorm
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
287 if res < tol:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
288 break
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
289 # Compute X = L \ X / (X' * (L \ X)).
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
290 # L \ X can have an arbitrary projection on the nullspace of L,
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
291 # which will be eliminated.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
292 W[:, :] = solver.solve(X, tol)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
293 X = (inv(W.T @ X) @ W.T).T # Preserves Fortran storage order.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
294 project(X)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
295
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
296 return sigma, asarray(X)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
297
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
298
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
299 def _get_fiedler_func(method):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
300 """Returns a function that solves the Fiedler eigenvalue problem.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
301 """
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
302 if method == "tracemin": # old style keyword <v2.1
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
303 method = "tracemin_pcg"
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
304 if method in ("tracemin_pcg", "tracemin_chol", "tracemin_lu"):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
305
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
306 def find_fiedler(L, x, normalized, tol, seed):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
307 q = 1 if method == "tracemin_pcg" else min(4, L.shape[0] - 1)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
308 X = asarray(seed.normal(size=(q, L.shape[0]))).T
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
309 sigma, X = _tracemin_fiedler(L, X, normalized, tol, method)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
310 return sigma[0], X[:, 0]
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
311
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
312 elif method == "lanczos" or method == "lobpcg":
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
313
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
314 def find_fiedler(L, x, normalized, tol, seed):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
315 L = csc_matrix(L, dtype=float)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
316 n = L.shape[0]
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
317 if normalized:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
318 D = spdiags(1.0 / sqrt(L.diagonal()), [0], n, n, format="csc")
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
319 L = D * L * D
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
320 if method == "lanczos" or n < 10:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
321 # Avoid LOBPCG when n < 10 due to
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
322 # https://github.com/scipy/scipy/issues/3592
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
323 # https://github.com/scipy/scipy/pull/3594
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
324 sigma, X = eigsh(L, 2, which="SM", tol=tol, return_eigenvectors=True)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
325 return sigma[1], X[:, 1]
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
326 else:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
327 X = asarray(atleast_2d(x).T)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
328 M = spdiags(1.0 / L.diagonal(), [0], n, n)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
329 Y = ones(n)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
330 if normalized:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
331 Y /= D.diagonal()
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
332 sigma, X = lobpcg(
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
333 L, X, M=M, Y=atleast_2d(Y).T, tol=tol, maxiter=n, largest=False
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
334 )
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
335 return sigma[0], X[:, 0]
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
336
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
337 else:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
338 raise nx.NetworkXError(f"unknown method '{method}'.")
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
339
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
340 return find_fiedler
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
341
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
342
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
343 @random_state(5)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
344 @not_implemented_for("directed")
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
345 def algebraic_connectivity(
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
346 G, weight="weight", normalized=False, tol=1e-8, method="tracemin_pcg", seed=None
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
347 ):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
348 """Returns the algebraic connectivity of an undirected graph.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
349
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
350 The algebraic connectivity of a connected undirected graph is the second
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
351 smallest eigenvalue of its Laplacian matrix.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
352
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
353 Parameters
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
354 ----------
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
355 G : NetworkX graph
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
356 An undirected graph.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
357
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
358 weight : object, optional (default: None)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
359 The data key used to determine the weight of each edge. If None, then
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
360 each edge has unit weight.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
361
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
362 normalized : bool, optional (default: False)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
363 Whether the normalized Laplacian matrix is used.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
364
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
365 tol : float, optional (default: 1e-8)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
366 Tolerance of relative residual in eigenvalue computation.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
367
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
368 method : string, optional (default: 'tracemin_pcg')
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
369 Method of eigenvalue computation. It must be one of the tracemin
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
370 options shown below (TraceMIN), 'lanczos' (Lanczos iteration)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
371 or 'lobpcg' (LOBPCG).
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
372
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
373 The TraceMIN algorithm uses a linear system solver. The following
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
374 values allow specifying the solver to be used.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
375
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
376 =============== ========================================
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
377 Value Solver
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
378 =============== ========================================
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
379 'tracemin_pcg' Preconditioned conjugate gradient method
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
380 'tracemin_chol' Cholesky factorization
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
381 'tracemin_lu' LU factorization
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
382 =============== ========================================
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
383
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
384 seed : integer, random_state, or None (default)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
385 Indicator of random number generation state.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
386 See :ref:`Randomness<randomness>`.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
387
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
388 Returns
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
389 -------
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
390 algebraic_connectivity : float
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
391 Algebraic connectivity.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
392
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
393 Raises
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
394 ------
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
395 NetworkXNotImplemented
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
396 If G is directed.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
397
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
398 NetworkXError
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
399 If G has less than two nodes.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
400
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
401 Notes
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
402 -----
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
403 Edge weights are interpreted by their absolute values. For MultiGraph's,
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
404 weights of parallel edges are summed. Zero-weighted edges are ignored.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
405
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
406 To use Cholesky factorization in the TraceMIN algorithm, the
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
407 :samp:`scikits.sparse` package must be installed.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
408
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
409 See Also
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
410 --------
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
411 laplacian_matrix
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
412 """
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
413 if len(G) < 2:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
414 raise nx.NetworkXError("graph has less than two nodes.")
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
415 G = _preprocess_graph(G, weight)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
416 if not nx.is_connected(G):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
417 return 0.0
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
418
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
419 L = nx.laplacian_matrix(G)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
420 if L.shape[0] == 2:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
421 return 2.0 * L[0, 0] if not normalized else 2.0
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
422
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
423 find_fiedler = _get_fiedler_func(method)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
424 x = None if method != "lobpcg" else _rcm_estimate(G, G)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
425 sigma, fiedler = find_fiedler(L, x, normalized, tol, seed)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
426 return sigma
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
427
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
428
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
429 @random_state(5)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
430 @not_implemented_for("directed")
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
431 def fiedler_vector(
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
432 G, weight="weight", normalized=False, tol=1e-8, method="tracemin_pcg", seed=None
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
433 ):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
434 """Returns the Fiedler vector of a connected undirected graph.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
435
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
436 The Fiedler vector of a connected undirected graph is the eigenvector
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
437 corresponding to the second smallest eigenvalue of the Laplacian matrix of
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
438 of the graph.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
439
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
440 Parameters
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
441 ----------
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
442 G : NetworkX graph
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
443 An undirected graph.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
444
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
445 weight : object, optional (default: None)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
446 The data key used to determine the weight of each edge. If None, then
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
447 each edge has unit weight.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
448
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
449 normalized : bool, optional (default: False)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
450 Whether the normalized Laplacian matrix is used.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
451
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
452 tol : float, optional (default: 1e-8)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
453 Tolerance of relative residual in eigenvalue computation.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
454
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
455 method : string, optional (default: 'tracemin_pcg')
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
456 Method of eigenvalue computation. It must be one of the tracemin
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
457 options shown below (TraceMIN), 'lanczos' (Lanczos iteration)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
458 or 'lobpcg' (LOBPCG).
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
459
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
460 The TraceMIN algorithm uses a linear system solver. The following
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
461 values allow specifying the solver to be used.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
462
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
463 =============== ========================================
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
464 Value Solver
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
465 =============== ========================================
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
466 'tracemin_pcg' Preconditioned conjugate gradient method
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
467 'tracemin_chol' Cholesky factorization
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
468 'tracemin_lu' LU factorization
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
469 =============== ========================================
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
470
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
471 seed : integer, random_state, or None (default)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
472 Indicator of random number generation state.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
473 See :ref:`Randomness<randomness>`.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
474
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
475 Returns
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
476 -------
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
477 fiedler_vector : NumPy array of floats.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
478 Fiedler vector.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
479
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
480 Raises
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
481 ------
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
482 NetworkXNotImplemented
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
483 If G is directed.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
484
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
485 NetworkXError
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
486 If G has less than two nodes or is not connected.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
487
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
488 Notes
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
489 -----
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
490 Edge weights are interpreted by their absolute values. For MultiGraph's,
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
491 weights of parallel edges are summed. Zero-weighted edges are ignored.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
492
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
493 To use Cholesky factorization in the TraceMIN algorithm, the
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
494 :samp:`scikits.sparse` package must be installed.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
495
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
496 See Also
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
497 --------
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
498 laplacian_matrix
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
499 """
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
500 if len(G) < 2:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
501 raise nx.NetworkXError("graph has less than two nodes.")
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
502 G = _preprocess_graph(G, weight)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
503 if not nx.is_connected(G):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
504 raise nx.NetworkXError("graph is not connected.")
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
505
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
506 if len(G) == 2:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
507 return array([1.0, -1.0])
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
508
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
509 find_fiedler = _get_fiedler_func(method)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
510 L = nx.laplacian_matrix(G)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
511 x = None if method != "lobpcg" else _rcm_estimate(G, G)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
512 sigma, fiedler = find_fiedler(L, x, normalized, tol, seed)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
513 return fiedler
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
514
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
515
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
516 @random_state(5)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
517 def spectral_ordering(
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
518 G, weight="weight", normalized=False, tol=1e-8, method="tracemin_pcg", seed=None
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
519 ):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
520 """Compute the spectral_ordering of a graph.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
521
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
522 The spectral ordering of a graph is an ordering of its nodes where nodes
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
523 in the same weakly connected components appear contiguous and ordered by
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
524 their corresponding elements in the Fiedler vector of the component.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
525
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
526 Parameters
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
527 ----------
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
528 G : NetworkX graph
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
529 A graph.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
530
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
531 weight : object, optional (default: None)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
532 The data key used to determine the weight of each edge. If None, then
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
533 each edge has unit weight.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
534
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
535 normalized : bool, optional (default: False)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
536 Whether the normalized Laplacian matrix is used.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
537
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
538 tol : float, optional (default: 1e-8)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
539 Tolerance of relative residual in eigenvalue computation.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
540
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
541 method : string, optional (default: 'tracemin_pcg')
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
542 Method of eigenvalue computation. It must be one of the tracemin
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
543 options shown below (TraceMIN), 'lanczos' (Lanczos iteration)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
544 or 'lobpcg' (LOBPCG).
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
545
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
546 The TraceMIN algorithm uses a linear system solver. The following
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
547 values allow specifying the solver to be used.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
548
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
549 =============== ========================================
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
550 Value Solver
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
551 =============== ========================================
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
552 'tracemin_pcg' Preconditioned conjugate gradient method
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
553 'tracemin_chol' Cholesky factorization
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
554 'tracemin_lu' LU factorization
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
555 =============== ========================================
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
556
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
557 seed : integer, random_state, or None (default)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
558 Indicator of random number generation state.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
559 See :ref:`Randomness<randomness>`.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
560
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
561 Returns
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
562 -------
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
563 spectral_ordering : NumPy array of floats.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
564 Spectral ordering of nodes.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
565
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
566 Raises
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
567 ------
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
568 NetworkXError
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
569 If G is empty.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
570
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
571 Notes
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
572 -----
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
573 Edge weights are interpreted by their absolute values. For MultiGraph's,
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
574 weights of parallel edges are summed. Zero-weighted edges are ignored.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
575
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
576 To use Cholesky factorization in the TraceMIN algorithm, the
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
577 :samp:`scikits.sparse` package must be installed.
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
578
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
579 See Also
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
580 --------
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
581 laplacian_matrix
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
582 """
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
583 if len(G) == 0:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
584 raise nx.NetworkXError("graph is empty.")
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
585 G = _preprocess_graph(G, weight)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
586
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
587 find_fiedler = _get_fiedler_func(method)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
588 order = []
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
589 for component in nx.connected_components(G):
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
590 size = len(component)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
591 if size > 2:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
592 L = nx.laplacian_matrix(G, component)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
593 x = None if method != "lobpcg" else _rcm_estimate(G, component)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
594 sigma, fiedler = find_fiedler(L, x, normalized, tol, seed)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
595 sort_info = zip(fiedler, range(size), component)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
596 order.extend(u for x, c, u in sorted(sort_info))
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
597 else:
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
598 order.extend(component)
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
599
4f3585e2f14b "planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
shellac
parents:
diff changeset
600 return order