python/samba/kcc/graph_utils.py

   1 # Graph topology utilities, used by KCC
   2 #
   3 # Copyright (C) Andrew Bartlett 2015
   4 #
   5 # Copyright goes to Andrew Bartlett, but the actual work was performed
   6 # by Douglas Bagnall and Garming Sam.
   7 #
   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.
  12 #
  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.
  17 #
  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/>.
  20
  21 from __future__ import print_function
  22 import os
  23 import itertools
  24
  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
  28
  29
  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)
  33     if label:
  34         # sanitise DN and guid labels
  35         basename += '_' + label.translate(None, ', ')
  36
  37     filename = os.path.join(dot_file_dir, "%s.dot" % basename)
  38     if debug is not None:
  39         debug("writing graph to %s" % filename)
  40     f = open(filename, 'w')
  41     f.write(s)
  42     f.close()
  43
  44
  45 class GraphError(Exception):
  46     pass
  47
  48
  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."""
  52     for v in vertices:
  53         remotes = set()
  54         for a, b in edges:
  55             if a == v:
  56                 remotes.add(b)
  57             elif b == v:
  58                 remotes.add(a)
  59         if len(remotes) + 1 != len(vertices):
  60             raise GraphError("graph is not fully connected")
  61
  62
  63 def verify_graph_connected(edges, vertices, edge_vertices):
  64     """There is a path between any two nodes."""
  65     if not edges:
  66         if len(vertices) <= 1:
  67             return
  68         raise GraphError("disconnected vertices were found:\n"
  69                          "vertices: %s\n edges: %s" %
  70                          (sorted(vertices), sorted(edges)))
  71
  72     remaining_edges = list(edges)
  73     reached = set(remaining_edges.pop())
  74     while True:
  75         doomed = []
  76         for i, e in enumerate(remaining_edges):
  77             a, b = e
  78             if a in reached:
  79                 reached.add(b)
  80                 doomed.append(i)
  81             elif b in reached:
  82                 reached.add(a)
  83                 doomed.append(i)
  84         if not doomed:
  85             break
  86         for i in reversed(doomed):
  87             del remaining_edges[i]
  88
  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)))
  94
  95
  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)
 100
 101
 102 def verify_graph_connected_under_vertex_failures(edges, vertices,
 103                                                  edge_vertices):
 104     """The graph stays connected when any single vertex is removed."""
 105     for v in vertices:
 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)
 109
 110
 111 def verify_graph_forest(edges, vertices, edge_vertices):
 112     """The graph contains no loops. A forest that is also connected is a
 113     tree."""
 114     trees = [set(e) for e in edges]
 115     while True:
 116         for a, b in itertools.combinations(trees, 2):
 117             intersection = a & b
 118             if intersection:
 119                 if len(intersection) == 1:
 120                     a |= b
 121                     trees.remove(b)
 122                     break
 123                 else:
 124                     raise GraphError("there is a loop in the graph\n"
 125                                      " vertices %s\n edges %s\n"
 126                                      " intersection %s" %
 127                                      (vertices, edges, intersection))
 128         else:
 129             # no break in itertools.combinations loop means no
 130             # further mergers, so we're done.
 131             #
 132             # XXX here we also know whether it is a tree or a
 133             # forest by len(trees) but the connected test already
 134             # tells us that.
 135             return
 136
 137
 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.
 142
 143     e.g.:
 144                         o
 145     pass: o-o=o  o=o   (|)             fail:  o-o
 146             `o          o                     `o'
 147     """
 148     unique_edges = set(edges)
 149     trees = [set(e) for e in unique_edges]
 150     while True:
 151         for a, b in itertools.combinations(trees, 2):
 152             intersection = a & b
 153             if intersection:
 154                 if len(intersection) == 1:
 155                     a |= b
 156                     trees.remove(b)
 157                     break
 158                 else:
 159                     raise GraphError("there is a loop in the graph")
 160         else:
 161             return
 162
 163
 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)
 167     if lonely:
 168         raise GraphError("some vertices are not connected:\n%s" %
 169                          '\n'.join(sorted(lonely)))
 170
 171
 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)
 175     if unknown:
 176         raise GraphError("some edge vertices are seemingly unknown:\n%s" %
 177                          '\n'.join(sorted(unknown)))
 178
 179
 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.
 185
 186     There might be other connections that *aren't* part of the ring.
 187
 188     Deciding this for sure is NP-complete (the Hamiltonian path
 189     problem), but there are some easy failures that can be detected.
 190     So far we check for:
 191       - leaf nodes
 192       - disjoint subgraphs
 193       - robustness against edge and vertex failure
 194     """
 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:
 199         return
 200     if len(edges) < 2 * len(vertices):
 201         raise GraphError("directed double ring requires at least twice "
 202                          "as many edges as vertices")
 203
 204     # Reduce the problem space by looking only at bi-directional links.
 205     half_duplex = set(edges)
 206     duplex_links = set()
 207     for edge in 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)
 213
 214     # the Hamiltonian cycle problem is NP-complete in general, but we
 215     # can cheat a bit and prove a less strong result.
 216     #
 217     # We declutter the graph by replacing nodes with edges connecting
 218     # their neighbours.
 219     #
 220     #       A-B-C --> A-C
 221     #
 222     #    -A-B-C-   -->  -A--C-
 223     #       `D_           `D'_
 224     #
 225     # In the end there should be a single 2 vertex graph.
 226
 227     edge_map = {}
 228     for a, b in duplex_links:
 229         edge_map.setdefault(a, set()).add(b)
 230         edge_map.setdefault(b, set()).add(a)
 231
 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"
 236                              "(%s)" % vertex)
 237
 238     for vertex in edge_map.keys():
 239         nset = edge_map[vertex]
 240         if not nset:
 241             continue
 242         for n in nset:
 243             n_neighbours = edge_map[n]
 244             n_neighbours.remove(vertex)
 245             n_neighbours.update(x for x in nset if x != n)
 246         del edge_map[vertex]
 247
 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()))
 253
 254     verify_graph_connected_under_edge_failures(duplex_links, vertices,
 255                                                edge_vertices)
 256     verify_graph_connected_under_vertex_failures(duplex_links, vertices,
 257                                                  edge_vertices)
 258
 259
 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
 263     apply."""
 264     if len(vertices) < 2:
 265         return
 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]):
 271             return
 272         raise GraphError("A two vertex graph should have an edge each way.")
 273
 274     return verify_graph_directed_double_ring(edges, vertices, edge_vertices)
 275
 276
 277 def verify_graph(title, edges, vertices=None, directed=False, properties=(),
 278                  fatal=True, debug=null_debug):
 279     errors = []
 280     debug("%sStarting verify_graph for %s%s%s" % (PURPLE, MAGENTA, title,
 281                                                   C_NORMAL))
 282
 283     properties = [x.replace(' ', '_') for x in properties]
 284
 285     edge_vertices = set()
 286     for a, b in edges:
 287         edge_vertices.add(a)
 288         edge_vertices.add(b)
 289
 290     if vertices is None:
 291         vertices = edge_vertices
 292     else:
 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)))
 297
 298     for p in properties:
 299         fn = 'verify_graph_%s' % p
 300         try:
 301             f = globals()[fn]
 302         except KeyError:
 303             errors.append((p, "There is no verification check for '%s'" % p))
 304         try:
 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))
 309
 310     if errors:
 311         if fatal:
 312             raise GraphError("The '%s' graph lacks the following properties:"
 313                              "\n%s" %
 314                              (title, '\n'.join('%s: %s' % x for x in errors)))
 315         debug(("%s%s%s FAILED:" % (MAGENTA, title, RED)))
 316         for p, e in errors:
 317             debug(" %18s: %s%s%s" % (p, DARK_YELLOW, e, RED))
 318         debug(C_NORMAL)
 319
 320
 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,
 326                    vertex_colors=None):
 327
 328     title = '%s %s' % (basename, label or '')
 329     if verify:
 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)
 338
 339
 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_', ''))
 344             if v.__doc__:
 345                 print('    %s%s%s' % (GREY, v.__doc__.rstrip(), C_NORMAL))
 346             else:
 347                 print()