# topsort - dependency (topological) sorting and cycle finding functions

# Copyright (C) 2007 RADLogic

# 

# This library is free software; you can redistribute it and/or

# modify it under the terms of the GNU Lesser General Public

# License as published by the Free Software Foundation; 

# version 2.1 of the License.

# 

# This library is distributed in the hope that it will be useful,

# but WITHOUT ANY WARRANTY; without even the implied warranty of

# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU

# Lesser General Public License for more details.

#

# See http://www.fsf.org/licensing/licenses/lgpl.txt for full license text.

"""Provide toplogical sorting (i.e. dependency sorting) functions.

The topsort function is based on code posted on Usenet by Tim Peters.

Modifications:

- added doctests

- changed some bits to use current Python idioms

  (listcomp instead of filter, +=/-=, inherit from Exception)

- added a topsort_levels version that ports items in each dependency level

  into a sub-list

- added find_cycles to aid in cycle debugging

Run this module directly to run the doctests (unittests).

Make sure they all pass before checking in any modifications.

Requires Python >= 2.2

(For Python 2.2 also requires separate sets.py module)

This requires the rad_util.py module.

"""

# Provide support for Python 2.2*

from __future__ import generators

__version__ = '$Revision: 0.9 $'

__date__ = '$Date: 2007/03/27 04:15:26 $'

__credits__ = '''Tim Peters -- original topsort code

Tim Wegener -- doctesting, updating to current idioms, topsort_levels,

               find_cycles

'''

# Make Python 2.3 sets look like Python 2.4 sets.

try:

    set

except NameError:

    from sets import Set as set

from rad_util import is_rotated

class CycleError(Exception):

    """Cycle Error"""

    pass

def topsort(pairlist):

    """Topologically sort a list of (parent, child) pairs.

    Return a list of the elements in dependency order (parent to child order).

    >>> print topsort( [(1,2), (3,4), (5,6), (1,3), (1,5), (1,6), (2,5)] ) 

    [1, 2, 3, 5, 4, 6]

    >>> print topsort( [(1,2), (1,3), (2,4), (3,4), (5,6), (4,5)] )

    [1, 2, 3, 4, 5, 6]

    >>> print topsort( [(1,2), (2,3), (3,2)] )

    Traceback (most recent call last):

    CycleError: ([1], {2: 1, 3: 1}, {2: [3], 3: [2]})

    """

    num_parents = {}  # element -> # of predecessors 

    children = {}  # element -> list of successors 

    for parent, child in pairlist: 

        # Make sure every element is a key in num_parents.

        if not num_parents.has_key( parent ): 

            num_parents[parent] = 0 

        if not num_parents.has_key( child ): 

            num_parents[child] = 0 

        # Since child has a parent, increment child's num_parents count.

        num_parents[child] += 1

        # ... and parent gains a child.

        children.setdefault(parent, []).append(child)

    # Suck up everything without a parent.

    answer = [x for x in num_parents.keys() if num_parents[x] == 0]

    # For everything in answer, knock down the parent count on its children.

    # Note that answer grows *in* the loop.

    for parent in answer: 

        del num_parents[parent]

        if children.has_key( parent ): 

            for child in children[parent]: 

                num_parents[child] -= 1

                if num_parents[child] == 0: 

                    answer.append( child ) 

            # Following "del" isn't needed; just makes 

            # CycleError details easier to grasp.

            del children[parent]

    if num_parents: 

        # Everything in num_parents has at least one child -> 

        # there's a cycle.

        raise CycleError(answer, num_parents, children)

    return answer 

