topology: check topology in ipa-replica-manage del

ipa-replica-manage del now:
- checks the whole current topology(before deletion), reports issues
- simulates deletion of server and checks the topology again, reports issues

Asks admin if he wants to continue with the deletion if any errors are found.

https://fedorahosted.org/freeipa/ticket/4302

Reviewed-By: David Kupka <dkupka@redhat.com>

1 files changed, 73 insertions, 0 deletions

diff --git a/ipapython/graph.py b/ipapython/graph.py
new file mode 100644
index 000000000..20b612548
--- /dev/null
+++ b/ipapython/graph.py
@@ -0,0 +1,73 @@
+#
+# Copyright (C) 2015  FreeIPA Contributors see COPYING for license
+#
+
+
+class Graph():
+    """
+    Simple oriented graph structure
+
+    G = (V, E) where G is graph, V set of vertices and E list of edges.
+    E = (tail, head) where tail and head are vertices
+    """
+
+    def __init__(self):
+        self.vertices = set()
+        self.edges = []
+        self._adj = dict()
+
+    def add_vertex(self, vertex):
+        self.vertices.add(vertex)
+        self._adj[vertex] = []
+
+    def add_edge(self, tail, head):
+        if tail not in self.vertices:
+            raise ValueError("tail is not a vertex")
+        if head not in self.vertices:
+            raise ValueError("head is not a vertex")
+        self.edges.append((tail, head))
+        self._adj[tail].append(head)
+
+    def remove_edge(self, tail, head):
+        self.edges.remove((tail, head))
+        self._adj[tail].remove(head)
+
+    def remove_vertex(self, vertex):
+        self.vertices.remove(vertex)
+
+        # delete _adjacencies
+        del self._adj[vertex]
+        for key, _adj in self._adj.iteritems():
+            _adj[:] = [v for v in _adj if v != vertex]
+
+        # delete edges
+        edges = [e for e in self.edges if e[0] != vertex and e[1] != vertex]
+        self.edges[:] = edges
+
+    def get_tails(self, head):
+        """
+        Get list of vertices where a vertex is on the right side of an edge
+        """
+        return [e[0] for e in self.edges if e[1] == head]
+
+    def get_heads(self, tail):
+        """
+        Get list of vertices where a vertex is on the left side of an edge
+        """
+        return [e[1] for e in self.edges if e[0] == tail]
+
+    def bfs(self, start=None):
+        """
+        Breadth-first search traversal of the graph from `start` vertex.
+        Return a set of all visited vertices
+        """
+        if not start:
+            start = list(self.vertices)[0]
+        visited = set()
+        queue = [start]
+        while queue:
+            vertex = queue.pop(0)
+            if vertex not in visited:
+                visited.add(vertex)
+                queue.extend(set(self._adj.get(vertex, [])) - visited)
+        return visited