Full join operation and cograph generator (#3503)

* * Implements full join operation and a generator for cographs.

* * Adding myself as a contributor.

* * Fix full join description.

* * Removes full_join function from the cograph generator file.

* * Changes ^ for **.

* Docstrings improvements, fixes and new tests.

* Includes new features in the docs.

* Fix typo in test_cograph.py.

* Random cograph docstring improvements.

* Adds support for directed graphs.

* Improvements to the full join operator and new tests.

* Fixed rename.

* Fix test description.

8 files changed, 293 insertions, 1 deletions

diff --git a/CONTRIBUTORS.rst b/CONTRIBUTORS.rst
index b3884b2e..638ddb0c 100644
--- a/CONTRIBUTORS.rst
+++ b/CONTRIBUTORS.rst
@@ -127,6 +127,7 @@ is partially historical, and now, mostly arbitrary.
 - Julien Klaus
 - Weisheng Si, Github: `ws4u <https://github.com/ws4u>`_
 - Haakon H. Rød, Gitlab: `haakonhr <https://gitlab.com/haakonhr>`_, `<https://haakonhr.gitlab.io>`_ 
+- Efraim Rodrigues, `GitHub <https://github.com/efraimrodrigues>`_, `LinkedIn <https://linkedin.com/in/efraim-rodrigues/>`_
 
 Support
 -------
diff --git a/doc/reference/algorithms/operators.rst b/doc/reference/algorithms/operators.rst
index 11555193..7babf2cc 100644
--- a/doc/reference/algorithms/operators.rst
+++ b/doc/reference/algorithms/operators.rst
@@ -20,6 +20,7 @@ Operators
    intersection
    difference
    symmetric_difference
+   full_join
 
 
 .. automodule:: networkx.algorithms.operators.all
diff --git a/doc/reference/generators.rst b/doc/reference/generators.rst
index ab173382..454bf59b 100644
--- a/doc/reference/generators.rst
+++ b/doc/reference/generators.rst
@@ -324,3 +324,11 @@ Harary Graph
 
    hnm_harary_graph
    hkn_harary_graph
+
+Cographs
+------------
+.. automodule:: networkx.generators.cographs
+.. autosummary::
+   :toctree: generated/
+
+   random_cograph
diff --git a/networkx/algorithms/operators/binary.py b/networkx/algorithms/operators/binary.py
index b0b85f1d..b0b97f88 100644
--- a/networkx/algorithms/operators/binary.py
+++ b/networkx/algorithms/operators/binary.py
@@ -13,7 +13,7 @@ __author__ = """\n""".join(['Aric Hagberg <aric.hagberg@gmail.com>',
                             'Pieter Swart (swart@lanl.gov)',
                             'Dan Schult(dschult@colgate.edu)'])
 __all__ = ['union', 'compose', 'disjoint_union', 'intersection',
-           'difference', 'symmetric_difference']
+           'difference', 'symmetric_difference', 'full_join']
 
 
 def union(G, H, rename=(None, None), name=None):
@@ -329,3 +329,73 @@ def compose(G, H):
     else:
         R.add_edges_from(H.edges(data=True))
     return R