def topsort_levels(pairlist):

    """Topologically sort a list of (parent, child) pairs into depth levels.

    This returns a generator. 

    Turn this into a an iterator using the iter built-in function.

    (if you iterate over the iterator, each element gets generated when

    it is asked for, rather than generating the whole list up-front.)

    Each generated element is a list of items at that dependency level.

    >>> dependency_pairs = [(1,2), (3,4), (5,6), (1,3), (1,5), (1,6), (2,5)]

    >>> for level in iter(topsort_levels( dependency_pairs )):

    ...    print level

    [1]

    [2, 3]

    [4, 5]

    [6]

    >>> dependency_pairs = [(1,2), (1,3), (2,4), (3,4), (5,6), (4,5)]

    >>> for level in iter(topsort_levels( dependency_pairs )):

    ...    print level

    [1]

    [2, 3]

    [4]

    [5]

    [6]

    >>> dependency_pairs = [(1,2), (2,3), (3,4), (4, 3)]

    >>> try:

    ...     for level in iter(topsort_levels( dependency_pairs )):

    ...         print level

    ... except CycleError, exc:

    ...     print 'CycleError:', exc

    [1]

    [2]

    CycleError: ({3: 1, 4: 1}, {3: [4], 4: [3]})

    The cycle error should look like.

    CycleError: ({3: 1, 4: 1}, {3: [4], 4: [3]})

    # todo: Make the doctest more robust (i.e. handle arbitrary dict order).

    """

    num_parents = {}  # element -> # of predecessors 

    children = {}  # element -> list of successors 

    for parent, child in pairlist: 

        # Make sure every element is a key in num_parents.

        if not num_parents.has_key( parent ): 

            num_parents[parent] = 0 

        if not num_parents.has_key( child ): 

            num_parents[child] = 0 

        # Since child has a parent, increment child's num_parents count.

        num_parents[child] += 1

        # ... and parent gains a child.

        children.setdefault(parent, []).append(child)

    return topsort_levels_core(num_parents, children)

def topsort_levels_core(num_parents, children):

    """Topologically sort a bunch of interdependent items based on dependency.

    This returns a generator.

    Turn this into a an iterator using the iter built-in function.

    (if you iterate over the iterator, each element gets generated when

    it is asked for, rather than generating the whole list up-front.)

    Each generated element is a list of items at that dependency level.

    >>> list(topsort_levels_core(

    ...          {1: 0, 2: 1, 3: 1, 4: 1, 5: 2, 6: 2},

    ...          {1: [2, 3, 5, 6], 2: [5], 3: [4], 4: [], 5: [6]}))

    [[1], [2, 3], [4, 5], [6]]

    >>> list(topsort_levels_core(

    ...          {1: 0, 2: 2, 3: 1},

    ...          {1: [2], 2: [3], 3: [2]}))

    Traceback (most recent call last):

    CycleError: ({2: 1, 3: 1}, {2: [3], 3: [2]})

    This function has a more complicated interface than topsort_levels,

    but is useful if the data is easier to generate in this form.

    Arguments:

    num_parents -- key: item, value: number of parents (predecessors)

    children -- key: item, value: list of children (successors)

    """

    while 1:

        # Suck up everything without a predecessor.

        level_parents = [x for x in num_parents.keys() if num_parents[x] == 0]

        if not level_parents:

            break

        # Offer the next generated item,

        # which is a list of the items at this dependency level.

        yield level_parents

        # For everything item in this level,

        # decrement the parent count,

        # since we have accounted for its parent.

        for level_parent in level_parents:

            del num_parents[level_parent]

            if children.has_key(level_parent):

                for level_parent_child in children[level_parent]:

                    num_parents[level_parent_child] -= 1

                del children[level_parent]

    if num_parents: 

        # Everything in num_parents has at least one child -> 

        # there's a cycle.

        raise CycleError(num_parents, children)

    else:

        # This is the end of the generator.

        raise StopIteration

