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 import os
  22 import itertools
  23
  24 from samba.kcc.debug import null_debug, PURPLE, MAGENTA, DARK_YELLOW, RED
  25 from samba.kcc.debug import DARK_GREEN, C_NORMAL, GREY
  26
  27
  28 def write_dot_file(basename, edge_list, vertices=None, label=None,
  29                    dot_file_dir=None, reformat_labels=True, directed=False,
  30                    debug=None, edge_colors=None, edge_labels=None,
  31                    vertex_colors=None):
  32     if label:
  33         # sanitise DN and guid labels
  34         basename += '_' + label.translate(None, ', ')
  35
  36     f = open(os.path.join(dot_file_dir, "%s.dot" % basename), 'w')
  37
  38     if debug is not None:
  39         debug(f.name)
  40     graphname = ''.join(x for x in basename if x.isalnum())
  41     print >>f, '%s %s {' % ('digraph' if directed else 'graph', graphname)
  42     print >>f, 'label="%s";\nfontsize=20;' % (label or graphname)
  43     if vertices:
  44         for i, v in enumerate(vertices):
  45             if reformat_labels:
  46                 v = v.replace(',', '\\n')
  47             vc = ('color="%s"' % vertex_colors[i]) if vertex_colors else ''
  48             print >>f, '"%s" [%s];' % (v, vc)
  49
  50     for i, edge in enumerate(edge_list):
  51         a, b = edge
  52         if reformat_labels:
  53             a = a.replace(',', '\\n')
  54             b = b.replace(',', '\\n')
  55         line = '->' if directed else '--'
  56         el = ('label="%s"' % edge_labels[i]) if edge_labels else ''
  57         ec = ('color="%s"' % edge_colors[i]) if edge_colors else ''
  58         print >>f, '"%s" %s "%s" [%s %s];' % (a, line, b, el, ec)
  59     print >>f, '}'
  60     f.close()
  61
  62
  63 class GraphError(Exception):
  64     pass
  65
  66
  67 def verify_graph_complete(edges, vertices, edge_vertices):
  68     """The graph is complete, which is to say there is an edge between
  69     every pair of nodes."""
  70     for v in vertices:
  71         remotes = set()
  72         for a, b in edges:
  73             if a == v:
  74                 remotes.add(b)
  75             elif b == v:
  76                 remotes.add(a)
  77         if len(remotes) + 1 != len(vertices):
  78             raise GraphError("graph is not fully connected")
  79
  80
  81 def verify_graph_connected(edges, vertices, edge_vertices):
  82     """There is a path between any two nodes."""
  83     if not edges:
  84         if len(vertices) <= 1:
  85             return
  86         raise GraphError("disconnected vertices were found:\n"
  87                          "vertices: %s\n edges: %s" %
  88                          (sorted(vertices), sorted(edges)))
  89
  90     remaining_edges = list(edges)
  91     reached = set(remaining_edges.pop())
  92     while True:
  93         doomed = []
  94         for i, e in enumerate(remaining_edges):
  95             a, b = e
  96             if a in reached:
  97                 reached.add(b)
  98                 doomed.append(i)
  99             elif b in reached:
 100                 reached.add(a)
 101                 doomed.append(i)
 102         if not doomed:
 103             break
 104         for i in reversed(doomed):
 105             del remaining_edges[i]
 106
 107     if remaining_edges or reached != set(vertices):
 108         raise GraphError("graph is not connected:\n vertices: %s\n edges: %s\n"
 109                          " reached: %s\n remaining edges: %s" %
 110                          (sorted(vertices), sorted(edges),
 111                           sorted(reached), sorted(remaining_edges)))
 112
 113
 114 def verify_graph_connected_under_edge_failures(edges, vertices, edge_vertices):
 115     """The graph stays connected when any single edge is removed."""
 116     for subset in itertools.combinations(edges, len(edges) - 1):
 117         verify_graph_connected(subset, vertices, edge_vertices)
 118
 119
 120 def verify_graph_connected_under_vertex_failures(edges, vertices,
 121                                                  edge_vertices):
 122     """The graph stays connected when any single vertex is removed."""
 123     for v in vertices:
 124         sub_vertices = [x for x in vertices if x is not v]
 125         sub_edges = [x for x in edges if v not in x]
 126         verify_graph_connected(sub_edges, sub_vertices, sub_vertices)
 127
 128
 129 def verify_graph_forest(edges, vertices, edge_vertices):
 130     """The graph contains no loops. A forest that is also connected is a
 131     tree."""
 132     trees = [set(e) for e in edges]
 133     while True:
 134         for a, b in itertools.combinations(trees, 2):
 135             intersection = a & b
 136             if intersection:
 137                 if len(intersection) == 1:
 138                     a |= b
 139                     trees.remove(b)
 140                     break
 141                 else:
 142                     raise GraphError("there is a loop in the graph\n"
 143                                      " vertices %s\n edges %s\n"
 144                                      " intersection %s" %
 145                                      (vertices, edges, intersection))
 146         else:
 147             # no break in itertools.combinations loop means no
 148             # further mergers, so we're done.
 149             #
 150             # XXX here we also know whether it is a tree or a
 151             # forest by len(trees) but the connected test already
 152             # tells us that.
 153             return
 154
 155
 156 def verify_graph_multi_edge_forest(edges, vertices, edge_vertices):
 157     """This allows a forest with duplicate edges. That is if multiple
 158     edges go between the same two vertices, they are treated as a
 159     single edge by this test.
 160
 161     e.g.:
 162                         o
 163     pass: o-o=o  o=o   (|)             fail:  o-o
 164             `o          o                     `o'
 165     """
 166     unique_edges = set(edges)
 167     trees = [set(e) for e in unique_edges]
 168     while True:
 169         for a, b in itertools.combinations(trees, 2):
 170             intersection = a & b
 171             if intersection:
 172                 if len(intersection) == 1:
 173                     a |= b
 174                     trees.remove(b)
 175                     break
 176                 else:
 177                     raise GraphError("there is a loop in the graph")
 178         else:
 179             return
 180
 181
 182 def verify_graph_no_lonely_vertices(edges, vertices, edge_vertices):
 183     """There are no vertices without edges."""
 184     lonely = set(vertices) - set(edge_vertices)
 185     if lonely:
 186         raise GraphError("some vertices are not connected:\n%s" %
 187                          '\n'.join(sorted(lonely)))
 188
 189
 190 def verify_graph_no_unknown_vertices(edges, vertices, edge_vertices):
 191     """The edge endpoints contain no vertices that are otherwise unknown."""
 192     unknown = set(edge_vertices) - set(vertices)
 193     if unknown:
 194         raise GraphError("some edge vertices are seemingly unknown:\n%s" %
 195                          '\n'.join(sorted(unknown)))
 196
 197
 198 def verify_graph_directed_double_ring(edges, vertices, edge_vertices):
 199     """Each node has at least two directed edges leaving it, and two
 200     arriving. The edges work in pairs that have the same end points
 201     but point in opposite directions. The pairs form a path that
 202     touches every vertex and form a loop.
 203
 204     There might be other connections that *aren't* part of the ring.
 205
 206     Deciding this for sure is NP-complete (the Hamiltonian path
 207     problem), but there are some easy failures that can be detected.
 208     So far we check for:
 209       - leaf nodes
 210       - disjoint subgraphs
 211       - robustness against edge and vertex failure
 212     """
 213     # a zero or one node graph is OK with no edges.
 214     # The two vertex case is special. Use
 215     # verify_graph_directed_double_ring_or_small() to allow that.
 216     if not edges and len(vertices) <= 1:
 217         return
 218     if len(edges) < 2 * len(vertices):
 219         raise GraphError("directed double ring requires at least twice "
 220                          "as many edges as vertices")
 221
 222     # Reduce the problem space by looking only at bi-directional links.
 223     half_duplex = set(edges)
 224     duplex_links = set()
 225     for edge in edges:
 226         rev_edge = (edge[1], edge[0])
 227         if edge in half_duplex and rev_edge in half_duplex:
 228             duplex_links.add(edge)
 229             half_duplex.remove(edge)
 230             half_duplex.remove(rev_edge)
 231
 232     # the Hamiltonian cycle problem is NP-complete in general, but we
 233     # can cheat a bit and prove a less strong result.
 234     #
 235     # We declutter the graph by replacing nodes with edges connecting
 236     # their neighbours.
 237     #
 238     #       A-B-C --> A-C
 239     #
 240     #    -A-B-C-   -->  -A--C-
 241     #       `D_           `D'_
 242     #
 243     # In the end there should be a single 2 vertex graph.
 244
 245     edge_map = {}
 246     for a, b in duplex_links:
 247         edge_map.setdefault(a, set()).add(b)
 248         edge_map.setdefault(b, set()).add(a)
 249
 250     # an easy to detect failure is a lonely leaf node
 251     for vertex, neighbours in edge_map.items():
 252         if len(neighbours) == 1:
 253             raise GraphError("wanted double directed ring, found a leaf node"
 254                              "(%s)" % vertex)
 255
 256     for vertex in edge_map.keys():
 257         nset = edge_map[vertex]
 258         if not nset:
 259             continue
 260         for n in nset:
 261             n_neighbours = edge_map[n]
 262             n_neighbours.remove(vertex)
 263             n_neighbours.update(x for x in nset if x != n)
 264         del edge_map[vertex]
 265
 266     if len(edge_map) > 1:
 267         raise GraphError("wanted double directed ring, but "
 268                          "this looks like a split graph\n"
 269                          "(%s can't reach each other)" %
 270                          ', '.join(edge_map.keys()))
 271
 272     verify_graph_connected_under_edge_failures(duplex_links, vertices,
 273                                                edge_vertices)
 274     verify_graph_connected_under_vertex_failures(duplex_links, vertices,
 275                                                  edge_vertices)
 276
 277
 278 def verify_graph_directed_double_ring_or_small(edges, vertices, edge_vertices):
 279     """This performs the directed_double_ring test but makes special
 280     concessions for small rings where the strict rules don't really
 281     apply."""
 282     if len(vertices) < 2:
 283         return
 284     if len(vertices) == 2:
 285         """With 2 nodes there should be a single link in each directions."""
 286         if (len(edges) == 2 and
 287             edges[0][0] == edges[1][1] and
 288             edges[0][1] == edges[1][0]):
 289             return
 290         raise GraphError("A two vertex graph should have an edge each way.")
 291
 292     return verify_graph_directed_double_ring(edges, vertices, edge_vertices)
 293
 294
 295 def verify_graph(title, edges, vertices=None, directed=False, properties=(),
 296                  fatal=True, debug=null_debug):
 297     errors = []
 298     debug("%sStarting verify_graph for %s%s%s" % (PURPLE, MAGENTA, title,
 299                                                   C_NORMAL))
 300
 301     properties = [x.replace(' ', '_') for x in properties]
 302
 303     edge_vertices = set()
 304     for a, b in edges:
 305         edge_vertices.add(a)
 306         edge_vertices.add(b)
 307
 308     if vertices is None:
 309         vertices = edge_vertices
 310     else:
 311         vertices = set(vertices)
 312         if vertices != edge_vertices:
 313             debug("vertices in edges don't match given vertices:\n %s != %s" %
 314                   (sorted(edge_vertices), sorted(vertices)))
 315
 316     for p in properties:
 317         fn = 'verify_graph_%s' % p
 318         try:
 319             f = globals()[fn]
 320         except KeyError:
 321             errors.append((p, "There is no verification check for '%s'" % p))
 322         try:
 323             f(edges, vertices, edge_vertices)
 324             debug(" %s%18s:%s verified!" % (DARK_GREEN, p, C_NORMAL))
 325         except GraphError, e:
 326             errors.append((p, e))
 327
 328     if errors:
 329         if fatal:
 330             raise GraphError("The '%s' graph lacks the following properties:"
 331                              "\n%s" %
 332                              (title, '\n'.join('%s: %s' % x for x in errors)))
 333         debug(("%s%s%s FAILED:" % (MAGENTA, title, RED)))
 334         for p, e in errors:
 335             debug(" %18s: %s%s%s" % (p, DARK_YELLOW, e, RED))
 336         debug(C_NORMAL)
 337
 338
 339 def verify_and_dot(basename, edges, vertices=None, label=None,
 340                    reformat_labels=True, directed=False,
 341                    properties=(), fatal=True, debug=None,
 342                    verify=True, dot_file_dir=None,
 343                    edge_colors=None, edge_labels=None,
 344                    vertex_colors=None):
 345
 346     title = '%s %s' % (basename, label or '')
 347     if verify:
 348         verify_graph(title, edges, vertices, properties=properties,
 349                      fatal=fatal, debug=debug)
 350     if dot_file_dir is not None:
 351         write_dot_file(basename, edges, vertices=vertices, label=label,
 352                        dot_file_dir=dot_file_dir,
 353                        reformat_labels=reformat_labels, directed=directed,
 354                        debug=debug, edge_colors=edge_colors,
 355                        edge_labels=edge_labels, vertex_colors=vertex_colors)
 356
 357
 358 def list_verify_tests():
 359     for k, v in sorted(globals().items()):
 360         if k.startswith('verify_graph_'):
 361             print k.replace('verify_graph_', '')
 362             if v.__doc__:
 363                 print '    %s%s%s' % (GREY, v.__doc__.rstrip(), C_NORMAL)
 364             else:
 365                 print