guppy_basecaller: env/lib/python3.7/site-packages/networkx/linalg/algebraicconnectivity.py annotate

annotate env/lib/python3.7/site-packages/networkx/linalg/algebraicconnectivity.py @ 2:6af9afd405e9 draft

"planemo upload commit 0a63dd5f4d38a1f6944587f52a8cd79874177fc1"

author	shellac
date	Thu, 14 May 2020 14:56:58 -0400
parents	26e78fe6e8c4
children

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

Mercurial > repos > shellac > guppy_basecaller

annotate env/lib/python3.7/site-packages/networkx/linalg/algebraicconnectivity.py @ 2:6af9afd405e9 draft