Mercurial > repos > shellac > sam_consensus_v3
view env/lib/python3.9/site-packages/networkx/generators/cographs.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
line wrap: on
line source
r"""Generators for cographs A cograph is a graph containing no path on four vertices. Cographs or $P_4$-free graphs can be obtained from a single vertex by disjoint union and complementation operations. References ---------- .. [0] D.G. Corneil, H. Lerchs, L.Stewart Burlingham, "Complement reducible graphs", Discrete Applied Mathematics, Volume 3, Issue 3, 1981, Pages 163-174, ISSN 0166-218X. """ import networkx as nx from networkx.utils import py_random_state __all__ = ["random_cograph"] @py_random_state(1) def random_cograph(n, seed=None): r"""Returns a random cograph with $2 ^ n$ nodes. A cograph is a graph containing no path on four vertices. Cographs or $P_4$-free graphs can be obtained from a single vertex by disjoint union and complementation operations. This generator starts off from a single vertex and performes disjoint union and full join operations on itself. The decision on which operation will take place is random. Parameters ---------- n : int The order of the cograph. seed : integer, random_state, or None (default) Indicator of random number generation state. See :ref:`Randomness<randomness>`. Returns ------- G : A random graph containing no path on four vertices. See Also -------- full_join union References ---------- .. [1] D.G. Corneil, H. Lerchs, L.Stewart Burlingham, "Complement reducible graphs", Discrete Applied Mathematics, Volume 3, Issue 3, 1981, Pages 163-174, ISSN 0166-218X. """ R = nx.empty_graph(1) for i in range(n): RR = nx.relabel_nodes(R.copy(), lambda x: x + len(R)) if seed.randint(0, 1) == 0: R = nx.full_join(R, RR) else: R = nx.disjoint_union(R, RR) return R