AT-free graph recognition (#3377)

* Included asteroidal module.

* Initial commit for asteroidal module.

The asteroidal module implements a function which checks whether
a given graph is AT-free or not.

* Tests for asteroidal.py

The tests include checks for small, well-known cases of
AT-free and non-AT-free graphs.

* Updated runtime for recognition algorithm in docstring.

* Included "r" to start docstring to enable LaTeX codes.

* Included .rst file for asteroidal module

* Fixed not implemented for decorator statements

If multiple types are inputed into a decorator this
works as an AND condition, but we want an OR condition.

* Refactoring of unnecessary work

The helper function in is_at_free now consists of a return
statement directly, which saves having to evaluate boolean
statements unneccesarily. The for loop in the component_strucutre
function now omits an unecessary generator definition.

* Updated docstring to reflect optional output and runtime.

The docstring now includes a more precise description of the
worst-case runtime. The optional output parameter `certificate`
is more thoroughly documented.

* Change optional output to a tuple including a bool

* Refactor tests to be shorter and more readable

* Included tests with certificate option enabled.

The certificate option outputs a certificate, if any exists,
which proves that a graph is not AT-free.

* Fix bug due to typo in tests

An 's' had snuck its way into an assert_equal statement,
and I didn't check properly before pushing.

* docstring for is_at_free re-structured and re-formulated.

* Split is_at_free method

The previous method had an extra parameter, `certificate`, that could be used
to decide whether the output should be a boolean value or a tuple with a
boolean value and a certificate. This has now been split into two functions:
`is_at_free` and `find_asteroidal_triple`, for more intuitive behaviour.

* Changed `is_at_free` to find_asteroidal_triple

The new version returns an asteroidal triple if one exists
and returns None if none exists. This method is used in the
new `is_at_free` method.

* Updated docstrings

Docstrings updated to reflect changed functionality and
new structure.

* Refactor `find_asteroidal_triple`

The previous version defined a function to check whether a
triple of vertices is an asteroidal triple. The current
version uses this function inline instead, to avoid many
function calls in order to increase performance.

* Refactored return statement in `is_at_free`

Removed the else block according to Chromium style guide.

* feat: expose `find_asteroidal_triple`

The find_asteroidal_triple is also imported when the asteroidal
module is imported.

* style: refactor is_at_free

The function can be written as a readable oneliner instead
of using an if else block.

* docs: asteroidal: updated module docstring

Rewrote module docstring to be more precise.

* chore: include find_asteroidal_triple in reference

The find_asteroidal_triple is now exposed when importing
the asteroidal module so the method should also be included
in the asteroidal.rst for auto-generation of documentation.

* Added myself, Haakon H. Rød, as a contributor

* chore: removed redundant tests

Some tests are no longer valid after changing the output
of `is_at_free` to purely boolean.

5 files changed, 214 insertions, 0 deletions

diff --git a/CONTRIBUTORS.rst b/CONTRIBUTORS.rst
index f8631917..b3884b2e 100644
--- a/CONTRIBUTORS.rst
+++ b/CONTRIBUTORS.rst
@@ -126,6 +126,7 @@ is partially historical, and now, mostly arbitrary.
 - Brian Kiefer, Github: `bkief <https://github.com/bkief>`_
 - Julien Klaus
 - Weisheng Si, Github: `ws4u <https://github.com/ws4u>`_
+- Haakon H. Rød, Gitlab: `haakonhr <https://gitlab.com/haakonhr>`_, `<https://haakonhr.gitlab.io>`_ 
 
 Support
 -------
diff --git a/doc/reference/algorithms/asteroidal.rst b/doc/reference/algorithms/asteroidal.rst
new file mode 100644
index 00000000..13db0c40
--- /dev/null
+++ b/doc/reference/algorithms/asteroidal.rst
@@ -0,0 +1,10 @@
+**********
+Asteroidal
+**********
+
+.. automodule:: networkx.algorithms.asteroidal
+.. autosummary::
+   :toctree: generated/
+
+   is_at_free
+   find_asteroidal_triple
diff --git a/networkx/algorithms/__init__.py b/networkx/algorithms/__init__.py
index 64eea5fc..ecb18580 100644
--- a/networkx/algorithms/__init__.py
+++ b/networkx/algorithms/__init__.py
@@ -1,4 +1,5 @@
 from networkx.algorithms.assortativity import *
+from networkx.algorithms.asteroidal import *
 from networkx.algorithms.boundary import *
 from networkx.algorithms.bridges import *
 from networkx.algorithms.chains import *
diff --git a/networkx/algorithms/asteroidal.py b/networkx/algorithms/asteroidal.py
new file mode 100644
index 00000000..7d33671f
--- /dev/null
+++ b/networkx/algorithms/asteroidal.py
@@ -0,0 +1,175 @@
+# -*- 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: Haakon H. Rød (haakonhr@gmail.com)
+"""
+Algorithms for asteroidal triples and asteroidal numbers in graphs.
+
+An asteroidal triple in a graph G is a set of three non-adjacent vertices
+u, v and w such that there exist a path between any two of them that avoids
+closed neighborhood of the third. More formally, v_j, v_k belongs to the same
+connected component of G - N[v_i], where N[v_i] denotes the closed neighborhood
+of v_i. A graph which does not contain any asteroidal triples is called
+an AT-free graph. The class of AT-free graphs is a graph class for which
+many NP-complete problems are solvable in polynomial time. Amongst them,
+independent set and coloring.
+"""
+import networkx as nx
+from networkx.utils import not_implemented_for
+
+__all__ = ["is_at_free", "find_asteroidal_triple"]
+
+
+@not_implemented_for("directed")
+@not_implemented_for("multigraph")
+def find_asteroidal_triple(G):
+    r"""Find an asteroidal triple in the given graph.
+
+    An asteroidal triple is a triple of non-adjacent vertices such that
+    there exists a path between any two of them which avoids the closed
+    neighborhood of the third. It checks all independent triples of vertices
+    and whether they are an asteroidal triple or not. This is done with the
+    help of a data structure called a component structure.
+    A component structure encodes information about which vertices belongs to
+    the same connected component when the closed neighborhood of a given vertex
+    is removed from the graph. The algorithm used to check is the trivial
+    one, outlined in [1]_, which has a runtime of
+    :math:`O(|V||\overline{E} + |V||E|)`, where the second term is the
+    creation of the component structure.
+
+    Parameters
+    ----------
+    G : NetworkX Graph
+        The graph to check whether is AT-free or not
+
+    Returns
+    -------
+    list or None
+        An asteroidal triple is returned as a list of nodes. If no asteroidal
+        triple exists, i.e. the graph is AT-free, then None is returned.
+        The returned value depends on the certificate parameter. The default
+        option is a bool which is True if the graph is AT-free, i.e. the
+        given graph contains no asteroidal triples, and False otherwise, i.e.
+        if the graph contains at least one asteroidal triple.
+
+    Notes
+    -----
+    The component structure and the algorithm is described in [1]_. The current
+    implementation implements the trivial algorithm for simple graphs.
+
+    References
+    ----------
+    .. [1] Ekkehard Köhler,
+       "Recognizing Graphs without asteroidal triples",
+       Journal of Discrete Algorithms 2, pages 439-452, 2004.
+       https://www.sciencedirect.com/science/article/pii/S157086670400019X
+    """
+    V = set(G.nodes)
+
+    if len(V) < 6:
+        # An asteroidal triple cannot exist in a graph with 5 or less vertices.
+        return None
+
+    component_structure = create_component_structure(G)
+    E_complement = set(nx.complement(G).edges)
+
+    for e in E_complement:
+        u = e[0]
+        v = e[1]
+        u_neighborhood = set(G[u]).union([u])
+        v_neighborhood = set(G[v]).union([v])
+        union_of_neighborhoods = u_neighborhood.union(v_neighborhood)
+        for w in V - union_of_neighborhoods:
+            """Check for each pair of vertices whether they belong to the
+            same connected component when the closed neighborhood of the
+            third is removed."""
+            if (component_structure[u][v] == component_structure[u][w] and
+                component_structure[v][u] == component_structure[v][w] and
+                    component_structure[w][u] == component_structure[w][v]):
+                return [u, v, w]
+
+    return None
+
+
+@not_implemented_for("directed")
+@not_implemented_for("multigraph")
+def is_at_free(G):
+    """Check if a graph is AT-free.
+
+    The method uses the `find_asteroidal_triple` method to recognize
+    an AT-free graph. If no asteroidal triple is found the graph is
+    AT-free and True is returned. If at least one asteroidal triple is
+    found the graph is not AT-free and False is returned.
+
+    Parameters
+    ----------
+    G : NetworkX Graph
+        The graph to check whether is AT-free or not.
+
+    Returns
+    -------
+    bool
+        True if G is AT-free and False otherwise.
+
+    Examples
+    --------
+    >>> G = nx.Graph([(0, 1), (0, 2), (1, 2), (1, 3), (1, 4), (4, 5)])
+    >>> nx.is_at_free(G)
+    True
+
+    >>> G = nx.cycle_graph(6)
+    >>> nx.is_at_free(G)
+    False
+    """
+    return find_asteroidal_triple(G) is None
+
+
+@not_implemented_for("directed")
+@not_implemented_for("multigraph")
+def create_component_structure(G):
+    r"""Create component structure for G.
+
+    A *component structure* is an `nxn` array, denoted `c`, where `n` is
+    the number of vertices,  where each row and column corresponds to a vertex.
+
+    .. math::
+        c_{uv} = \begin{cases} 0, if v \in N[u] \\
+            k, if v \in component k of G \setminus N[u] \end{cases}
+
+    Where `k` is an arbitrary label for each component. The structure is used
+    to simplify the detection of asteroidal triples.
+
+    Parameters
+    ----------
+    G : NetworkX Graph
+        Undirected, simple graph.
+
+    Returns
+    -------
+    component_structure : dictionary
+        A dictionary of dictionaries, keyed by pairs of vertices.
+
+    """
+    V = set(G.nodes)
+    component_structure = {}
+    for v in V:
+        label = 0
+        closed_neighborhood = set(G[v]).union(set([v]))
+        row_dict = {}
+        for u in closed_neighborhood:
+            row_dict[u] = 0
+
+        G_reduced = G.subgraph(set(G.nodes) - closed_neighborhood)
+        for cc in nx.connected_components(G_reduced):
+            label += 1
+            for u in cc:
+                row_dict[u] = label
+
+        component_structure[v] = row_dict
+
+    return component_structure
diff --git a/networkx/algorithms/tests/test_asteroidal.py b/networkx/algorithms/tests/test_asteroidal.py
new file mode 100644
index 00000000..330b51bc
--- /dev/null
+++ b/networkx/algorithms/tests/test_asteroidal.py
@@ -0,0 +1,27 @@
+import networkx as nx
+from nose.tools import assert_true
+from nose.tools import assert_false
+from nose.tools import assert_equal
+
+
+def test_is_at_free():
+
+    is_at_free = nx.asteroidal.is_at_free
+
+    cycle = nx.cycle_graph(6)
+    assert_false(is_at_free(cycle))
+
+    path = nx.path_graph(6)
+    assert_true(is_at_free(path))
+
+    small_graph = nx.complete_graph(2)
+    assert_true(is_at_free(small_graph))
+
+    petersen = nx.petersen_graph()
+    assert_false(is_at_free(petersen))
+
+    clique = nx.complete_graph(6)
+    assert_true(is_at_free(clique))
+
+    line_clique = nx.line_graph(clique)
+    assert_false(is_at_free(line_clique))