1 files changed, 105 insertions, 0 deletions
diff --git a/pyanaconda/storage/tsort.py b/pyanaconda/storage/tsort.py
new file mode 100644
index 000000000..52a871f56
--- /dev/null
+++ b/pyanaconda/storage/tsort.py
@@ -0,0 +1,105 @@
+#!/usr/bin/python
+# tsort.py
+# Topological sorting.
+#
+# Copyright (C) 2010  Red Hat, Inc.
+#
+# This copyrighted material is made available to anyone wishing to use,
+# modify, copy, or redistribute it subject to the terms and conditions of
+# the GNU General Public License v.2, or (at your option) any later version.
+# This program is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY expressed or implied, including the implied warranties of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General
+# Public License for more details.  You should have received a copy of the
+# GNU General Public License along with this program; if not, write to the
+# Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+# 02110-1301, USA.  Any Red Hat trademarks that are incorporated in the
+# source code or documentation are not subject to the GNU General Public
+# License and may only be used or replicated with the express permission of
+# Red Hat, Inc.
+#
+# Red Hat Author(s): Dave Lehman <dlehman@redhat.com>
+#
+
+class CyclicGraphError(Exception):
+    pass
+
+def tsort(graph):
+    order = []  # sorted list of items
+
+    if not graph or not graph['items']:
+        return order
+
+    # determine which nodes have no incoming edges
+    roots = [n for n in graph['items'] if graph['incoming'][n] == 0]
+    if not roots:
+        raise CyclicGraphError("no root nodes")
+
+    visited = []    # list of nodes visited, for cycle detection
+    while roots:
+        # remove a root, add it to the order
+        root = roots.pop()
+        if root in visited:
+            raise CyclicGraphError("graph contains cycles")
+
+        visited.append(root)
+        i = graph['items'].index(root)
+        order.append(root)
+        # remove each edge from the root to another node
+        for (parent, child) in [e for e in graph['edges'] if e[0] == root]:
+            graph['incoming'][child] -= 1
+            graph['edges'].remove((parent, child))
+            # if destination node is now a root, add it to roots
+            if graph['incoming'][child] == 0:
+                roots.append(child)
+
+    if len(graph['items']) != len(visited):
+        raise CyclicGraphError("graph contains cycles")
+
+
+    return order
+
+def create_graph(items, edges):
+    """ Create a graph based on a list of items and a list of edges.
+
+        Arguments:
+
+            items   -   an iterable containing (hashable) items to sort
+            edges   -   an iterable containing (parent, child) edge pair tuples
+
+        Return Value:
+
+            The return value is a dictionary representing the directed graph.
+            It has three keys:
+
+                items is the same as the input argument of the same name
+                edges is the same as the input argument of the same name
+                incoming is a dict of incoming edge count hashed by item
+
+    """
+    graph = {'items': [],       # the items to sort
+             'edges': [],       # partial order info: (parent, child) pairs
+             'incoming': {}}    # incoming edge count for each item
+
+    graph['items'] = items
+    graph['edges'] = edges
+    for item in items:
+        graph['incoming'][item] = 0
+
+    for (parent, child) in edges:
+        graph['incoming'][child] += 1
+
+    return graph 
+
+
+if __name__ == "__main__":
+
+    items = [5, 2, 3, 4, 1]
+    edges = [(1, 2), (2, 4), (4, 5), (3, 2)]
+
+    print items
+    print edges
+
+    graph = create_graph(items, edges)
+    print tsort(graph)
+