'''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