#NEWLINE# def posort( l , * cmps ) : #NEWLINE# #INDENT# '\n    Partially ordered sort with multiple comparators.\n\n    Given a list of comparators, orders the elements in l so that the\n    comparators are satisfied as much as possible giving precedence to\n    earlier comparators.\n\n    Parameters\n    ----------\n    l\n        An iterable of nodes in a graph.\n    cmps\n        A sequence of comparator functions that describe which nodes should\n        come before which others.\n\n    Returns\n    -------\n    list\n        A list of nodes which satisfy the comparators as much as possible.\n\n    Notes\n    -----\n    Implemented with _toposort.\n\n    Examples\n    --------\n    >>> lower_tens = lambda a, b: a/10 - b/10 # prefer lower numbers div 10\n    >>> prefer evens = lambda a, b: a%2 - b%2 # prefer even numbers\n    >>> posort(list(range(20)), lower_tens, prefer_evens)\n    [0, 8, 2, 4, 6, 1, 3, 5, 7, 9, 16, 18, 10, 12, 14, 17, 19, 11, 13, 15]\n\n    ' #NEWLINE# comes_before = dict ( ( ( a , set ( ) ) for a in l ) ) #NEWLINE# comes_after = dict ( ( ( a , set ( ) ) for a in l ) ) #NEWLINE# def add_links( a , b ) : #NEWLINE# #INDENT# comes_after [ a ] . add ( b ) #NEWLINE# comes_after [ a ] . update ( comes_after [ b ] ) #NEWLINE# for c in comes_before [ a ] : #NEWLINE# #INDENT# comes_after [ c ] . update ( comes_after [ a ] ) #NEWLINE# #UNINDENT# comes_before [ b ] . add ( a ) #NEWLINE# comes_before [ b ] . update ( comes_before [ a ] ) #NEWLINE# for c in comes_after [ b ] : #NEWLINE# #INDENT# comes_before [ c ] . update ( comes_before [ b ] ) #NEWLINE# #UNINDENT# #UNINDENT# def check( ) : #NEWLINE# #INDENT# '\n        Tests for cycles in manufactured edges.\n\n        ' #NEWLINE# for a in l : #NEWLINE# #INDENT# for b in l : #NEWLINE# #INDENT# assert ( not ( ( b in comes_after [ a ] ) and ( a in comes_after [ b ] ) ) ) #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# for cmp_fn in cmps : #NEWLINE# #INDENT# for a in l : #NEWLINE# #INDENT# for b in l : #NEWLINE# #INDENT# if ( cmp_fn ( a , b ) < 0 ) : #NEWLINE# #INDENT# if ( ( b not in comes_before [ a ] ) and ( b not in comes_after [ a ] ) ) : #NEWLINE# #INDENT# add_links ( a , b ) #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# #UNINDENT# #UNINDENT# return _toposort ( comes_after )