Skip to main content
`Ctrl`+`K`

# Source code for networkx.generators.cographs

    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)
    @nx._dispatchable(graphs=None, returns_graph=True)
    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 performs 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