1"""
2Algorithms for asteroidal triples and asteroidal numbers in graphs.
3
4An asteroidal triple in a graph G is a set of three non-adjacent vertices
5u, v and w such that there exist a path between any two of them that avoids
6closed neighborhood of the third. More formally, v_j, v_k belongs to the same
7connected component of G - N[v_i], where N[v_i] denotes the closed neighborhood
8of v_i. A graph which does not contain any asteroidal triples is called
9an AT-free graph. The class of AT-free graphs is a graph class for which
10many NP-complete problems are solvable in polynomial time. Amongst them,
11independent set and coloring.
12"""
13import networkx as nx
14from networkx.utils import not_implemented_for
15
16__all__ = ["is_at_free", "find_asteroidal_triple"]
17
18
19@not_implemented_for("directed")
20@not_implemented_for("multigraph")
21def find_asteroidal_triple(G):
22    r"""Find an asteroidal triple in the given graph.
23
24    An asteroidal triple is a triple of non-adjacent vertices such that
25    there exists a path between any two of them which avoids the closed
26    neighborhood of the third. It checks all independent triples of vertices
27    and whether they are an asteroidal triple or not. This is done with the
28    help of a data structure called a component structure.
29    A component structure encodes information about which vertices belongs to
30    the same connected component when the closed neighborhood of a given vertex
31    is removed from the graph. The algorithm used to check is the trivial
32    one, outlined in [1]_, which has a runtime of
33    :math:`O(|V||\overline{E} + |V||E|)`, where the second term is the
34    creation of the component structure.
35
36    Parameters
37    ----------
38    G : NetworkX Graph
39        The graph to check whether is AT-free or not
40
41    Returns
42    -------
43    list or None
44        An asteroidal triple is returned as a list of nodes. If no asteroidal
45        triple exists, i.e. the graph is AT-free, then None is returned.
46        The returned value depends on the certificate parameter. The default
47        option is a bool which is True if the graph is AT-free, i.e. the
48        given graph contains no asteroidal triples, and False otherwise, i.e.
49        if the graph contains at least one asteroidal triple.
50
51    Notes
52    -----
53    The component structure and the algorithm is described in [1]_. The current
54    implementation implements the trivial algorithm for simple graphs.
55
56    References
57    ----------
58    .. [1] Ekkehard Köhler,
59       "Recognizing Graphs without asteroidal triples",
60       Journal of Discrete Algorithms 2, pages 439-452, 2004.
61       https://www.sciencedirect.com/science/article/pii/S157086670400019X
62    """
63    V = set(G.nodes)
64
65    if len(V) < 6:
66        # An asteroidal triple cannot exist in a graph with 5 or less vertices.
67        return None
68
69    component_structure = create_component_structure(G)
70    E_complement = set(nx.complement(G).edges)
71
72    for e in E_complement:
73        u = e[0]
74        v = e[1]
75        u_neighborhood = set(G[u]).union([u])
76        v_neighborhood = set(G[v]).union([v])
77        union_of_neighborhoods = u_neighborhood.union(v_neighborhood)
78        for w in V - union_of_neighborhoods:
79            """Check for each pair of vertices whether they belong to the
80            same connected component when the closed neighborhood of the
81            third is removed."""
82            if (
83                component_structure[u][v] == component_structure[u][w]
84                and component_structure[v][u] == component_structure[v][w]
85                and component_structure[w][u] == component_structure[w][v]
86            ):
87                return [u, v, w]
88
89    return None
90
91
92@not_implemented_for("directed")
93@not_implemented_for("multigraph")
94def is_at_free(G):
95    """Check if a graph is AT-free.
96
97    The method uses the `find_asteroidal_triple` method to recognize
98    an AT-free graph. If no asteroidal triple is found the graph is
99    AT-free and True is returned. If at least one asteroidal triple is
100    found the graph is not AT-free and False is returned.
101
102    Parameters
103    ----------
104    G : NetworkX Graph
105        The graph to check whether is AT-free or not.
106
107    Returns
108    -------
109    bool
110        True if G is AT-free and False otherwise.
111
112    Examples
113    --------
114    >>> G = nx.Graph([(0, 1), (0, 2), (1, 2), (1, 3), (1, 4), (4, 5)])
115    >>> nx.is_at_free(G)
116    True
117
118    >>> G = nx.cycle_graph(6)
119    >>> nx.is_at_free(G)
120    False
121    """
122    return find_asteroidal_triple(G) is None
123
124
125@not_implemented_for("directed")
126@not_implemented_for("multigraph")
127def create_component_structure(G):
128    r"""Create component structure for G.
129
130    A *component structure* is an `nxn` array, denoted `c`, where `n` is
131    the number of vertices,  where each row and column corresponds to a vertex.
132
133    .. math::
134        c_{uv} = \begin{cases} 0, if v \in N[u] \\
135            k, if v \in component k of G \setminus N[u] \end{cases}
136
137    Where `k` is an arbitrary label for each component. The structure is used
138    to simplify the detection of asteroidal triples.
139
140    Parameters
141    ----------
142    G : NetworkX Graph
143        Undirected, simple graph.
144
145    Returns
146    -------
147    component_structure : dictionary
148        A dictionary of dictionaries, keyed by pairs of vertices.
149
150    """
151    V = set(G.nodes)
152    component_structure = {}
153    for v in V:
154        label = 0
155        closed_neighborhood = set(G[v]).union({v})
156        row_dict = {}
157        for u in closed_neighborhood:
158            row_dict[u] = 0
159
160        G_reduced = G.subgraph(set(G.nodes) - closed_neighborhood)
161        for cc in nx.connected_components(G_reduced):
162            label += 1
163            for u in cc:
164                row_dict[u] = label
165
166        component_structure[v] = row_dict
167
168    return component_structure
169