'''DFS sweep, adding listing of tree, back edges for undirected graph.
'''
from DFS import fromStr, toStr, test, driver, numToChar, charToNum
def UndirectedEdgeClassify(g):
'''g is a list of lists of adjacent nodes,
indicating both directions for each edge.
'''
if '>' in g[0]:
print('This classification only works for undirected graphs')
return
n = len(g) - 1 # the number of nodes
visited = ['no']*(n+1) # 3 choices needed: 'no', 'started', 'done'
for i in range(1, n+1):
if visited[i] == 'no':
print("root:", numToChar(i, g))
dfs(g, visited, i, 0) #0 is not used as a node; no parent
def dfs(g, visited, v, parent):
'''g is a list for a graph containing lists of adjacent nodes.
visited is a list of the current visited of nodes,
v is the starting vertex for the search
Lists indexed by vertex number; ignore index 0.
'''
visited[v] = 'started' # need third category for unfinished
for w in g[v]:
if visited[w] == 'no':
print("Tree:", edge(v, w, g))
dfs(g, visited, w, v)
elif visited[w] == 'started' and w != parent:
print("Back:", edge(v, w, g))
visited[v] = 'done'
def edge(v, w, g):
return numToChar(v, g) + numToChar(w, g)
if __name__ == '__main__':
driver(UndirectedEdgeClassify, 'A:BCF B:ACD C:ABDF D:BC E:G F:AC G:E')