+
+
+def full_join(G, H, rename=(None, None)):
+    """Returns the full join of graphs G and H.
+
+    Full join is the union of G and H in which all edges between
+    G and H are added.
+    The node sets of G and H must be disjoint,
+    otherwise an exception is raised.
+
+    Parameters
+    ----------
+    G, H : graph
+       A NetworkX graph
+
+    rename : bool , default=(None, None)
+       Node names of G and H can be changed by specifying the tuple
+       rename=('G-','H-') (for example).  Node "u" in G is then renamed
+       "G-u" and "v" in H is renamed "H-v".
+
+    Returns
+    -------
+    U : The full join graph with the same type as G.
+
+    Notes
+    -----
+    It is recommended that G and H be either both directed or both undirected.
+
+    If G is directed, then edges from G to H are added as well as from H to G.
+
+    Note that full_join() does not produce parallel edges for MultiGraphs.
+
+    The full join operation of graphs G and H is the same as getting
+    their complement, performing a disjoint union, and finally getting
+    the complement of the resulting graph.
+
+    Graph, edge, and node attributes are propagated from G and H
+    to the union graph.  If a graph attribute is present in both
+    G and H the value from H is used.
+
+    See Also
+    --------
+    union
+    disjoint_union
+    """
+    R = union(G, H, rename)
+
+    def add_prefix(graph, prefix):
+        if prefix is None:
+            return graph
+
+        def label(x):
+            if is_string_like(x):
+                name = prefix + x
+            else:
+                name = prefix + repr(x)
+            return name
+        return nx.relabel_nodes(graph, label)
+    G = add_prefix(G, rename[0])
+    H = add_prefix(H, rename[1])
+
+    for i in G:
+        for j in H:
+            R.add_edge(i, j)
+    if R.is_directed():
+        for i in H:
+            for j in G:
+                R.add_edge(i, j)
+
+    return R
diff --git a/networkx/algorithms/operators/tests/test_binary.py b/networkx/algorithms/operators/tests/test_binary.py
index d8590745..7054f002 100644
--- a/networkx/algorithms/operators/tests/test_binary.py
+++ b/networkx/algorithms/operators/tests/test_binary.py
@@ -283,6 +283,112 @@ def test_compose_multigraph():
                  set(G.edges(keys=True)) | set(H.edges(keys=True)))
 
 
+def test_full_join_graph():
+    # Simple Graphs
+    G = nx.Graph()
+    G.add_node(0)
+    G.add_edge(1, 2)
+    H = nx.Graph()
+    H.add_edge(3, 4)
+
+    U = nx.full_join(G, H)
+    assert_equal(set(U), set(G) | set(H))
+    assert_equal(len(U), len(G) + len(H))
+    assert_equal(len(U.edges()),
+                 len(G.edges()) + len(H.edges()) + len(G) * len(H)
+                 )
+
+    # Rename
+    U = nx.full_join(G, H, rename=('g', 'h'))
+    assert_equal(set(U), set(['g0', 'g1', 'g2', 'h3', 'h4']))
+    assert_equal(len(U), len(G) + len(H))
+    assert_equal(len(U.edges()),
+                 len(G.edges()) + len(H.edges()) + len(G) * len(H)
+                 )
+
+    # Rename graphs with string-like nodes
+    G = nx.Graph()
+    G.add_node("a")
+    G.add_edge("b", "c")
+    H = nx.Graph()
+    H.add_edge("d", "e")
+
+    U = nx.full_join(G, H, rename=('g', 'h'))
+    assert_equal(set(U), set(['ga', 'gb', 'gc', 'hd', 'he']))
+    assert_equal(len(U), len(G) + len(H))
+    assert_equal(len(U.edges()),
+                 len(G.edges()) + len(H.edges()) + len(G) * len(H)
+                 )
+
+    # DiGraphs
+    G = nx.DiGraph()
+    G.add_node(0)
+    G.add_edge(1, 2)
+    H = nx.DiGraph()
+    H.add_edge(3, 4)
+
+    U = nx.full_join(G, H)
+    assert_equal(set(U), set(G) | set(H))
+    assert_equal(len(U), len(G) + len(H))
+    assert_equal(len(U.edges()),
+                 len(G.edges()) + len(H.edges()) + len(G)*len(H) * 2
+                 )
+
+    # DiGraphs Rename
+    U = nx.full_join(G, H, rename=('g', 'h'))
+    assert_equal(set(U), set(['g0', 'g1', 'g2', 'h3', 'h4']))
+    assert_equal(len(U), len(G) + len(H))
+    assert_equal(len(U.edges()),
+                 len(G.edges()) + len(H.edges()) + len(G) * len(H) * 2
+                 )
+
+
+def test_full_join_multigraph():
+    # MultiGraphs
+    G = nx.MultiGraph()
+    G.add_node(0)
+    G.add_edge(1, 2)
+    H = nx.MultiGraph()
+    H.add_edge(3, 4)
+
+    U = nx.full_join(G, H)
+    assert_equal(set(U), set(G) | set(H))
+    assert_equal(len(U), len(G) + len(H))
+    assert_equal(len(U.edges()),
+                 len(G.edges()) + len(H.edges()) + len(G) * len(H)
+                 )
+
+    # MultiGraphs rename
+    U = nx.full_join(G, H, rename=('g', 'h'))
+    assert_equal(set(U), set(['g0', 'g1', 'g2', 'h3', 'h4']))
+    assert_equal(len(U), len(G) + len(H))
+    assert_equal(len(U.edges()),
+                 len(G.edges()) + len(H.edges()) + len(G) * len(H)
+                 )
+
+    # MultiDiGraphs
+    G = nx.MultiDiGraph()
+    G.add_node(0)
+    G.add_edge(1, 2)
+    H = nx.MultiDiGraph()
+    H.add_edge(3, 4)
+
+    U = nx.full_join(G, H)
+    assert_equal(set(U), set(G) | set(H))
+    assert_equal(len(U), len(G) + len(H))
+    assert_equal(len(U.edges()),
+                 len(G.edges()) + len(H.edges()) + len(G) * len(H) * 2
+                 )
+
+    # MultiDiGraphs rename
+    U = nx.full_join(G, H, rename=('g', 'h'))
+    assert_equal(set(U), set(['g0', 'g1', 'g2', 'h3', 'h4']))
+    assert_equal(len(U), len(G) + len(H))
+    assert_equal(len(U.edges()),
+                 len(G.edges()) + len(H.edges()) + len(G) * len(H) * 2
+                 )
+
+
 @raises(nx.NetworkXError)
 def test_mixed_type_union():
     G = nx.Graph()
