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