# topological.py# Copyright (C) 2005, 2006, 2007, 2008 Michael Bayer mike_mp@zzzcomputing.com## This module is part of SQLAlchemy and is released under# the MIT License: http://www.opensource.org/licenses/mit-license.php"""Topological sorting algorithms.The topological sort is an algorithm that receives this list ofdependencies as a *partial ordering*, that is a list of pairs whichmight say, *X is dependent on Y*, *Q is dependent on Z*, but does notnecessarily tell you anything about Q being dependent on X. Therefore,its not a straight sort where every element can be compared toanother... only some of the elements have any sorting preference, andthen only towards just some of the other elements.  For a particularpartial ordering, there can be many possible sorts that satisfy theconditions."""from sqlalchemy import utilfrom sqlalchemy.exceptions import CircularDependencyError__all__ = ['sort', 'sort_with_cycles', 'sort_as_tree']def sort(tuples, allitems):    """sort the given list of items by dependency.        'tuples' is a list of tuples representing a partial ordering.    """        return [n.item for n in _sort(tuples, allitems, allow_cycles=False, ignore_self_cycles=True)]def sort_with_cycles(tuples, allitems):    """sort the given list of items by dependency, cutting out cycles.        returns results as an iterable of 2-tuples, containing the item,    and a list containing items involved in a cycle with this item, if any.        'tuples' is a list of tuples representing a partial ordering.    """        return [(n.item, [n.item for n in n.cycles or []]) for n in _sort(tuples, allitems, allow_cycles=True)]    def sort_as_tree(tuples, allitems, with_cycles=False):    """sort the given list of items by dependency, and return results    as a hierarchical tree structure.        returns results as an iterable of 3-tuples, containing the item,    and a list containing items involved in a cycle with this item, if any,    and a list of child tuples.          if with_cycles is False, the returned structure is of the same form    but the second element of each tuple, i.e. the 'cycles', is an empty list.        'tuples' is a list of tuples representing a partial ordering.    """    return _organize_as_tree(_sort(tuples, allitems, allow_cycles=with_cycles))class _Node(object):    """Represent each item in the sort."""    def __init__(self, item):        self.item = item        self.dependencies = util.Set()        self.children = []        self.cycles = None    def __str__(self):        return self.safestr()        def safestr(self, indent=0):        return (' ' * indent * 2) + \            str(self.item) + \            (self.cycles is not None and (" (cycles: " + repr([x for x in self.cycles]) + ")") or "") + \            "\n" + \            ''.join([str(n) for n in self.children])    def __repr__(self):        return "%s" % (str(self.item))    def all_deps(self):        """Return a set of dependencies for this node and all its cycles."""        deps = util.Set(self.dependencies)        if self.cycles is not None:            for c in self.cycles:                deps.update(c.dependencies)        return depsclass _EdgeCollection(object):    """A collection of directed edges."""    def __init__(self):        self.parent_to_children = {}        self.child_to_parents = {}    def add(self, edge):        """Add an edge to this collection."""        (parentnode, childnode) = edge        if parentnode not in self.parent_to_children:            self.parent_to_children[parentnode] = util.Set()        self.parent_to_children[parentnode].add(childnode)        if childnode not in self.child_to_parents:            self.child_to_parents[childnode] = util.Set()        self.child_to_parents[childnode].add(parentnode)        parentnode.dependencies.add(childnode)    def remove(self, edge):        """Remove an edge from this collection.        Return the childnode if it has no other parents.        """        (parentnode, childnode) = edge        self.parent_to_children[parentnode].remove(childnode)        self.child_to_parents[childnode].remove(parentnode)        if len(self.child_to_parents[childnode]) == 0:            return childnode        else:            return None    def has_parents(self, node):        return node in self.child_to_parents and len(self.child_to_parents[node]) > 0    def edges_by_parent(self, node):        if node in self.parent_to_children:            return [(node, child) for child in self.parent_to_children[node]]        else:            return []    def get_parents(self):        return self.parent_to_children.keys()    def pop_node(self, node):        """Remove all edges where the given node is a parent.        Return the collection of all nodes which were children of the        given node, and have no further parents.        """        children = self.parent_to_children.pop(node, None)        if children is not None:            for child in children:                self.child_to_parents[child].remove(node)                if not self.child_to_parents[child]:                    yield child    def __len__(self):        return sum([len(x) for x in self.parent_to_children.values()])    def __iter__(self):        for parent, children in self.parent_to_children.iteritems():            for child in children:                yield (parent, child)    def __str__(self):        return repr(list(self))    def __repr__(self):        return repr(list(self))def _sort(tuples, allitems, allow_cycles=False, ignore_self_cycles=False):    nodes = {}    edges = _EdgeCollection()    for item in list(allitems) + [t[0] for t in tuples] + [t[1] for t in tuples]:        if id(item) not in nodes:            node = _Node(item)            nodes[item] = node    for t in tuples:        if t[0] is t[1]:            if allow_cycles:                n = nodes[t[0]]                n.cycles = util.Set([n])            elif not ignore_self_cycles:                raise CircularDependencyError("Self-referential dependency detected " + repr(t))            continue        childnode = nodes[t[1]]        parentnode = nodes[t[0]]        edges.add((parentnode, childnode))    queue = []    for n in nodes.values():        if not edges.has_parents(n):            queue.append(n)    output = []    while nodes:        if not queue:            # edges remain but no edgeless nodes to remove; this indicates            # a cycle            if allow_cycles:                for cycle in _find_cycles(edges):                    lead = cycle[0][0]                    lead.cycles = util.Set()                    for edge in cycle:                        n = edges.remove(edge)                        lead.cycles.add(edge[0])                        lead.cycles.add(edge[1])                        if n is not None:                            queue.append(n)                    for n in lead.cycles:                        if n is not lead:                            n._cyclical = True                            for (n,k) in list(edges.edges_by_parent(n)):                                edges.add((lead, k))                                edges.remove((n,k))                continue            else:                # long cycles not allowed                raise CircularDependencyError("Circular dependency detected " + repr(edges) + repr(queue))        node = queue.pop()        if not hasattr(node, '_cyclical'):            output.append(node)        del nodes[node.item]        for childnode in edges.pop_node(node):            queue.append(childnode)    return outputdef _organize_as_tree(nodes):    """Given a list of nodes from a topological sort, organize the    nodes into a tree structure, with as many non-dependent nodes    set as siblings to each other as possible.        returns nodes as 3-tuples (item, cycles, children).    """    if not nodes:        return None    # a list of all currently independent subtrees as a tuple of    # (root_node, set_of_all_tree_nodes, set_of_all_cycle_nodes_in_tree)    # order of the list has no semantics for the algorithmic    independents = []    # in reverse topological order    for node in util.reversed(nodes):        # nodes subtree and cycles contain the node itself        subtree = util.Set([node])        if node.cycles is not None:            cycles = util.Set(node.cycles)        else:            cycles = util.Set()        # get a set of dependent nodes of node and its cycles        nodealldeps = node.all_deps()        if nodealldeps:            # iterate over independent node indexes in reverse order so we can efficiently remove them            for index in xrange(len(independents)-1,-1,-1):                child, childsubtree, childcycles = independents[index]                # if there is a dependency between this node and an independent node                if (childsubtree.intersection(nodealldeps) or childcycles.intersection(node.dependencies)):                    # prepend child to nodes children                    # (append should be fine, but previous implemetation used prepend)                    node.children[0:0] = [(child.item, [n.item for n in child.cycles or []], child.children)]                    # merge childs subtree and cycles                    subtree.update(childsubtree)                    cycles.update(childcycles)                    # remove the child from list of independent subtrees                    independents[index:index+1] = []        # add node as a new independent subtree        independents.append((node,subtree,cycles))    # choose an arbitrary node from list of all independent subtrees    head = independents.pop()[0]    # add all other independent subtrees as a child of the chosen root    # used prepend [0:0] instead of extend to maintain exact behaviour of previous implementation    head.children[0:0] = [(i[0].item, [n.item for n in i[0].cycles or []], i[0].children) for i in independents]    return (head.item, [n.item for n in head.cycles or []], head.children)def _find_cycles(edges):    involved_in_cycles = util.Set()    cycles = {}    def traverse(node, goal=None, cycle=None):        if goal is None:            goal = node            cycle = []        elif node is goal:            return True        for (n, key) in edges.edges_by_parent(node):            if key in cycle:                continue            cycle.append(key)            if traverse(key, goal, cycle):                cycset = util.Set(cycle)                for x in cycle:                    involved_in_cycles.add(x)                    if x in cycles:                        existing_set = cycles[x]                        [existing_set.add(y) for y in cycset]                        for y in existing_set:                            cycles[y] = existing_set                        cycset = existing_set                    else:                        cycles[x] = cycset            cycle.pop()    for parent in edges.get_parents():        traverse(parent)    # sets are not hashable, so uniquify with id    unique_cycles = dict([(id(s), s) for s in cycles.values()]).values()    for cycle in unique_cycles:        edgecollection = [edge for edge in edges                          if edge[0] in cycle and edge[1] in cycle]        yield edgecollection