def find_cycles(parent_children):

    """Yield cycles. Each result is a list of items comprising a cycle.

    Use a 'stack' based approach to find all the cycles.

    This is a generator, so yields each cycle as it finds it.

    It is implicit that the last item in each cycle list is a parent of the

    first item (thereby forming a cycle).

    Arguments:

    parent_children -- parent -> collection of children

    Simplest cycle:

    >>> cycles = list(find_cycles({'A': ['B'], 'B': ['A']}))

    >>> len(cycles)

    1

    >>> cycle = cycles[0]

    >>> cycle.sort()

    >>> print cycle

    ['A', 'B']

    Simplest cycle with extra baggage at the start and the end:

    >>> cycles = list(find_cycles(parent_children={'A': ['B'],

    ...                                            'B': ['C'],

    ...                                            'C': ['B', 'D'],

    ...                                            'D': [],

    ...                                            }))

    >>> len(cycles)

    1

    >>> cycle = cycles[0]

    >>> cycle.sort()

    >>> print cycle

    ['B', 'C']

    Double cycle:

    >>> cycles = list(find_cycles(parent_children={'A': ['B'],

    ...                                            'B': ['C1', 'C2'],

    ...                                            'C1': ['D1'],

    ...                                            'D1': ['E1'],

    ...                                            'E1': ['D1'],

    ...                                            'C2': ['D2'],

    ...                                            'D2': ['E2'],

    ...                                            'E2': ['D2'],

    ...                                            }))

    >>> len(cycles)

    2

    >>> for cycle in cycles:

    ...     cycle.sort()

    >>> cycles.sort()

    >>> cycle1 = cycles[0]

    >>> cycle1.sort()

    >>> print cycle1

    ['D1', 'E1']

    >>> cycle2 = cycles[1]

    >>> cycle2.sort()

    >>> print cycle2

    ['D2', 'E2']

    Simple cycle with children not specified for one item:

    # todo: Should this barf instead?

    >>> cycles = list(find_cycles(parent_children={'A': ['B'],

    ...                                            'B': ['A'],

    ...                                            'C': ['D']}))

    >>> len(cycles)

    1

    >>> cycle = cycles[0]

    >>> cycle.sort()

    >>> print cycle

    ['A', 'B']

    Diamond cycle

    >>> cycles = list(find_cycles(parent_children={'A': ['B1', 'B2'],

    ...                                            'B1': ['C'],

    ...                                            'B2': ['C'],

    ...                                            'C': ['A', 'B1']}))

    >>> len(cycles)

    3

    >>> sorted_cycles = []

    >>> for cycle in cycles:

    ...     cycle = list(cycle)

    ...     cycle.sort()

    ...     sorted_cycles.append(cycle)

    >>> sorted_cycles.sort()

    >>> for cycle in sorted_cycles:

    ...     print cycle

    ['A', 'B1', 'C']

    ['A', 'B2', 'C']

    ['B1', 'C']

    Hairy case (order can matter if something is wrong):

    (Note order of B and C in the list.)

    >>> cycles = list(find_cycles(parent_children={

    ...                                           'TD': ['DD'],

    ...                                           'TC': ['DC'],

    ...                                           'DC': ['DQ'],

    ...                                           'C': ['DQ'],

    ...                                           'DQ': ['IA', 'TO'],

    ...                                           'IA': ['A'],

    ...                                           'A': ['B', 'C'],

    ...                                           }))

    >>> len(cycles)

    1

    >>> cycle = cycles[0]

    >>> cycle.sort()

    >>> print cycle

    ['A', 'C', 'DQ', 'IA']

    """

    cycles = []

    visited_nodes = set()

    for parent in parent_children:

        if parent in visited_nodes:

            # This node is part of a path that has already been traversed.

            continue

        paths = [[parent]]

        while paths:

            path = paths.pop()

            parent = path[-1]

            try:

                children = parent_children[parent]

            except KeyError:

                continue

            for child in children:

                # Keeping a set of the path nodes, for O(1) lookups at the

                # expense of more memory and complexity, actually makes speed

                # worse. (Due to construction of sets.)

                # This is O(N).

                if child in path:

                    # This is a cycle.

                    cycle = path[path.index(child):]

                    # Check that this is not a dup cycle.

                    is_dup = False

                    for other_cycle in cycles:

                        if is_rotated(other_cycle, cycle):

                            is_dup = True

                            break

                    if not is_dup:

                        cycles.append(cycle)

                        yield cycle

                else:

                    # Push this new path onto the 'stack'.

                    # This is probably the most expensive part of the algorithm

                    # (a list copy).

                    paths.append(path + [child])

                    # Mark the node as visited.

                    visited_nodes.add(child)

if __name__ == '__main__':

    # Run the doctest tests.

    import sys

    import doctest

    doctest.testmod(sys.modules['__main__'])