LSD.dag_creation

The package that constructs the dags out of the subgraphs. This could be a sung graph or a simple DAG

LSD.dag_creation.BLACK = 2

COLOR Definition

LSD.dag_creation.GREY = 1

COLOR Definition

LSD.dag_creation.WHITE = 0

COLOR Definition

LSD.dag_creation.choose_random_root(c)

Choose a arbitrary root. To be deterministic the minimum vertex identifier is used

LSD.dag_creation.choose_root(c)

Choose a or a b’’ as root. The root is connected with a

LSD.dag_creation.construct_dag(c)

Construct the DAG that contain the same week superbubbles as G. In this procedure the DFS tree is constructed indirectly. It does a lineare version of a deep first search. The recusive version of the same algorithm would look like this:

def construct_dag(c):
    recursive_dag(c, g.a)
    

def recursive_dag(c, v):
    c.set_color(v, GREY)
    for child in c.successors(v):
        if c.has_no_color(child):
            recursive_dag(g, child)
        elif c.get_color(child) == GREY:
            c.remove_edge(v, child)
            c.connect2sink(v)
            c.connect2source(child)
    c.set_color(v, BLACK)

LSD.dag_creation.construct_sung_graph(c)

Construct the sung graph. That is also a DAG. In this procedure the DFS tree is constructed indirectly.