Gecko [ biogenelab.eu ]

Name	Size	Permission
__init__.py	2.32 KB	-rw-r--r--
__init__.pyc	3.7 KB	-rw-r--r--
_collections.py	24.48 KB	-rw-r--r--
_collections.pyc	41.6 KB	-rw-r--r--
compat.py	6.65 KB	-rw-r--r--
compat.pyc	8.71 KB	-rw-r--r--
deprecations.py	4.3 KB	-rw-r--r--
deprecations.pyc	5.47 KB	-rw-r--r--
langhelpers.py	36.86 KB	-rw-r--r--
langhelpers.pyc	43.99 KB	-rw-r--r--
queue.py	6.39 KB	-rw-r--r--
queue.pyc	6.94 KB	-rw-r--r--
topological.py	2.53 KB	-rw-r--r--
topological.pyc	2.19 KB	-rw-r--r--

Code Editor : topological.py

# util/topological.py
# Copyright (C) 2005-2014 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 ..exc import CircularDependencyError
from .. 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):
    # adapted from:
    # http://neopythonic.blogspot.com/2009/01/detecting-cycles-in-directed-graph.html

edges = util.defaultdict(set)
    for parent, child in tuples:
        edges[parent].add(child)
    nodes_to_test = set(edges)

output = set()

# we'd like to find all nodes that are
    # involved in cycles, so we do the full
    # pass through the whole thing for each
    # node in the original list.

# we can go just through parent edge nodes.
    # if a node is only a child and never a parent,
    # by definition it can't be part of a cycle.  same
    # if it's not in the edges at all.
    for node in nodes_to_test:
        stack = [node]
        todo = nodes_to_test.difference(stack)
        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]
    ])

${this.title}

Code Editor : topological.py