Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/asteroidal.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ | |
2 Algorithms for asteroidal triples and asteroidal numbers in graphs. | |
3 | |
4 An asteroidal triple in a graph G is a set of three non-adjacent vertices | |
5 u, v and w such that there exist a path between any two of them that avoids | |
6 closed neighborhood of the third. More formally, v_j, v_k belongs to the same | |
7 connected component of G - N[v_i], where N[v_i] denotes the closed neighborhood | |
8 of v_i. A graph which does not contain any asteroidal triples is called | |
9 an AT-free graph. The class of AT-free graphs is a graph class for which | |
10 many NP-complete problems are solvable in polynomial time. Amongst them, | |
11 independent set and coloring. | |
12 """ | |
13 import networkx as nx | |
14 from 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") | |
21 def 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") | |
94 def 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") | |
127 def 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 |