'''Graph traversal labeling the number of starting and finishing times,
imagining a time tick each time a vertex is started or finished.
'''
from DFS import driver, numToChar
def DFSActiveInterval(g, verbose=True):
'''g is a list containing lists of adjacent nodes,
indicating both directions for each edge.
return (startTime, endTime) lists giving for each node
the start time and end time of processing each vertex.
Prints descriptive output if verbose.
'''
time = [0] # in list so can essentially pass by reference, and update
lim = len(g)
startTime = [None]*lim # also serves the part of visited
endTime = [None]*lim
for i in range(1, lim):
if startTime[i] is None:
dfs(g, startTime, endTime, i, 0, time, verbose)
if verbose:
fstr = "{:>2}{:>6}{:>4}"
print("\n"+fstr.format("v", "start", "end"))
for v in range(1, lim):
print(fstr.format(numToChar(v, g), startTime[v], endTime[v]))
return (startTime, endTime)
def dfs(g, startTime, endTime, v, lev, time, verbose):
'''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
time[0] gives the starting/ending sequence number.
'''
time[0] += 1
startTime[v] = time[0]
if verbose:
print('{:2} {}visiting {}'.format(time[0], lev*' ', numToChar(v, g)))
for w in g[v]:
if startTime[w] is None:
dfs(g, startTime, endTime, w, lev+1, time, verbose)
time[0] += 1
endTime[v] = time[0]
if verbose:
print('{:2} {}finishing {}'.format(time[0], lev*' ', numToChar(v, g)))
if __name__ == '__main__':
driver(DFSActiveInterval, 'A:BCF B:ACD C:ABDF D:BC E:G F:AC G:E')
print('-'*30)
driver(DFSActiveInterval, 'A>BC B>AD C>F D> E>G F>C G>E')