aboutsummaryrefslogtreecommitdiffstats
path: root/lib/python2.7/site-packages/SQLAlchemy-0.7.0-py2.7-linux-x86_64.egg/sqlalchemy/util/topological.py
diff options
context:
space:
mode:
Diffstat (limited to 'lib/python2.7/site-packages/SQLAlchemy-0.7.0-py2.7-linux-x86_64.egg/sqlalchemy/util/topological.py')
-rwxr-xr-xlib/python2.7/site-packages/SQLAlchemy-0.7.0-py2.7-linux-x86_64.egg/sqlalchemy/util/topological.py83
1 files changed, 0 insertions, 83 deletions
diff --git a/lib/python2.7/site-packages/SQLAlchemy-0.7.0-py2.7-linux-x86_64.egg/sqlalchemy/util/topological.py b/lib/python2.7/site-packages/SQLAlchemy-0.7.0-py2.7-linux-x86_64.egg/sqlalchemy/util/topological.py
deleted file mode 100755
index 8f340647..00000000
--- a/lib/python2.7/site-packages/SQLAlchemy-0.7.0-py2.7-linux-x86_64.egg/sqlalchemy/util/topological.py
+++ /dev/null
@@ -1,83 +0,0 @@
-# util/topological.py
-# Copyright (C) 2005-2011 the SQLAlchemy authors and contributors <see AUTHORS file>
-#
-# This module is part of SQLAlchemy and is released under
-# the MIT License: http://www.opensource.org/licenses/mit-license.php
-
-"""Topological sorting algorithms."""
-
-from sqlalchemy.exc import CircularDependencyError
-from sqlalchemy import util
-
-
-__all__ = ['sort', 'sort_as_subsets', 'find_cycles']
-
-def sort_as_subsets(tuples, allitems):
-
- edges = util.defaultdict(set)
- for parent, child in tuples:
- edges[child].add(parent)
-
- todo = set(allitems)
-
- while todo:
- output = set()
- for node in list(todo):
- if not todo.intersection(edges[node]):
- output.add(node)
-
- if not output:
- raise CircularDependencyError(
- "Circular dependency detected",
- find_cycles(tuples, allitems),
- _gen_edges(edges)
- )
-
- todo.difference_update(output)
- yield output
-
-def sort(tuples, allitems):
- """sort the given list of items by dependency.
-
- 'tuples' is a list of tuples representing a partial ordering.
- """
-
- for set_ in sort_as_subsets(tuples, allitems):
- for s in set_:
- yield s
-
-def find_cycles(tuples, allitems):
- # straight from gvr with some mods
- todo = set(allitems)
-
- edges = util.defaultdict(set)
- for parent, child in tuples:
- edges[parent].add(child)
-
- output = set()
-
- while todo:
- node = todo.pop()
- stack = [node]
- while stack:
- top = stack[-1]
- for node in edges[top]:
- if node in stack:
- cyc = stack[stack.index(node):]
- todo.difference_update(cyc)
- output.update(cyc)
-
- if node in todo:
- stack.append(node)
- todo.remove(node)
- break
- else:
- node = stack.pop()
- return output
-
-def _gen_edges(edges):
- return set([
- (right, left)
- for left in edges
- for right in edges[left]
- ])