Mercurial > repos > guerler > springsuite
diff planemo/lib/python3.7/site-packages/networkx/generators/cographs.py @ 1:56ad4e20f292 draft
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author | guerler |
---|---|
date | Fri, 31 Jul 2020 00:32:28 -0400 (2020-07-31) |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/planemo/lib/python3.7/site-packages/networkx/generators/cographs.py Fri Jul 31 00:32:28 2020 -0400 @@ -0,0 +1,75 @@ +# -*- coding: utf-8 -*- +# Copyright (C) 2004-2019 by +# Aric Hagberg <hagberg@lanl.gov> +# Dan Schult <dschult@colgate.edu> +# Pieter Swart <swart@lanl.gov> +# All rights reserved. +# BSD license. +# +# Authors: Efraim Rodrigues (efraimnaassom@gmail.com) +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