ioftools / networkxMiCe / networkxmaster / networkx / algorithms / asteroidal.py @ 5cef0f13
History  View  Annotate  Download (5.91 KB)
1 
# * coding: utf8 *


2 
# Copyright (C) 20042019 by

3 
# Aric Hagberg <hagberg@lanl.gov>

4 
# Dan Schult <dschult@colgate.edu>

5 
# Pieter Swart <swart@lanl.gov>

6 
# All rights reserved.

7 
# BSD license.

8 
#

9 
# Authors: Haakon H. Rød (haakonhr@gmail.com)

10 
"""

11 
Algorithms for asteroidal triples and asteroidal numbers in graphs.

12 

13 
An asteroidal triple in a graph G is a set of three nonadjacent vertices

14 
u, v and w such that there exist a path between any two of them that avoids

15 
closed neighborhood of the third. More formally, v_j, v_k belongs to the same

16 
connected component of G  N[v_i], where N[v_i] denotes the closed neighborhood

17 
of v_i. A graph which does not contain any asteroidal triples is called

18 
an ATfree graph. The class of ATfree graphs is a graph class for which

19 
many NPcomplete problems are solvable in polynomial time. Amongst them,

20 
independent set and coloring.

21 
"""

22 
import networkx as nx 
23 
from networkx.utils import not_implemented_for 
24  
25 
__all__ = ["is_at_free", "find_asteroidal_triple"] 
26  
27  
28 
@not_implemented_for("directed") 
29 
@not_implemented_for("multigraph") 
30 
def find_asteroidal_triple(G): 
31 
r"""Find an asteroidal triple in the given graph.

32 

33 
An asteroidal triple is a triple of nonadjacent vertices such that

34 
there exists a path between any two of them which avoids the closed

35 
neighborhood of the third. It checks all independent triples of vertices

36 
and whether they are an asteroidal triple or not. This is done with the

37 
help of a data structure called a component structure.

38 
A component structure encodes information about which vertices belongs to

39 
the same connected component when the closed neighborhood of a given vertex

40 
is removed from the graph. The algorithm used to check is the trivial

41 
one, outlined in [1]_, which has a runtime of

42 
:math:`O(V\overline{E} + VE)`, where the second term is the

43 
creation of the component structure.

44 

45 
Parameters

46 


47 
G : NetworkX Graph

48 
The graph to check whether is ATfree or not

49 

50 
Returns

51 


52 
list or None

53 
An asteroidal triple is returned as a list of nodes. If no asteroidal

54 
triple exists, i.e. the graph is ATfree, then None is returned.

55 
The returned value depends on the certificate parameter. The default

56 
option is a bool which is True if the graph is ATfree, i.e. the

57 
given graph contains no asteroidal triples, and False otherwise, i.e.

58 
if the graph contains at least one asteroidal triple.

59 

60 
Notes

61 


62 
The component structure and the algorithm is described in [1]_. The current

63 
implementation implements the trivial algorithm for simple graphs.

64 

65 
References

66 


67 
.. [1] Ekkehard Köhler,

68 
"Recognizing Graphs without asteroidal triples",

69 
Journal of Discrete Algorithms 2, pages 439452, 2004.

70 
https://www.sciencedirect.com/science/article/pii/S157086670400019X

71 
"""

72 
V = set(G.nodes)

73  
74 
if len(V) < 6: 
75 
# An asteroidal triple cannot exist in a graph with 5 or less vertices.

76 
return None 
77  
78 
component_structure = create_component_structure(G) 
79 
E_complement = set(nx.complement(G).edges)

80  
81 
for e in E_complement: 
82 
u = e[0]

83 
v = e[1]

84 
u_neighborhood = set(G[u]).union([u])

85 
v_neighborhood = set(G[v]).union([v])

86 
union_of_neighborhoods = u_neighborhood.union(v_neighborhood) 
87 
for w in V  union_of_neighborhoods: 
88 
"""Check for each pair of vertices whether they belong to the

89 
same connected component when the closed neighborhood of the

90 
third is removed."""

91 
if (component_structure[u][v] == component_structure[u][w] and 
92 
component_structure[v][u] == component_structure[v][w] and

93 
component_structure[w][u] == component_structure[w][v]): 
94 
return [u, v, w]

95  
96 
return None 
97  
98  
99 
@not_implemented_for("directed") 
100 
@not_implemented_for("multigraph") 
101 
def is_at_free(G): 
102 
"""Check if a graph is ATfree.

103 

104 
The method uses the `find_asteroidal_triple` method to recognize

105 
an ATfree graph. If no asteroidal triple is found the graph is

106 
ATfree and True is returned. If at least one asteroidal triple is

107 
found the graph is not ATfree and False is returned.

108 

109 
Parameters

110 


111 
G : NetworkX Graph

112 
The graph to check whether is ATfree or not.

113 

114 
Returns

115 


116 
bool

117 
True if G is ATfree and False otherwise.

118 

119 
Examples

120 


121 
>>> G = nx.Graph([(0, 1), (0, 2), (1, 2), (1, 3), (1, 4), (4, 5)])

122 
>>> nx.is_at_free(G)

123 
True

124 

125 
>>> G = nx.cycle_graph(6)

126 
>>> nx.is_at_free(G)

127 
False

128 
"""

129 
return find_asteroidal_triple(G) is None 
130  
131  
132 
@not_implemented_for("directed") 
133 
@not_implemented_for("multigraph") 
134 
def create_component_structure(G): 
135 
r"""Create component structure for G.

136 

137 
A *component structure* is an `nxn` array, denoted `c`, where `n` is

138 
the number of vertices, where each row and column corresponds to a vertex.

139 

140 
.. math::

141 
c_{uv} = \begin{cases} 0, if v \in N[u] \\

142 
k, if v \in component k of G \setminus N[u] \end{cases}

143 

144 
Where `k` is an arbitrary label for each component. The structure is used

145 
to simplify the detection of asteroidal triples.

146 

147 
Parameters

148 


149 
G : NetworkX Graph

150 
Undirected, simple graph.

151 

152 
Returns

153 


154 
component_structure : dictionary

155 
A dictionary of dictionaries, keyed by pairs of vertices.

156 

157 
"""

158 
V = set(G.nodes)

159 
component_structure = {} 
160 
for v in V: 
161 
label = 0

162 
closed_neighborhood = set(G[v]).union(set([v])) 
163 
row_dict = {} 
164 
for u in closed_neighborhood: 
165 
row_dict[u] = 0

166  
167 
G_reduced = G.subgraph(set(G.nodes)  closed_neighborhood)

168 
for cc in nx.connected_components(G_reduced): 
169 
label += 1

170 
for u in cc: 
171 
row_dict[u] = label 
172  
173 
component_structure[v] = row_dict 
174  
175 
return component_structure
