Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/algorithms/asteroidal.py @ 1:56ad4e20f292 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author guerler
date Fri, 31 Jul 2020 00:32:28 -0400
parents
children
comparison
equal deleted inserted replaced
0:d30785e31577 1:56ad4e20f292
1 # -*- coding: utf-8 -*-
2 # Copyright (C) 2004-2019 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 non-adjacent 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 AT-free graph. The class of AT-free graphs is a graph class for which
19 many NP-complete 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 non-adjacent 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} + |V||E|)`, 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 AT-free 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 AT-free, 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 AT-free, 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 439-452, 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 AT-free.
103
104 The method uses the `find_asteroidal_triple` method to recognize
105 an AT-free graph. If no asteroidal triple is found the graph is
106 AT-free and True is returned. If at least one asteroidal triple is
107 found the graph is not AT-free and False is returned.
108
109 Parameters
110 ----------
111 G : NetworkX Graph
112 The graph to check whether is AT-free or not.
113
114 Returns
115 -------
116 bool
117 True if G is AT-free 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