diff options
Diffstat (limited to 'networkx')
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]) |