diff options
Diffstat (limited to 'lib/python2.7/site-packages/SQLAlchemy-0.7.0-py2.7-linux-x86_64.egg/sqlalchemy/util/topological.py')
-rwxr-xr-x | lib/python2.7/site-packages/SQLAlchemy-0.7.0-py2.7-linux-x86_64.egg/sqlalchemy/util/topological.py | 83 |
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] - ]) |