diff --git a/networkx/generators/__init__.py b/networkx/generators/__init__.py
index 707bab41..ebe83e32 100644
--- a/networkx/generators/__init__.py
+++ b/networkx/generators/__init__.py
@@ -4,6 +4,7 @@ A package for generating various graphs in networkx.
 """
 from networkx.generators.atlas import *
 from networkx.generators.classic import *
+from networkx.generators.cographs import *
 from networkx.generators.community import *
 from networkx.generators.degree_seq import *
 from networkx.generators.directed import *
diff --git a/networkx/generators/cographs.py b/networkx/generators/cographs.py
new file mode 100644
index 00000000..3365747b
--- /dev/null
+++ b/networkx/generators/cographs.py
@@ -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
+----------
+.. [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.
+"""
+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
diff --git a/networkx/generators/tests/test_cographs.py b/networkx/generators/tests/test_cographs.py
new file mode 100644
index 00000000..cf2564c5
--- /dev/null
+++ b/networkx/generators/tests/test_cographs.py
@@ -0,0 +1,30 @@
+# -*- encoding: utf-8 -*-
+# test_cographs.py - unit tests for cograph generators
+#
+# Copyright 2010-2019 NetworkX developers.
+#
+# This file is part of NetworkX.
+#
+# NetworkX is distributed under a BSD license; see LICENSE.txt for more
+# information.
+"""Unit tests for the :mod:`networkx.generators.cographs` module.
+
+"""
+
+import networkx as nx
+from nose.tools import *
+
+
+def test_random_cograph():
+    n = 3
+    G = nx.random_cograph(n)
+
+    assert_equal(len(G), 2 ** n)
+
+    #Every connected subgraph of G has diameter <= 2
+    if nx.is_connected(G):
+        assert_true(nx.diameter(G) <= 2)
+    else:
+        components = nx.connected_components(G)
+        for component in components:
+            assert_true(nx.diameter(G.subgraph(component)) <= 2)