'''DFS generating a topological or reverse topological order from the ending
times of visits.  Also tests for error due to a cycle.
'''
from DFS import driver, vertexStr

def DFSTopoOrder(g, reverse=True, verbose=True):
    '''g is a list containing lists of adjacent nodes in a DAG,
    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).
    If there is a cycle (graph not actually a DAG), None is returned.
    '''
    if g[0][0] == ':':
        print('This algorithm is only for a digraph.')
        return
    endings = [] 
    lim = len(g)
    visited = ['no']*lim # testing for back edges,need options no, started, done
    for i in range(1, lim):
        if visited[i] == 'no':
            try:
                dfs(g, visited, i, endings)
            except ValueError:
                if verbose:
                    print('Cycle found:  no topological order.')
                return None
    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] = 'started' # needed for back edge test
    for w in g[v]:
        if visited[w] == 'no':
            dfs(g, visited, w, endings)
        elif visited[w] == 'started':
            raise ValueError # raise exception if back edge: making cycle
    endings.append(v)
    visited[v] = 'done'

if __name__ == '__main__':
    driver(DFSTopoOrder, 'A>BCD B>CD C> D>C E>CG F>E G>')
    driver(DFSTopoOrder, 'A>BCD B>CD C> D>C E>CG F>E G>CF') # cycle EGF