1 # Graph topology utilities, used by KCC
3 # Copyright (C) Andrew Bartlett 2015
5 # Copyright goes to Andrew Bartlett, but the actual work was performed
6 # by Douglas Bagnall and Garming Sam.
8 # This program is free software; you can redistribute it and/or modify
9 # it under the terms of the GNU General Public License as published by
10 # the Free Software Foundation; either version 3 of the License, or
11 # (at your option) any later version.
13 # This program is distributed in the hope that it will be useful,
14 # but WITHOUT ANY WARRANTY; without even the implied warranty of
15 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 # GNU General Public License for more details.
18 # You should have received a copy of the GNU General Public License
19 # along with this program. If not, see <http://www.gnu.org/licenses/>.
21 from __future__ import print_function
25 from samba.kcc.debug import null_debug, PURPLE, MAGENTA, DARK_YELLOW, RED
26 from samba.kcc.debug import DARK_GREEN, C_NORMAL, GREY
27 from samba.graph import dot_graph
30 def write_dot_file(basename, edge_list, vertices=None, label=None,
31 dot_file_dir=None, debug=None, **kwargs):
32 s = dot_graph(vertices, edge_list, title=label, **kwargs)
34 # sanitise DN and guid labels
35 basename += '_' + label.translate(None, ', ')
37 filename = os.path.join(dot_file_dir, "%s.dot" % basename)
39 debug("writing graph to %s" % filename)
40 f = open(filename, 'w')
45 class GraphError(Exception):
49 def verify_graph_complete(edges, vertices, edge_vertices):
50 """The graph is complete, which is to say there is an edge between
51 every pair of nodes."""
59 if len(remotes) + 1 != len(vertices):
60 raise GraphError("graph is not fully connected")
63 def verify_graph_connected(edges, vertices, edge_vertices):
64 """There is a path between any two nodes."""
66 if len(vertices) <= 1:
68 raise GraphError("disconnected vertices were found:\n"
69 "vertices: %s\n edges: %s" %
70 (sorted(vertices), sorted(edges)))
72 remaining_edges = list(edges)
73 reached = set(remaining_edges.pop())
76 for i, e in enumerate(remaining_edges):
86 for i in reversed(doomed):
87 del remaining_edges[i]
89 if remaining_edges or reached != set(vertices):
90 raise GraphError("graph is not connected:\n vertices: %s\n edges: %s\n"
91 " reached: %s\n remaining edges: %s" %
92 (sorted(vertices), sorted(edges),
93 sorted(reached), sorted(remaining_edges)))
96 def verify_graph_connected_under_edge_failures(edges, vertices, edge_vertices):
97 """The graph stays connected when any single edge is removed."""
98 for subset in itertools.combinations(edges, len(edges) - 1):
99 verify_graph_connected(subset, vertices, edge_vertices)
102 def verify_graph_connected_under_vertex_failures(edges, vertices,
104 """The graph stays connected when any single vertex is removed."""
106 sub_vertices = [x for x in vertices if x is not v]
107 sub_edges = [x for x in edges if v not in x]
108 verify_graph_connected(sub_edges, sub_vertices, sub_vertices)
111 def verify_graph_forest(edges, vertices, edge_vertices):
112 """The graph contains no loops. A forest that is also connected is a
114 trees = [set(e) for e in edges]
116 for a, b in itertools.combinations(trees, 2):
119 if len(intersection) == 1:
124 raise GraphError("there is a loop in the graph\n"
125 " vertices %s\n edges %s\n"
127 (vertices, edges, intersection))
129 # no break in itertools.combinations loop means no
130 # further mergers, so we're done.
132 # XXX here we also know whether it is a tree or a
133 # forest by len(trees) but the connected test already
138 def verify_graph_multi_edge_forest(edges, vertices, edge_vertices):
139 """This allows a forest with duplicate edges. That is if multiple
140 edges go between the same two vertices, they are treated as a
141 single edge by this test.
145 pass: o-o=o o=o (|) fail: o-o
148 unique_edges = set(edges)
149 trees = [set(e) for e in unique_edges]
151 for a, b in itertools.combinations(trees, 2):
154 if len(intersection) == 1:
159 raise GraphError("there is a loop in the graph")
164 def verify_graph_no_lonely_vertices(edges, vertices, edge_vertices):
165 """There are no vertices without edges."""
166 lonely = set(vertices) - set(edge_vertices)
168 raise GraphError("some vertices are not connected:\n%s" %
169 '\n'.join(sorted(lonely)))
172 def verify_graph_no_unknown_vertices(edges, vertices, edge_vertices):
173 """The edge endpoints contain no vertices that are otherwise unknown."""
174 unknown = set(edge_vertices) - set(vertices)
176 raise GraphError("some edge vertices are seemingly unknown:\n%s" %
177 '\n'.join(sorted(unknown)))
180 def verify_graph_directed_double_ring(edges, vertices, edge_vertices):
181 """Each node has at least two directed edges leaving it, and two
182 arriving. The edges work in pairs that have the same end points
183 but point in opposite directions. The pairs form a path that
184 touches every vertex and form a loop.
186 There might be other connections that *aren't* part of the ring.
188 Deciding this for sure is NP-complete (the Hamiltonian path
189 problem), but there are some easy failures that can be detected.
193 - robustness against edge and vertex failure
195 # a zero or one node graph is OK with no edges.
196 # The two vertex case is special. Use
197 # verify_graph_directed_double_ring_or_small() to allow that.
198 if not edges and len(vertices) <= 1:
200 if len(edges) < 2 * len(vertices):
201 raise GraphError("directed double ring requires at least twice "
202 "as many edges as vertices")
204 # Reduce the problem space by looking only at bi-directional links.
205 half_duplex = set(edges)
208 rev_edge = (edge[1], edge[0])
209 if edge in half_duplex and rev_edge in half_duplex:
210 duplex_links.add(edge)
211 half_duplex.remove(edge)
212 half_duplex.remove(rev_edge)
214 # the Hamiltonian cycle problem is NP-complete in general, but we
215 # can cheat a bit and prove a less strong result.
217 # We declutter the graph by replacing nodes with edges connecting
225 # In the end there should be a single 2 vertex graph.
228 for a, b in duplex_links:
229 edge_map.setdefault(a, set()).add(b)
230 edge_map.setdefault(b, set()).add(a)
232 # an easy to detect failure is a lonely leaf node
233 for vertex, neighbours in edge_map.items():
234 if len(neighbours) == 1:
235 raise GraphError("wanted double directed ring, found a leaf node"
238 for vertex in edge_map.keys():
239 nset = edge_map[vertex]
243 n_neighbours = edge_map[n]
244 n_neighbours.remove(vertex)
245 n_neighbours.update(x for x in nset if x != n)
248 if len(edge_map) > 1:
249 raise GraphError("wanted double directed ring, but "
250 "this looks like a split graph\n"
251 "(%s can't reach each other)" %
252 ', '.join(edge_map.keys()))
254 verify_graph_connected_under_edge_failures(duplex_links, vertices,
256 verify_graph_connected_under_vertex_failures(duplex_links, vertices,
260 def verify_graph_directed_double_ring_or_small(edges, vertices, edge_vertices):
261 """This performs the directed_double_ring test but makes special
262 concessions for small rings where the strict rules don't really
264 if len(vertices) < 2:
266 if len(vertices) == 2:
267 """With 2 nodes there should be a single link in each directions."""
268 if (len(edges) == 2 and
269 edges[0][0] == edges[1][1] and
270 edges[0][1] == edges[1][0]):
272 raise GraphError("A two vertex graph should have an edge each way.")
274 return verify_graph_directed_double_ring(edges, vertices, edge_vertices)
277 def verify_graph(title, edges, vertices=None, directed=False, properties=(),
278 fatal=True, debug=null_debug):
280 debug("%sStarting verify_graph for %s%s%s" % (PURPLE, MAGENTA, title,
283 properties = [x.replace(' ', '_') for x in properties]
285 edge_vertices = set()
291 vertices = edge_vertices
293 vertices = set(vertices)
294 if vertices != edge_vertices:
295 debug("vertices in edges don't match given vertices:\n %s != %s" %
296 (sorted(edge_vertices), sorted(vertices)))
299 fn = 'verify_graph_%s' % p
303 errors.append((p, "There is no verification check for '%s'" % p))
305 f(edges, vertices, edge_vertices)
306 debug(" %s%18s:%s verified!" % (DARK_GREEN, p, C_NORMAL))
307 except GraphError as e:
308 errors.append((p, e))
312 raise GraphError("The '%s' graph lacks the following properties:"
314 (title, '\n'.join('%s: %s' % x for x in errors)))
315 debug(("%s%s%s FAILED:" % (MAGENTA, title, RED)))
317 debug(" %18s: %s%s%s" % (p, DARK_YELLOW, e, RED))
321 def verify_and_dot(basename, edges, vertices=None, label=None,
322 reformat_labels=True, directed=False,
323 properties=(), fatal=True, debug=None,
324 verify=True, dot_file_dir=None,
325 edge_colors=None, edge_labels=None,
328 title = '%s %s' % (basename, label or '')
330 verify_graph(title, edges, vertices, properties=properties,
331 fatal=fatal, debug=debug)
332 if dot_file_dir is not None:
333 write_dot_file(basename, edges, vertices=vertices, label=label,
334 dot_file_dir=dot_file_dir,
335 reformat_labels=reformat_labels, directed=directed,
336 debug=debug, edge_colors=edge_colors,
337 edge_labels=edge_labels, vertex_colors=vertex_colors)
340 def list_verify_tests():
341 for k, v in sorted(globals().items()):
342 if k.startswith('verify_graph_'):
343 print(k.replace('verify_graph_', ''))
345 print(' %s%s%s' % (GREY, v.__doc__.rstrip(), C_NORMAL))