From c5c8bfc0989aa6abf0765a4a80a724de67b21972 Mon Sep 17 00:00:00 2001 From: Ludovic Stephan Date: Thu, 20 May 2021 05:04:32 +0200 Subject: =?UTF-8?q?Add=20`initial=5Fgraph`=20parameter=20to=20simple=20and?= =?UTF-8?q?=20dual=20Bar=C3=A1basi-Albert=20random=20graphs=20(#4659)?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Adds an initial_graph parameter to allow users to specify a base graph to the BA and dual BA genertors. Co-authored-by: Ludovic Stephan Co-authored-by: Dan Schult --- doc/release/release_dev.rst | 3 + networkx/generators/random_graphs.py | 106 ++++++++----- networkx/generators/tests/test_random_graphs.py | 203 ++++++++++++------------ 3 files changed, 167 insertions(+), 145 deletions(-) diff --git a/doc/release/release_dev.rst b/doc/release/release_dev.rst index 0fdce5dd..2a0eaeef 100644 --- a/doc/release/release_dev.rst +++ b/doc/release/release_dev.rst @@ -34,6 +34,9 @@ Improvements - [`#4640 `_] ``prefix_tree`` now uses a non-recursive algorithm. The original recursive algorithm is still available via ``prefix_tree_recursive``. +- [`#4659 `_] + New ``initial_graph`` argument to ``barabasi_albert_graph`` and + ``dual_barabasi_albert_graph`` to supply an initial graph to the model. API Changes ----------- diff --git a/networkx/generators/random_graphs.py b/networkx/generators/random_graphs.py index 5e1a2f06..4a658f8f 100644 --- a/networkx/generators/random_graphs.py +++ b/networkx/generators/random_graphs.py @@ -5,12 +5,13 @@ Generators for random graphs. import itertools import math +from collections import defaultdict import networkx as nx from networkx.utils import py_random_state -from .classic import empty_graph, path_graph, complete_graph + +from .classic import complete_graph, empty_graph, path_graph, star_graph from .degree_seq import degree_sequence_tree -from collections import defaultdict __all__ = [ "fast_gnp_random_graph", @@ -615,9 +616,8 @@ def _random_subset(seq, m, rng): @py_random_state(2) -def barabasi_albert_graph(n, m, seed=None): - """Returns a random graph according to the Barabási–Albert preferential - attachment model. +def barabasi_albert_graph(n, m, seed=None, initial_graph=None): + """Returns a random graph using Barabási–Albert preferential attachment A graph of $n$ nodes is grown by attaching new nodes each with $m$ edges that are preferentially attached to existing nodes with high degree. @@ -631,6 +631,11 @@ def barabasi_albert_graph(n, m, seed=None): seed : integer, random_state, or None (default) Indicator of random number generation state. See :ref:`Randomness`. + initial_graph : Graph or None (default) + Initial network for Barabási–Albert algorithm. + It should be a connected graph for most use cases. + A copy of `initial_graph` is used. + If None, starts from a star graph on (m+1) nodes. Returns ------- @@ -639,7 +644,8 @@ def barabasi_albert_graph(n, m, seed=None): Raises ------ NetworkXError - If `m` does not satisfy ``1 <= m < n``. + If `m` does not satisfy ``1 <= m < n``, or + the initial graph number of nodes m0 does not satisfy ``m <= m0 <= n``. References ---------- @@ -652,32 +658,38 @@ def barabasi_albert_graph(n, m, seed=None): f"Barabási–Albert network must have m >= 1 and m < n, m = {m}, n = {n}" ) - # Add m initial nodes (m0 in barabasi-speak) - G = empty_graph(m) - # Target nodes for new edges - targets = list(range(m)) + if initial_graph is None: + # Default initial graph : star graph on (m + 1) nodes + G = star_graph(m) + else: + if len(initial_graph) < m or len(initial_graph) > n: + raise nx.NetworkXError( + f"Barabási–Albert initial graph needs between m={m} and n={n} nodes" + ) + G = initial_graph.copy() + # List of existing nodes, with nodes repeated once for each adjacent edge - repeated_nodes = [] - # Start adding the other n-m nodes. The first node is m. - source = m + repeated_nodes = [n for n, d in G.degree() for _ in range(d)] + # Start adding the other n - m0 nodes. + source = len(G) while source < n: + # Now choose m unique nodes from the existing nodes + # Pick uniformly from repeated_nodes (preferential attachment) + targets = _random_subset(repeated_nodes, m, seed) # Add edges to m nodes from the source. G.add_edges_from(zip([source] * m, targets)) # Add one node to the list for each new edge just created. repeated_nodes.extend(targets) # And the new node "source" has m edges to add to the list. repeated_nodes.extend([source] * m) - # Now choose m unique nodes from the existing nodes - # Pick uniformly from repeated_nodes (preferential attachment) - targets = _random_subset(repeated_nodes, m, seed) + source += 1 return G @py_random_state(4) -def dual_barabasi_albert_graph(n, m1, m2, p, seed=None): - """Returns a random graph according to the dual Barabási–Albert preferential - attachment model. +def dual_barabasi_albert_graph(n, m1, m2, p, seed=None, initial_graph=None): + """Returns a random graph using dual Barabási–Albert preferential attachment A graph of $n$ nodes is grown by attaching new nodes each with either $m_1$ edges (with probability $p$) or $m_2$ edges (with probability $1-p$) that @@ -688,14 +700,19 @@ def dual_barabasi_albert_graph(n, m1, m2, p, seed=None): n : int Number of nodes m1 : int - Number of edges to attach from a new node to existing nodes with probability $p$ + Number of edges to link each new node to existing nodes with probability $p$ m2 : int - Number of edges to attach from a new node to existing nodes with probability $1-p$ + Number of edges to link each new node to existing nodes with probability $1-p$ p : float The probability of attaching $m_1$ edges (as opposed to $m_2$ edges) seed : integer, random_state, or None (default) Indicator of random number generation state. See :ref:`Randomness`. + initial_graph : Graph or None (default) + Initial network for Barabási–Albert algorithm. + A copy of `initial_graph` is used. + It should be connected for most use cases. + If None, starts from an star graph on max(m1, m2) + 1 nodes. Returns ------- @@ -704,7 +721,9 @@ def dual_barabasi_albert_graph(n, m1, m2, p, seed=None): Raises ------ NetworkXError - If `m1` and `m2` do not satisfy ``1 <= m1,m2 < n`` or `p` does not satisfy ``0 <= p <= 1``. + If `m1` and `m2` do not satisfy ``1 <= m1,m2 < n``, or + `p` does not satisfy ``0 <= p <= 1``, or + the initial graph number of nodes m0 does not satisfy m1, m2 <= m0 <= n. References ---------- @@ -713,11 +732,11 @@ def dual_barabasi_albert_graph(n, m1, m2, p, seed=None): if m1 < 1 or m1 >= n: raise nx.NetworkXError( - f"Dual Barabási–Albert network must have m1 >= 1 and m1 < n, m1 = {m1}, n = {n}" + f"Dual Barabási–Albert must have m1 >= 1 and m1 < n, m1 = {m1}, n = {n}" ) if m2 < 1 or m2 >= n: raise nx.NetworkXError( - f"Dual Barabási–Albert network must have m2 >= 1 and m2 < n, m2 = {m2}, n = {n}" + f"Dual Barabási–Albert must have m2 >= 1 and m2 < n, m2 = {m2}, n = {n}" ) if p < 0 or p > 1: raise nx.NetworkXError( @@ -730,27 +749,25 @@ def dual_barabasi_albert_graph(n, m1, m2, p, seed=None): elif p == 0: return barabasi_albert_graph(n, m2, seed) - # Add max(m1,m2) initial nodes (m0 in barabasi-speak) - G = empty_graph(max(m1, m2)) + if initial_graph is None: + # Default initial graph : empty graph on max(m1, m2) nodes + G = star_graph(max(m1, m2)) + else: + if len(initial_graph) < max(m1, m2) or len(initial_graph) > n: + raise nx.NetworkXError( + f"Barabási–Albert initial graph must have between " + f"max(m1, m2) = {max(m1, m2)} and n = {n} nodes" + ) + G = initial_graph.copy() + # Target nodes for new edges - targets = list(range(max(m1, m2))) + targets = list(G) # List of existing nodes, with nodes repeated once for each adjacent edge - repeated_nodes = [] + repeated_nodes = [n for n, d in G.degree() for _ in range(d)] # Start adding the remaining nodes. - source = max(m1, m2) - # Pick which m to use first time (m1 or m2) - if seed.random() < p: - m = m1 - else: - m = m2 + source = len(G) while source < n: - # Add edges to m nodes from the source. - G.add_edges_from(zip([source] * m, targets)) - # Add one node to the list for each new edge just created. - repeated_nodes.extend(targets) - # And the new node "source" has m edges to add to the list. - repeated_nodes.extend([source] * m) - # Pick which m to use next time (m1 or m2) + # Pick which m to use (m1 or m2) if seed.random() < p: m = m1 else: @@ -758,6 +775,13 @@ def dual_barabasi_albert_graph(n, m1, m2, p, seed=None): # Now choose m unique nodes from the existing nodes # Pick uniformly from repeated_nodes (preferential attachment) targets = _random_subset(repeated_nodes, m, seed) + # Add edges to m nodes from the source. + G.add_edges_from(zip([source] * m, targets)) + # Add one node to the list for each new edge just created. + repeated_nodes.extend(targets) + # And the new node "source" has m edges to add to the list. + repeated_nodes.extend([source] * m) + source += 1 return G diff --git a/networkx/generators/tests/test_random_graphs.py b/networkx/generators/tests/test_random_graphs.py index 6835e880..d0068cd6 100644 --- a/networkx/generators/tests/test_random_graphs.py +++ b/networkx/generators/tests/test_random_graphs.py @@ -1,95 +1,78 @@ """Unit tests for the :mod:`networkx.generators.random_graphs` module. """ +import networkx as nx import pytest -from networkx.exception import NetworkXError -from networkx.generators.random_graphs import barabasi_albert_graph -from networkx.generators.random_graphs import dual_barabasi_albert_graph -from networkx.generators.random_graphs import extended_barabasi_albert_graph -from networkx.generators.random_graphs import binomial_graph -from networkx.generators.random_graphs import connected_watts_strogatz_graph -from networkx.generators.random_graphs import dense_gnm_random_graph -from networkx.generators.random_graphs import erdos_renyi_graph -from networkx.generators.random_graphs import fast_gnp_random_graph -from networkx.generators.random_graphs import gnm_random_graph -from networkx.generators.random_graphs import gnp_random_graph -from networkx.generators.random_graphs import newman_watts_strogatz_graph -from networkx.generators.random_graphs import powerlaw_cluster_graph -from networkx.generators.random_graphs import random_kernel_graph -from networkx.generators.random_graphs import random_lobster -from networkx.generators.random_graphs import random_powerlaw_tree -from networkx.generators.random_graphs import random_powerlaw_tree_sequence -from networkx.generators.random_graphs import random_regular_graph -from networkx.generators.random_graphs import random_shell_graph -from networkx.generators.random_graphs import watts_strogatz_graph - class TestGeneratorsRandom: def test_random_graph(self): seed = 42 - G = gnp_random_graph(100, 0.25, seed) - G = gnp_random_graph(100, 0.25, seed, directed=True) - G = binomial_graph(100, 0.25, seed) - G = erdos_renyi_graph(100, 0.25, seed) - G = fast_gnp_random_graph(100, 0.25, seed) - G = fast_gnp_random_graph(100, 0.25, seed, directed=True) - G = gnm_random_graph(100, 20, seed) - G = gnm_random_graph(100, 20, seed, directed=True) - G = dense_gnm_random_graph(100, 20, seed) - - G = watts_strogatz_graph(10, 2, 0.25, seed) + G = nx.gnp_random_graph(100, 0.25, seed) + G = nx.gnp_random_graph(100, 0.25, seed, directed=True) + G = nx.binomial_graph(100, 0.25, seed) + G = nx.erdos_renyi_graph(100, 0.25, seed) + G = nx.fast_gnp_random_graph(100, 0.25, seed) + G = nx.fast_gnp_random_graph(100, 0.25, seed, directed=True) + G = nx.gnm_random_graph(100, 20, seed) + G = nx.gnm_random_graph(100, 20, seed, directed=True) + G = nx.dense_gnm_random_graph(100, 20, seed) + + G = nx.watts_strogatz_graph(10, 2, 0.25, seed) assert len(G) == 10 assert G.number_of_edges() == 10 - G = connected_watts_strogatz_graph(10, 2, 0.1, tries=10, seed=seed) + G = nx.connected_watts_strogatz_graph(10, 2, 0.1, tries=10, seed=seed) assert len(G) == 10 assert G.number_of_edges() == 10 pytest.raises( - NetworkXError, connected_watts_strogatz_graph, 10, 2, 0.1, tries=0 + nx.NetworkXError, nx.connected_watts_strogatz_graph, 10, 2, 0.1, tries=0 ) - G = watts_strogatz_graph(10, 4, 0.25, seed) + G = nx.watts_strogatz_graph(10, 4, 0.25, seed) assert len(G) == 10 assert G.number_of_edges() == 20 - G = newman_watts_strogatz_graph(10, 2, 0.0, seed) + G = nx.newman_watts_strogatz_graph(10, 2, 0.0, seed) assert len(G) == 10 assert G.number_of_edges() == 10 - G = newman_watts_strogatz_graph(10, 4, 0.25, seed) + G = nx.newman_watts_strogatz_graph(10, 4, 0.25, seed) assert len(G) == 10 assert G.number_of_edges() >= 20 - G = barabasi_albert_graph(100, 1, seed) - G = barabasi_albert_graph(100, 3, seed) + G = nx.barabasi_albert_graph(100, 1, seed) + G = nx.barabasi_albert_graph(100, 3, seed) assert G.number_of_edges() == (97 * 3) - G = extended_barabasi_albert_graph(100, 1, 0, 0, seed) + G = nx.barabasi_albert_graph(100, 3, seed, nx.complete_graph(5)) + assert G.number_of_edges() == (10 + 95 * 3) + + G = nx.extended_barabasi_albert_graph(100, 1, 0, 0, seed) assert G.number_of_edges() == 99 - G = extended_barabasi_albert_graph(100, 3, 0, 0, seed) + G = nx.extended_barabasi_albert_graph(100, 3, 0, 0, seed) assert G.number_of_edges() == 97 * 3 - G = extended_barabasi_albert_graph(100, 1, 0, 0.5, seed) + G = nx.extended_barabasi_albert_graph(100, 1, 0, 0.5, seed) assert G.number_of_edges() == 99 - G = extended_barabasi_albert_graph(100, 2, 0.5, 0, seed) + G = nx.extended_barabasi_albert_graph(100, 2, 0.5, 0, seed) assert G.number_of_edges() > 100 * 3 assert G.number_of_edges() < 100 * 4 - G = extended_barabasi_albert_graph(100, 2, 0.3, 0.3, seed) + G = nx.extended_barabasi_albert_graph(100, 2, 0.3, 0.3, seed) assert G.number_of_edges() > 100 * 2 assert G.number_of_edges() < 100 * 4 - G = powerlaw_cluster_graph(100, 1, 1.0, seed) - G = powerlaw_cluster_graph(100, 3, 0.0, seed) + G = nx.powerlaw_cluster_graph(100, 1, 1.0, seed) + G = nx.powerlaw_cluster_graph(100, 3, 0.0, seed) assert G.number_of_edges() == (97 * 3) - G = random_regular_graph(10, 20, seed) + G = nx.random_regular_graph(10, 20, seed) - pytest.raises(NetworkXError, random_regular_graph, 3, 21) - pytest.raises(NetworkXError, random_regular_graph, 33, 21) + pytest.raises(nx.NetworkXError, nx.random_regular_graph, 3, 21) + pytest.raises(nx.NetworkXError, nx.random_regular_graph, 33, 21) constructor = [(10, 20, 0.8), (20, 40, 0.8)] - G = random_shell_graph(constructor, seed) + G = nx.random_shell_graph(constructor, seed) def is_caterpillar(g): """ @@ -113,20 +96,20 @@ class TestGeneratorsRandom: non_leafs = [n for n in g if g.degree(n) > 1] return is_caterpillar(g.subgraph(non_leafs)) - G = random_lobster(10, 0.1, 0.5, seed) + G = nx.random_lobster(10, 0.1, 0.5, seed) assert max([G.degree(n) for n in G.nodes()]) > 3 assert is_lobster(G) - pytest.raises(NetworkXError, random_lobster, 10, 0.1, 1, seed) - pytest.raises(NetworkXError, random_lobster, 10, 1, 1, seed) - pytest.raises(NetworkXError, random_lobster, 10, 1, 0.5, seed) + pytest.raises(nx.NetworkXError, nx.random_lobster, 10, 0.1, 1, seed) + pytest.raises(nx.NetworkXError, nx.random_lobster, 10, 1, 1, seed) + pytest.raises(nx.NetworkXError, nx.random_lobster, 10, 1, 0.5, seed) # docstring says this should be a caterpillar - G = random_lobster(10, 0.1, 0.0, seed) + G = nx.random_lobster(10, 0.1, 0.0, seed) assert is_caterpillar(G) # difficult to find seed that requires few tries - seq = random_powerlaw_tree_sequence(10, 3, seed=14, tries=1) - G = random_powerlaw_tree(10, 3, seed=14, tries=1) + seq = nx.random_powerlaw_tree_sequence(10, 3, seed=14, tries=1) + G = nx.random_powerlaw_tree(10, 3, seed=14, tries=1) def test_dual_barabasi_albert(self, m1=1, m2=4, p=0.5): """ @@ -137,28 +120,42 @@ class TestGeneratorsRandom: The graphs generation are repeated several times to prevent lucky shots """ - seed = 42 - repeats = 2 + seeds = [42, 314, 2718] + initial_graph = nx.complete_graph(10) - while repeats: - repeats -= 1 + for seed in seeds: # This should be BA with m = m1 - BA1 = barabasi_albert_graph(100, m1, seed) - DBA1 = dual_barabasi_albert_graph(100, m1, m2, 1, seed) - assert BA1.size() == DBA1.size() + BA1 = nx.barabasi_albert_graph(100, m1, seed) + DBA1 = nx.dual_barabasi_albert_graph(100, m1, m2, 1, seed) + assert BA1.edges() == DBA1.edges() # This should be BA with m = m2 - BA2 = barabasi_albert_graph(100, m2, seed) - DBA2 = dual_barabasi_albert_graph(100, m1, m2, 0, seed) - assert BA2.size() == DBA2.size() + BA2 = nx.barabasi_albert_graph(100, m2, seed) + DBA2 = nx.dual_barabasi_albert_graph(100, m1, m2, 0, seed) + assert BA2.edges() == DBA2.edges() + + BA3 = nx.barabasi_albert_graph(100, m1, seed) + DBA3 = nx.dual_barabasi_albert_graph(100, m1, m1, p, seed) + # We can't compare edges here since randomness is "consumed" when drawing + # between m1 and m2 + assert BA3.size() == DBA3.size() + + DBA = nx.dual_barabasi_albert_graph(100, m1, m2, p, seed, initial_graph) + BA1 = nx.barabasi_albert_graph(100, m1, seed, initial_graph) + BA2 = nx.barabasi_albert_graph(100, m2, seed, initial_graph) + assert ( + min(BA1.size(), BA2.size()) <= DBA.size() <= max(BA1.size(), BA2.size()) + ) # Testing exceptions - dbag = dual_barabasi_albert_graph - pytest.raises(NetworkXError, dbag, m1, m1, m2, 0) - pytest.raises(NetworkXError, dbag, m2, m1, m2, 0) - pytest.raises(NetworkXError, dbag, 100, m1, m2, -0.5) - pytest.raises(NetworkXError, dbag, 100, m1, m2, 1.5) + dbag = nx.dual_barabasi_albert_graph + pytest.raises(nx.NetworkXError, dbag, m1, m1, m2, 0) + pytest.raises(nx.NetworkXError, dbag, m2, m1, m2, 0) + pytest.raises(nx.NetworkXError, dbag, 100, m1, m2, -0.5) + pytest.raises(nx.NetworkXError, dbag, 100, m1, m2, 1.5) + initial = nx.complete_graph(max(m1, m2) - 1) + pytest.raises(nx.NetworkXError, dbag, 100, m1, m2, p, initial_graph=initial) def test_extended_barabasi_albert(self, m=2): """ @@ -169,36 +166,34 @@ class TestGeneratorsRandom: The graphs generation are repeated several times to prevent lucky-shots """ - seed = 42 - repeats = 2 - BA_model = barabasi_albert_graph(100, m, seed) - BA_model_edges = BA_model.number_of_edges() + seeds = [42, 314, 2718] - while repeats: - repeats -= 1 + for seed in seeds: + BA_model = nx.barabasi_albert_graph(100, m, seed) + BA_model_edges = BA_model.number_of_edges() # This behaves just like BA, the number of edges must be the same - G1 = extended_barabasi_albert_graph(100, m, 0, 0, seed) + G1 = nx.extended_barabasi_albert_graph(100, m, 0, 0, seed) assert G1.size() == BA_model_edges # More than twice more edges should have been added - G1 = extended_barabasi_albert_graph(100, m, 0.8, 0, seed) + G1 = nx.extended_barabasi_albert_graph(100, m, 0.8, 0, seed) assert G1.size() > BA_model_edges * 2 # Only edge rewiring, so the number of edges less than original - G2 = extended_barabasi_albert_graph(100, m, 0, 0.8, seed) + G2 = nx.extended_barabasi_albert_graph(100, m, 0, 0.8, seed) assert G2.size() == BA_model_edges # Mixed scenario: less edges than G1 and more edges than G2 - G3 = extended_barabasi_albert_graph(100, m, 0.3, 0.3, seed) + G3 = nx.extended_barabasi_albert_graph(100, m, 0.3, 0.3, seed) assert G3.size() > G2.size() assert G3.size() < G1.size() # Testing exceptions - ebag = extended_barabasi_albert_graph - pytest.raises(NetworkXError, ebag, m, m, 0, 0) - pytest.raises(NetworkXError, ebag, 1, 0.5, 0, 0) - pytest.raises(NetworkXError, ebag, 100, 2, 0.5, 0.5) + ebag = nx.extended_barabasi_albert_graph + pytest.raises(nx.NetworkXError, ebag, m, m, 0, 0) + pytest.raises(nx.NetworkXError, ebag, 1, 0.5, 0, 0) + pytest.raises(nx.NetworkXError, ebag, 100, 2, 0.5, 0.5) def test_random_zero_regular_graph(self): """Tests that a 0-regular graph has the correct number of nodes and @@ -206,16 +201,16 @@ class TestGeneratorsRandom: """ seed = 42 - G = random_regular_graph(0, 10, seed) + G = nx.random_regular_graph(0, 10, seed) assert len(G) == 10 assert sum(1 for _ in G.edges()) == 0 def test_gnp(self): for generator in [ - gnp_random_graph, - binomial_graph, - erdos_renyi_graph, - fast_gnp_random_graph, + nx.gnp_random_graph, + nx.binomial_graph, + nx.erdos_renyi_graph, + nx.fast_gnp_random_graph, ]: G = generator(10, -1.1) assert len(G) == 10 @@ -253,39 +248,39 @@ class TestGeneratorsRandom: assert abs(edges / float(runs) - 90) <= runs * 2.0 / 100 def test_gnm(self): - G = gnm_random_graph(10, 3) + G = nx.gnm_random_graph(10, 3) assert len(G) == 10 assert sum(1 for _ in G.edges()) == 3 - G = gnm_random_graph(10, 3, seed=42) + G = nx.gnm_random_graph(10, 3, seed=42) assert len(G) == 10 assert sum(1 for _ in G.edges()) == 3 - G = gnm_random_graph(10, 100) + G = nx.gnm_random_graph(10, 100) assert len(G) == 10 assert sum(1 for _ in G.edges()) == 45 - G = gnm_random_graph(10, 100, directed=True) + G = nx.gnm_random_graph(10, 100, directed=True) assert len(G) == 10 assert sum(1 for _ in G.edges()) == 90 - G = gnm_random_graph(10, -1.1) + G = nx.gnm_random_graph(10, -1.1) assert len(G) == 10 assert sum(1 for _ in G.edges()) == 0 def test_watts_strogatz_big_k(self): # Test to make sure than n <= k - pytest.raises(NetworkXError, watts_strogatz_graph, 10, 11, 0.25) - pytest.raises(NetworkXError, newman_watts_strogatz_graph, 10, 11, 0.25) + pytest.raises(nx.NetworkXError, nx.watts_strogatz_graph, 10, 11, 0.25) + pytest.raises(nx.NetworkXError, nx.newman_watts_strogatz_graph, 10, 11, 0.25) # could create an infinite loop, now doesn't # infinite loop used to occur when a node has degree n-1 and needs to rewire - watts_strogatz_graph(10, 9, 0.25, seed=0) - newman_watts_strogatz_graph(10, 9, 0.5, seed=0) + nx.watts_strogatz_graph(10, 9, 0.25, seed=0) + nx.newman_watts_strogatz_graph(10, 9, 0.5, seed=0) # Test k==n scenario - watts_strogatz_graph(10, 10, 0.25, seed=0) - newman_watts_strogatz_graph(10, 10, 0.25, seed=0) + nx.watts_strogatz_graph(10, 10, 0.25, seed=0) + nx.newman_watts_strogatz_graph(10, 10, 0.25, seed=0) def test_random_kernel_graph(self): def integral(u, w, z): @@ -295,6 +290,6 @@ class TestGeneratorsRandom: return r / c + w c = 1 - graph = random_kernel_graph(1000, integral, root) - graph = random_kernel_graph(1000, integral, root, seed=42) + graph = nx.random_kernel_graph(1000, integral, root) + graph = nx.random_kernel_graph(1000, integral, root, seed=42) assert len(graph) == 1000 -- cgit v1.2.1