LSD.topological_sorting

class LSD.topological_sorting.Order(source, sink)

A order representation. Get a vertex on an arbitrary position in O(1). Get the position of an arbitrary vertex in O(1).

__getitem__(item)

Get element at position item

__init__(source, sink)

Init the order set source position -1 and sink and None position to infinity

add(v)

Add an element to the end of the order

get_position(v)

Get position of element v. If v not contained return -2

n

Get the length of the order.

LSD.topological_sorting.check_pre(v, g, order)

Check if all predecessors have already been placed.

LSD.topological_sorting.toposort(g)

Do a topological ordering of the graph. It does a lineare version of a deep first search. The recusive version of the same algorithm would look like this:

def toposort(g):
    order = Order(g.a, g.b)
    rec_call(g.a, order, g, lambda v: check_pre(v, g, order))
    return order

    
def rec_call(v, order, g, check_predecessor):
    for child in g.successors(v):
        if check_predecessor(child):
            order.add(child)
            rec_call(child, order, g, check_predecessor)