summaryrefslogtreecommitdiff
path: root/networkx
diff options
context:
space:
mode:
Diffstat (limited to 'networkx')
-rw-r--r--networkx/algorithms/centrality/eigenvector.py33
-rw-r--r--networkx/algorithms/centrality/subgraph_alg.py111
-rw-r--r--networkx/algorithms/link_analysis/hits_alg.py28
-rw-r--r--networkx/algorithms/link_analysis/pagerank_alg.py19
-rw-r--r--networkx/convert.py104
-rw-r--r--networkx/convert_matrix.py200
-rw-r--r--networkx/exception.py28
-rw-r--r--networkx/linalg/algebraicconnectivity.py122
-rw-r--r--networkx/linalg/attrmatrix.py67
-rw-r--r--networkx/linalg/bethehessianmatrix.py18
-rw-r--r--networkx/linalg/graphmatrix.py12
-rw-r--r--networkx/linalg/laplacianmatrix.py92
-rw-r--r--networkx/linalg/modularitymatrix.py17
-rw-r--r--networkx/linalg/spectrum.py20
-rw-r--r--networkx/linalg/tests/test_algebraic_connectivity.py246
-rw-r--r--networkx/linalg/tests/test_attrmatrix.py8
-rw-r--r--networkx/linalg/tests/test_bethehessian.py32
-rw-r--r--networkx/linalg/tests/test_laplacian.py75
-rw-r--r--networkx/linalg/tests/test_modularity.py32
-rw-r--r--networkx/linalg/tests/test_spectrum.py30
-rw-r--r--networkx/relabel.py55
-rw-r--r--networkx/tests/test_convert.py42
-rw-r--r--networkx/tests/test_convert_numpy.py95
-rw-r--r--networkx/tests/test_convert_scipy.py116
-rw-r--r--networkx/tests/test_relabel.py85
25 files changed, 1028 insertions, 659 deletions
diff --git a/networkx/algorithms/centrality/eigenvector.py b/networkx/algorithms/centrality/eigenvector.py
index 71fcb735..611cf407 100644
--- a/networkx/algorithms/centrality/eigenvector.py
+++ b/networkx/algorithms/centrality/eigenvector.py
@@ -5,12 +5,11 @@ from math import sqrt
import networkx as nx
from networkx.utils import not_implemented_for
-__all__ = ['eigenvector_centrality', 'eigenvector_centrality_numpy']
+__all__ = ["eigenvector_centrality", "eigenvector_centrality_numpy"]
-@not_implemented_for('multigraph')
-def eigenvector_centrality(G, max_iter=100, tol=1.0e-6, nstart=None,
- weight=None):
+@not_implemented_for("multigraph")
+def eigenvector_centrality(G, max_iter=100, tol=1.0e-6, nstart=None, weight=None):
r"""Compute the eigenvector centrality for the graph `G`.
Eigenvector centrality computes the centrality for a node based on the
@@ -104,13 +103,14 @@ def eigenvector_centrality(G, max_iter=100, tol=1.0e-6, nstart=None,
"""
if len(G) == 0:
- raise nx.NetworkXPointlessConcept('cannot compute centrality for the'
- ' null graph')
+ raise nx.NetworkXPointlessConcept(
+ "cannot compute centrality for the null graph"
+ )
# If no initial vector is provided, start with the all-ones vector.
if nstart is None:
nstart = {v: 1 for v in G}
if all(v == 0 for v in nstart.values()):
- raise nx.NetworkXError('initial vector cannot have all zero values')
+ raise nx.NetworkXError("initial vector cannot have all zero values")
# Normalize the initial vector so that each entry is in [0, 1]. This is
# guaranteed to never have a divide-by-zero error by the previous line.
nstart_sum = sum(nstart.values())
@@ -177,7 +177,7 @@ def eigenvector_centrality_numpy(G, weight=None, max_iter=50, tol=0):
--------
>>> G = nx.path_graph(4)
>>> centrality = nx.eigenvector_centrality_numpy(G)
- >>> print([f"{node} {centrality[node]:0.2f}" for node in centrality])
+ >>> print([f"{node} {centrality[node]:0.2f}" for node in centrality])
['0 0.37', '1 0.60', '2 0.60', '3 0.37']
See Also
@@ -212,15 +212,18 @@ def eigenvector_centrality_numpy(G, weight=None, max_iter=50, tol=0):
Networks: An Introduction.
Oxford University Press, USA, 2010, pp. 169.
"""
+ import numpy as np
import scipy as sp
from scipy.sparse import linalg
+
if len(G) == 0:
- raise nx.NetworkXPointlessConcept('cannot compute centrality for the'
- ' null graph')
- M = nx.to_scipy_sparse_matrix(G, nodelist=list(G), weight=weight,
- dtype=float)
- eigenvalue, eigenvector = linalg.eigs(M.T, k=1, which='LR',
- maxiter=max_iter, tol=tol)
+ raise nx.NetworkXPointlessConcept(
+ "cannot compute centrality for the null graph"
+ )
+ M = nx.to_scipy_sparse_matrix(G, nodelist=list(G), weight=weight, dtype=float)
+ eigenvalue, eigenvector = linalg.eigs(
+ M.T, k=1, which="LR", maxiter=max_iter, tol=tol
+ )
largest = eigenvector.flatten().real
- norm = sp.sign(largest.sum()) * sp.linalg.norm(largest)
+ norm = np.sign(largest.sum()) * sp.linalg.norm(largest)
return dict(zip(G, largest / norm))
diff --git a/networkx/algorithms/centrality/subgraph_alg.py b/networkx/algorithms/centrality/subgraph_alg.py
index f45cae24..d8c883e3 100644
--- a/networkx/algorithms/centrality/subgraph_alg.py
+++ b/networkx/algorithms/centrality/subgraph_alg.py
@@ -4,15 +4,16 @@ Subraph centrality and communicability betweenness.
import networkx as nx
from networkx.utils import not_implemented_for
-__all__ = ['subgraph_centrality_exp',
- 'subgraph_centrality',
- 'communicability_betweenness_centrality',
- 'estrada_index'
- ]
+__all__ = [
+ "subgraph_centrality_exp",
+ "subgraph_centrality",
+ "communicability_betweenness_centrality",
+ "estrada_index",
+]
-@not_implemented_for('directed')
-@not_implemented_for('multigraph')
+@not_implemented_for("directed")
+@not_implemented_for("multigraph")
def subgraph_centrality_exp(G):
r"""Returns the subgraph centrality for each node of G.
@@ -61,13 +62,29 @@ def subgraph_centrality_exp(G):
Examples
--------
(Example from [1]_)
- >>> G = nx.Graph([(1,2),(1,5),(1,8),(2,3),(2,8),(3,4),(3,6),(4,5),(4,7),(5,6),(6,7),(7,8)])
+ >>> G = nx.Graph(
+ ... [
+ ... (1, 2),
+ ... (1, 5),
+ ... (1, 8),
+ ... (2, 3),
+ ... (2, 8),
+ ... (3, 4),
+ ... (3, 6),
+ ... (4, 5),
+ ... (4, 7),
+ ... (5, 6),
+ ... (6, 7),
+ ... (7, 8),
+ ... ]
+ ... )
>>> sc = nx.subgraph_centrality_exp(G)
- >>> print(['%s %0.2f'%(node,sc[node]) for node in sorted(sc)])
+ >>> print([f"{node} {sc[node]:0.2f}" for node in sorted(sc)])
['1 3.90', '2 3.90', '3 3.64', '4 3.71', '5 3.64', '6 3.71', '7 3.64', '8 3.90']
"""
# alternative implementation that calculates the matrix exponential
import scipy.linalg
+
nodelist = list(G) # ordering of nodes in matrix
A = nx.to_numpy_array(G, nodelist)
# convert to 0-1 matrix
@@ -78,8 +95,8 @@ def subgraph_centrality_exp(G):
return sc
-@not_implemented_for('directed')
-@not_implemented_for('multigraph')
+@not_implemented_for("directed")
+@not_implemented_for("multigraph")
def subgraph_centrality(G):
r"""Returns subgraph centrality for each node in G.
@@ -125,9 +142,24 @@ def subgraph_centrality(G):
Examples
--------
(Example from [1]_)
- >>> G = nx.Graph([(1,2),(1,5),(1,8),(2,3),(2,8),(3,4),(3,6),(4,5),(4,7),(5,6),(6,7),(7,8)])
+ >>> G = nx.Graph(
+ ... [
+ ... (1, 2),
+ ... (1, 5),
+ ... (1, 8),
+ ... (2, 3),
+ ... (2, 8),
+ ... (3, 4),
+ ... (3, 6),
+ ... (4, 5),
+ ... (4, 7),
+ ... (5, 6),
+ ... (6, 7),
+ ... (7, 8),
+ ... ]
+ ... )
>>> sc = nx.subgraph_centrality(G)
- >>> print(['%s %0.2f'%(node,sc[node]) for node in sorted(sc)])
+ >>> print([f"{node} {sc[node]:0.2f}" for node in sorted(sc)])
['1 3.90', '2 3.90', '3 3.64', '4 3.71', '5 3.64', '6 3.71', '7 3.64', '8 3.90']
References
@@ -138,23 +170,24 @@ def subgraph_centrality(G):
https://arxiv.org/abs/cond-mat/0504730
"""
- import numpy
+ import numpy as np
import numpy.linalg
+
nodelist = list(G) # ordering of nodes in matrix
A = nx.to_numpy_matrix(G, nodelist)
# convert to 0-1 matrix
A[A != 0.0] = 1
w, v = numpy.linalg.eigh(A.A)
- vsquare = numpy.array(v)**2
- expw = numpy.exp(w)
- xg = numpy.dot(vsquare, expw)
+ vsquare = np.array(v) ** 2
+ expw = np.exp(w)
+ xg = np.dot(vsquare, expw)
# convert vector dictionary keyed by node
sc = dict(zip(nodelist, map(float, xg)))
return sc
-@not_implemented_for('directed')
-@not_implemented_for('multigraph')
+@not_implemented_for("directed")
+@not_implemented_for("multigraph")
def communicability_betweenness_centrality(G, normalized=True):
r"""Returns subgraph communicability for all pairs of nodes in G.
@@ -215,11 +248,25 @@ def communicability_betweenness_centrality(G, normalized=True):
Examples
--------
- >>> G = nx.Graph([(0,1),(1,2),(1,5),(5,4),(2,4),(2,3),(4,3),(3,6)])
+ >>> G = nx.Graph(
+ ... [
+ ... (0, 1),
+ ... (1, 2),
+ ... (1, 5),
+ ... (5, 4),
+ ... (2, 4),
+ ... (2, 3),
+ ... (4, 3),
+ ... (3, 6),
+ ... ]
+ ... )
>>> cbc = nx.communicability_betweenness_centrality(G)
+ >>> print([f"{node} {cbc[node]:0.2f}" for node in sorted(cbc)])
+ ['0 0.03', '1 0.45', '2 0.51', '3 0.45', '4 0.40', '5 0.19', '6 0.03']
"""
- import scipy
+ import numpy as np
import scipy.linalg
+
nodelist = list(G) # ordering of nodes in matrix
n = len(nodelist)
A = nx.to_numpy_matrix(G, nodelist)
@@ -239,7 +286,7 @@ def communicability_betweenness_centrality(G, normalized=True):
# sum with row/col of node v and diag set to zero
B[i, :] = 0
B[:, i] = 0
- B -= scipy.diag(scipy.diag(B))
+ B -= np.diag(np.diag(B))
cbc[v] = float(B.sum())
# put row and col back
A[i, :] = row
@@ -256,7 +303,7 @@ def _rescale(cbc, normalized):
if order <= 2:
scale = None
else:
- scale = 1.0 / ((order - 1.0)**2 - (order - 1.0))
+ scale = 1.0 / ((order - 1.0) ** 2 - (order - 1.0))
if scale is not None:
for v in cbc:
cbc[v] *= scale
@@ -303,7 +350,21 @@ def estrada_index(G):
Examples
--------
- >>> G=nx.Graph([(0,1),(1,2),(1,5),(5,4),(2,4),(2,3),(4,3),(3,6)])
- >>> ei=nx.estrada_index(G)
+ >>> G = nx.Graph(
+ ... [
+ ... (0, 1),
+ ... (1, 2),
+ ... (1, 5),
+ ... (5, 4),
+ ... (2, 4),
+ ... (2, 3),
+ ... (4, 3),
+ ... (3, 6),
+ ... ]
+ ... )
+ >>> G = nx.Graph([(0,1),(1,2),(1,5),(5,4),(2,4),(2,3),(4,3),(3,6)])
+ >>> ei = nx.estrada_index(G)
+ >>> print(f"{ei:0.5}")
+ 20.55
"""
return sum(subgraph_centrality(G).values())
diff --git a/networkx/algorithms/link_analysis/hits_alg.py b/networkx/algorithms/link_analysis/hits_alg.py
index 56dbf1a2..42b5856d 100644
--- a/networkx/algorithms/link_analysis/hits_alg.py
+++ b/networkx/algorithms/link_analysis/hits_alg.py
@@ -2,7 +2,7 @@
"""
import networkx as nx
-__all__ = ['hits', 'hits_numpy', 'hits_scipy', 'authority_matrix', 'hub_matrix']
+__all__ = ["hits", "hits_numpy", "hits_scipy", "authority_matrix", "hub_matrix"]
def hits(G, max_iter=100, tol=1.0e-8, nstart=None, normalized=True):
@@ -44,8 +44,8 @@ def hits(G, max_iter=100, tol=1.0e-8, nstart=None, normalized=True):
Examples
--------
- >>> G=nx.path_graph(4)
- >>> h,a=nx.hits(G)
+ >>> G = nx.path_graph(4)
+ >>> h, a = nx.hits(G)
Notes
-----
@@ -90,11 +90,11 @@ def hits(G, max_iter=100, tol=1.0e-8, nstart=None, normalized=True):
# doing a left multiply a^T=hlast^T*G
for n in h:
for nbr in G[n]:
- a[nbr] += hlast[n] * G[n][nbr].get('weight', 1)
+ a[nbr] += hlast[n] * G[n][nbr].get("weight", 1)
# now multiply h=Ga
for n in h:
for nbr in G[n]:
- h[n] += a[nbr] * G[n][nbr].get('weight', 1)
+ h[n] += a[nbr] * G[n][nbr].get("weight", 1)
# normalize vector
s = 1.0 / max(h.values())
for n in h:
@@ -154,8 +154,8 @@ def hits_numpy(G, normalized=True):
Examples
--------
- >>> G=nx.path_graph(4)
- >>> h,a=nx.hits(G)
+ >>> G = nx.path_graph(4)
+ >>> h, a = nx.hits(G)
Notes
-----
@@ -179,8 +179,7 @@ def hits_numpy(G, normalized=True):
try:
import numpy as np
except ImportError:
- raise ImportError(
- "hits_numpy() requires NumPy: http://scipy.org/")
+ raise ImportError("hits_numpy() requires NumPy: http://scipy.org/")
if len(G) == 0:
return {}, {}
H = nx.hub_matrix(G, list(G))
@@ -234,8 +233,8 @@ def hits_scipy(G, max_iter=100, tol=1.0e-6, normalized=True):
Examples
--------
- >>> G=nx.path_graph(4)
- >>> h,a=nx.hits(G)
+ >>> G = nx.path_graph(4)
+ >>> h, a = nx.hits(G)
Notes
-----
@@ -272,14 +271,13 @@ def hits_scipy(G, max_iter=100, tol=1.0e-6, normalized=True):
import scipy.sparse
import numpy as np
except ImportError:
- raise ImportError(
- "hits_scipy() requires SciPy: http://scipy.org/")
+ raise ImportError("hits_scipy() requires SciPy: http://scipy.org/")
if len(G) == 0:
return {}, {}
M = nx.to_scipy_sparse_matrix(G, nodelist=list(G))
(n, m) = M.shape # should be square
A = M.T * M # authority matrix
- x = scipy.ones((n, 1)) / n # initial guess
+ x = np.ones((n, 1)) / n # initial guess
# power iteration on authority matrix
i = 0
while True:
@@ -287,7 +285,7 @@ def hits_scipy(G, max_iter=100, tol=1.0e-6, normalized=True):
x = A * x
x = x / x.max()
# check convergence, l1 norm
- err = scipy.absolute(x - xlast).sum()
+ err = np.absolute(x - xlast).sum()
if err < tol:
break
if i > max_iter:
diff --git a/networkx/algorithms/link_analysis/pagerank_alg.py b/networkx/algorithms/link_analysis/pagerank_alg.py
index 01eab2c5..e6815dfc 100644
--- a/networkx/algorithms/link_analysis/pagerank_alg.py
+++ b/networkx/algorithms/link_analysis/pagerank_alg.py
@@ -412,6 +412,7 @@ def pagerank_scipy(G, alpha=0.85, personalization=None,
The PageRank citation ranking: Bringing order to the Web. 1999
http://dbpubs.stanford.edu:8090/pub/showDoc.Fulltext?lang=en&doc=1999-66&format=pdf
"""
+ import numpy as np
import scipy.sparse
N = len(G)
@@ -421,23 +422,23 @@ def pagerank_scipy(G, alpha=0.85, personalization=None,
nodelist = list(G)
M = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight,
dtype=float)
- S = scipy.array(M.sum(axis=1)).flatten()
+ S = np.array(M.sum(axis=1)).flatten()
S[S != 0] = 1.0 / S[S != 0]
Q = scipy.sparse.spdiags(S.T, 0, *M.shape, format='csr')
M = Q * M
# initial vector
if nstart is None:
- x = scipy.repeat(1.0 / N, N)
+ x = np.repeat(1.0 / N, N)
else:
- x = scipy.array([nstart.get(n, 0) for n in nodelist], dtype=float)
+ x = np.array([nstart.get(n, 0) for n in nodelist], dtype=float)
x = x / x.sum()
# Personalization vector
if personalization is None:
- p = scipy.repeat(1.0 / N, N)
+ p = np.repeat(1.0 / N, N)
else:
- p = scipy.array([personalization.get(n, 0) for n in nodelist], dtype=float)
+ p = np.array([personalization.get(n, 0) for n in nodelist], dtype=float)
p = p / p.sum()
# Dangling nodes
@@ -445,10 +446,10 @@ def pagerank_scipy(G, alpha=0.85, personalization=None,
dangling_weights = p
else:
# Convert the dangling dictionary into an array in nodelist order
- dangling_weights = scipy.array([dangling.get(n, 0) for n in nodelist],
- dtype=float)
+ dangling_weights = np.array([dangling.get(n, 0) for n in nodelist],
+ dtype=float)
dangling_weights /= dangling_weights.sum()
- is_dangling = scipy.where(S == 0)[0]
+ is_dangling = np.where(S == 0)[0]
# power iteration: make up to max_iter iterations
for _ in range(max_iter):
@@ -456,7 +457,7 @@ def pagerank_scipy(G, alpha=0.85, personalization=None,
x = alpha * (x * M + sum(x[is_dangling]) * dangling_weights) + \
(1 - alpha) * p
# check convergence, l1 norm
- err = scipy.absolute(x - xlast).sum()
+ err = np.absolute(x - xlast).sum()
if err < N * tol:
return dict(zip(nodelist, map(float, x)))
raise nx.PowerIterationFailedConvergence(max_iter)
diff --git a/networkx/convert.py b/networkx/convert.py
index cfd16ba4..344ef22a 100644
--- a/networkx/convert.py
+++ b/networkx/convert.py
@@ -18,10 +18,15 @@ nx_agraph, nx_pydot
import warnings
import networkx as nx
-__all__ = ['to_networkx_graph',
- 'from_dict_of_dicts', 'to_dict_of_dicts',
- 'from_dict_of_lists', 'to_dict_of_lists',
- 'from_edgelist', 'to_edgelist']
+__all__ = [
+ "to_networkx_graph",
+ "from_dict_of_dicts",
+ "to_dict_of_dicts",
+ "from_dict_of_lists",
+ "to_dict_of_lists",
+ "from_edgelist",
+ "to_edgelist",
+]
def to_networkx_graph(data, create_using=None, multigraph_input=False):
@@ -65,12 +70,14 @@ def to_networkx_graph(data, create_using=None, multigraph_input=False):
# NX graph
if hasattr(data, "adj"):
try:
- result = from_dict_of_dicts(data.adj,
- create_using=create_using,
- multigraph_input=data.is_multigraph())
- if hasattr(data, 'graph'): # data.graph should be dict-like
+ result = from_dict_of_dicts(
+ data.adj,
+ create_using=create_using,
+ multigraph_input=data.is_multigraph(),
+ )
+ if hasattr(data, "graph"): # data.graph should be dict-like
result.graph.update(data.graph)
- if hasattr(data, 'nodes'): # data.nodes should be dict-like
+ if hasattr(data, "nodes"): # data.nodes should be dict-like
# result.add_node_from(data.nodes.items()) possible but
# for custom node_attr_dict_factory which may be hashable
# will be unexpected behavior
@@ -90,8 +97,9 @@ def to_networkx_graph(data, create_using=None, multigraph_input=False):
# dict of dicts/lists
if isinstance(data, dict):
try:
- return from_dict_of_dicts(data, create_using=create_using,
- multigraph_input=multigraph_input)
+ return from_dict_of_dicts(
+ data, create_using=create_using, multigraph_input=multigraph_input
+ )
except:
try:
return from_dict_of_lists(data, create_using=create_using)
@@ -100,8 +108,9 @@ def to_networkx_graph(data, create_using=None, multigraph_input=False):
# list or generator of edges
- if (isinstance(data, (list, tuple)) or
- any(hasattr(data, attr) for attr in ['_adjdict', 'next', '__next__'])):
+ if isinstance(data, (list, tuple)) or any(
+ hasattr(data, attr) for attr in ["_adjdict", "next", "__next__"]
+ ):
try:
return from_edgelist(data, create_using=create_using)
except:
@@ -110,6 +119,7 @@ def to_networkx_graph(data, create_using=None, multigraph_input=False):
# Pandas DataFrame
try:
import pandas as pd
+
if isinstance(data, pd.DataFrame):
if data.shape[0] == data.shape[1]:
try:
@@ -119,42 +129,43 @@ def to_networkx_graph(data, create_using=None, multigraph_input=False):
raise nx.NetworkXError(msg)
else:
try:
- return nx.from_pandas_edgelist(data, edge_attr=True, create_using=create_using)
+ return nx.from_pandas_edgelist(
+ data, edge_attr=True, create_using=create_using
+ )
except:
msg = "Input is not a correct Pandas DataFrame edge-list."
raise nx.NetworkXError(msg)
except ImportError:
- msg = 'pandas not found, skipping conversion test.'
+ msg = "pandas not found, skipping conversion test."
warnings.warn(msg, ImportWarning)
# numpy matrix or ndarray
try:
import numpy
+
if isinstance(data, (numpy.matrix, numpy.ndarray)):
try:
return nx.from_numpy_matrix(data, create_using=create_using)
except:
- raise nx.NetworkXError(
- "Input is not a correct numpy matrix or array.")
+ raise nx.NetworkXError("Input is not a correct numpy matrix or array.")
except ImportError:
- warnings.warn('numpy not found, skipping conversion test.',
- ImportWarning)
+ warnings.warn("numpy not found, skipping conversion test.", ImportWarning)
# scipy sparse matrix - any format
try:
import scipy
+
if hasattr(data, "format"):
try:
return nx.from_scipy_sparse_matrix(data, create_using=create_using)
except:
raise nx.NetworkXError(
- "Input is not a correct scipy sparse matrix type.")
+ "Input is not a correct scipy sparse matrix type."
+ )
except ImportError:
- warnings.warn('scipy not found, skipping conversion test.',
- ImportWarning)
+ warnings.warn("scipy not found, skipping conversion test.", ImportWarning)
- raise nx.NetworkXError(
- "Input is not a known data type for conversion.")
+ raise nx.NetworkXError("Input is not a known data type for conversion.")
def to_dict_of_lists(G, nodelist=None):
@@ -216,8 +227,9 @@ def from_dict_of_lists(d, create_using=None):
G.add_edge(node, nbr)
seen[node] = 1 # don't allow reverse edge to show up
else:
- G.add_edges_from(((node, nbr) for node, nbrlist in d.items()
- for nbr in nbrlist))
+ G.add_edges_from(
+ ((node, nbr) for node, nbrlist in d.items() for nbr in nbrlist)
+ )
return G
@@ -294,31 +306,37 @@ def from_dict_of_dicts(d, create_using=None, multigraph_input=False):
# make a copy of the list of edge data (but not the edge data)
if G.is_directed():
if G.is_multigraph():
- G.add_edges_from((u, v, key, data)
- for u, nbrs in d.items()
- for v, datadict in nbrs.items()
- for key, data in datadict.items())
+ G.add_edges_from(
+ (u, v, key, data)
+ for u, nbrs in d.items()
+ for v, datadict in nbrs.items()
+ for key, data in datadict.items()
+ )
else:
- G.add_edges_from((u, v, data)
- for u, nbrs in d.items()
- for v, datadict in nbrs.items()
- for key, data in datadict.items())
+ G.add_edges_from(
+ (u, v, data)
+ for u, nbrs in d.items()
+ for v, datadict in nbrs.items()
+ for key, data in datadict.items()
+ )
else: # Undirected
if G.is_multigraph():
- seen = set() # don't add both directions of undirected graph
+ seen = set() # don't add both directions of undirected graph
for u, nbrs in d.items():
for v, datadict in nbrs.items():
if (u, v) not in seen:
- G.add_edges_from((u, v, key, data)
- for key, data in datadict.items())
+ G.add_edges_from(
+ (u, v, key, data) for key, data in datadict.items()
+ )
seen.add((v, u))
else:
- seen = set() # don't add both directions of undirected graph
+ seen = set() # don't add both directions of undirected graph
for u, nbrs in d.items():
for v, datadict in nbrs.items():
if (u, v) not in seen:
- G.add_edges_from((u, v, data)
- for key, data in datadict.items())
+ G.add_edges_from(
+ (u, v, data) for key, data in datadict.items()
+ )
seen.add((v, u))
else: # not a multigraph to multigraph transfer
@@ -334,9 +352,9 @@ def from_dict_of_dicts(d, create_using=None, multigraph_input=False):
G[u][v][0].update(data)
seen.add((v, u))
else:
- G.add_edges_from(((u, v, data)
- for u, nbrs in d.items()
- for v, data in nbrs.items()))
+ G.add_edges_from(
+ ((u, v, data) for u, nbrs in d.items() for v, data in nbrs.items())
+ )
return G
diff --git a/networkx/convert_matrix.py b/networkx/convert_matrix.py
index 0746af7c..4a3dacb7 100644
--- a/networkx/convert_matrix.py
+++ b/networkx/convert_matrix.py
@@ -25,16 +25,30 @@ import itertools
import networkx as nx
from networkx.utils import not_implemented_for
-__all__ = ['from_numpy_matrix', 'to_numpy_matrix',
- 'from_pandas_adjacency', 'to_pandas_adjacency',
- 'from_pandas_edgelist', 'to_pandas_edgelist',
- 'to_numpy_recarray',
- 'from_scipy_sparse_matrix', 'to_scipy_sparse_matrix',
- 'from_numpy_array', 'to_numpy_array']
-
-
-def to_pandas_adjacency(G, nodelist=None, dtype=None, order=None,
- multigraph_weight=sum, weight='weight', nonedge=0.0):
+__all__ = [
+ "from_numpy_matrix",
+ "to_numpy_matrix",
+ "from_pandas_adjacency",
+ "to_pandas_adjacency",
+ "from_pandas_edgelist",
+ "to_pandas_edgelist",
+ "to_numpy_recarray",
+ "from_scipy_sparse_matrix",
+ "to_scipy_sparse_matrix",
+ "from_numpy_array",
+ "to_numpy_array",
+]
+
+
+def to_pandas_adjacency(
+ G,
+ nodelist=None,
+ dtype=None,
+ order=None,
+ multigraph_weight=sum,
+ weight="weight",
+ nonedge=0.0,
+):
"""Returns the graph adjacency matrix as a Pandas DataFrame.
Parameters
@@ -117,9 +131,16 @@ def to_pandas_adjacency(G, nodelist=None, dtype=None, order=None,
"""
import pandas as pd
- M = to_numpy_array(G, nodelist=nodelist, dtype=dtype, order=order,
- multigraph_weight=multigraph_weight, weight=weight,
- nonedge=nonedge)
+
+ M = to_numpy_array(
+ G,
+ nodelist=nodelist,
+ dtype=dtype,
+ order=order,
+ multigraph_weight=multigraph_weight,
+ weight=weight,
+ nonedge=nonedge,
+ )
if nodelist is None:
nodelist = list(G)
return pd.DataFrame(data=M, index=nodelist, columns=nodelist)
@@ -190,8 +211,9 @@ def from_pandas_adjacency(df, create_using=None):
return G
-def to_pandas_edgelist(G, source='source', target='target', nodelist=None,
- dtype=None, order=None):
+def to_pandas_edgelist(
+ G, source="source", target="target", nodelist=None, dtype=None, order=None
+):
"""Returns the graph edge list as a Pandas DataFrame.
Parameters
@@ -227,6 +249,7 @@ def to_pandas_edgelist(G, source='source', target='target', nodelist=None,
"""
import pandas as pd
+
if nodelist is None:
edgelist = G.edges(data=True)
else:
@@ -234,15 +257,15 @@ def to_pandas_edgelist(G, source='source', target='target', nodelist=None,
source_nodes = [s for s, t, d in edgelist]
target_nodes = [t for s, t, d in edgelist]
all_keys = set().union(*(d.keys() for s, t, d in edgelist))
- edge_attr = {k: [d.get(k, float("nan")) for s, t, d in edgelist]
- for k in all_keys}
+ edge_attr = {k: [d.get(k, float("nan")) for s, t, d in edgelist] for k in all_keys}
edgelistdict = {source: source_nodes, target: target_nodes}
edgelistdict.update(edge_attr)
return pd.DataFrame(edgelistdict)
-def from_pandas_edgelist(df, source='source', target='target', edge_attr=None,
- create_using=None):
+def from_pandas_edgelist(
+ df, source="source", target="target", edge_attr=None, create_using=None
+):
"""Returns a graph from Pandas DataFrame containing an edge list.
The Pandas DataFrame should contain at least two columns of node names and
@@ -347,8 +370,15 @@ def from_pandas_edgelist(df, source='source', target='target', edge_attr=None,
return g
-def to_numpy_matrix(G, nodelist=None, dtype=None, order=None,
- multigraph_weight=sum, weight='weight', nonedge=0.0):
+def to_numpy_matrix(
+ G,
+ nodelist=None,
+ dtype=None,
+ order=None,
+ multigraph_weight=sum,
+ weight="weight",
+ nonedge=0.0,
+):
"""Returns the graph adjacency matrix as a NumPy matrix.
Parameters
@@ -442,9 +472,15 @@ def to_numpy_matrix(G, nodelist=None, dtype=None, order=None,
"""
import numpy as np
- A = to_numpy_array(G, nodelist=nodelist, dtype=dtype, order=order,
- multigraph_weight=multigraph_weight, weight=weight,
- nonedge=nonedge)
+ A = to_numpy_array(
+ G,
+ nodelist=nodelist,
+ dtype=dtype,
+ order=order,
+ multigraph_weight=multigraph_weight,
+ weight=weight,
+ nonedge=nonedge,
+ )
M = np.asmatrix(A, dtype=dtype)
return M
@@ -536,18 +572,21 @@ def from_numpy_matrix(A, parallel_edges=False, create_using=None):
"""
# This should never fail if you have created a numpy matrix with numpy...
import numpy as np
- kind_to_python_type = {'f': float,
- 'i': int,
- 'u': int,
- 'b': bool,
- 'c': complex,
- 'S': str,
- 'V': 'void'}
- kind_to_python_type['U'] = str
+
+ kind_to_python_type = {
+ "f": float,
+ "i": int,
+ "u": int,
+ "b": bool,
+ "c": complex,
+ "S": str,
+ "V": "void",
+ }
+ kind_to_python_type["U"] = str
G = nx.empty_graph(0, create_using)
n, m = A.shape
if n != m:
- raise nx.NetworkXError('Adjacency matrix is not square.', f"nx,ny={A.shape}")
+ raise nx.NetworkXError("Adjacency matrix is not square.", f"nx,ny={A.shape}")
dt = A.dtype
try:
python_type = kind_to_python_type[dt.kind]
@@ -558,16 +597,24 @@ def from_numpy_matrix(A, parallel_edges=False, create_using=None):
G.add_nodes_from(range(n))
# Get a list of all the entries in the matrix with nonzero entries. These
# coordinates will become the edges in the graph.
- edges = map(lambda e: (int(e[0]), int(e[1])),
- zip(*(np.asarray(A).nonzero())))
+ edges = map(lambda e: (int(e[0]), int(e[1])), zip(*(np.asarray(A).nonzero())))
# handle numpy constructed data type
- if python_type == 'void':
+ if python_type == "void":
# Sort the fields by their offset, then by dtype, then by name.
- fields = sorted((offset, dtype, name) for name, (dtype, offset) in
- A.dtype.fields.items())
- triples = ((u, v, {name: kind_to_python_type[dtype.kind](val)
- for (_, dtype, name), val in zip(fields, A[u, v])})
- for u, v in edges)
+ fields = sorted(
+ (offset, dtype, name) for name, (dtype, offset) in A.dtype.fields.items()
+ )
+ triples = (
+ (
+ u,
+ v,
+ {
+ name: kind_to_python_type[dtype.kind](val)
+ for (_, dtype, name), val in zip(fields, A[u, v])
+ },
+ )
+ for u, v in edges
+ )
# If the entries in the adjacency matrix are integers, the graph is a
# multigraph, and parallel_edges is True, then create parallel edges, each
# with weight 1, for each entry in the adjacency matrix. Otherwise, create
@@ -581,11 +628,11 @@ def from_numpy_matrix(A, parallel_edges=False, create_using=None):
# for d in range(A[u, v]):
# G.add_edge(u, v, weight=1)
#
- triples = chain(((u, v, dict(weight=1)) for d in range(A[u, v]))
- for (u, v) in edges)
+ triples = chain(
+ ((u, v, dict(weight=1)) for d in range(A[u, v])) for (u, v) in edges
+ )
else: # basic data type
- triples = ((u, v, dict(weight=python_type(A[u, v])))
- for u, v in edges)
+ triples = ((u, v, dict(weight=python_type(A[u, v]))) for u, v in edges)
# If we are creating an undirected multigraph, only add the edges from the
# upper triangle of the matrix. Otherwise, add all the edges. This relies
# on the fact that the vertices created in the
@@ -600,7 +647,7 @@ def from_numpy_matrix(A, parallel_edges=False, create_using=None):
return G
-@not_implemented_for('multigraph')
+@not_implemented_for("multigraph")
def to_numpy_recarray(G, nodelist=None, dtype=None, order=None):
"""Returns the graph adjacency matrix as a NumPy recarray.
@@ -647,8 +694,9 @@ def to_numpy_recarray(G, nodelist=None, dtype=None, order=None):
"""
if dtype is None:
- dtype = [('weight', float)]
+ dtype = [("weight", float)]
import numpy as np
+
if nodelist is None:
nodelist = list(G)
nodeset = set(nodelist)
@@ -672,8 +720,7 @@ def to_numpy_recarray(G, nodelist=None, dtype=None, order=None):
return M.view(np.recarray)
-def to_scipy_sparse_matrix(G, nodelist=None, dtype=None,
- weight='weight', format='csr'):
+def to_scipy_sparse_matrix(G, nodelist=None, dtype=None, weight="weight", format="csr"):
"""Returns the graph adjacency matrix as a SciPy sparse matrix.
Parameters
@@ -757,6 +804,7 @@ def to_scipy_sparse_matrix(G, nodelist=None, dtype=None,
https://docs.scipy.org/doc/scipy/reference/sparse.html
"""
from scipy import sparse
+
if nodelist is None:
nodelist = list(G)
nlen = len(nodelist)
@@ -768,9 +816,13 @@ def to_scipy_sparse_matrix(G, nodelist=None, dtype=None,
raise nx.NetworkXError(msg)
index = dict(zip(nodelist, range(nlen)))
- coefficients = zip(*((index[u], index[v], d.get(weight, 1))
- for u, v, d in G.edges(nodelist, data=True)
- if u in index and v in index))
+ coefficients = zip(
+ *(
+ (index[u], index[v], d.get(weight, 1))
+ for u, v, d in G.edges(nodelist, data=True)
+ if u in index and v in index
+ )
+ )
try:
row, col, data = coefficients
except ValueError:
@@ -778,8 +830,7 @@ def to_scipy_sparse_matrix(G, nodelist=None, dtype=None,
row, col, data = [], [], []
if G.is_directed():
- M = sparse.coo_matrix((data, (row, col)),
- shape=(nlen, nlen), dtype=dtype)
+ M = sparse.coo_matrix((data, (row, col)), shape=(nlen, nlen), dtype=dtype)
else:
# symmetrize matrix
d = data + data
@@ -789,9 +840,13 @@ def to_scipy_sparse_matrix(G, nodelist=None, dtype=None,
# so we subtract the data on the diagonal
selfloops = list(nx.selfloop_edges(G, data=True))
if selfloops:
- diag_index, diag_data = zip(*((index[u], -d.get(weight, 1))
- for u, v, d in selfloops
- if u in index and v in index))
+ diag_index, diag_data = zip(
+ *(
+ (index[u], -d.get(weight, 1))
+ for u, v, d in selfloops
+ if u in index and v in index
+ )
+ )
d += diag_data
r += diag_index
c += diag_index
@@ -853,18 +908,19 @@ def _generate_weighted_edges(A):
`A` is a SciPy sparse matrix (in any format).
"""
- if A.format == 'csr':
+ if A.format == "csr":
return _csr_gen_triples(A)
- if A.format == 'csc':
+ if A.format == "csc":
return _csc_gen_triples(A)
- if A.format == 'dok':
+ if A.format == "dok":
return _dok_gen_triples(A)
# If A is in any other format (including COO), convert it to COO format.
return _coo_gen_triples(A.tocoo())
-def from_scipy_sparse_matrix(A, parallel_edges=False, create_using=None,
- edge_attribute='weight'):
+def from_scipy_sparse_matrix(
+ A, parallel_edges=False, create_using=None, edge_attribute="weight"
+):
"""Creates a new graph from an adjacency matrix given as a SciPy sparse
matrix.
@@ -942,7 +998,7 @@ def from_scipy_sparse_matrix(A, parallel_edges=False, create_using=None,
# with weight 1, for each entry in the adjacency matrix. Otherwise, create
# one edge for each positive entry in the adjacency matrix and set the
# weight of that edge to be the entry in the matrix.
- if A.dtype.kind in ('i', 'u') and G.is_multigraph() and parallel_edges:
+ if A.dtype.kind in ("i", "u") and G.is_multigraph() and parallel_edges:
chain = itertools.chain.from_iterable
# The following line is equivalent to:
#
@@ -965,8 +1021,15 @@ def from_scipy_sparse_matrix(A, parallel_edges=False, create_using=None,
return G
-def to_numpy_array(G, nodelist=None, dtype=None, order=None,
- multigraph_weight=sum, weight='weight', nonedge=0.0):
+def to_numpy_array(
+ G,
+ nodelist=None,
+ dtype=None,
+ order=None,
+ multigraph_weight=sum,
+ weight="weight",
+ nonedge=0.0,
+):
"""Returns the graph adjacency matrix as a NumPy array.
Parameters
@@ -1111,7 +1174,7 @@ def to_numpy_array(G, nodelist=None, dtype=None, order=None,
try:
op = operator[multigraph_weight]
except Exception:
- raise ValueError('multigraph_weight must be sum, min, or max')
+ raise ValueError("multigraph_weight must be sum, min, or max")
for u, v, attrs in G.edges(data=True):
if (u in nodeset) and (v in nodeset):
@@ -1225,5 +1288,6 @@ def from_numpy_array(A, parallel_edges=False, create_using=None):
1.0
"""
- return from_numpy_matrix(A, parallel_edges=parallel_edges,
- create_using=create_using)
+ return from_numpy_matrix(
+ A, parallel_edges=parallel_edges, create_using=create_using
+ )
diff --git a/networkx/exception.py b/networkx/exception.py
index e32574e1..96694cc3 100644
--- a/networkx/exception.py
+++ b/networkx/exception.py
@@ -7,20 +7,20 @@ Base exceptions and errors for NetworkX.
"""
__all__ = [
- 'HasACycle',
- 'NodeNotFound',
- 'PowerIterationFailedConvergence',
- 'ExceededMaxIterations',
- 'AmbiguousSolution',
- 'NetworkXAlgorithmError',
- 'NetworkXException',
- 'NetworkXError',
- 'NetworkXNoCycle',
- 'NetworkXNoPath',
- 'NetworkXNotImplemented',
- 'NetworkXPointlessConcept',
- 'NetworkXUnbounded',
- 'NetworkXUnfeasible',
+ "HasACycle",
+ "NodeNotFound",
+ "PowerIterationFailedConvergence",
+ "ExceededMaxIterations",
+ "AmbiguousSolution",
+ "NetworkXAlgorithmError",
+ "NetworkXException",
+ "NetworkXError",
+ "NetworkXNoCycle",
+ "NetworkXNoPath",
+ "NetworkXNotImplemented",
+ "NetworkXPointlessConcept",
+ "NetworkXUnbounded",
+ "NetworkXUnfeasible",
]
diff --git a/networkx/linalg/algebraicconnectivity.py b/networkx/linalg/algebraicconnectivity.py
index 96552d8e..40311398 100644
--- a/networkx/linalg/algebraicconnectivity.py
+++ b/networkx/linalg/algebraicconnectivity.py
@@ -13,7 +13,8 @@ try:
from scipy.linalg import eigh, inv
from scipy.sparse import csc_matrix, spdiags
from scipy.sparse.linalg import eigsh, lobpcg
- __all__ = ['algebraic_connectivity', 'fiedler_vector', 'spectral_ordering']
+
+ __all__ = ["algebraic_connectivity", "fiedler_vector", "spectral_ordering"]
except ImportError:
__all__ = []
@@ -53,7 +54,7 @@ class _PCGSolver:
def solve(self, B, tol):
B = asarray(B)
- X = ndarray(B.shape, order='F')
+ X = ndarray(B.shape, order="F")
for j in range(B.shape[1]):
X[:, j] = self._solve(B[:, j], tol)
return X
@@ -95,7 +96,7 @@ class _CholeskySolver:
def __init__(self, A):
if not self._cholesky:
- raise nx.NetworkXError('Cholesky solver unavailable.')
+ raise nx.NetworkXError("Cholesky solver unavailable.")
self._chol = self._cholesky(A)
def solve(self, B, tol=None):
@@ -103,6 +104,7 @@ class _CholeskySolver:
try:
from scikits.sparse.cholmod import cholesky
+
_cholesky = cholesky
except ImportError:
_cholesky = None
@@ -121,20 +123,25 @@ class _LUSolver:
def __init__(self, A):
if not self._splu:
- raise nx.NetworkXError('LU solver unavailable.')
+ raise nx.NetworkXError("LU solver unavailable.")
self._LU = self._splu(A)
def solve(self, B, tol=None):
B = asarray(B)
- X = ndarray(B.shape, order='F')
+ X = ndarray(B.shape, order="F")
for j in range(B.shape[1]):
X[:, j] = self._LU.solve(B[:, j])
return X
try:
from scipy.sparse.linalg import splu
- _splu = partial(splu, permc_spec='MMD_AT_PLUS_A', diag_pivot_thresh=0.,
- options={'Equil': True, 'SymmetricMode': True})
+
+ _splu = partial(
+ splu,
+ permc_spec="MMD_AT_PLUS_A",
+ diag_pivot_thresh=0.0,
+ options={"Equil": True, "SymmetricMode": True},
+ )
except ImportError:
_splu = None
@@ -145,16 +152,21 @@ def _preprocess_graph(G, weight):
if G.is_directed():
H = nx.MultiGraph()
H.add_nodes_from(G)
- H.add_weighted_edges_from(((u, v, e.get(weight, 1.))
- for u, v, e in G.edges(data=True)
- if u != v), weight=weight)
+ H.add_weighted_edges_from(
+ ((u, v, e.get(weight, 1.0)) for u, v, e in G.edges(data=True) if u != v),
+ weight=weight,
+ )
G = H
if not G.is_multigraph():
- edges = ((u, v, abs(e.get(weight, 1.)))
- for u, v, e in G.edges(data=True) if u != v)
+ edges = (
+ (u, v, abs(e.get(weight, 1.0))) for u, v, e in G.edges(data=True) if u != v
+ )
else:
- edges = ((u, v, sum(abs(e.get(weight, 1.)) for e in G[u][v].values()))
- for u, v in G.edges() if u != v)
+ edges = (
+ (u, v, sum(abs(e.get(weight, 1.0)) for e in G[u][v].values()))
+ for u, v in G.edges()
+ if u != v
+ )
H = nx.Graph()
H.add_nodes_from(G)
H.add_weighted_edges_from((u, v, e) for u, v, e in edges if e != 0)
@@ -171,7 +183,7 @@ def _rcm_estimate(G, nodelist):
x = ndarray(n, dtype=float)
for i, u in enumerate(order):
x[index[u]] = i
- x -= (n - 1) / 2.
+ x -= (n - 1) / 2.0
return x
@@ -215,18 +227,21 @@ def _tracemin_fiedler(L, X, normalized, tol, method):
# Form the normalized Laplacian matrix and determine the eigenvector of
# its nullspace.
e = sqrt(L.diagonal())
- D = spdiags(1. / e, [0], n, n, format='csr')
+ D = spdiags(1.0 / e, [0], n, n, format="csr")
L = D * L * D
- e *= 1. / norm(e, 2)
+ e *= 1.0 / norm(e, 2)
if normalized:
+
def project(X):
"""Make X orthogonal to the nullspace of L.
"""
X = asarray(X)
for j in range(X.shape[1]):
X[:, j] -= dot(X[:, j], e) * e
+
else:
+
def project(X):
"""Make X orthogonal to the nullspace of L.
"""
@@ -234,10 +249,10 @@ def _tracemin_fiedler(L, X, normalized, tol, method):
for j in range(X.shape[1]):
X[:, j] -= X[:, j].sum() / n
- if method == 'tracemin_pcg':
+ if method == "tracemin_pcg":
D = L.diagonal().astype(float)
solver = _PCGSolver(lambda x: L * x, lambda x: D * x)
- elif method == 'tracemin_chol' or method == 'tracemin_lu':
+ elif method == "tracemin_chol" or method == "tracemin_lu":
# Convert A to CSC to suppress SparseEfficiencyWarning.
A = csc_matrix(L, dtype=float, copy=True)
# Force A to be nonsingular. Since A is the Laplacian matrix of a
@@ -245,18 +260,18 @@ def _tracemin_fiedler(L, X, normalized, tol, method):
# element needs to modified. Changing to infinity forces a zero in the
# corresponding element in the solution.
i = (A.indptr[1:] - A.indptr[:-1]).argmax()
- A[i, i] = float('inf')
- if method == 'tracemin_chol':
+ A[i, i] = float("inf")
+ if method == "tracemin_chol":
solver = _CholeskySolver(A)
else:
solver = _LUSolver(A)
else:
- raise nx.NetworkXError('Unknown linear system solver: ' + method)
+ raise nx.NetworkXError("Unknown linear system solver: " + method)
# Initialize.
Lnorm = abs(L).sum(axis=1).flatten().max()
project(X)
- W = asmatrix(ndarray(X.shape, order='F'))
+ W = asmatrix(ndarray(X.shape, order="F"))
while True:
# Orthonormalize X.
@@ -287,34 +302,38 @@ def _get_fiedler_func(method):
if method == "tracemin": # old style keyword <v2.1
method = "tracemin_pcg"
if method in ("tracemin_pcg", "tracemin_chol", "tracemin_lu"):
+
def find_fiedler(L, x, normalized, tol, seed):
- q = 1 if method == 'tracemin_pcg' else min(4, L.shape[0] - 1)
+ q = 1 if method == "tracemin_pcg" else min(4, L.shape[0] - 1)
X = asmatrix(seed.normal(size=(q, L.shape[0]))).T
sigma, X = _tracemin_fiedler(L, X, normalized, tol, method)
return sigma[0], X[:, 0]
- elif method == 'lanczos' or method == 'lobpcg':
+
+ elif method == "lanczos" or method == "lobpcg":
+
def find_fiedler(L, x, normalized, tol, seed):
L = csc_matrix(L, dtype=float)
n = L.shape[0]
if normalized:
- D = spdiags(1. / sqrt(L.diagonal()), [0], n, n, format='csc')
+ D = spdiags(1.0 / sqrt(L.diagonal()), [0], n, n, format="csc")
L = D * L * D
- if method == 'lanczos' or n < 10:
+ if method == "lanczos" or n < 10:
# Avoid LOBPCG when n < 10 due to
# https://github.com/scipy/scipy/issues/3592
# https://github.com/scipy/scipy/pull/3594
- sigma, X = eigsh(L, 2, which='SM', tol=tol,
- return_eigenvectors=True)
+ sigma, X = eigsh(L, 2, which="SM", tol=tol, return_eigenvectors=True)
return sigma[1], X[:, 1]
else:
X = asarray(asmatrix(x).T)
- M = spdiags(1. / L.diagonal(), [0], n, n)
+ M = spdiags(1.0 / L.diagonal(), [0], n, n)
Y = ones(n)
if normalized:
Y /= D.diagonal()
- sigma, X = lobpcg(L, X, M=M, Y=asmatrix(Y).T, tol=tol,
- maxiter=n, largest=False)
+ sigma, X = lobpcg(
+ L, X, M=M, Y=asmatrix(Y).T, tol=tol, maxiter=n, largest=False
+ )
return sigma[0], X[:, 0]
+
else:
raise nx.NetworkXError(f"unknown method '{method}'.")
@@ -322,9 +341,10 @@ def _get_fiedler_func(method):
@random_state(5)
-@not_implemented_for('directed')
-def algebraic_connectivity(G, weight='weight', normalized=False, tol=1e-8,
- method='tracemin_pcg', seed=None):
+@not_implemented_for("directed")
+def algebraic_connectivity(
+ G, weight="weight", normalized=False, tol=1e-8, method="tracemin_pcg", seed=None
+):
"""Returns the algebraic connectivity of an undirected graph.
The algebraic connectivity of a connected undirected graph is the second
@@ -391,25 +411,26 @@ def algebraic_connectivity(G, weight='weight', normalized=False, tol=1e-8,
laplacian_matrix
"""
if len(G) < 2:
- raise nx.NetworkXError('graph has less than two nodes.')
+ raise nx.NetworkXError("graph has less than two nodes.")
G = _preprocess_graph(G, weight)
if not nx.is_connected(G):
- return 0.
+ return 0.0
L = nx.laplacian_matrix(G)
if L.shape[0] == 2:
- return 2. * L[0, 0] if not normalized else 2.
+ return 2.0 * L[0, 0] if not normalized else 2.0
find_fiedler = _get_fiedler_func(method)
- x = None if method != 'lobpcg' else _rcm_estimate(G, G)
+ x = None if method != "lobpcg" else _rcm_estimate(G, G)
sigma, fiedler = find_fiedler(L, x, normalized, tol, seed)
return sigma
@random_state(5)
-@not_implemented_for('directed')
-def fiedler_vector(G, weight='weight', normalized=False, tol=1e-8,
- method='tracemin_pcg', seed=None):
+@not_implemented_for("directed")
+def fiedler_vector(
+ G, weight="weight", normalized=False, tol=1e-8, method="tracemin_pcg", seed=None
+):
"""Returns the Fiedler vector of a connected undirected graph.
The Fiedler vector of a connected undirected graph is the eigenvector
@@ -477,24 +498,25 @@ def fiedler_vector(G, weight='weight', normalized=False, tol=1e-8,
laplacian_matrix
"""
if len(G) < 2:
- raise nx.NetworkXError('graph has less than two nodes.')
+ raise nx.NetworkXError("graph has less than two nodes.")
G = _preprocess_graph(G, weight)
if not nx.is_connected(G):
- raise nx.NetworkXError('graph is not connected.')
+ raise nx.NetworkXError("graph is not connected.")
if len(G) == 2:
- return array([1., -1.])
+ return array([1.0, -1.0])
find_fiedler = _get_fiedler_func(method)
L = nx.laplacian_matrix(G)
- x = None if method != 'lobpcg' else _rcm_estimate(G, G)
+ x = None if method != "lobpcg" else _rcm_estimate(G, G)
sigma, fiedler = find_fiedler(L, x, normalized, tol, seed)
return fiedler
@random_state(5)
-def spectral_ordering(G, weight='weight', normalized=False, tol=1e-8,
- method='tracemin_pcg', seed=None):
+def spectral_ordering(
+ G, weight="weight", normalized=False, tol=1e-8, method="tracemin_pcg", seed=None
+):
"""Compute the spectral_ordering of a graph.
The spectral ordering of a graph is an ordering of its nodes where nodes
@@ -559,7 +581,7 @@ def spectral_ordering(G, weight='weight', normalized=False, tol=1e-8,
laplacian_matrix
"""
if len(G) == 0:
- raise nx.NetworkXError('graph is empty.')
+ raise nx.NetworkXError("graph is empty.")
G = _preprocess_graph(G, weight)
find_fiedler = _get_fiedler_func(method)
@@ -568,7 +590,7 @@ def spectral_ordering(G, weight='weight', normalized=False, tol=1e-8,
size = len(component)
if size > 2:
L = nx.laplacian_matrix(G, component)
- x = None if method != 'lobpcg' else _rcm_estimate(G, component)
+ x = None if method != "lobpcg" else _rcm_estimate(G, component)
sigma, fiedler = find_fiedler(L, x, normalized, tol, seed)
sort_info = zip(fiedler, range(size), component)
order.extend(u for x, c, u in sorted(sort_info))
diff --git a/networkx/linalg/attrmatrix.py b/networkx/linalg/attrmatrix.py
index 84521bce..3661bb89 100644
--- a/networkx/linalg/attrmatrix.py
+++ b/networkx/linalg/attrmatrix.py
@@ -2,7 +2,7 @@
Functions for constructing matrix-like objects from graph attributes.
"""
-__all__ = ['attr_matrix', 'attr_sparse_matrix']
+__all__ = ["attr_matrix", "attr_sparse_matrix"]
def _node_value(G, node_attr):
@@ -30,10 +30,15 @@ def _node_value(G, node_attr):
"""
if node_attr is None:
- def value(u): return u
- elif not hasattr(node_attr, '__call__'):
+
+ def value(u):
+ return u
+
+ elif not hasattr(node_attr, "__call__"):
# assume it is a key for the node attribute dictionary
- def value(u): return G.nodes[u][node_attr]
+ def value(u):
+ return G.nodes[u][node_attr]
+
else:
# Advanced: Allow users to specify something else.
#
@@ -80,25 +85,41 @@ def _edge_value(G, edge_attr):
# topological count of edges
if G.is_multigraph():
- def value(u, v): return len(G[u][v])
+
+ def value(u, v):
+ return len(G[u][v])
+
else:
- def value(u, v): return 1
- elif not hasattr(edge_attr, '__call__'):
+ def value(u, v):
+ return 1
+
+ elif not hasattr(edge_attr, "__call__"):
# assume it is a key for the edge attribute dictionary
- if edge_attr == 'weight':
+ if edge_attr == "weight":
# provide a default value
if G.is_multigraph():
- def value(u, v): return sum([d.get(edge_attr, 1) for d in G[u][v].values()])
+
+ def value(u, v):
+ return sum([d.get(edge_attr, 1) for d in G[u][v].values()])
+
else:
- def value(u, v): return G[u][v].get(edge_attr, 1)
+
+ def value(u, v):
+ return G[u][v].get(edge_attr, 1)
+
else:
# otherwise, the edge attribute MUST exist for each edge
if G.is_multigraph():
- def value(u, v): return sum([d[edge_attr] for d in G[u][v].values()])
+
+ def value(u, v):
+ return sum([d[edge_attr] for d in G[u][v].values()])
+
else:
- def value(u, v): return G[u][v][edge_attr]
+
+ def value(u, v):
+ return G[u][v][edge_attr]
else:
# Advanced: Allow users to specify something else.
@@ -120,8 +141,15 @@ def _edge_value(G, edge_attr):
return value
-def attr_matrix(G, edge_attr=None, node_attr=None, normalized=False,
- rc_order=None, dtype=None, order=None):
+def attr_matrix(
+ G,
+ edge_attr=None,
+ node_attr=None,
+ normalized=False,
+ rc_order=None,
+ dtype=None,
+ order=None,
+):
"""Returns a NumPy matrix using attributes from G.
If only `G` is passed in, then the adjacency matrix is constructed.
@@ -242,8 +270,7 @@ def attr_matrix(G, edge_attr=None, node_attr=None, normalized=False,
try:
import numpy as np
except ImportError:
- raise ImportError(
- "attr_matrix() requires numpy: http://scipy.org/ ")
+ raise ImportError("attr_matrix() requires numpy: http://scipy.org/ ")
edge_value = _edge_value(G, edge_attr)
node_value = _node_value(G, node_attr)
@@ -282,8 +309,9 @@ def attr_matrix(G, edge_attr=None, node_attr=None, normalized=False,
return M
-def attr_sparse_matrix(G, edge_attr=None, node_attr=None,
- normalized=False, rc_order=None, dtype=None):
+def attr_sparse_matrix(
+ G, edge_attr=None, node_attr=None, normalized=False, rc_order=None, dtype=None
+):
"""Returns a SciPy sparse matrix using attributes from G.
If only `G` is passed in, then the adjacency matrix is constructed.
@@ -406,8 +434,7 @@ def attr_sparse_matrix(G, edge_attr=None, node_attr=None,
import numpy as np
from scipy import sparse
except ImportError:
- raise ImportError(
- "attr_sparse_matrix() requires scipy: http://scipy.org/ ")
+ raise ImportError("attr_sparse_matrix() requires scipy: http://scipy.org/ ")
edge_value = _edge_value(G, edge_attr)
node_value = _node_value(G, node_attr)
diff --git a/networkx/linalg/bethehessianmatrix.py b/networkx/linalg/bethehessianmatrix.py
index 77c90f71..a772594f 100644
--- a/networkx/linalg/bethehessianmatrix.py
+++ b/networkx/linalg/bethehessianmatrix.py
@@ -2,11 +2,11 @@
import networkx as nx
from networkx.utils import not_implemented_for
-__all__ = ['bethe_hessian_matrix']
+__all__ = ["bethe_hessian_matrix"]
-@not_implemented_for('directed')
-@not_implemented_for('multigraph')
+@not_implemented_for("directed")
+@not_implemented_for("multigraph")
def bethe_hessian_matrix(G, r=None, nodelist=None):
r"""Returns the Bethe Hessian matrix of G.
@@ -63,14 +63,16 @@ def bethe_hessian_matrix(G, r=None, nodelist=None):
arXiv:1507.00827, 2015.
"""
import scipy.sparse
+
if nodelist is None:
nodelist = list(G)
if r is None:
- r = sum([d ** 2 for v, d in nx.degree(G)]) /\
- sum([d for v, d in nx.degree(G)]) - 1
- A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, format='csr')
+ r = (
+ sum([d ** 2 for v, d in nx.degree(G)]) / sum([d for v, d in nx.degree(G)]) - 1
+ )
+ A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, format="csr")
n, m = A.shape
diags = A.sum(axis=1)
- D = scipy.sparse.spdiags(diags.flatten(), [0], m, n, format='csr')
- I = scipy.sparse.eye(m, n, format='csr')
+ D = scipy.sparse.spdiags(diags.flatten(), [0], m, n, format="csr")
+ I = scipy.sparse.eye(m, n, format="csr")
return (r ** 2 - 1) * I - r * A + D
diff --git a/networkx/linalg/graphmatrix.py b/networkx/linalg/graphmatrix.py
index e5e35970..4b4b43d5 100644
--- a/networkx/linalg/graphmatrix.py
+++ b/networkx/linalg/graphmatrix.py
@@ -3,13 +3,10 @@ Adjacency matrix and incidence matrix of graphs.
"""
import networkx as nx
-__all__ = ['incidence_matrix',
- 'adj_matrix', 'adjacency_matrix',
- ]
+__all__ = ["incidence_matrix", "adj_matrix", "adjacency_matrix"]
-def incidence_matrix(G, nodelist=None, edgelist=None,
- oriented=False, weight=None):
+def incidence_matrix(G, nodelist=None, edgelist=None, oriented=False, weight=None):
"""Returns incidence matrix of G.
The incidence matrix assigns each row to a node and each column to an edge.
@@ -60,6 +57,7 @@ def incidence_matrix(G, nodelist=None, edgelist=None,
http://academicearth.org/lectures/network-applications-incidence-matrix
"""
import scipy.sparse
+
if nodelist is None:
nodelist = list(G)
if edgelist is None:
@@ -92,10 +90,10 @@ def incidence_matrix(G, nodelist=None, edgelist=None,
else:
A[ui, ei] = wt
A[vi, ei] = wt
- return A.asformat('csc')
+ return A.asformat("csc")
-def adjacency_matrix(G, nodelist=None, weight='weight'):
+def adjacency_matrix(G, nodelist=None, weight="weight"):
"""Returns adjacency matrix of G.
Parameters
diff --git a/networkx/linalg/laplacianmatrix.py b/networkx/linalg/laplacianmatrix.py
index a05f4cae..b8d28fd6 100644
--- a/networkx/linalg/laplacianmatrix.py
+++ b/networkx/linalg/laplacianmatrix.py
@@ -3,14 +3,16 @@
import networkx as nx
from networkx.utils import not_implemented_for
-__all__ = ['laplacian_matrix',
- 'normalized_laplacian_matrix',
- 'directed_laplacian_matrix',
- 'directed_combinatorial_laplacian_matrix']
+__all__ = [
+ "laplacian_matrix",
+ "normalized_laplacian_matrix",
+ "directed_laplacian_matrix",
+ "directed_combinatorial_laplacian_matrix",
+]
-@not_implemented_for('directed')
-def laplacian_matrix(G, nodelist=None, weight='weight'):
+@not_implemented_for("directed")
+def laplacian_matrix(G, nodelist=None, weight="weight"):
"""Returns the Laplacian matrix of G.
The graph Laplacian is the matrix L = D - A, where
@@ -45,18 +47,18 @@ def laplacian_matrix(G, nodelist=None, weight='weight'):
laplacian_spectrum
"""
import scipy.sparse
+
if nodelist is None:
nodelist = list(G)
- A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight,
- format='csr')
+ A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, format="csr")
n, m = A.shape
diags = A.sum(axis=1)
- D = scipy.sparse.spdiags(diags.flatten(), [0], m, n, format='csr')
+ D = scipy.sparse.spdiags(diags.flatten(), [0], m, n, format="csr")
return D - A
-@not_implemented_for('directed')
-def normalized_laplacian_matrix(G, nodelist=None, weight='weight'):
+@not_implemented_for("directed")
+def normalized_laplacian_matrix(G, nodelist=None, weight="weight"):
r"""Returns the normalized Laplacian matrix of G.
The normalized graph Laplacian is the matrix
@@ -107,31 +109,34 @@ def normalized_laplacian_matrix(G, nodelist=None, weight='weight'):
Laplacian, Electronic Journal of Linear Algebra, Volume 16, pp. 90-98,
March 2007.
"""
+ import numpy as np
import scipy
import scipy.sparse
+
if nodelist is None:
nodelist = list(G)
- A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight,
- format='csr')
+ A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, format="csr")
n, m = A.shape
diags = A.sum(axis=1).flatten()
- D = scipy.sparse.spdiags(diags, [0], m, n, format='csr')
+ D = scipy.sparse.spdiags(diags, [0], m, n, format="csr")
L = D - A
- with scipy.errstate(divide='ignore'):
- diags_sqrt = 1.0 / scipy.sqrt(diags)
- diags_sqrt[scipy.isinf(diags_sqrt)] = 0
- DH = scipy.sparse.spdiags(diags_sqrt, [0], m, n, format='csr')
+ with scipy.errstate(divide="ignore"):
+ diags_sqrt = 1.0 / np.sqrt(diags)
+ diags_sqrt[np.isinf(diags_sqrt)] = 0
+ DH = scipy.sparse.spdiags(diags_sqrt, [0], m, n, format="csr")
return DH.dot(L.dot(DH))
+
###############################################################################
# Code based on
# https://bitbucket.org/bedwards/networkx-community/src/370bd69fc02f/networkx/algorithms/community/
-@not_implemented_for('undirected')
-@not_implemented_for('multigraph')
-def directed_laplacian_matrix(G, nodelist=None, weight='weight',
- walk_type=None, alpha=0.95):
+@not_implemented_for("undirected")
+@not_implemented_for("multigraph")
+def directed_laplacian_matrix(
+ G, nodelist=None, weight="weight", walk_type=None, alpha=0.95
+):
r"""Returns the directed Laplacian matrix of G.
The graph directed Laplacian is the matrix
@@ -187,28 +192,30 @@ def directed_laplacian_matrix(G, nodelist=None, weight='weight',
Laplacians and the Cheeger inequality for directed graphs.
Annals of Combinatorics, 9(1), 2005
"""
- import scipy as sp
+ import numpy as np
from scipy.sparse import spdiags, linalg
- P = _transition_matrix(G, nodelist=nodelist, weight=weight,
- walk_type=walk_type, alpha=alpha)
+ P = _transition_matrix(
+ G, nodelist=nodelist, weight=weight, walk_type=walk_type, alpha=alpha
+ )
n, m = P.shape
evals, evecs = linalg.eigs(P.T, k=1)
v = evecs.flatten().real
p = v / v.sum()
- sqrtp = sp.sqrt(p)
+ sqrtp = np.sqrt(p)
Q = spdiags(sqrtp, [0], n, n) * P * spdiags(1.0 / sqrtp, [0], n, n)
- I = sp.identity(len(G))
+ I = np.identity(len(G))
return I - (Q + Q.T) / 2.0
-@not_implemented_for('undirected')
-@not_implemented_for('multigraph')
-def directed_combinatorial_laplacian_matrix(G, nodelist=None, weight='weight',
- walk_type=None, alpha=0.95):
+@not_implemented_for("undirected")
+@not_implemented_for("multigraph")
+def directed_combinatorial_laplacian_matrix(
+ G, nodelist=None, weight="weight", walk_type=None, alpha=0.95
+):
r"""Return the directed combinatorial Laplacian matrix of G.
The graph directed combinatorial Laplacian is the matrix
@@ -265,8 +272,9 @@ def directed_combinatorial_laplacian_matrix(G, nodelist=None, weight='weight',
"""
from scipy.sparse import spdiags, linalg
- P = _transition_matrix(G, nodelist=nodelist, weight=weight,
- walk_type=walk_type, alpha=alpha)
+ P = _transition_matrix(
+ G, nodelist=nodelist, weight=weight, walk_type=walk_type, alpha=alpha
+ )
n, m = P.shape
@@ -277,11 +285,10 @@ def directed_combinatorial_laplacian_matrix(G, nodelist=None, weight='weight',
Phi = Phi.todense()
- return Phi - (Phi*P + P.T*Phi) / 2.0
+ return Phi - (Phi * P + P.T * Phi) / 2.0
-def _transition_matrix(G, nodelist=None, weight='weight',
- walk_type=None, alpha=0.95):
+def _transition_matrix(G, nodelist=None, weight="weight", walk_type=None, alpha=0.95):
"""Returns the transition matrix of G.
This is a row stochastic giving the transition probabilities while
@@ -319,9 +326,9 @@ def _transition_matrix(G, nodelist=None, weight='weight',
NetworkXError
If walk_type not specified or alpha not in valid range
"""
-
- import scipy as sp
+ import numpy as np
from scipy.sparse import identity, spdiags
+
if walk_type is None:
if nx.is_strongly_connected(G):
if nx.is_aperiodic(G):
@@ -331,11 +338,10 @@ def _transition_matrix(G, nodelist=None, weight='weight',
else:
walk_type = "pagerank"
- M = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight,
- dtype=float)
+ M = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, dtype=float)
n, m = M.shape
if walk_type in ["random", "lazy"]:
- DI = spdiags(1.0 / sp.array(M.sum(axis=1).flat), [0], n, n)
+ DI = spdiags(1.0 / np.array(M.sum(axis=1).flat), [0], n, n)
if walk_type == "random":
P = DI * M
else:
@@ -344,11 +350,11 @@ def _transition_matrix(G, nodelist=None, weight='weight',
elif walk_type == "pagerank":
if not (0 < alpha < 1):
- raise nx.NetworkXError('alpha must be between 0 and 1')
+ raise nx.NetworkXError("alpha must be between 0 and 1")
# this is using a dense representation
M = M.todense()
# add constant to dangling nodes' row
- dangling = sp.where(M.sum(axis=1) == 0)
+ dangling = np.where(M.sum(axis=1) == 0)
for d in dangling[0]:
M[d] = 1.0 / n
# normalize
diff --git a/networkx/linalg/modularitymatrix.py b/networkx/linalg/modularitymatrix.py
index 927bff93..e2b8f905 100644
--- a/networkx/linalg/modularitymatrix.py
+++ b/networkx/linalg/modularitymatrix.py
@@ -2,11 +2,12 @@
"""
import networkx as nx
from networkx.utils import not_implemented_for
-__all__ = ['modularity_matrix', 'directed_modularity_matrix']
+__all__ = ["modularity_matrix", "directed_modularity_matrix"]
-@not_implemented_for('directed')
-@not_implemented_for('multigraph')
+
+@not_implemented_for("directed")
+@not_implemented_for("multigraph")
def modularity_matrix(G, nodelist=None, weight=None):
r"""Returns the modularity matrix of G.
@@ -63,8 +64,7 @@ def modularity_matrix(G, nodelist=None, weight=None):
"""
if nodelist is None:
nodelist = list(G)
- A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight,
- format='csr')
+ A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, format="csr")
k = A.sum(axis=1)
m = k.sum() * 0.5
# Expected adjacency matrix
@@ -72,8 +72,8 @@ def modularity_matrix(G, nodelist=None, weight=None):
return A - X
-@not_implemented_for('undirected')
-@not_implemented_for('multigraph')
+@not_implemented_for("undirected")
+@not_implemented_for("multigraph")
def directed_modularity_matrix(G, nodelist=None, weight=None):
"""Returns the directed modularity matrix of G.
@@ -139,8 +139,7 @@ def directed_modularity_matrix(G, nodelist=None, weight=None):
"""
if nodelist is None:
nodelist = list(G)
- A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight,
- format='csr')
+ A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, format="csr")
k_in = A.sum(axis=0)
k_out = A.sum(axis=1)
m = k_in.sum()
diff --git a/networkx/linalg/spectrum.py b/networkx/linalg/spectrum.py
index f9de6e54..8612e5f4 100644
--- a/networkx/linalg/spectrum.py
+++ b/networkx/linalg/spectrum.py
@@ -3,11 +3,16 @@ Eigenvalue spectrum of graphs.
"""
import networkx as nx
-__all__ = ['laplacian_spectrum', 'adjacency_spectrum', 'modularity_spectrum',
- 'normalized_laplacian_spectrum', 'bethe_hessian_spectrum']
+__all__ = [
+ "laplacian_spectrum",
+ "adjacency_spectrum",
+ "modularity_spectrum",
+ "normalized_laplacian_spectrum",
+ "bethe_hessian_spectrum",
+]
-def laplacian_spectrum(G, weight='weight'):
+def laplacian_spectrum(G, weight="weight"):
"""Returns eigenvalues of the Laplacian of G
Parameters
@@ -34,10 +39,11 @@ def laplacian_spectrum(G, weight='weight'):
laplacian_matrix
"""
from scipy.linalg import eigvalsh
+
return eigvalsh(nx.laplacian_matrix(G, weight=weight).todense())
-def normalized_laplacian_spectrum(G, weight='weight'):
+def normalized_laplacian_spectrum(G, weight="weight"):
"""Return eigenvalues of the normalized Laplacian of G
Parameters
@@ -64,10 +70,11 @@ def normalized_laplacian_spectrum(G, weight='weight'):
normalized_laplacian_matrix
"""
from scipy.linalg import eigvalsh
+
return eigvalsh(nx.normalized_laplacian_matrix(G, weight=weight).todense())
-def adjacency_spectrum(G, weight='weight'):
+def adjacency_spectrum(G, weight="weight"):
"""Returns eigenvalues of the adjacency matrix of G.
Parameters
@@ -94,6 +101,7 @@ def adjacency_spectrum(G, weight='weight'):
adjacency_matrix
"""
from scipy.linalg import eigvals
+
return eigvals(nx.adjacency_matrix(G, weight=weight).todense())
@@ -120,6 +128,7 @@ def modularity_spectrum(G):
Proc. Natl. Acad. Sci. USA, vol. 103, pp. 8577-8582, 2006.
"""
from scipy.linalg import eigvals
+
if G.is_directed():
return eigvals(nx.directed_modularity_matrix(G))
else:
@@ -153,4 +162,5 @@ def bethe_hessian_spectrum(G, r=None):
Advances in Neural Information Processing Systems. 2014.
"""
from scipy.linalg import eigvalsh
+
return eigvalsh(nx.bethe_hessian_matrix(G, r).todense())
diff --git a/networkx/linalg/tests/test_algebraic_connectivity.py b/networkx/linalg/tests/test_algebraic_connectivity.py
index bfabfa63..96596db4 100644
--- a/networkx/linalg/tests/test_algebraic_connectivity.py
+++ b/networkx/linalg/tests/test_algebraic_connectivity.py
@@ -1,10 +1,11 @@
from math import sqrt
import pytest
-numpy = pytest.importorskip('numpy')
-numpy.linalg = pytest.importorskip('numpy.linalg')
-scipy = pytest.importorskip('scipy')
-scipy.sparse = pytest.importorskip('scipy.sparse')
+
+numpy = pytest.importorskip("numpy")
+numpy.linalg = pytest.importorskip("numpy.linalg")
+scipy = pytest.importorskip("scipy")
+scipy.sparse = pytest.importorskip("scipy.sparse")
import networkx as nx
@@ -12,14 +13,15 @@ from networkx.testing import almost_equal
try:
from scikits.sparse.cholmod import cholesky
+
_cholesky = cholesky
except ImportError:
_cholesky = None
if _cholesky is None:
- methods = ('tracemin_pcg', 'tracemin_lu', 'lanczos', 'lobpcg')
+ methods = ("tracemin_pcg", "tracemin_lu", "lanczos", "lobpcg")
else:
- methods = ('tracemin_pcg', 'tracemin_chol', 'tracemin_lu', 'lanczos', 'lobpcg')
+ methods = ("tracemin_pcg", "tracemin_chol", "tracemin_lu", "lanczos", "lobpcg")
def check_eigenvector(A, l, x):
@@ -35,75 +37,71 @@ def check_eigenvector(A, l, x):
class TestAlgebraicConnectivity:
-
def test_directed(self):
G = nx.DiGraph()
for method in self._methods:
- pytest.raises(nx.NetworkXNotImplemented, nx.algebraic_connectivity,
- G, method=method)
- pytest.raises(nx.NetworkXNotImplemented, nx.fiedler_vector, G,
- method=method)
+ pytest.raises(
+ nx.NetworkXNotImplemented, nx.algebraic_connectivity, G, method=method
+ )
+ pytest.raises(
+ nx.NetworkXNotImplemented, nx.fiedler_vector, G, method=method
+ )
def test_null_and_singleton(self):
G = nx.Graph()
for method in self._methods:
- pytest.raises(nx.NetworkXError, nx.algebraic_connectivity, G,
- method=method)
- pytest.raises(nx.NetworkXError, nx.fiedler_vector, G,
- method=method)
+ pytest.raises(nx.NetworkXError, nx.algebraic_connectivity, G, method=method)
+ pytest.raises(nx.NetworkXError, nx.fiedler_vector, G, method=method)
G.add_edge(0, 0)
for method in self._methods:
- pytest.raises(nx.NetworkXError, nx.algebraic_connectivity, G,
- method=method)
- pytest.raises(nx.NetworkXError, nx.fiedler_vector, G,
- method=method)
+ pytest.raises(nx.NetworkXError, nx.algebraic_connectivity, G, method=method)
+ pytest.raises(nx.NetworkXError, nx.fiedler_vector, G, method=method)
def test_disconnected(self):
G = nx.Graph()
G.add_nodes_from(range(2))
for method in self._methods:
assert nx.algebraic_connectivity(G) == 0
- pytest.raises(nx.NetworkXError, nx.fiedler_vector, G,
- method=method)
+ pytest.raises(nx.NetworkXError, nx.fiedler_vector, G, method=method)
G.add_edge(0, 1, weight=0)
for method in self._methods:
assert nx.algebraic_connectivity(G) == 0
- pytest.raises(nx.NetworkXError, nx.fiedler_vector, G,
- method=method)
+ pytest.raises(nx.NetworkXError, nx.fiedler_vector, G, method=method)
def test_unrecognized_method(self):
G = nx.path_graph(4)
- pytest.raises(nx.NetworkXError, nx.algebraic_connectivity, G,
- method='unknown')
- pytest.raises(nx.NetworkXError, nx.fiedler_vector, G, method='unknown')
+ pytest.raises(nx.NetworkXError, nx.algebraic_connectivity, G, method="unknown")
+ pytest.raises(nx.NetworkXError, nx.fiedler_vector, G, method="unknown")
def test_two_nodes(self):
G = nx.Graph()
G.add_edge(0, 1, weight=1)
A = nx.laplacian_matrix(G)
for method in self._methods:
- assert almost_equal(nx.algebraic_connectivity(
- G, tol=1e-12, method=method), 2)
+ assert almost_equal(
+ nx.algebraic_connectivity(G, tol=1e-12, method=method), 2
+ )
x = nx.fiedler_vector(G, tol=1e-12, method=method)
check_eigenvector(A, 2, x)
G = nx.MultiGraph()
G.add_edge(0, 0, spam=1e8)
G.add_edge(0, 1, spam=1)
G.add_edge(0, 1, spam=-2)
- A = -3 * nx.laplacian_matrix(G, weight='spam')
+ A = -3 * nx.laplacian_matrix(G, weight="spam")
for method in self._methods:
- assert almost_equal(nx.algebraic_connectivity(
- G, weight='spam', tol=1e-12, method=method), 6)
- x = nx.fiedler_vector(G, weight='spam', tol=1e-12, method=method)
+ assert almost_equal(
+ nx.algebraic_connectivity(G, weight="spam", tol=1e-12, method=method), 6
+ )
+ x = nx.fiedler_vector(G, weight="spam", tol=1e-12, method=method)
check_eigenvector(A, 6, x)
def test_abbreviation_of_method(self):
G = nx.path_graph(8)
A = nx.laplacian_matrix(G)
sigma = 2 - sqrt(2 + sqrt(2))
- ac = nx.algebraic_connectivity(G, tol=1e-12, method='tracemin')
+ ac = nx.algebraic_connectivity(G, tol=1e-12, method="tracemin")
assert almost_equal(ac, sigma)
- x = nx.fiedler_vector(G, tol=1e-12, method='tracemin')
+ x = nx.fiedler_vector(G, tol=1e-12, method="tracemin")
check_eigenvector(A, sigma, x)
def test_path(self):
@@ -149,21 +147,99 @@ class TestAlgebraicConnectivity:
def test_buckminsterfullerene(self):
G = nx.Graph(
- [(1, 10), (1, 41), (1, 59), (2, 12), (2, 42), (2, 60), (3, 6),
- (3, 43), (3, 57), (4, 8), (4, 44), (4, 58), (5, 13), (5, 56),
- (5, 57), (6, 10), (6, 31), (7, 14), (7, 56), (7, 58), (8, 12),
- (8, 32), (9, 23), (9, 53), (9, 59), (10, 15), (11, 24), (11, 53),
- (11, 60), (12, 16), (13, 14), (13, 25), (14, 26), (15, 27),
- (15, 49), (16, 28), (16, 50), (17, 18), (17, 19), (17, 54),
- (18, 20), (18, 55), (19, 23), (19, 41), (20, 24), (20, 42),
- (21, 31), (21, 33), (21, 57), (22, 32), (22, 34), (22, 58),
- (23, 24), (25, 35), (25, 43), (26, 36), (26, 44), (27, 51),
- (27, 59), (28, 52), (28, 60), (29, 33), (29, 34), (29, 56),
- (30, 51), (30, 52), (30, 53), (31, 47), (32, 48), (33, 45),
- (34, 46), (35, 36), (35, 37), (36, 38), (37, 39), (37, 49),
- (38, 40), (38, 50), (39, 40), (39, 51), (40, 52), (41, 47),
- (42, 48), (43, 49), (44, 50), (45, 46), (45, 54), (46, 55),
- (47, 54), (48, 55)])
+ [
+ (1, 10),
+ (1, 41),
+ (1, 59),
+ (2, 12),
+ (2, 42),
+ (2, 60),
+ (3, 6),
+ (3, 43),
+ (3, 57),
+ (4, 8),
+ (4, 44),
+ (4, 58),
+ (5, 13),
+ (5, 56),
+ (5, 57),
+ (6, 10),
+ (6, 31),
+ (7, 14),
+ (7, 56),
+ (7, 58),
+ (8, 12),
+ (8, 32),
+ (9, 23),
+ (9, 53),
+ (9, 59),
+ (10, 15),
+ (11, 24),
+ (11, 53),
+ (11, 60),
+ (12, 16),
+ (13, 14),
+ (13, 25),
+ (14, 26),
+ (15, 27),
+ (15, 49),
+ (16, 28),
+ (16, 50),
+ (17, 18),
+ (17, 19),
+ (17, 54),
+ (18, 20),
+ (18, 55),
+ (19, 23),
+ (19, 41),
+ (20, 24),
+ (20, 42),
+ (21, 31),
+ (21, 33),
+ (21, 57),
+ (22, 32),
+ (22, 34),
+ (22, 58),
+ (23, 24),
+ (25, 35),
+ (25, 43),
+ (26, 36),
+ (26, 44),
+ (27, 51),
+ (27, 59),
+ (28, 52),
+ (28, 60),
+ (29, 33),
+ (29, 34),
+ (29, 56),
+ (30, 51),
+ (30, 52),
+ (30, 53),
+ (31, 47),
+ (32, 48),
+ (33, 45),
+ (34, 46),
+ (35, 36),
+ (35, 37),
+ (36, 38),
+ (37, 39),
+ (37, 49),
+ (38, 40),
+ (38, 50),
+ (39, 40),
+ (39, 51),
+ (40, 52),
+ (41, 47),
+ (42, 48),
+ (43, 49),
+ (44, 50),
+ (45, 46),
+ (45, 54),
+ (46, 55),
+ (47, 54),
+ (48, 55),
+ ]
+ )
for normalized in (False, True):
if not normalized:
A = nx.laplacian_matrix(G)
@@ -173,22 +249,27 @@ class TestAlgebraicConnectivity:
sigma = 0.08113391537997749
for method in methods:
try:
- assert almost_equal(nx.algebraic_connectivity(
- G, normalized=normalized, tol=1e-12, method=method),
- sigma)
- x = nx.fiedler_vector(G, normalized=normalized, tol=1e-12,
- method=method)
+ assert almost_equal(
+ nx.algebraic_connectivity(
+ G, normalized=normalized, tol=1e-12, method=method
+ ),
+ sigma,
+ )
+ x = nx.fiedler_vector(
+ G, normalized=normalized, tol=1e-12, method=method
+ )
check_eigenvector(A, sigma, x)
except nx.NetworkXError as e:
- if e.args not in (('Cholesky solver unavailable.',),
- ('LU solver unavailable.',)):
+ if e.args not in (
+ ("Cholesky solver unavailable.",),
+ ("LU solver unavailable.",),
+ ):
raise
_methods = methods
class TestSpectralOrdering:
-
def test_nullgraph(self):
for graph in (nx.Graph, nx.DiGraph, nx.MultiGraph, nx.MultiDiGraph):
G = graph()
@@ -197,23 +278,21 @@ class TestSpectralOrdering:
def test_singleton(self):
for graph in (nx.Graph, nx.DiGraph, nx.MultiGraph, nx.MultiDiGraph):
G = graph()
- G.add_node('x')
- assert nx.spectral_ordering(G) == ['x']
- G.add_edge('x', 'x', weight=33)
- G.add_edge('x', 'x', weight=33)
- assert nx.spectral_ordering(G) == ['x']
+ G.add_node("x")
+ assert nx.spectral_ordering(G) == ["x"]
+ G.add_edge("x", "x", weight=33)
+ G.add_edge("x", "x", weight=33)
+ assert nx.spectral_ordering(G) == ["x"]
def test_unrecognized_method(self):
G = nx.path_graph(4)
- pytest.raises(nx.NetworkXError, nx.spectral_ordering, G,
- method='unknown')
+ pytest.raises(nx.NetworkXError, nx.spectral_ordering, G, method="unknown")
def test_three_nodes(self):
G = nx.Graph()
- G.add_weighted_edges_from([(1, 2, 1), (1, 3, 2), (2, 3, 1)],
- weight='spam')
+ G.add_weighted_edges_from([(1, 2, 1), (1, 3, 2), (2, 3, 1)], weight="spam")
for method in self._methods:
- order = nx.spectral_ordering(G, weight='spam', method=method)
+ order = nx.spectral_ordering(G, weight="spam", method=method)
assert set(order) == set(G)
assert {1, 3} in (set(order[:-1]), set(order[1:]))
G = nx.MultiDiGraph()
@@ -226,6 +305,7 @@ class TestSpectralOrdering:
def test_path(self):
# based on setup_class numpy is installed if we get here
from numpy.random import shuffle
+
path = list(range(10))
shuffle(path)
G = nx.Graph()
@@ -237,6 +317,7 @@ class TestSpectralOrdering:
def test_seed_argument(self):
# based on setup_class numpy is installed if we get here
from numpy.random import shuffle
+
path = list(range(10))
shuffle(path)
G = nx.Graph()
@@ -252,8 +333,12 @@ class TestSpectralOrdering:
for method in self._methods:
order = nx.spectral_ordering(G, method=method)
assert set(order) == set(G)
- seqs = [list(range(0, 10, 2)), list(range(8, -1, -2)),
- list(range(1, 10, 2)), list(range(9, -1, -2))]
+ seqs = [
+ list(range(0, 10, 2)),
+ list(range(8, -1, -2)),
+ list(range(1, 10, 2)),
+ list(range(9, -1, -2)),
+ ]
assert order[:5] in seqs
assert order[5:] in seqs
@@ -266,18 +351,25 @@ class TestSpectralOrdering:
for normalized in (False, True):
for method in methods:
try:
- order = nx.spectral_ordering(G, normalized=normalized,
- method=method)
+ order = nx.spectral_ordering(
+ G, normalized=normalized, method=method
+ )
except nx.NetworkXError as e:
- if e.args not in (('Cholesky solver unavailable.',),
- ('LU solver unavailable.',)):
+ if e.args not in (
+ ("Cholesky solver unavailable.",),
+ ("LU solver unavailable.",),
+ ):
raise
else:
if not normalized:
- assert order in [[1, 2, 0, 3, 4, 5, 6, 9, 7, 8],
- [8, 7, 9, 6, 5, 4, 3, 0, 2, 1]]
+ assert order in [
+ [1, 2, 0, 3, 4, 5, 6, 9, 7, 8],
+ [8, 7, 9, 6, 5, 4, 3, 0, 2, 1],
+ ]
else:
- assert order in [[1, 2, 3, 0, 4, 5, 9, 6, 7, 8],
- [8, 7, 6, 9, 5, 4, 0, 3, 2, 1]]
+ assert order in [
+ [1, 2, 3, 0, 4, 5, 9, 6, 7, 8],
+ [8, 7, 6, 9, 5, 4, 0, 3, 2, 1],
+ ]
_methods = methods
diff --git a/networkx/linalg/tests/test_attrmatrix.py b/networkx/linalg/tests/test_attrmatrix.py
index e2f888d4..1fe2412e 100644
--- a/networkx/linalg/tests/test_attrmatrix.py
+++ b/networkx/linalg/tests/test_attrmatrix.py
@@ -1,6 +1,6 @@
import pytest
-np = pytest.importorskip('numpy')
+np = pytest.importorskip("numpy")
import numpy.testing as npt
import networkx as nx
@@ -14,10 +14,10 @@ def test_attr_matrix():
G.add_edge(1, 2, thickness=3)
def node_attr(u):
- return G.nodes[u].get('size', .5) * 3
+ return G.nodes[u].get("size", .5) * 3
def edge_attr(u, v):
- return G[u][v].get('thickness', .5)
+ return G[u][v].get("thickness", .5)
M = nx.attr_matrix(G, edge_attr=edge_attr, node_attr=node_attr)
npt.assert_equal(M[0], np.array([[6.]]))
@@ -70,7 +70,7 @@ def test_attr_matrix_multigraph():
def test_attr_sparse_matrix():
- pytest.importorskip('scipy')
+ pytest.importorskip("scipy")
G = nx.Graph()
G.add_edge(0, 1, thickness=1, weight=3)
G.add_edge(0, 2, thickness=2)
diff --git a/networkx/linalg/tests/test_bethehessian.py b/networkx/linalg/tests/test_bethehessian.py
index a1555bc2..61fd1f65 100644
--- a/networkx/linalg/tests/test_bethehessian.py
+++ b/networkx/linalg/tests/test_bethehessian.py
@@ -1,14 +1,14 @@
import pytest
-numpy = pytest.importorskip('numpy')
-npt = pytest.importorskip('numpy.testing')
-scipy = pytest.importorskip('scipy')
+
+np = pytest.importorskip("numpy")
+npt = pytest.importorskip("numpy.testing")
+sp = pytest.importorskip("scipy")
import networkx as nx
from networkx.generators.degree_seq import havel_hakimi_graph
class TestBetheHessian:
-
@classmethod
def setup_class(cls):
deg = [3, 2, 2, 1, 0]
@@ -17,18 +17,24 @@ class TestBetheHessian:
def test_bethe_hessian(self):
"Bethe Hessian matrix"
- H = numpy.array([[4, -2, 0],
- [-2, 5, -2],
- [0, -2, 4]])
+ H = np.array([[4, -2, 0],
+ [-2, 5, -2],
+ [0, -2, 4]])
permutation = [2, 0, 1]
# Bethe Hessian gives expected form
npt.assert_equal(nx.bethe_hessian_matrix(self.P, r=2).todense(), H)
# nodelist is correctly implemented
- npt.assert_equal(nx.bethe_hessian_matrix(self.P, r=2, nodelist=permutation).todense(),
- H[numpy.ix_(permutation, permutation)])
+ npt.assert_equal(
+ nx.bethe_hessian_matrix(self.P, r=2, nodelist=permutation).todense(),
+ H[np.ix_(permutation, permutation)],
+ )
# Equal to Laplacian matrix when r=1
- npt.assert_equal(nx.bethe_hessian_matrix(self.G, r=1).todense(),
- nx.laplacian_matrix(self.G).todense())
+ npt.assert_equal(
+ nx.bethe_hessian_matrix(self.G, r=1).todense(),
+ nx.laplacian_matrix(self.G).todense(),
+ )
# Correct default for the regularizer r
- npt.assert_equal(nx.bethe_hessian_matrix(self.G).todense(),
- nx.bethe_hessian_matrix(self.G, r=1.25).todense())
+ npt.assert_equal(
+ nx.bethe_hessian_matrix(self.G).todense(),
+ nx.bethe_hessian_matrix(self.G, r=1.25).todense(),
+ )
diff --git a/networkx/linalg/tests/test_laplacian.py b/networkx/linalg/tests/test_laplacian.py
index c29faa19..7d76fdf7 100644
--- a/networkx/linalg/tests/test_laplacian.py
+++ b/networkx/linalg/tests/test_laplacian.py
@@ -1,8 +1,8 @@
import pytest
-np = pytest.importorskip('numpy')
-npt = pytest.importorskip('numpy.testing')
-pytest.importorskip('scipy')
+np = pytest.importorskip("numpy")
+npt = pytest.importorskip("numpy.testing")
+pytest.importorskip("scipy")
import networkx as nx
from networkx.generators.degree_seq import havel_hakimi_graph
@@ -16,7 +16,7 @@ class TestLaplacian:
deg = [3, 2, 2, 1, 0]
cls.G = havel_hakimi_graph(deg)
cls.WG = nx.Graph(
- (u, v, {'weight': 0.5, 'other': 0.3}) for (u, v) in cls.G.edges()
+ (u, v, {"weight": 0.5, "other": 0.3}) for (u, v) in cls.G.edges()
)
cls.WG.add_node(4)
cls.MG = nx.MultiGraph(cls.G)
@@ -43,7 +43,7 @@ class TestLaplacian:
)
npt.assert_equal(nx.laplacian_matrix(self.WG).todense(), WL)
npt.assert_equal(nx.laplacian_matrix(self.WG, weight=None).todense(), NL)
- npt.assert_equal(nx.laplacian_matrix(self.WG, weight='other').todense(), OL)
+ npt.assert_equal(nx.laplacian_matrix(self.WG, weight="other").todense(), OL)
def test_normalized_laplacian(self):
"Generalized Graph Laplacian"
@@ -63,18 +63,24 @@ class TestLaplacian:
[-0.3536, 0., 0., 0.5, 0.],
[0., 0., 0., 0., 0.]])
- npt.assert_almost_equal(nx.normalized_laplacian_matrix(self.G, nodelist=range(5)).todense(),
- G, decimal=3)
- npt.assert_almost_equal(nx.normalized_laplacian_matrix(self.G).todense(),
- GL, decimal=3)
- npt.assert_almost_equal(nx.normalized_laplacian_matrix(self.MG).todense(),
- GL, decimal=3)
- npt.assert_almost_equal(nx.normalized_laplacian_matrix(self.WG).todense(),
- GL, decimal=3)
- npt.assert_almost_equal(nx.normalized_laplacian_matrix(self.WG, weight='other').todense(),
- GL, decimal=3)
- npt.assert_almost_equal(nx.normalized_laplacian_matrix(self.Gsl).todense(),
- Lsl, decimal=3)
+ npt.assert_almost_equal(
+ nx.normalized_laplacian_matrix(self.G, nodelist=range(5)).todense(), G, decimal=3
+ )
+ npt.assert_almost_equal(
+ nx.normalized_laplacian_matrix(self.G).todense(), GL, decimal=3
+ )
+ npt.assert_almost_equal(
+ nx.normalized_laplacian_matrix(self.MG).todense(), GL, decimal=3
+ )
+ npt.assert_almost_equal(
+ nx.normalized_laplacian_matrix(self.WG).todense(), GL, decimal=3
+ )
+ npt.assert_almost_equal(
+ nx.normalized_laplacian_matrix(self.WG, weight="other").todense(), GL, decimal=3
+ )
+ npt.assert_almost_equal(
+ nx.normalized_laplacian_matrix(self.Gsl).todense(), Lsl, decimal=3
+ )
def test_directed_laplacian(self):
"Directed Laplacian"
@@ -82,8 +88,20 @@ class TestLaplacian:
# "Google's PageRank and Beyond". The graph contains dangling nodes, so
# the pagerank random walk is selected by directed_laplacian
G = nx.DiGraph()
- G.add_edges_from(((1, 2), (1, 3), (3, 1), (3, 2), (3, 5), (4, 5), (4, 6),
- (5, 4), (5, 6), (6, 4)))
+ G.add_edges_from(
+ (
+ (1, 2),
+ (1, 3),
+ (3, 1),
+ (3, 2),
+ (3, 5),
+ (4, 5),
+ (4, 6),
+ (5, 4),
+ (5, 6),
+ (6, 4),
+ )
+ )
GL = np.array([[0.9833, -0.2941, -0.3882, -0.0291, -0.0231, -0.0261],
[-0.2941, 0.8333, -0.2339, -0.0536, -0.0589, -0.0554],
[-0.3882, -0.2339, 0.9833, -0.0278, -0.0896, -0.0251],
@@ -101,7 +119,7 @@ class TestLaplacian:
[0., 0., 0., 1., -0.5, -0.5],
[0., -0.3162, -0.0913, -0.5, 1., -0.25],
[-0.3227, 0., 0., -0.5, -0.25, 1.]])
- L = nx.directed_laplacian_matrix(G, alpha=0.9, nodelist=sorted(G), walk_type='random')
+ L = nx.directed_laplacian_matrix(G, alpha=0.9, nodelist=sorted(G), walk_type="random")
npt.assert_almost_equal(L, GL, decimal=3)
GL = np.array([[0.5, -0.1531, -0.2357, 0., 0., -0.1614],
@@ -110,7 +128,7 @@ class TestLaplacian:
[0., 0., 0., 0.5, -0.25, -0.25],
[0., -0.1581, -0.0456, -0.25, 0.5, -0.125],
[-0.1614, 0., 0., -0.25, -0.125, 0.5]])
- L = nx.directed_laplacian_matrix(G, alpha=0.9, nodelist=sorted(G), walk_type='lazy')
+ L = nx.directed_laplacian_matrix(G, alpha=0.9, nodelist=sorted(G), walk_type="lazy")
npt.assert_almost_equal(L, GL, decimal=3)
def test_directed_combinatorial_laplacian(self):
@@ -140,8 +158,7 @@ class TestLaplacian:
[-0.0020, -0.0062, -0.0083, -0.1356, 0.2026, -0.0505],
[-0.0027, -0.0069, -0.0027, -0.2187, -0.0505, 0.2815]])
- L = nx.directed_combinatorial_laplacian_matrix(G, alpha=0.9,
- nodelist=sorted(G))
+ L = nx.directed_combinatorial_laplacian_matrix(G, alpha=0.9, nodelist=sorted(G))
npt.assert_almost_equal(L, GL, decimal=3)
# Make the graph strongly connected, so we can use a random and lazy walk
@@ -154,9 +171,9 @@ class TestLaplacian:
[0, -0.0465, -0.0116, -0.1163, 0.2326, -0.0581],
[-0.0581, 0, 0, -0.1163, -0.0581, 0.2326]])
- L = nx.directed_combinatorial_laplacian_matrix(G, alpha=0.9,
- nodelist=sorted(G),
- walk_type='random')
+ L = nx.directed_combinatorial_laplacian_matrix(
+ G, alpha=0.9, nodelist=sorted(G), walk_type="random"
+ )
npt.assert_almost_equal(L, GL, decimal=3)
GL = np.array([[0.0698, -0.0174, -0.0233, 0, 0, -0.0291],
@@ -166,9 +183,9 @@ class TestLaplacian:
[0, -0.0233, -0.0058, -0.0581, 0.1163, -0.0291],
[-0.0291, 0, 0, -0.0581, -0.0291, 0.1163]])
- L = nx.directed_combinatorial_laplacian_matrix(G, alpha=0.9,
- nodelist=sorted(G),
- walk_type='lazy')
+ L = nx.directed_combinatorial_laplacian_matrix(
+ G, alpha=0.9, nodelist=sorted(G), walk_type="lazy"
+ )
npt.assert_almost_equal(L, GL, decimal=3)
E = nx.DiGraph(margulis_gabber_galil_graph(2))
diff --git a/networkx/linalg/tests/test_modularity.py b/networkx/linalg/tests/test_modularity.py
index 50a061e0..f791dcea 100644
--- a/networkx/linalg/tests/test_modularity.py
+++ b/networkx/linalg/tests/test_modularity.py
@@ -1,7 +1,7 @@
import pytest
-np = pytest.importorskip('numpy')
-npt = pytest.importorskip('numpy.testing')
-scipy = pytest.importorskip('scipy')
+np = pytest.importorskip("numpy")
+npt = pytest.importorskip("numpy.testing")
+scipy = pytest.importorskip("scipy")
import networkx as nx
from networkx.generators.degree_seq import havel_hakimi_graph
@@ -16,8 +16,20 @@ class TestModularity:
# Graph used as an example in Sec. 4.1 of Langville and Meyer,
# "Google's PageRank and Beyond". (Used for test_directed_laplacian)
cls.DG = nx.DiGraph()
- cls.DG.add_edges_from(((1, 2), (1, 3), (3, 1), (3, 2), (3, 5), (4, 5), (4, 6),
- (5, 4), (5, 6), (6, 4)))
+ cls.DG.add_edges_from(
+ (
+ (1, 2),
+ (1, 3),
+ (3, 1),
+ (3, 2),
+ (3, 5),
+ (4, 5),
+ (4, 6),
+ (5, 4),
+ (5, 6),
+ (6, 4),
+ )
+ )
def test_modularity(self):
"Modularity matrix"
@@ -29,8 +41,10 @@ class TestModularity:
permutation = [4, 0, 1, 2, 3]
npt.assert_equal(nx.modularity_matrix(self.G), B)
- npt.assert_equal(nx.modularity_matrix(self.G, nodelist=permutation),
- B[np.ix_(permutation, permutation)])
+ npt.assert_equal(
+ nx.modularity_matrix(self.G, nodelist=permutation),
+ B[np.ix_(permutation, permutation)],
+ )
def test_modularity_weight(self):
"Modularity matrix with weights"
@@ -58,9 +72,9 @@ class TestModularity:
[-0.1, -0.2, -0.1, 0.8, -0.2, -0.2]])
node_permutation = [5, 1, 2, 3, 4, 6]
idx_permutation = [4, 0, 1, 2, 3, 5]
- mm = nx.directed_modularity_matrix(self.DG, nodelist=sorted(self.DG))
+ mm = nx.directed_modularity_matrix(self.DG, nodelist=sorted(self.DG))
npt.assert_equal(mm, B)
npt.assert_equal(
nx.directed_modularity_matrix(self.DG, nodelist=node_permutation),
- B[np.ix_(idx_permutation, idx_permutation)]
+ B[np.ix_(idx_permutation, idx_permutation)],
)
diff --git a/networkx/linalg/tests/test_spectrum.py b/networkx/linalg/tests/test_spectrum.py
index c22bd18c..63e12d37 100644
--- a/networkx/linalg/tests/test_spectrum.py
+++ b/networkx/linalg/tests/test_spectrum.py
@@ -1,69 +1,69 @@
import pytest
-numpy = pytest.importorskip('numpy')
-npt = pytest.importorskip('numpy.testing')
-scipy = pytest.importorskip('scipy')
+
+np = pytest.importorskip("numpy")
+npt = pytest.importorskip("numpy.testing")
+scipy = pytest.importorskip("scipy")
import networkx as nx
from networkx.generators.degree_seq import havel_hakimi_graph
class TestSpectrum:
-
@classmethod
def setup_class(cls):
deg = [3, 2, 2, 1, 0]
cls.G = havel_hakimi_graph(deg)
cls.P = nx.path_graph(3)
- cls.WG = nx.Graph((u, v, {'weight': 0.5, 'other': 0.3})
- for (u, v) in cls.G.edges())
+ cls.WG = nx.Graph(
+ (u, v, {"weight": 0.5, "other": 0.3}) for (u, v) in cls.G.edges()
+ )
cls.WG.add_node(4)
cls.DG = nx.DiGraph()
nx.add_path(cls.DG, [0, 1, 2])
def test_laplacian_spectrum(self):
"Laplacian eigenvalues"
- evals = numpy.array([0, 0, 1, 3, 4])
+ evals = np.array([0, 0, 1, 3, 4])
e = sorted(nx.laplacian_spectrum(self.G))
npt.assert_almost_equal(e, evals)
e = sorted(nx.laplacian_spectrum(self.WG, weight=None))
npt.assert_almost_equal(e, evals)
e = sorted(nx.laplacian_spectrum(self.WG))
npt.assert_almost_equal(e, 0.5 * evals)
- e = sorted(nx.laplacian_spectrum(self.WG, weight='other'))
+ e = sorted(nx.laplacian_spectrum(self.WG, weight="other"))
npt.assert_almost_equal(e, 0.3 * evals)
def test_normalized_laplacian_spectrum(self):
"Normalized Laplacian eigenvalues"
- evals = numpy.array([0, 0, 0.7712864461218, 1.5, 1.7287135538781])
+ evals = np.array([0, 0, 0.7712864461218, 1.5, 1.7287135538781])
e = sorted(nx.normalized_laplacian_spectrum(self.G))
npt.assert_almost_equal(e, evals)
e = sorted(nx.normalized_laplacian_spectrum(self.WG, weight=None))
npt.assert_almost_equal(e, evals)
e = sorted(nx.normalized_laplacian_spectrum(self.WG))
npt.assert_almost_equal(e, evals)
- e = sorted(nx.normalized_laplacian_spectrum(self.WG, weight='other'))
+ e = sorted(nx.normalized_laplacian_spectrum(self.WG, weight="other"))
npt.assert_almost_equal(e, evals)
def test_adjacency_spectrum(self):
"Adjacency eigenvalues"
- evals = numpy.array([-numpy.sqrt(2), 0, numpy.sqrt(2)])
+ evals = np.array([-np.sqrt(2), 0, np.sqrt(2)])
e = sorted(nx.adjacency_spectrum(self.P))
npt.assert_almost_equal(e, evals)
def test_modularity_spectrum(self):
"Modularity eigenvalues"
- evals = numpy.array([-1.5, 0., 0.])
+ evals = np.array([-1.5, 0.0, 0.0])
e = sorted(nx.modularity_spectrum(self.P))
npt.assert_almost_equal(e, evals)
# Directed modularity eigenvalues
- evals = numpy.array([-0.5, 0., 0.])
+ evals = np.array([-0.5, 0.0, 0.0])
e = sorted(nx.modularity_spectrum(self.DG))
npt.assert_almost_equal(e, evals)
def test_bethe_hessian_spectrum(self):
"Bethe Hessian eigenvalues"
- evals = numpy.array([0.5 * (9 - numpy.sqrt(33)), 4,
- 0.5 * (9 + numpy.sqrt(33))])
+ evals = np.array([0.5 * (9 - np.sqrt(33)), 4, 0.5 * (9 + np.sqrt(33))])
e = sorted(nx.bethe_hessian_spectrum(self.P, r=2))
npt.assert_almost_equal(e, evals)
# Collapses back to Laplacian:
diff --git a/networkx/relabel.py b/networkx/relabel.py
index ab1779e1..8bd954b4 100644
--- a/networkx/relabel.py
+++ b/networkx/relabel.py
@@ -1,6 +1,6 @@
import networkx as nx
-__all__ = ['convert_node_labels_to_integers', 'relabel_nodes']
+__all__ = ["convert_node_labels_to_integers", "relabel_nodes"]
def relabel_nodes(G, mapping, copy=True):
@@ -104,9 +104,10 @@ def _relabel_inplace(G, mapping):
try:
nodes = reversed(list(nx.topological_sort(D)))
except nx.NetworkXUnfeasible:
- raise nx.NetworkXUnfeasible('The node label sets are overlapping '
- 'and no ordering can resolve the '
- 'mapping. Use copy=True.')
+ raise nx.NetworkXUnfeasible(
+ "The node label sets are overlapping and no ordering can "
+ "resolve the mapping. Use copy=True."
+ )
else:
# non-overlapping label sets
nodes = old_labels
@@ -126,19 +127,25 @@ def _relabel_inplace(G, mapping):
except KeyError:
raise KeyError(f"Node {old} is not in the graph")
if multigraph:
- new_edges = [(new, new if old == target else target, key, data)
- for (_, target, key, data)
- in G.edges(old, data=True, keys=True)]
+ new_edges = [
+ (new, new if old == target else target, key, data)
+ for (_, target, key, data) in G.edges(old, data=True, keys=True)
+ ]
if directed:
- new_edges += [(new if old == source else source, new, key, data)
- for (source, _, key, data)
- in G.in_edges(old, data=True, keys=True)]
+ new_edges += [
+ (new if old == source else source, new, key, data)
+ for (source, _, key, data) in G.in_edges(old, data=True, keys=True)
+ ]
else:
- new_edges = [(new, new if old == target else target, data)
- for (_, target, data) in G.edges(old, data=True)]
+ new_edges = [
+ (new, new if old == target else target, data)
+ for (_, target, data) in G.edges(old, data=True)
+ ]
if directed:
- new_edges += [(new if old == source else source, new, data)
- for (source, _, data) in G.in_edges(old, data=True)]
+ new_edges += [
+ (new if old == source else source, new, data)
+ for (source, _, data) in G.in_edges(old, data=True)
+ ]
G.remove_node(old)
G.add_edges_from(new_edges)
return G
@@ -149,17 +156,22 @@ def _relabel_copy(G, mapping):
H.add_nodes_from(mapping.get(n, n) for n in G)
H._node.update((mapping.get(n, n), d.copy()) for n, d in G.nodes.items())
if G.is_multigraph():
- H.add_edges_from((mapping.get(n1, n1), mapping.get(n2, n2), k, d.copy())
- for (n1, n2, k, d) in G.edges(keys=True, data=True))
+ H.add_edges_from(
+ (mapping.get(n1, n1), mapping.get(n2, n2), k, d.copy())
+ for (n1, n2, k, d) in G.edges(keys=True, data=True)
+ )
else:
- H.add_edges_from((mapping.get(n1, n1), mapping.get(n2, n2), d.copy())
- for (n1, n2, d) in G.edges(data=True))
+ H.add_edges_from(
+ (mapping.get(n1, n1), mapping.get(n2, n2), d.copy())
+ for (n1, n2, d) in G.edges(data=True)
+ )
H.graph.update(G.graph)
return H
-def convert_node_labels_to_integers(G, first_label=0, ordering="default",
- label_attribute=None):
+def convert_node_labels_to_integers(
+ G, first_label=0, ordering="default", label_attribute=None
+):
"""Returns a copy of the graph G with the nodes relabeled using
consecutive integers.
@@ -214,6 +226,5 @@ def convert_node_labels_to_integers(G, first_label=0, ordering="default",
H = relabel_nodes(G, mapping)
# create node attribute with the old label
if label_attribute is not None:
- nx.set_node_attributes(H, {v: k for k, v in mapping.items()},
- label_attribute)
+ nx.set_node_attributes(H, {v: k for k, v in mapping.items()}, label_attribute)
return H
diff --git a/networkx/tests/test_convert.py b/networkx/tests/test_convert.py
index b7315d11..72c9fee8 100644
--- a/networkx/tests/test_convert.py
+++ b/networkx/tests/test_convert.py
@@ -2,21 +2,25 @@ import pytest
import networkx as nx
from networkx.testing import assert_nodes_equal, assert_edges_equal, assert_graphs_equal
-from networkx.convert import (to_networkx_graph,
- to_dict_of_dicts,
- from_dict_of_dicts,
- to_dict_of_lists,
- from_dict_of_lists)
+from networkx.convert import (
+ to_networkx_graph,
+ to_dict_of_dicts,
+ from_dict_of_dicts,
+ to_dict_of_lists,
+ from_dict_of_lists,
+)
from networkx.generators.classic import barbell_graph, cycle_graph
-class TestConvert():
+class TestConvert:
def edgelists_equal(self, e1, e2):
return sorted(sorted(e) for e in e1) == sorted(sorted(e) for e in e2)
def test_simple_graphs(self):
- for dest, source in [(to_dict_of_dicts, from_dict_of_dicts),
- (to_dict_of_lists, from_dict_of_lists)]:
+ for dest, source in [
+ (to_dict_of_dicts, from_dict_of_dicts),
+ (to_dict_of_lists, from_dict_of_lists),
+ ]:
G = barbell_graph(10, 3)
G.graph = {}
dod = dest(G)
@@ -65,8 +69,10 @@ class TestConvert():
pytest.raises(nx.NetworkXError, to_networkx_graph, "a")
def test_digraphs(self):
- for dest, source in [(to_dict_of_dicts, from_dict_of_dicts),
- (to_dict_of_lists, from_dict_of_lists)]:
+ for dest, source in [
+ (to_dict_of_dicts, from_dict_of_dicts),
+ (to_dict_of_lists, from_dict_of_lists),
+ ]:
G = cycle_graph(10)
# Dict of [dicts, lists]
@@ -170,8 +176,7 @@ class TestConvert():
# Dict of dicts
# with multiedges, OK
dod = to_dict_of_dicts(XGM)
- GG = from_dict_of_dicts(dod, create_using=nx.MultiGraph,
- multigraph_input=True)
+ GG = from_dict_of_dicts(dod, create_using=nx.MultiGraph, multigraph_input=True)
assert_nodes_equal(sorted(XGM.nodes()), sorted(GG.nodes()))
assert_edges_equal(sorted(XGM.edges()), sorted(GG.edges()))
GW = to_networkx_graph(dod, create_using=nx.MultiGraph, multigraph_input=True)
@@ -181,8 +186,7 @@ class TestConvert():
assert_nodes_equal(sorted(XGM.nodes()), sorted(GI.nodes()))
# assert_not_equal(sorted(XGM.edges()), sorted(GI.edges()))
assert not sorted(XGM.edges()) == sorted(GI.edges())
- GE = from_dict_of_dicts(dod, create_using=nx.MultiGraph,
- multigraph_input=False)
+ GE = from_dict_of_dicts(dod, create_using=nx.MultiGraph, multigraph_input=False)
assert_nodes_equal(sorted(XGM.nodes()), sorted(GE.nodes()))
assert sorted(XGM.edges()) != sorted(GE.edges())
GI = nx.MultiGraph(XGM)
@@ -234,10 +238,12 @@ class TestConvert():
assert self.edgelists_equal(nx.MultiGraph(nx.DiGraph(edges1)).edges(), edges1)
assert self.edgelists_equal(nx.MultiGraph(nx.DiGraph(edges2)).edges(), edges1)
- assert self.edgelists_equal(nx.MultiGraph(nx.MultiDiGraph(edges1)).edges(),
- edges1)
- assert self.edgelists_equal(nx.MultiGraph(nx.MultiDiGraph(edges2)).edges(),
- edges1)
+ assert self.edgelists_equal(
+ nx.MultiGraph(nx.MultiDiGraph(edges1)).edges(), edges1
+ )
+ assert self.edgelists_equal(
+ nx.MultiGraph(nx.MultiDiGraph(edges2)).edges(), edges1
+ )
assert self.edgelists_equal(nx.Graph(nx.MultiDiGraph(edges1)).edges(), edges1)
assert self.edgelists_equal(nx.Graph(nx.MultiDiGraph(edges2)).edges(), edges1)
diff --git a/networkx/tests/test_convert_numpy.py b/networkx/tests/test_convert_numpy.py
index b6de36bd..46720306 100644
--- a/networkx/tests/test_convert_numpy.py
+++ b/networkx/tests/test_convert_numpy.py
@@ -1,5 +1,6 @@
import pytest
-np = pytest.importorskip('numpy')
+
+np = pytest.importorskip("numpy")
np_assert_equal = np.testing.assert_equal
import networkx as nx
@@ -30,7 +31,7 @@ class TestConvertNumpy:
assert sorted(G1.edges()) == sorted(G2.edges())
def identity_conversion(self, G, A, create_using):
- assert(A.sum() > 0)
+ assert A.sum() > 0
GG = nx.from_numpy_matrix(A, create_using=create_using)
self.assert_equal(G, GG)
GW = nx.to_networkx_graph(A, create_using=create_using)
@@ -107,28 +108,28 @@ class TestConvertNumpy:
A = nx.to_numpy_matrix(P4)
np_assert_equal(A, nx.to_numpy_matrix(WP4, weight=None))
np_assert_equal(0.5 * A, nx.to_numpy_matrix(WP4))
- np_assert_equal(0.3 * A, nx.to_numpy_matrix(WP4, weight='other'))
+ np_assert_equal(0.3 * A, nx.to_numpy_matrix(WP4, weight="other"))
def test_from_numpy_matrix_type(self):
A = np.matrix([[1]])
G = nx.from_numpy_matrix(A)
- assert type(G[0][0]['weight']) == int
+ assert type(G[0][0]["weight"]) == int
A = np.matrix([[1]]).astype(np.float)
G = nx.from_numpy_matrix(A)
- assert type(G[0][0]['weight']) == float
+ assert type(G[0][0]["weight"]) == float
A = np.matrix([[1]]).astype(np.str)
G = nx.from_numpy_matrix(A)
- assert type(G[0][0]['weight']) == str
+ assert type(G[0][0]["weight"]) == str
A = np.matrix([[1]]).astype(np.bool)
G = nx.from_numpy_matrix(A)
- assert type(G[0][0]['weight']) == bool
+ assert type(G[0][0]["weight"]) == bool
A = np.matrix([[1]]).astype(np.complex)
G = nx.from_numpy_matrix(A)
- assert type(G[0][0]['weight']) == complex
+ assert type(G[0][0]["weight"]) == complex
A = np.matrix([[1]]).astype(np.object)
pytest.raises(TypeError, nx.from_numpy_matrix, A)
@@ -141,19 +142,19 @@ class TestConvertNumpy:
assert all(type(m) == int and type(n) == int for m, n in H.edges())
def test_from_numpy_matrix_dtype(self):
- dt = [('weight', float), ('cost', int)]
+ dt = [("weight", float), ("cost", int)]
A = np.matrix([[(1.0, 2)]], dtype=dt)
G = nx.from_numpy_matrix(A)
- assert type(G[0][0]['weight']) == float
- assert type(G[0][0]['cost']) == int
- assert G[0][0]['cost'] == 2
- assert G[0][0]['weight'] == 1.0
+ assert type(G[0][0]["weight"]) == float
+ assert type(G[0][0]["cost"]) == int
+ assert G[0][0]["cost"] == 2
+ assert G[0][0]["weight"] == 1.0
def test_to_numpy_recarray(self):
G = nx.Graph()
G.add_edge(1, 2, weight=7.0, cost=5)
- A = nx.to_numpy_recarray(G, dtype=[('weight', float), ('cost', int)])
- assert sorted(A.dtype.names) == ['cost', 'weight']
+ A = nx.to_numpy_recarray(G, dtype=[("weight", float), ("cost", int)])
+ assert sorted(A.dtype.names) == ["cost", "weight"]
assert A.weight[0, 1] == 7.0
assert A.weight[0, 0] == 0.0
assert A.cost[0, 1] == 5
@@ -183,11 +184,9 @@ class TestConvertNumpy:
edges = [(0, 0), (0, 1), (1, 0)]
expected.add_weighted_edges_from([(u, v, 1) for (u, v) in edges])
expected.add_edge(1, 1, weight=2)
- actual = nx.from_numpy_matrix(A, parallel_edges=True,
- create_using=nx.DiGraph)
+ actual = nx.from_numpy_matrix(A, parallel_edges=True, create_using=nx.DiGraph)
assert_graphs_equal(actual, expected)
- actual = nx.from_numpy_matrix(A, parallel_edges=False,
- create_using=nx.DiGraph)
+ actual = nx.from_numpy_matrix(A, parallel_edges=False, create_using=nx.DiGraph)
assert_graphs_equal(actual, expected)
# Now each integer entry in the adjacency matrix is interpreted as the
# number of parallel edges in the graph if the appropriate keyword
@@ -195,15 +194,17 @@ class TestConvertNumpy:
edges = [(0, 0), (0, 1), (1, 0), (1, 1), (1, 1)]
expected = nx.MultiDiGraph()
expected.add_weighted_edges_from([(u, v, 1) for (u, v) in edges])
- actual = nx.from_numpy_matrix(A, parallel_edges=True,
- create_using=nx.MultiDiGraph)
+ actual = nx.from_numpy_matrix(
+ A, parallel_edges=True, create_using=nx.MultiDiGraph
+ )
assert_graphs_equal(actual, expected)
expected = nx.MultiDiGraph()
expected.add_edges_from(set(edges), weight=1)
# The sole self-loop (edge 0) on vertex 1 should have weight 2.
- expected[1][1][0]['weight'] = 2
- actual = nx.from_numpy_matrix(A, parallel_edges=False,
- create_using=nx.MultiDiGraph)
+ expected[1][1][0]["weight"] = 2
+ actual = nx.from_numpy_matrix(
+ A, parallel_edges=False, create_using=nx.MultiDiGraph
+ )
assert_graphs_equal(actual, expected)
def test_symmetric(self):
@@ -256,7 +257,7 @@ class TestConvertNumpyArray:
assert sorted(G1.edges()) == sorted(G2.edges())
def identity_conversion(self, G, A, create_using):
- assert(A.sum() > 0)
+ assert A.sum() > 0
GG = nx.from_numpy_array(A, create_using=create_using)
self.assert_equal(G, GG)
GW = nx.to_networkx_graph(A, create_using=create_using)
@@ -309,46 +310,46 @@ class TestConvertNumpyArray:
A = nx.to_numpy_array(P4)
np_assert_equal(A, nx.to_numpy_array(WP4, weight=None))
np_assert_equal(0.5 * A, nx.to_numpy_array(WP4))
- np_assert_equal(0.3 * A, nx.to_numpy_array(WP4, weight='other'))
+ np_assert_equal(0.3 * A, nx.to_numpy_array(WP4, weight="other"))
def test_from_numpy_array_type(self):
A = np.array([[1]])
G = nx.from_numpy_array(A)
- assert type(G[0][0]['weight']) == int
+ assert type(G[0][0]["weight"]) == int
A = np.array([[1]]).astype(np.float)
G = nx.from_numpy_array(A)
- assert type(G[0][0]['weight']) == float
+ assert type(G[0][0]["weight"]) == float
A = np.array([[1]]).astype(np.str)
G = nx.from_numpy_array(A)
- assert type(G[0][0]['weight']) == str
+ assert type(G[0][0]["weight"]) == str
A = np.array([[1]]).astype(np.bool)
G = nx.from_numpy_array(A)
- assert type(G[0][0]['weight']) == bool
+ assert type(G[0][0]["weight"]) == bool
A = np.array([[1]]).astype(np.complex)
G = nx.from_numpy_array(A)
- assert type(G[0][0]['weight']) == complex
+ assert type(G[0][0]["weight"]) == complex
A = np.array([[1]]).astype(np.object)
pytest.raises(TypeError, nx.from_numpy_array, A)
def test_from_numpy_array_dtype(self):
- dt = [('weight', float), ('cost', int)]
+ dt = [("weight", float), ("cost", int)]
A = np.array([[(1.0, 2)]], dtype=dt)
G = nx.from_numpy_array(A)
- assert type(G[0][0]['weight']) == float
- assert type(G[0][0]['cost']) == int
- assert G[0][0]['cost'] == 2
- assert G[0][0]['weight'] == 1.0
+ assert type(G[0][0]["weight"]) == float
+ assert type(G[0][0]["cost"]) == int
+ assert G[0][0]["cost"] == 2
+ assert G[0][0]["weight"] == 1.0
def test_to_numpy_recarray(self):
G = nx.Graph()
G.add_edge(1, 2, weight=7.0, cost=5)
- A = nx.to_numpy_recarray(G, dtype=[('weight', float), ('cost', int)])
- assert sorted(A.dtype.names) == ['cost', 'weight']
+ A = nx.to_numpy_recarray(G, dtype=[("weight", float), ("cost", int)])
+ assert sorted(A.dtype.names) == ["cost", "weight"]
assert A.weight[0, 1] == 7.0
assert A.weight[0, 0] == 0.0
assert A.cost[0, 1] == 5
@@ -378,11 +379,9 @@ class TestConvertNumpyArray:
edges = [(0, 0), (0, 1), (1, 0)]
expected.add_weighted_edges_from([(u, v, 1) for (u, v) in edges])
expected.add_edge(1, 1, weight=2)
- actual = nx.from_numpy_array(A, parallel_edges=True,
- create_using=nx.DiGraph)
+ actual = nx.from_numpy_array(A, parallel_edges=True, create_using=nx.DiGraph)
assert_graphs_equal(actual, expected)
- actual = nx.from_numpy_array(A, parallel_edges=False,
- create_using=nx.DiGraph)
+ actual = nx.from_numpy_array(A, parallel_edges=False, create_using=nx.DiGraph)
assert_graphs_equal(actual, expected)
# Now each integer entry in the adjacency matrix is interpreted as the
# number of parallel edges in the graph if the appropriate keyword
@@ -390,15 +389,17 @@ class TestConvertNumpyArray:
edges = [(0, 0), (0, 1), (1, 0), (1, 1), (1, 1)]
expected = nx.MultiDiGraph()
expected.add_weighted_edges_from([(u, v, 1) for (u, v) in edges])
- actual = nx.from_numpy_array(A, parallel_edges=True,
- create_using=nx.MultiDiGraph)
+ actual = nx.from_numpy_array(
+ A, parallel_edges=True, create_using=nx.MultiDiGraph
+ )
assert_graphs_equal(actual, expected)
expected = nx.MultiDiGraph()
expected.add_edges_from(set(edges), weight=1)
# The sole self-loop (edge 0) on vertex 1 should have weight 2.
- expected[1][1][0]['weight'] = 2
- actual = nx.from_numpy_array(A, parallel_edges=False,
- create_using=nx.MultiDiGraph)
+ expected[1][1][0]["weight"] = 2
+ actual = nx.from_numpy_array(
+ A, parallel_edges=False, create_using=nx.MultiDiGraph
+ )
assert_graphs_equal(actual, expected)
def test_symmetric(self):
diff --git a/networkx/tests/test_convert_scipy.py b/networkx/tests/test_convert_scipy.py
index 0ddd72e8..f001e5ab 100644
--- a/networkx/tests/test_convert_scipy.py
+++ b/networkx/tests/test_convert_scipy.py
@@ -9,8 +9,8 @@ class TestConvertNumpy:
@classmethod
def setup_class(cls):
global np, sp, sparse, np_assert_equal
- np = pytest.importorskip('numpy')
- sp = pytest.importorskip('scipy')
+ np = pytest.importorskip("numpy")
+ sp = pytest.importorskip("scipy")
sparse = sp.sparse
np_assert_equal = np.testing.assert_equal
@@ -106,62 +106,68 @@ class TestConvertNumpy:
# Make nodelist ambiguous by containing duplicates.
nodelist += [nodelist[0]]
- pytest.raises(nx.NetworkXError, nx.to_numpy_matrix, P3,
- nodelist=nodelist)
+ pytest.raises(nx.NetworkXError, nx.to_numpy_matrix, P3, nodelist=nodelist)
def test_weight_keyword(self):
WP4 = nx.Graph()
- WP4.add_edges_from((n, n + 1, dict(weight=0.5, other=0.3))
- for n in range(3))
+ WP4.add_edges_from((n, n + 1, dict(weight=0.5, other=0.3)) for n in range(3))
P4 = path_graph(4)
A = nx.to_scipy_sparse_matrix(P4)
- np_assert_equal(A.todense(),
- nx.to_scipy_sparse_matrix(WP4, weight=None).todense())
- np_assert_equal(0.5 * A.todense(),
- nx.to_scipy_sparse_matrix(WP4).todense())
- np_assert_equal(0.3 * A.todense(),
- nx.to_scipy_sparse_matrix(WP4, weight='other').todense())
+ np_assert_equal(
+ A.todense(), nx.to_scipy_sparse_matrix(WP4, weight=None).todense()
+ )
+ np_assert_equal(0.5 * A.todense(), nx.to_scipy_sparse_matrix(WP4).todense())
+ np_assert_equal(
+ 0.3 * A.todense(), nx.to_scipy_sparse_matrix(WP4, weight="other").todense()
+ )
def test_format_keyword(self):
WP4 = nx.Graph()
- WP4.add_edges_from((n, n + 1, dict(weight=0.5, other=0.3))
- for n in range(3))
+ WP4.add_edges_from((n, n + 1, dict(weight=0.5, other=0.3)) for n in range(3))
P4 = path_graph(4)
- A = nx.to_scipy_sparse_matrix(P4, format='csr')
- np_assert_equal(A.todense(),
- nx.to_scipy_sparse_matrix(WP4, weight=None).todense())
-
- A = nx.to_scipy_sparse_matrix(P4, format='csc')
- np_assert_equal(A.todense(),
- nx.to_scipy_sparse_matrix(WP4, weight=None).todense())
-
- A = nx.to_scipy_sparse_matrix(P4, format='coo')
- np_assert_equal(A.todense(),
- nx.to_scipy_sparse_matrix(WP4, weight=None).todense())
-
- A = nx.to_scipy_sparse_matrix(P4, format='bsr')
- np_assert_equal(A.todense(),
- nx.to_scipy_sparse_matrix(WP4, weight=None).todense())
-
- A = nx.to_scipy_sparse_matrix(P4, format='lil')
- np_assert_equal(A.todense(),
- nx.to_scipy_sparse_matrix(WP4, weight=None).todense())
-
- A = nx.to_scipy_sparse_matrix(P4, format='dia')
- np_assert_equal(A.todense(),
- nx.to_scipy_sparse_matrix(WP4, weight=None).todense())
-
- A = nx.to_scipy_sparse_matrix(P4, format='dok')
- np_assert_equal(A.todense(),
- nx.to_scipy_sparse_matrix(WP4, weight=None).todense())
+ A = nx.to_scipy_sparse_matrix(P4, format="csr")
+ np_assert_equal(
+ A.todense(), nx.to_scipy_sparse_matrix(WP4, weight=None).todense()
+ )
+
+ A = nx.to_scipy_sparse_matrix(P4, format="csc")
+ np_assert_equal(
+ A.todense(), nx.to_scipy_sparse_matrix(WP4, weight=None).todense()
+ )
+
+ A = nx.to_scipy_sparse_matrix(P4, format="coo")
+ np_assert_equal(
+ A.todense(), nx.to_scipy_sparse_matrix(WP4, weight=None).todense()
+ )
+
+ A = nx.to_scipy_sparse_matrix(P4, format="bsr")
+ np_assert_equal(
+ A.todense(), nx.to_scipy_sparse_matrix(WP4, weight=None).todense()
+ )
+
+ A = nx.to_scipy_sparse_matrix(P4, format="lil")
+ np_assert_equal(
+ A.todense(), nx.to_scipy_sparse_matrix(WP4, weight=None).todense()
+ )
+
+ A = nx.to_scipy_sparse_matrix(P4, format="dia")
+ np_assert_equal(
+ A.todense(), nx.to_scipy_sparse_matrix(WP4, weight=None).todense()
+ )
+
+ A = nx.to_scipy_sparse_matrix(P4, format="dok")
+ np_assert_equal(
+ A.todense(), nx.to_scipy_sparse_matrix(WP4, weight=None).todense()
+ )
def test_format_keyword_raise(self):
with pytest.raises(nx.NetworkXError):
WP4 = nx.Graph()
- WP4.add_edges_from((n, n + 1, dict(weight=0.5, other=0.3))
- for n in range(3))
+ WP4.add_edges_from(
+ (n, n + 1, dict(weight=0.5, other=0.3)) for n in range(3)
+ )
P4 = path_graph(4)
- nx.to_scipy_sparse_matrix(P4, format='any_other')
+ nx.to_scipy_sparse_matrix(P4, format="any_other")
def test_null_raise(self):
with pytest.raises(nx.NetworkXError):
@@ -204,11 +210,13 @@ class TestConvertNumpy:
edges = [(0, 0), (0, 1), (1, 0)]
expected.add_weighted_edges_from([(u, v, 1) for (u, v) in edges])
expected.add_edge(1, 1, weight=2)
- actual = nx.from_scipy_sparse_matrix(A, parallel_edges=True,
- create_using=nx.DiGraph)
+ actual = nx.from_scipy_sparse_matrix(
+ A, parallel_edges=True, create_using=nx.DiGraph
+ )
assert_graphs_equal(actual, expected)
- actual = nx.from_scipy_sparse_matrix(A, parallel_edges=False,
- create_using=nx.DiGraph)
+ actual = nx.from_scipy_sparse_matrix(
+ A, parallel_edges=False, create_using=nx.DiGraph
+ )
assert_graphs_equal(actual, expected)
# Now each integer entry in the adjacency matrix is interpreted as the
# number of parallel edges in the graph if the appropriate keyword
@@ -216,15 +224,17 @@ class TestConvertNumpy:
edges = [(0, 0), (0, 1), (1, 0), (1, 1), (1, 1)]
expected = nx.MultiDiGraph()
expected.add_weighted_edges_from([(u, v, 1) for (u, v) in edges])
- actual = nx.from_scipy_sparse_matrix(A, parallel_edges=True,
- create_using=nx.MultiDiGraph)
+ actual = nx.from_scipy_sparse_matrix(
+ A, parallel_edges=True, create_using=nx.MultiDiGraph
+ )
assert_graphs_equal(actual, expected)
expected = nx.MultiDiGraph()
expected.add_edges_from(set(edges), weight=1)
# The sole self-loop (edge 0) on vertex 1 should have weight 2.
- expected[1][1][0]['weight'] = 2
- actual = nx.from_scipy_sparse_matrix(A, parallel_edges=False,
- create_using=nx.MultiDiGraph)
+ expected[1][1][0]["weight"] = 2
+ actual = nx.from_scipy_sparse_matrix(
+ A, parallel_edges=False, create_using=nx.MultiDiGraph
+ )
assert_graphs_equal(actual, expected)
def test_symmetric(self):
diff --git a/networkx/tests/test_relabel.py b/networkx/tests/test_relabel.py
index bad58272..9b8ad299 100644
--- a/networkx/tests/test_relabel.py
+++ b/networkx/tests/test_relabel.py
@@ -4,7 +4,7 @@ from networkx.generators.classic import empty_graph
from networkx.testing import assert_nodes_equal, assert_edges_equal
-class TestRelabel():
+class TestRelabel:
def test_convert_node_labels_to_integers(self):
# test that empty graph converts fine for all options
G = empty_graph()
@@ -19,7 +19,7 @@ class TestRelabel():
assert list(H.edges()) == []
G = empty_graph()
- G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'D')])
+ G.add_edges_from([("A", "B"), ("A", "C"), ("B", "C"), ("C", "D")])
H = nx.convert_node_labels_to_integers(G)
degH = (d for n, d in H.degree())
degG = (d for n, d in G.degree())
@@ -49,8 +49,9 @@ class TestRelabel():
assert H.degree(2) == 2
assert H.degree(3) == 1
- H = nx.convert_node_labels_to_integers(G, ordering="increasing degree",
- label_attribute='label')
+ H = nx.convert_node_labels_to_integers(
+ G, ordering="increasing degree", label_attribute="label"
+ )
degH = (d for n, d in H.degree())
degG = (d for n, d in G.degree())
assert sorted(degH) == sorted(degG)
@@ -60,25 +61,26 @@ class TestRelabel():
assert H.degree(3) == 3
# check mapping
- assert H.nodes[3]['label'] == 'C'
- assert H.nodes[0]['label'] == 'D'
- assert H.nodes[1]['label'] == 'A' or H.nodes[2]['label'] == 'A'
- assert H.nodes[1]['label'] == 'B' or H.nodes[2]['label'] == 'B'
+ assert H.nodes[3]["label"] == "C"
+ assert H.nodes[0]["label"] == "D"
+ assert H.nodes[1]["label"] == "A" or H.nodes[2]["label"] == "A"
+ assert H.nodes[1]["label"] == "B" or H.nodes[2]["label"] == "B"
def test_convert_to_integers2(self):
G = empty_graph()
- G.add_edges_from([('C', 'D'), ('A', 'B'), ('A', 'C'), ('B', 'C')])
+ G.add_edges_from([("C", "D"), ("A", "B"), ("A", "C"), ("B", "C")])
H = nx.convert_node_labels_to_integers(G, ordering="sorted")
degH = (d for n, d in H.degree())
degG = (d for n, d in G.degree())
assert sorted(degH) == sorted(degG)
- H = nx.convert_node_labels_to_integers(G, ordering="sorted",
- label_attribute='label')
- assert H.nodes[0]['label'] == 'A'
- assert H.nodes[1]['label'] == 'B'
- assert H.nodes[2]['label'] == 'C'
- assert H.nodes[3]['label'] == 'D'
+ H = nx.convert_node_labels_to_integers(
+ G, ordering="sorted", label_attribute="label"
+ )
+ assert H.nodes[0]["label"] == "A"
+ assert H.nodes[1]["label"] == "B"
+ assert H.nodes[2]["label"] == "C"
+ assert H.nodes[3]["label"] == "D"
def test_convert_to_integers_raise(self):
with pytest.raises(nx.NetworkXError):
@@ -87,54 +89,55 @@ class TestRelabel():
def test_relabel_nodes_copy(self):
G = nx.empty_graph()
- G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'D')])
- mapping = {'A': 'aardvark', 'B': 'bear', 'C': 'cat', 'D': 'dog'}
+ G.add_edges_from([("A", "B"), ("A", "C"), ("B", "C"), ("C", "D")])
+ mapping = {"A": "aardvark", "B": "bear", "C": "cat", "D": "dog"}
H = nx.relabel_nodes(G, mapping)
- assert_nodes_equal(H.nodes(), ['aardvark', 'bear', 'cat', 'dog'])
+ assert_nodes_equal(H.nodes(), ["aardvark", "bear", "cat", "dog"])
def test_relabel_nodes_function(self):
G = nx.empty_graph()
- G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'D')])
+ G.add_edges_from([("A", "B"), ("A", "C"), ("B", "C"), ("C", "D")])
# function mapping no longer encouraged but works
def mapping(n):
return ord(n)
+
H = nx.relabel_nodes(G, mapping)
assert_nodes_equal(H.nodes(), [65, 66, 67, 68])
def test_relabel_nodes_graph(self):
- G = nx.Graph([('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'D')])
- mapping = {'A': 'aardvark', 'B': 'bear', 'C': 'cat', 'D': 'dog'}
+ G = nx.Graph([("A", "B"), ("A", "C"), ("B", "C"), ("C", "D")])
+ mapping = {"A": "aardvark", "B": "bear", "C": "cat", "D": "dog"}
H = nx.relabel_nodes(G, mapping)
- assert_nodes_equal(H.nodes(), ['aardvark', 'bear', 'cat', 'dog'])
+ assert_nodes_equal(H.nodes(), ["aardvark", "bear", "cat", "dog"])
def test_relabel_nodes_orderedgraph(self):
G = nx.OrderedGraph()
G.add_nodes_from([1, 2, 3])
G.add_edges_from([(1, 3), (2, 3)])
- mapping = {1: 'a', 2: 'b', 3: 'c'}
+ mapping = {1: "a", 2: "b", 3: "c"}
H = nx.relabel_nodes(G, mapping)
- assert list(H.nodes) == ['a', 'b', 'c']
+ assert list(H.nodes) == ["a", "b", "c"]
def test_relabel_nodes_digraph(self):
- G = nx.DiGraph([('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'D')])
- mapping = {'A': 'aardvark', 'B': 'bear', 'C': 'cat', 'D': 'dog'}
+ G = nx.DiGraph([("A", "B"), ("A", "C"), ("B", "C"), ("C", "D")])
+ mapping = {"A": "aardvark", "B": "bear", "C": "cat", "D": "dog"}
H = nx.relabel_nodes(G, mapping, copy=False)
- assert_nodes_equal(H.nodes(), ['aardvark', 'bear', 'cat', 'dog'])
+ assert_nodes_equal(H.nodes(), ["aardvark", "bear", "cat", "dog"])
def test_relabel_nodes_multigraph(self):
- G = nx.MultiGraph([('a', 'b'), ('a', 'b')])
- mapping = {'a': 'aardvark', 'b': 'bear'}
+ G = nx.MultiGraph([("a", "b"), ("a", "b")])
+ mapping = {"a": "aardvark", "b": "bear"}
G = nx.relabel_nodes(G, mapping, copy=False)
- assert_nodes_equal(G.nodes(), ['aardvark', 'bear'])
- assert_edges_equal(G.edges(), [('aardvark', 'bear'), ('aardvark', 'bear')])
+ assert_nodes_equal(G.nodes(), ["aardvark", "bear"])
+ assert_edges_equal(G.edges(), [("aardvark", "bear"), ("aardvark", "bear")])
def test_relabel_nodes_multidigraph(self):
- G = nx.MultiDiGraph([('a', 'b'), ('a', 'b')])
- mapping = {'a': 'aardvark', 'b': 'bear'}
+ G = nx.MultiDiGraph([("a", "b"), ("a", "b")])
+ mapping = {"a": "aardvark", "b": "bear"}
G = nx.relabel_nodes(G, mapping, copy=False)
- assert_nodes_equal(G.nodes(), ['aardvark', 'bear'])
- assert_edges_equal(G.edges(), [('aardvark', 'bear'), ('aardvark', 'bear')])
+ assert_nodes_equal(G.nodes(), ["aardvark", "bear"])
+ assert_edges_equal(G.edges(), [("aardvark", "bear"), ("aardvark", "bear")])
def test_relabel_isolated_nodes_to_same(self):
G = nx.Graph()
@@ -145,8 +148,8 @@ class TestRelabel():
def test_relabel_nodes_missing(self):
with pytest.raises(KeyError):
- G = nx.Graph([('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'D')])
- mapping = {0: 'aardvark'}
+ G = nx.Graph([("A", "B"), ("A", "C"), ("B", "C"), ("C", "D")])
+ mapping = {0: "aardvark"}
G = nx.relabel_nodes(G, mapping, copy=False)
def test_relabel_copy_name(self):
@@ -172,11 +175,11 @@ class TestRelabel():
def test_relabel_selfloop(self):
G = nx.DiGraph([(1, 1), (1, 2), (2, 3)])
- G = nx.relabel_nodes(G, {1: 'One', 2: 'Two', 3: 'Three'}, copy=False)
- assert_nodes_equal(G.nodes(), ['One', 'Three', 'Two'])
+ G = nx.relabel_nodes(G, {1: "One", 2: "Two", 3: "Three"}, copy=False)
+ assert_nodes_equal(G.nodes(), ["One", "Three", "Two"])
G = nx.MultiDiGraph([(1, 1), (1, 2), (2, 3)])
- G = nx.relabel_nodes(G, {1: 'One', 2: 'Two', 3: 'Three'}, copy=False)
- assert_nodes_equal(G.nodes(), ['One', 'Three', 'Two'])
+ G = nx.relabel_nodes(G, {1: "One", 2: "Two", 3: "Three"}, copy=False)
+ assert_nodes_equal(G.nodes(), ["One", "Three", "Two"])
G = nx.MultiDiGraph([(1, 1)])
G = nx.relabel_nodes(G, {1: 0}, copy=False)
assert_nodes_equal(G.nodes(), [0])