aboutsummaryrefslogtreecommitdiff
path: root/.venv/lib/python3.12/site-packages/networkx/generators/random_clustered.py
diff options
context:
space:
mode:
authorS. Solomon Darnell2025-03-28 21:52:21 -0500
committerS. Solomon Darnell2025-03-28 21:52:21 -0500
commit4a52a71956a8d46fcb7294ac71734504bb09bcc2 (patch)
treeee3dc5af3b6313e921cd920906356f5d4febc4ed /.venv/lib/python3.12/site-packages/networkx/generators/random_clustered.py
parentcc961e04ba734dd72309fb548a2f97d67d578813 (diff)
downloadgn-ai-master.tar.gz
two version of R2R are hereHEADmaster
Diffstat (limited to '.venv/lib/python3.12/site-packages/networkx/generators/random_clustered.py')
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/generators/random_clustered.py117
1 files changed, 117 insertions, 0 deletions
diff --git a/.venv/lib/python3.12/site-packages/networkx/generators/random_clustered.py b/.venv/lib/python3.12/site-packages/networkx/generators/random_clustered.py
new file mode 100644
index 00000000..8fbf855e
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/generators/random_clustered.py
@@ -0,0 +1,117 @@
+"""Generate graphs with given degree and triangle sequence."""
+
+import networkx as nx
+from networkx.utils import py_random_state
+
+__all__ = ["random_clustered_graph"]
+
+
+@py_random_state(2)
+@nx._dispatchable(graphs=None, returns_graph=True)
+def random_clustered_graph(joint_degree_sequence, create_using=None, seed=None):
+ r"""Generate a random graph with the given joint independent edge degree and
+ triangle degree sequence.
+
+ This uses a configuration model-like approach to generate a random graph
+ (with parallel edges and self-loops) by randomly assigning edges to match
+ the given joint degree sequence.
+
+ The joint degree sequence is a list of pairs of integers of the form
+ $[(d_{1,i}, d_{1,t}), \dotsc, (d_{n,i}, d_{n,t})]$. According to this list,
+ vertex $u$ is a member of $d_{u,t}$ triangles and has $d_{u, i}$ other
+ edges. The number $d_{u,t}$ is the *triangle degree* of $u$ and the number
+ $d_{u,i}$ is the *independent edge degree*.
+
+ Parameters
+ ----------
+ joint_degree_sequence : list of integer pairs
+ Each list entry corresponds to the independent edge degree and
+ triangle degree of a node.
+ create_using : NetworkX graph constructor, optional (default MultiGraph)
+ Graph type to create. If graph instance, then cleared before populated.
+ seed : integer, random_state, or None (default)
+ Indicator of random number generation state.
+ See :ref:`Randomness<randomness>`.
+
+ Returns
+ -------
+ G : MultiGraph
+ A graph with the specified degree sequence. Nodes are labeled
+ starting at 0 with an index corresponding to the position in
+ deg_sequence.
+
+ Raises
+ ------
+ NetworkXError
+ If the independent edge degree sequence sum is not even
+ or the triangle degree sequence sum is not divisible by 3.
+
+ Notes
+ -----
+ As described by Miller [1]_ (see also Newman [2]_ for an equivalent
+ description).
+
+ A non-graphical degree sequence (not realizable by some simple
+ graph) is allowed since this function returns graphs with self
+ loops and parallel edges. An exception is raised if the
+ independent degree sequence does not have an even sum or the
+ triangle degree sequence sum is not divisible by 3.
+
+ This configuration model-like construction process can lead to
+ duplicate edges and loops. You can remove the self-loops and
+ parallel edges (see below) which will likely result in a graph
+ that doesn't have the exact degree sequence specified. This
+ "finite-size effect" decreases as the size of the graph increases.
+
+ References
+ ----------
+ .. [1] Joel C. Miller. "Percolation and epidemics in random clustered
+ networks". In: Physical review. E, Statistical, nonlinear, and soft
+ matter physics 80 (2 Part 1 August 2009).
+ .. [2] M. E. J. Newman. "Random Graphs with Clustering".
+ In: Physical Review Letters 103 (5 July 2009)
+
+ Examples
+ --------
+ >>> deg = [(1, 0), (1, 0), (1, 0), (2, 0), (1, 0), (2, 1), (0, 1), (0, 1)]
+ >>> G = nx.random_clustered_graph(deg)
+
+ To remove parallel edges:
+
+ >>> G = nx.Graph(G)
+
+ To remove self loops:
+
+ >>> G.remove_edges_from(nx.selfloop_edges(G))
+
+ """
+ # In Python 3, zip() returns an iterator. Make this into a list.
+ joint_degree_sequence = list(joint_degree_sequence)
+
+ N = len(joint_degree_sequence)
+ G = nx.empty_graph(N, create_using, default=nx.MultiGraph)
+ if G.is_directed():
+ raise nx.NetworkXError("Directed Graph not supported")
+
+ ilist = []
+ tlist = []
+ for n in G:
+ degrees = joint_degree_sequence[n]
+ for icount in range(degrees[0]):
+ ilist.append(n)
+ for tcount in range(degrees[1]):
+ tlist.append(n)
+
+ if len(ilist) % 2 != 0 or len(tlist) % 3 != 0:
+ raise nx.NetworkXError("Invalid degree sequence")
+
+ seed.shuffle(ilist)
+ seed.shuffle(tlist)
+ while ilist:
+ G.add_edge(ilist.pop(), ilist.pop())
+ while tlist:
+ n1 = tlist.pop()
+ n2 = tlist.pop()
+ n3 = tlist.pop()
+ G.add_edges_from([(n1, n2), (n1, n3), (n2, n3)])
+ return G