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