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