← Back to branch summary

~ubuntu-branches/debian/jessie/sqlalchemy/jessie

« back to all changes in this revision

Viewing changes to lib/sqlalchemy/util/topological.py

  • Committer: Package Import Robot
  • Author(s): Piotr Ożarowski, Jakub Wilk, Piotr Ożarowski
  • Date: 2013-07-06 20:53:52 UTC
  • mfrom: (1.4.23) (16.1.17 experimental)
  • Revision ID: package-import@ubuntu.com-20130706205352-ryppl1eto3illd79
Tags: 0.8.2-1
[ Jakub Wilk ]
* Use canonical URIs for Vcs-* fields.

[ Piotr Ożarowski ]
* New upstream release
* Upload to unstable
* Build depend on python3-all instead of -dev, extensions are not built for
  Python 3.X 

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/sqlalchemy/util/topological.py
1
1
# util/topological.py
2
 
# Copyright (C) 2005-2012 the SQLAlchemy authors and contributors <see AUTHORS file>
 
2
# Copyright (C) 2005-2013 the SQLAlchemy authors and contributors <see AUTHORS file>
3
3
#
4
4
# This module is part of SQLAlchemy and is released under
5
5
# the MIT License: http://www.opensource.org/licenses/mit-license.php
6
6
 
7
7
"""Topological sorting algorithms."""
8
8
 
9
 
from sqlalchemy.exc import CircularDependencyError
10
 
from sqlalchemy import util
11
 
 
 
9
from ..exc import CircularDependencyError
 
10
from .. import util
12
11
 
13
12
__all__ = ['sort', 'sort_as_subsets', 'find_cycles']
14
13
 
 
14
 
15
15
def sort_as_subsets(tuples, allitems):
16
16
 
17
17
    edges = util.defaultdict(set)
36
36
        todo.difference_update(output)
37
37
        yield output
38
38
 
 
39
 
39
40
def sort(tuples, allitems):
40
41
    """sort the given list of items by dependency.
41
42
 
46
47
        for s in set_:
47
48
            yield s
48
49
 
 
50
 
49
51
def find_cycles(tuples, allitems):
50
 
    # straight from gvr with some mods
 
52
    # adapted from:
 
53
    # http://neopythonic.blogspot.com/2009/01/detecting-cycles-in-directed-graph.html
51
54
 
52
55
    edges = util.defaultdict(set)
53
56
    for parent, child in tuples:
84
87
                node = stack.pop()
85
88
    return output
86
89
 
 
90
 
87
91
def _gen_edges(edges):
88
92
    return set([
89
93
                    (right, left)