bindings/python/topsort.py
author Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
Sun, 12 Oct 2008 18:04:10 +0100
changeset 3743 d0cf214d050c
parent 3408 2cc40b3e4fa5
permissions -rw-r--r--
Rescan API for Python.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
3408
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
     1
# topsort - dependency (topological) sorting and cycle finding functions
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
     2
# Copyright (C) 2007 RADLogic
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
     3
# 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
     4
# This library is free software; you can redistribute it and/or
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
     5
# modify it under the terms of the GNU Lesser General Public
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
     6
# License as published by the Free Software Foundation; 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
     7
# version 2.1 of the License.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
     8
# 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
     9
# This library is distributed in the hope that it will be useful,
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    10
# but WITHOUT ANY WARRANTY; without even the implied warranty of
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    11
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    12
# Lesser General Public License for more details.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    13
#
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    14
# See http://www.fsf.org/licensing/licenses/lgpl.txt for full license text.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    15
"""Provide toplogical sorting (i.e. dependency sorting) functions.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    16
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    17
The topsort function is based on code posted on Usenet by Tim Peters.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    18
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    19
Modifications:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    20
- added doctests
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    21
- changed some bits to use current Python idioms
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    22
  (listcomp instead of filter, +=/-=, inherit from Exception)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    23
- added a topsort_levels version that ports items in each dependency level
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    24
  into a sub-list
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    25
- added find_cycles to aid in cycle debugging
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    26
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    27
Run this module directly to run the doctests (unittests).
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    28
Make sure they all pass before checking in any modifications.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    29
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    30
Requires Python >= 2.2
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    31
(For Python 2.2 also requires separate sets.py module)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    32
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    33
This requires the rad_util.py module.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    34
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    35
"""
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    36
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    37
# Provide support for Python 2.2*
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    38
from __future__ import generators
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    39
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    40
__version__ = '$Revision: 0.9 $'
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    41
__date__ = '$Date: 2007/03/27 04:15:26 $'
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    42
__credits__ = '''Tim Peters -- original topsort code
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    43
Tim Wegener -- doctesting, updating to current idioms, topsort_levels,
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    44
               find_cycles
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    45
'''
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    46
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    47
# Make Python 2.3 sets look like Python 2.4 sets.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    48
try:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    49
    set
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    50
except NameError:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    51
    from sets import Set as set
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    52
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    53
from rad_util import is_rotated
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    54
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    55
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    56
class CycleError(Exception):
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    57
    """Cycle Error"""
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    58
    pass
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    59
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    60
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    61
def topsort(pairlist):
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    62
    """Topologically sort a list of (parent, child) pairs.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    63
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    64
    Return a list of the elements in dependency order (parent to child order).
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    65
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    66
    >>> print topsort( [(1,2), (3,4), (5,6), (1,3), (1,5), (1,6), (2,5)] ) 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    67
    [1, 2, 3, 5, 4, 6]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    68
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    69
    >>> print topsort( [(1,2), (1,3), (2,4), (3,4), (5,6), (4,5)] )
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    70
    [1, 2, 3, 4, 5, 6]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    71
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    72
    >>> print topsort( [(1,2), (2,3), (3,2)] )
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    73
    Traceback (most recent call last):
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    74
    CycleError: ([1], {2: 1, 3: 1}, {2: [3], 3: [2]})
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    75
    
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    76
    """
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    77
    num_parents = {}  # element -> # of predecessors 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    78
    children = {}  # element -> list of successors 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    79
    for parent, child in pairlist: 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    80
        # Make sure every element is a key in num_parents.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    81
        if not num_parents.has_key( parent ): 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    82
            num_parents[parent] = 0 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    83
        if not num_parents.has_key( child ): 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    84
            num_parents[child] = 0 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    85
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    86
        # Since child has a parent, increment child's num_parents count.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    87
        num_parents[child] += 1
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    88
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    89
        # ... and parent gains a child.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    90
        children.setdefault(parent, []).append(child)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    91
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    92
    # Suck up everything without a parent.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    93
    answer = [x for x in num_parents.keys() if num_parents[x] == 0]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    94
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    95
    # For everything in answer, knock down the parent count on its children.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    96
    # Note that answer grows *in* the loop.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    97
    for parent in answer: 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    98
        del num_parents[parent]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
    99
        if children.has_key( parent ): 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   100
            for child in children[parent]: 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   101
                num_parents[child] -= 1
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   102
                if num_parents[child] == 0: 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   103
                    answer.append( child ) 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   104
            # Following "del" isn't needed; just makes 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   105
            # CycleError details easier to grasp.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   106
            del children[parent]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   107
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   108
    if num_parents: 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   109
        # Everything in num_parents has at least one child -> 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   110
        # there's a cycle.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   111
        raise CycleError(answer, num_parents, children)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   112
    return answer 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   113
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   114
def topsort_levels(pairlist):
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   115
    """Topologically sort a list of (parent, child) pairs into depth levels.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   116
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   117
    This returns a generator. 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   118
    Turn this into a an iterator using the iter built-in function.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   119
    (if you iterate over the iterator, each element gets generated when
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   120
    it is asked for, rather than generating the whole list up-front.)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   121
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   122
    Each generated element is a list of items at that dependency level.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   123
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   124
    >>> dependency_pairs = [(1,2), (3,4), (5,6), (1,3), (1,5), (1,6), (2,5)]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   125
    >>> for level in iter(topsort_levels( dependency_pairs )):
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   126
    ...    print level
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   127
    [1]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   128
    [2, 3]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   129
    [4, 5]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   130
    [6]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   131
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   132
    >>> dependency_pairs = [(1,2), (1,3), (2,4), (3,4), (5,6), (4,5)]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   133
    >>> for level in iter(topsort_levels( dependency_pairs )):
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   134
    ...    print level
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   135
    [1]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   136
    [2, 3]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   137
    [4]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   138
    [5]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   139
    [6]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   140
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   141
    >>> dependency_pairs = [(1,2), (2,3), (3,4), (4, 3)]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   142
    >>> try:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   143
    ...     for level in iter(topsort_levels( dependency_pairs )):
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   144
    ...         print level
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   145
    ... except CycleError, exc:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   146
    ...     print 'CycleError:', exc
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   147
    [1]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   148
    [2]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   149
    CycleError: ({3: 1, 4: 1}, {3: [4], 4: [3]})
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   150
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   151
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   152
    The cycle error should look like.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   153
    CycleError: ({3: 1, 4: 1}, {3: [4], 4: [3]})
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   154
    # todo: Make the doctest more robust (i.e. handle arbitrary dict order).
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   155
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   156
    """
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   157
    num_parents = {}  # element -> # of predecessors 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   158
    children = {}  # element -> list of successors 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   159
    for parent, child in pairlist: 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   160
        # Make sure every element is a key in num_parents.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   161
        if not num_parents.has_key( parent ): 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   162
            num_parents[parent] = 0 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   163
        if not num_parents.has_key( child ): 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   164
            num_parents[child] = 0 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   165
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   166
        # Since child has a parent, increment child's num_parents count.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   167
        num_parents[child] += 1
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   168
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   169
        # ... and parent gains a child.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   170
        children.setdefault(parent, []).append(child)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   171
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   172
    return topsort_levels_core(num_parents, children)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   173
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   174
def topsort_levels_core(num_parents, children):
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   175
    """Topologically sort a bunch of interdependent items based on dependency.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   176
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   177
    This returns a generator.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   178
    Turn this into a an iterator using the iter built-in function.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   179
    (if you iterate over the iterator, each element gets generated when
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   180
    it is asked for, rather than generating the whole list up-front.)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   181
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   182
    Each generated element is a list of items at that dependency level.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   183
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   184
    >>> list(topsort_levels_core(
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   185
    ...          {1: 0, 2: 1, 3: 1, 4: 1, 5: 2, 6: 2},
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   186
    ...          {1: [2, 3, 5, 6], 2: [5], 3: [4], 4: [], 5: [6]}))
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   187
    [[1], [2, 3], [4, 5], [6]]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   188
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   189
    >>> list(topsort_levels_core(
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   190
    ...          {1: 0, 2: 2, 3: 1},
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   191
    ...          {1: [2], 2: [3], 3: [2]}))
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   192
    Traceback (most recent call last):
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   193
    CycleError: ({2: 1, 3: 1}, {2: [3], 3: [2]})
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   194
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   195
    This function has a more complicated interface than topsort_levels,
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   196
    but is useful if the data is easier to generate in this form.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   197
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   198
    Arguments:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   199
    num_parents -- key: item, value: number of parents (predecessors)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   200
    children -- key: item, value: list of children (successors)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   201
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   202
    """
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   203
    while 1:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   204
        # Suck up everything without a predecessor.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   205
        level_parents = [x for x in num_parents.keys() if num_parents[x] == 0]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   206
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   207
        if not level_parents:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   208
            break
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   209
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   210
        # Offer the next generated item,
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   211
        # which is a list of the items at this dependency level.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   212
        yield level_parents
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   213
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   214
        # For everything item in this level,
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   215
        # decrement the parent count,
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   216
        # since we have accounted for its parent.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   217
        for level_parent in level_parents:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   218
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   219
            del num_parents[level_parent]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   220
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   221
            if children.has_key(level_parent):
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   222
                for level_parent_child in children[level_parent]:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   223
                    num_parents[level_parent_child] -= 1
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   224
                del children[level_parent]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   225
        
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   226
    if num_parents: 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   227
        # Everything in num_parents has at least one child -> 
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   228
        # there's a cycle.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   229
        raise CycleError(num_parents, children)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   230
    else:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   231
        # This is the end of the generator.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   232
        raise StopIteration
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   233
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   234
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   235
def find_cycles(parent_children):
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   236
    """Yield cycles. Each result is a list of items comprising a cycle.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   237
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   238
    Use a 'stack' based approach to find all the cycles.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   239
    This is a generator, so yields each cycle as it finds it.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   240
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   241
    It is implicit that the last item in each cycle list is a parent of the
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   242
    first item (thereby forming a cycle).
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   243
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   244
    Arguments:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   245
    parent_children -- parent -> collection of children
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   246
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   247
    Simplest cycle:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   248
    >>> cycles = list(find_cycles({'A': ['B'], 'B': ['A']}))
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   249
    >>> len(cycles)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   250
    1
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   251
    >>> cycle = cycles[0]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   252
    >>> cycle.sort()
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   253
    >>> print cycle
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   254
    ['A', 'B']
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   255
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   256
    Simplest cycle with extra baggage at the start and the end:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   257
    >>> cycles = list(find_cycles(parent_children={'A': ['B'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   258
    ...                                            'B': ['C'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   259
    ...                                            'C': ['B', 'D'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   260
    ...                                            'D': [],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   261
    ...                                            }))
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   262
    >>> len(cycles)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   263
    1
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   264
    >>> cycle = cycles[0]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   265
    >>> cycle.sort()
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   266
    >>> print cycle
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   267
    ['B', 'C']
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   268
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   269
    Double cycle:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   270
    >>> cycles = list(find_cycles(parent_children={'A': ['B'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   271
    ...                                            'B': ['C1', 'C2'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   272
    ...                                            'C1': ['D1'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   273
    ...                                            'D1': ['E1'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   274
    ...                                            'E1': ['D1'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   275
    ...                                            'C2': ['D2'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   276
    ...                                            'D2': ['E2'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   277
    ...                                            'E2': ['D2'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   278
    ...                                            }))
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   279
    >>> len(cycles)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   280
    2
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   281
    >>> for cycle in cycles:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   282
    ...     cycle.sort()
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   283
    >>> cycles.sort()
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   284
    >>> cycle1 = cycles[0]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   285
    >>> cycle1.sort()
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   286
    >>> print cycle1
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   287
    ['D1', 'E1']
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   288
    >>> cycle2 = cycles[1]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   289
    >>> cycle2.sort()
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   290
    >>> print cycle2
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   291
    ['D2', 'E2']
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   292
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   293
    Simple cycle with children not specified for one item:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   294
    # todo: Should this barf instead?
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   295
    >>> cycles = list(find_cycles(parent_children={'A': ['B'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   296
    ...                                            'B': ['A'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   297
    ...                                            'C': ['D']}))
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   298
    >>> len(cycles)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   299
    1
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   300
    >>> cycle = cycles[0]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   301
    >>> cycle.sort()
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   302
    >>> print cycle
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   303
    ['A', 'B']
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   304
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   305
    Diamond cycle
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   306
    >>> cycles = list(find_cycles(parent_children={'A': ['B1', 'B2'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   307
    ...                                            'B1': ['C'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   308
    ...                                            'B2': ['C'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   309
    ...                                            'C': ['A', 'B1']}))
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   310
    >>> len(cycles)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   311
    3
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   312
    >>> sorted_cycles = []
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   313
    >>> for cycle in cycles:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   314
    ...     cycle = list(cycle)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   315
    ...     cycle.sort()
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   316
    ...     sorted_cycles.append(cycle)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   317
    >>> sorted_cycles.sort()
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   318
    >>> for cycle in sorted_cycles:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   319
    ...     print cycle
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   320
    ['A', 'B1', 'C']
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   321
    ['A', 'B2', 'C']
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   322
    ['B1', 'C']
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   323
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   324
    Hairy case (order can matter if something is wrong):
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   325
    (Note order of B and C in the list.)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   326
    >>> cycles = list(find_cycles(parent_children={
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   327
    ...                                           'TD': ['DD'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   328
    ...                                           'TC': ['DC'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   329
    ...                                           'DC': ['DQ'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   330
    ...                                           'C': ['DQ'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   331
    ...                                           'DQ': ['IA', 'TO'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   332
    ...                                           'IA': ['A'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   333
    ...                                           'A': ['B', 'C'],
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   334
    ...                                           }))
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   335
    >>> len(cycles)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   336
    1
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   337
    >>> cycle = cycles[0]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   338
    >>> cycle.sort()
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   339
    >>> print cycle
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   340
    ['A', 'C', 'DQ', 'IA']
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   341
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   342
    """
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   343
    cycles = []
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   344
    visited_nodes = set()
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   345
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   346
    for parent in parent_children:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   347
        if parent in visited_nodes:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   348
            # This node is part of a path that has already been traversed.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   349
            continue
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   350
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   351
        paths = [[parent]]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   352
        while paths:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   353
            path = paths.pop()
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   354
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   355
            parent = path[-1]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   356
            
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   357
            try:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   358
                children = parent_children[parent]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   359
            except KeyError:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   360
                continue
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   361
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   362
            for child in children:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   363
                # Keeping a set of the path nodes, for O(1) lookups at the
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   364
                # expense of more memory and complexity, actually makes speed
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   365
                # worse. (Due to construction of sets.)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   366
                # This is O(N).
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   367
                if child in path:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   368
                    # This is a cycle.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   369
                    cycle = path[path.index(child):]
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   370
                    # Check that this is not a dup cycle.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   371
                    is_dup = False
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   372
                    for other_cycle in cycles:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   373
                        if is_rotated(other_cycle, cycle):
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   374
                            is_dup = True
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   375
                            break
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   376
                    if not is_dup:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   377
                        cycles.append(cycle)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   378
                        yield cycle
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   379
                else:
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   380
                    # Push this new path onto the 'stack'.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   381
                    # This is probably the most expensive part of the algorithm
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   382
                    # (a list copy).
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   383
                    paths.append(path + [child])
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   384
                    # Mark the node as visited.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   385
                    visited_nodes.add(child)
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   386
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   387
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   388
if __name__ == '__main__':
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   389
    # Run the doctest tests.
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   390
    import sys
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   391
    import doctest
2cc40b3e4fa5 python bindings
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff changeset
   392
    doctest.testmod(sys.modules['__main__'])