python/samba/kcc/graph.py

   1 # Graph functions used by KCC intersite
   2 #
   3 # Copyright (C) Dave Craft 2011
   4 # Copyright (C) Andrew Bartlett 2015
   5 #
   6 # Andrew Bartlett's alleged work performed by his underlings Douglas
   7 # Bagnall and Garming Sam.
   8 #
   9 # This program is free software; you can redistribute it and/or modify
  10 # it under the terms of the GNU General Public License as published by
  11 # the Free Software Foundation; either version 3 of the License, or
  12 # (at your option) any later version.
  13 #
  14 # This program is distributed in the hope that it will be useful,
  15 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 # GNU General Public License for more details.
  18 #
  19 # You should have received a copy of the GNU General Public License
  20 # along with this program.  If not, see <http://www.gnu.org/licenses/>.
  21
  22 import itertools
  23 import heapq
  24
  25 from samba.kcc.graph_utils import write_dot_file, verify_and_dot, verify_graph
  26 from samba.ndr import ndr_pack
  27 from samba.dcerpc import misc
  28
  29 from samba.kcc.debug import DEBUG, DEBUG_FN
  30
  31 MAX_DWORD = 2 ** 32 - 1
  32
  33
  34 class ReplInfo(object):
  35     """Represents information about replication
  36
  37     NTDSConnections use one representation a replication schedule, and
  38     graph vertices use another. This is the Vertex one.
  39
  40     """
  41     def __init__(self):
  42         self.cost = 0
  43         self.interval = 0
  44         self.options = 0
  45         self.schedule = None
  46
  47
  48 def total_schedule(schedule):
  49     """Return the total number of 15 minute windows in which the schedule
  50     is set to replicate in a week. If the schedule is None it is
  51     assumed that the replication will happen in every 15 minute
  52     window.
  53
  54     This is essentially a bit population count.
  55     """
  56
  57     if schedule is None:
  58         return 84 * 8  # 84 bytes = 84 * 8 bits
  59
  60     total = 0
  61     for byte in schedule:
  62         while byte != 0:
  63             total += byte & 1
  64             byte >>= 1
  65     return total
  66
  67
  68 def convert_schedule_to_repltimes(schedule):
  69     """Convert NTDS Connection schedule to replTime schedule.
  70
  71     Schedule defined in  MS-ADTS 6.1.4.5.2
  72     ReplTimes defined in MS-DRSR 5.164.
  73
  74     "Schedule" has 168 bytes but only the lower nibble of each is
  75     significant. There is one byte per hour. Bit 3 (0x08) represents
  76     the first 15 minutes of the hour and bit 0 (0x01) represents the
  77     last 15 minutes. The first byte presumably covers 12am - 1am
  78     Sunday, though the spec doesn't define the start of a week.
  79
  80     "ReplTimes" has 84 bytes which are the 168 lower nibbles of
  81     "Schedule" packed together. Thus each byte covers 2 hours. Bits 7
  82     (i.e. 0x80) is the first 15 minutes and bit 0 is the last. The
  83     first byte covers Sunday 12am - 2am (per spec).
  84
  85     Here we pack two elements of the NTDS Connection schedule slots
  86     into one element of the replTimes list.
  87
  88     If no schedule appears in NTDS Connection then a default of 0x11
  89     is set in each replTimes slot as per behaviour noted in a Windows
  90     DC. That default would cause replication within the last 15
  91     minutes of each hour.
  92     """
  93     if schedule is None or schedule.dataArray[0] is None:
  94         return [0x11] * 84
  95
  96     times = []
  97     data = schedule.dataArray[0].slots
  98
  99     for i in range(84):
 100         times.append((data[i * 2] & 0xF) << 4 | (data[i * 2 + 1] & 0xF))
 101
 102     return times
 103
 104
 105 # Returns true if schedule intersect
 106 def combine_repl_info(info_a, info_b, info_c):
 107     """Set a replInfo to be the intersection of two others
 108
 109     If there is any overlap in the replication times specified by the
 110     first two parameters, the third replInfo parameter is set up with
 111     that overlap, and True is returned. If there is no overlap, the
 112     third parameter is unchanged and False is returned.
 113
 114     :param info_a: An input replInfo object
 115     :param info_b: An input replInfo object
 116     :param info_c: The result replInfo, set to the intersection of A and B
 117                    if the intersection is non-empty.
 118     :return: True if info_c allows any replication at all, otherwise False
 119     """
 120     info_c.interval = max(info_a.interval, info_b.interval)
 121     info_c.options = info_a.options & info_b.options
 122
 123     if info_a.schedule is None:
 124         info_a.schedule = [0xFF] * 84
 125     if info_b.schedule is None:
 126         info_b.schedule = [0xFF] * 84
 127
 128     new_info = [a & b for a, b in zip(info_a.schedule, info_b.schedule)]
 129
 130     if not any(new_info):
 131         return False
 132
 133     info_c.schedule = new_info
 134
 135     # Truncate to MAX_DWORD
 136     info_c.cost = info_a.cost + info_b.cost
 137     if info_c.cost > MAX_DWORD:
 138         info_c.cost = MAX_DWORD
 139
 140     return True
 141
 142
 143 def get_spanning_tree_edges(graph, my_site, label=None, verify=False,
 144                             dot_file_dir=None):
 145     """Find edges for the intersite graph
 146
 147     From MS-ADTS 6.2.2.3.4.4
 148
 149     :param graph: a kcc.kcc_utils.Graph object
 150     :param my_site: the topology generator's site
 151     :param label: a label for use in dot files and verification
 152     :param verify: if True, try to verify that graph properties are correct
 153     :param dot_file_dir: if not None, write Graphviz dot files here
 154     """
 155     # Phase 1: Run Dijkstra's to get a list of internal edges, which are
 156     # just the shortest-paths connecting colored vertices
 157
 158     internal_edges = set()
 159
 160     for e_set in graph.edge_set:
 161         edgeType = None
 162         for v in graph.vertices:
 163             v.edges = []
 164
 165         # All con_type in an edge set is the same
 166         for e in e_set.edges:
 167             edgeType = e.con_type
 168             for v in e.vertices:
 169                 v.edges.append(e)
 170
 171         if verify or dot_file_dir is not None:
 172             graph_edges = [(a.site.site_dnstr, b.site.site_dnstr)
 173                            for a, b in
 174                            itertools.chain(
 175                                *(itertools.combinations(edge.vertices, 2)
 176                                  for edge in e_set.edges))]
 177             graph_nodes = [v.site.site_dnstr for v in graph.vertices]
 178
 179             if dot_file_dir is not None:
 180                 write_dot_file('edgeset_%s' % (edgeType,), graph_edges,
 181                                vertices=graph_nodes, label=label)
 182
 183             if verify:
 184                 verify_graph('spanning tree edge set %s' % edgeType,
 185                              graph_edges, vertices=graph_nodes,
 186                              properties=('complete', 'connected'),
 187                              debug=DEBUG)
 188
 189         # Run dijkstra's algorithm with just the red vertices as seeds
 190         # Seed from the full replicas
 191         dijkstra(graph, edgeType, False)
 192
 193         # Process edge set
 194         process_edge_set(graph, e_set, internal_edges)
 195
 196         # Run dijkstra's algorithm with red and black vertices as the seeds
 197         # Seed from both full and partial replicas
 198         dijkstra(graph, edgeType, True)
 199
 200         # Process edge set
 201         process_edge_set(graph, e_set, internal_edges)
 202
 203     # All vertices have root/component as itself
 204     setup_vertices(graph)
 205     process_edge_set(graph, None, internal_edges)
 206
 207     if verify or dot_file_dir is not None:
 208         graph_edges = [(e.v1.site.site_dnstr, e.v2.site.site_dnstr)
 209                        for e in internal_edges]
 210         graph_nodes = [v.site.site_dnstr for v in graph.vertices]
 211         verify_properties = ('multi_edge_forest',)
 212         verify_and_dot('prekruskal', graph_edges, graph_nodes, label=label,
 213                        properties=verify_properties, debug=DEBUG,
 214                        verify=verify, dot_file_dir=dot_file_dir)
 215
 216     # Phase 2: Run Kruskal's on the internal edges
 217     output_edges, components = kruskal(graph, internal_edges)
 218
 219     # This recalculates the cost for the path connecting the
 220     # closest red vertex. Ignoring types is fine because NO
 221     # suboptimal edge should exist in the graph
 222     dijkstra(graph, "EDGE_TYPE_ALL", False)  # TODO rename
 223     # Phase 3: Process the output
 224     for v in graph.vertices:
 225         if v.is_red():
 226             v.dist_to_red = 0
 227         else:
 228             v.dist_to_red = v.repl_info.cost
 229
 230     if verify or dot_file_dir is not None:
 231         graph_edges = [(e.v1.site.site_dnstr, e.v2.site.site_dnstr)
 232                        for e in internal_edges]
 233         graph_nodes = [v.site.site_dnstr for v in graph.vertices]
 234         verify_properties = ('multi_edge_forest',)
 235         verify_and_dot('postkruskal', graph_edges, graph_nodes,
 236                        label=label, properties=verify_properties,
 237                        debug=DEBUG, verify=verify,
 238                        dot_file_dir=dot_file_dir)
 239
 240     # Ensure only one-way connections for partial-replicas,
 241     # and make sure they point the right way.
 242     edge_list = []
 243     for edge in output_edges:
 244         # We know these edges only have two endpoints because we made
 245         # them.
 246         v, w = edge.vertices
 247         if v.site is my_site or w.site is my_site:
 248             if (((v.is_black() or w.is_black()) and
 249                  v.dist_to_red != MAX_DWORD)):
 250                 edge.directed = True
 251
 252                 if w.dist_to_red < v.dist_to_red:
 253                     edge.vertices[:] = w, v
 254             edge_list.append(edge)
 255
 256     if verify or dot_file_dir is not None:
 257         graph_edges = [[x.site.site_dnstr for x in e.vertices]
 258                        for e in edge_list]
 259         #add the reverse edge if not directed.
 260         graph_edges.extend([x.site.site_dnstr
 261                             for x in reversed(e.vertices)]
 262                            for e in edge_list if not e.directed)
 263         graph_nodes = [x.site.site_dnstr for x in graph.vertices]
 264         verify_properties = ()
 265         verify_and_dot('post-one-way-partial', graph_edges, graph_nodes,
 266                        label=label, properties=verify_properties,
 267                        debug=DEBUG, verify=verify,
 268                        directed=True,
 269                        dot_file_dir=dot_file_dir)
 270
 271     # count the components
 272     return edge_list, components
 273
 274
 275 def create_edge(con_type, site_link, guid_to_vertex):
 276     """Set up a MultiEdge for the intersite graph
 277
 278     A MultiEdge can have multiple vertices.
 279
 280     From MS-ADTS 6.2.2.3.4.4
 281
 282     :param con_type: a transport type GUID
 283     :param  site_link: a kcc.kcc_utils.SiteLink object
 284     :param guid_to_vertex: a mapping between GUIDs and vertices
 285     :return: a MultiEdge
 286     """
 287     e = MultiEdge()
 288     e.site_link = site_link
 289     e.vertices = []
 290     for site_guid in site_link.site_list:
 291         if str(site_guid) in guid_to_vertex:
 292             e.vertices.extend(guid_to_vertex.get(str(site_guid)))
 293     e.repl_info.cost = site_link.cost
 294     e.repl_info.options = site_link.options
 295     e.repl_info.interval = site_link.interval
 296     e.repl_info.schedule = convert_schedule_to_repltimes(site_link.schedule)
 297     e.con_type = con_type
 298     e.directed = False
 299     return e
 300
 301
 302 def create_auto_edge_set(graph, transport_guid):
 303     """Set up an automatic MultiEdgeSet for the intersite graph
 304
 305     From within MS-ADTS 6.2.2.3.4.4
 306
 307     :param graph: the intersite graph object
 308     :param transport_guid: a transport type GUID
 309     :return: a MultiEdgeSet
 310     """
 311     e_set = MultiEdgeSet()
 312     # use a NULL guid, not associated with a SiteLinkBridge object
 313     e_set.guid = misc.GUID()
 314     for site_link in graph.edges:
 315         if site_link.con_type == transport_guid:
 316             e_set.edges.append(site_link)
 317
 318     return e_set
 319
 320
 321 def create_edge_set(graph, transport, site_link_bridge):
 322     # TODO not implemented - need to store all site link bridges
 323     raise NotImplementedError("We don't create fancy edge sets")
 324
 325
 326 def setup_vertices(graph):
 327     for v in graph.vertices:
 328         if v.is_white():
 329             v.repl_info.cost = MAX_DWORD
 330             v.root = None
 331             v.component_id = None
 332         else:
 333             v.repl_info.cost = 0
 334             v.root = v
 335             v.component_id = v
 336
 337         v.repl_info.interval = 0
 338         v.repl_info.options = 0xFFFFFFFF
 339         v.repl_info.schedule = None  # TODO highly suspicious
 340         v.demoted = False
 341
 342
 343 def dijkstra(graph, edge_type, include_black):
 344     queue = []
 345     setup_dijkstra(graph, edge_type, include_black, queue)
 346     while len(queue) > 0:
 347         cost, guid, vertex = heapq.heappop(queue)
 348         for edge in vertex.edges:
 349             for v in edge.vertices:
 350                 if v is not vertex:
 351                     # add new path from vertex to v
 352                     try_new_path(graph, queue, vertex, edge, v)
 353
 354
 355 def setup_dijkstra(graph, edge_type, include_black, queue):
 356     setup_vertices(graph)
 357     for vertex in graph.vertices:
 358         if vertex.is_white():
 359             continue
 360
 361         if (((vertex.is_black() and not include_black)
 362              or edge_type not in vertex.accept_black
 363              or edge_type not in vertex.accept_red_red)):
 364             vertex.repl_info.cost = MAX_DWORD
 365             vertex.root = None  # NULL GUID
 366             vertex.demoted = True  # Demoted appears not to be used
 367         else:
 368             heapq.heappush(queue, (vertex.repl_info.cost, vertex.guid, vertex))
 369
 370
 371 def try_new_path(graph, queue, vfrom, edge, vto):
 372     newRI = ReplInfo()
 373     #This function combines the repl_info and checks is that there is
 374     # a valid time frame for which replication can actually occur,
 375     # despite being adequately connected
 376     intersect = combine_repl_info(vfrom.repl_info, edge.repl_info, newRI)
 377
 378     # If the new path costs more than the current, then ignore the edge
 379     if newRI.cost > vto.repl_info.cost:
 380         return
 381
 382     if newRI.cost < vto.repl_info.cost and not intersect:
 383         return
 384
 385     new_duration = total_schedule(newRI.schedule)
 386     old_duration = total_schedule(vto.repl_info.schedule)
 387
 388     # Cheaper or longer schedule
 389     if newRI.cost < vto.repl_info.cost or new_duration > old_duration:
 390         vto.root = vfrom.root
 391         vto.component_id = vfrom.component_id
 392         vto.repl_info = newRI
 393         heapq.heappush(queue, (vto.repl_info.cost, vto.guid, vto))
 394
 395
 396 def check_demote_vertex(vertex, edge_type):
 397     if vertex.is_white():
 398         return
 399
 400     # Accepts neither red-red nor black edges, demote
 401     if ((edge_type not in vertex.accept_black and
 402          edge_type not in vertex.accept_red_red)):
 403         vertex.repl_info.cost = MAX_DWORD
 404         vertex.root = None
 405         vertex.demoted = True  # Demoted appears not to be used
 406
 407
 408 def undemote_vertex(vertex):
 409     if vertex.is_white():
 410         return
 411
 412     vertex.repl_info.cost = 0
 413     vertex.root = vertex
 414     vertex.demoted = False
 415
 416
 417 def process_edge_set(graph, e_set, internal_edges):
 418     if e_set is None:
 419         for edge in graph.edges:
 420             for vertex in edge.vertices:
 421                 check_demote_vertex(vertex, edge.con_type)
 422             process_edge(graph, edge, internal_edges)
 423             for vertex in edge.vertices:
 424                 undemote_vertex(vertex)
 425     else:
 426         for edge in e_set.edges:
 427             process_edge(graph, edge, internal_edges)
 428
 429
 430 def process_edge(graph, examine, internal_edges):
 431     # Find the set of all vertices touches the edge to examine
 432     vertices = []
 433     for v in examine.vertices:
 434         # Append a 4-tuple of color, repl cost, guid and vertex
 435         vertices.append((v.color, v.repl_info.cost, v.ndrpacked_guid, v))
 436     # Sort by color, lower
 437     DEBUG("vertices is %s" % vertices)
 438     vertices.sort()
 439
 440     color, cost, guid, bestv = vertices[0]
 441     # Add to internal edges an edge from every colored vertex to bestV
 442     for v in examine.vertices:
 443         if v.component_id is None or v.root is None:
 444             continue
 445
 446         # Only add edge if valid inter-tree edge - needs a root and
 447         # different components
 448         if ((bestv.component_id is not None and
 449              bestv.root is not None and
 450              v.component_id is not None and
 451              v.root is not None and
 452              bestv.component_id != v.component_id)):
 453             add_int_edge(graph, internal_edges, examine, bestv, v)
 454
 455
 456 # Add internal edge, endpoints are roots of the vertices to pass in
 457 # and are always red or black
 458 def add_int_edge(graph, internal_edges, examine, v1, v2):
 459     root1 = v1.root
 460     root2 = v2.root
 461
 462     red_red = False
 463     if root1.is_red() and root2.is_red():
 464         red_red = True
 465
 466     if red_red:
 467         if ((examine.con_type not in root1.accept_red_red
 468              or examine.con_type not in root2.accept_red_red)):
 469             return
 470     elif (examine.con_type not in root1.accept_black
 471           or examine.con_type not in root2.accept_black):
 472         return
 473
 474     ri = ReplInfo()
 475     ri2 = ReplInfo()
 476
 477     # Create the transitive replInfo for the two trees and this edge
 478     if not combine_repl_info(v1.repl_info, v2.repl_info, ri):
 479         return
 480     # ri is now initialized
 481     if not combine_repl_info(ri, examine.repl_info, ri2):
 482         return
 483
 484     newIntEdge = InternalEdge(root1, root2, red_red, ri2, examine.con_type,
 485                               examine.site_link)
 486     # Order by vertex guid
 487     #XXX guid comparison using ndr_pack
 488     if newIntEdge.v1.ndrpacked_guid > newIntEdge.v2.ndrpacked_guid:
 489         newIntEdge.v1 = root2
 490         newIntEdge.v2 = root1
 491
 492     internal_edges.add(newIntEdge)
 493
 494
 495 def kruskal(graph, edges):
 496     for v in graph.vertices:
 497         v.edges = []
 498
 499     components = set([x for x in graph.vertices if not x.is_white()])
 500     edges = list(edges)
 501
 502     # Sorted based on internal comparison function of internal edge
 503     edges.sort()
 504
 505     #XXX expected_num_tree_edges is never used
 506     expected_num_tree_edges = 0  # TODO this value makes little sense
 507
 508     count_edges = 0
 509     output_edges = []
 510     index = 0
 511     while index < len(edges):  # TODO and num_components > 1
 512         e = edges[index]
 513         parent1 = find_component(e.v1)
 514         parent2 = find_component(e.v2)
 515         if parent1 is not parent2:
 516             count_edges += 1
 517             add_out_edge(graph, output_edges, e)
 518             parent1.component_id = parent2
 519             components.discard(parent1)
 520
 521         index += 1
 522
 523     return output_edges, len(components)
 524
 525
 526 def find_component(vertex):
 527     if vertex.component_id is vertex:
 528         return vertex
 529
 530     current = vertex
 531     while current.component_id is not current:
 532         current = current.component_id
 533
 534     root = current
 535     current = vertex
 536     while current.component_id is not root:
 537         n = current.component_id
 538         current.component_id = root
 539         current = n
 540
 541     return root
 542
 543
 544 def add_out_edge(graph, output_edges, e):
 545     v1 = e.v1
 546     v2 = e.v2
 547
 548     # This multi-edge is a 'real' edge with no GUID
 549     ee = MultiEdge()
 550     ee.directed = False
 551     ee.site_link = e.site_link
 552     ee.vertices.append(v1)
 553     ee.vertices.append(v2)
 554     ee.con_type = e.e_type
 555     ee.repl_info = e.repl_info
 556     output_edges.append(ee)
 557
 558     v1.edges.append(ee)
 559     v2.edges.append(ee)
 560
 561
 562 def setup_graph(part, site_table, transport_guid, sitelink_table,
 563                 bridges_required):
 564     """Set up a GRAPH, populated with a VERTEX for each site
 565     object, a MULTIEDGE for each siteLink object, and a
 566     MUTLIEDGESET for each siteLinkBridge object (or implied
 567     siteLinkBridge).
 568
 569     ::returns: a new graph
 570     """
 571     guid_to_vertex = {}
 572     # Create graph
 573     g = IntersiteGraph()
 574     # Add vertices
 575     for site_guid, site in site_table.items():
 576         vertex = Vertex(site, part)
 577         vertex.guid = site_guid
 578         vertex.ndrpacked_guid = ndr_pack(site.site_guid)
 579         g.vertices.add(vertex)
 580         guid_vertices = guid_to_vertex.setdefault(site_guid, [])
 581         guid_vertices.append(vertex)
 582
 583     connected_vertices = set()
 584
 585     for site_link_dn, site_link in sitelink_table.items():
 586         new_edge = create_edge(transport_guid, site_link,
 587                                guid_to_vertex)
 588         connected_vertices.update(new_edge.vertices)
 589         g.edges.add(new_edge)
 590
 591     # If 'Bridge all site links' is enabled and Win2k3 bridges required
 592     # is not set
 593     # NTDSTRANSPORT_OPT_BRIDGES_REQUIRED 0x00000002
 594     # No documentation for this however, ntdsapi.h appears to have:
 595     # NTDSSETTINGS_OPT_W2K3_BRIDGES_REQUIRED = 0x00001000
 596     if bridges_required:
 597         g.edge_set.add(create_auto_edge_set(g, transport_guid))
 598     else:
 599         # TODO get all site link bridges
 600         for site_link_bridge in []:
 601             g.edge_set.add(create_edge_set(g, transport_guid,
 602                                            site_link_bridge))
 603
 604     g.connected_vertices = connected_vertices
 605
 606     return g
 607
 608
 609 class VertexColor(object):
 610     (red, black, white, unknown) = range(0, 4)
 611
 612
 613 class Vertex(object):
 614     """Class encapsulation of a Site Vertex in the
 615     intersite topology replication algorithm
 616     """
 617     def __init__(self, site, part):
 618         self.site = site
 619         self.part = part
 620         self.color = VertexColor.unknown
 621         self.edges = []
 622         self.accept_red_red = []
 623         self.accept_black = []
 624         self.repl_info = ReplInfo()
 625         self.root = self
 626         self.guid = None
 627         self.component_id = self
 628         self.demoted = False
 629         self.options = 0
 630         self.interval = 0
 631
 632     def color_vertex(self):
 633         """Color each vertex to indicate which kind of NC
 634         replica it contains
 635         """
 636         # IF s contains one or more DCs with full replicas of the
 637         # NC cr!nCName
 638         #    SET v.Color to COLOR.RED
 639         # ELSEIF s contains one or more partial replicas of the NC
 640         #    SET v.Color to COLOR.BLACK
 641         #ELSE
 642         #    SET v.Color to COLOR.WHITE
 643
 644         # set to minimum (no replica)
 645         self.color = VertexColor.white
 646
 647         for dnstr, dsa in self.site.dsa_table.items():
 648             rep = dsa.get_current_replica(self.part.nc_dnstr)
 649             if rep is None:
 650                 continue
 651
 652             # We have a full replica which is the largest
 653             # value so exit
 654             if not rep.is_partial():
 655                 self.color = VertexColor.red
 656                 break
 657             else:
 658                 self.color = VertexColor.black
 659
 660     def is_red(self):
 661         assert(self.color != VertexColor.unknown)
 662         return (self.color == VertexColor.red)
 663
 664     def is_black(self):
 665         assert(self.color != VertexColor.unknown)
 666         return (self.color == VertexColor.black)
 667
 668     def is_white(self):
 669         assert(self.color != VertexColor.unknown)
 670         return (self.color == VertexColor.white)
 671
 672
 673 class IntersiteGraph(object):
 674     """Graph for representing the intersite"""
 675     def __init__(self):
 676         self.vertices = set()
 677         self.edges = set()
 678         self.edge_set = set()
 679         # All vertices that are endpoints of edges
 680         self.connected_vertices = None
 681
 682
 683 class MultiEdgeSet(object):
 684     """Defines a multi edge set"""
 685     def __init__(self):
 686         self.guid = 0  # objectGuid siteLinkBridge
 687         self.edges = []
 688
 689
 690 class MultiEdge(object):
 691     def __init__(self):
 692         self.site_link = None  # object siteLink
 693         self.vertices = []
 694         self.con_type = None  # interSiteTransport GUID
 695         self.repl_info = ReplInfo()
 696         self.directed = True
 697
 698
 699 class InternalEdge(object):
 700     def __init__(self, v1, v2, redred, repl, eType, site_link):
 701         self.v1 = v1
 702         self.v2 = v2
 703         self.red_red = redred
 704         self.repl_info = repl
 705         self.e_type = eType
 706         self.site_link = site_link
 707
 708     def __eq__(self, other):
 709         return not self < other and not other < self
 710
 711     def __ne__(self, other):
 712         return self < other or other < self
 713
 714     def __gt__(self, other):
 715         return other < self
 716
 717     def __ge__(self, other):
 718         return not self < other
 719
 720     def __le__(self, other):
 721         return not other < self
 722
 723     # TODO compare options and interval
 724     def __lt__(self, other):
 725         if self.red_red != other.red_red:
 726             return self.red_red
 727
 728         if self.repl_info.cost != other.repl_info.cost:
 729             return self.repl_info.cost < other.repl_info.cost
 730
 731         self_time = total_schedule(self.repl_info.schedule)
 732         other_time = total_schedule(other.repl_info.schedule)
 733         if self_time != other_time:
 734             return self_time > other_time
 735
 736         #XXX guid comparison using ndr_pack
 737         if self.v1.guid != other.v1.guid:
 738             return self.v1.ndrpacked_guid < other.v1.ndrpacked_guid
 739
 740         if self.v2.guid != other.v2.guid:
 741             return self.v2.ndrpacked_guid < other.v2.ndrpacked_guid
 742
 743         return self.e_type < other.e_type