'''DFS generating a topological or reverse topological order from the ending
times of visits of a DAG - no test for cycles.  Bogus answer with a cycle.
'''
from DFS import driver, vertexStr, fromStr

def DAGTopoOrder(g, reverse=True, verbose=True):
    '''g is a list containing lists of adjacent nodes,
    indicating the direction for each edge.
    return a topological order of vertex indices if reverse is False
    or a reverse topological order if reverse is True (default).
    A bogus answer is returned if there is a cycle.
    '''
    if g[0][0] == ':':
        print('This algorithm is only for a DAGs.')
        return
    endings = [] 
    lim = len(g)
    visited = [False]*lim
    for i in range(1, lim):
        if not visited[i]:
            dfs(g, visited, i, endings)
    if not reverse: # endings give reverse topological order
        endings.reverse()
    if verbose:
        if reverse:
            direction = 'reversed '
        else:
            direction = ''
        print(direction + 'topological order:', vertexStr(endings, g))
    return endings

def dfs(g, visited, v, endings):
    '''g is a list of lists of adjacent nodes.
    visited is a list showing which nodes are visited so far,
    v is the starting vertex index >= 1, for the search
    endings is a list of the vertices finished so far.
    '''
    visited[v] = True
    for w in g[v]:
        if not visited[w]:
            dfs(g, visited, w, endings)
    endings.append(v)

if __name__ == '__main__':
    driver(DAGTopoOrder, 'A>BCD B>CD C> D>C E>CG F>E G>')
    DAGTopoOrder(fromStr(''), False) # get last list reversed