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