Source code for nxpy.core.sort

# nxpy.core package ----------------------------------------------------------

# Copyright Nicola Musatti 2010 - 2012
# Use, modification, and distribution are subject to the Boost Software
# License, Version 1.0. (See accompanying file LICENSE.txt or copy at
# http://www.boost.org/LICENSE_1_0.txt)

# See http://sourceforge.net/nxpy for library home page. ---------------------

r"""
Sort functions.

"""

def topological_sort(pairs):
    r"""
    Provide a topological ordering of the supplied pair elements.
    
    'pairs' is a sequence of two element sequences, in which the first element comes before
    the second according to the desired ordering criterium.
    
    """
    res = []
    top = set()
    nodes = {}
    for end, start in pairs:
        if not nodes.has_key(end):
            nodes[end] = []
        nodes[end].append(start)
    for end, start in pairs:
        if not nodes.has_key(start):
            top.add(start)
    while len(top) > 0:
        s = top.pop()
        res.append(s)
        for e in nodes:
            try:
                nodes[e].remove(s)
                if len(nodes[e]) == 0:
                    top.add(e)
            except ValueError:
                pass
        for e in top:
            try:
                del nodes[e]
            except:
                pass
    if len(nodes) > 0:
        return None
    else:
        return res


if __name__ == "__main__":
    print topological_sort(( ("w", "s"), ("w", "f"), ("s", "f"), ("w", "d"), ("s", "d"), 
                             ("f", "d") ))