'''graph traversal with component labeling.
Replace visited list with a list of components, 0 before visited'''
from DFS import driver, vertexStr
def DFSUndirectedComponents(g, verbose=True):
'''Return list of vertex lists for each component, and print components
if verbose.
g[1:] is a list containing lists of adjacent nodes for an undirected list,
g[0] used for directedness and vertex names.
'''
if g[0][0] == '>':
print('Components make sense for undirected graphs.')
return
lim = len(g)
comp = [0]*lim # list of n+1 False: extra so can number from 1
for i in range(1, lim):
if comp[i] == 0:
dfs(g, comp, i, i) #component number is first found index
# now comp[v] is equal for each vertex index v in the same component
comps = [[] for i in range(lim)] # initially components are empty lists
# note above, shorter [[]] * lim does not work since inner [] is mutable
for (v, i) in enumerate(comp): # collect indices v with same component i
comps[i].append(v)
comps = [c for c in comps[1:] if c] # skip c[0]; remove empty lists
if verbose: # print components via vertex labels
print(' '.join([vertexStr(c, g) for c in comps]))
return comps
def dfs(g, comp, v, component):
'''g is a list of 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.
The current component number is given.
'''
comp[v] = component # mark children with the component of the parent
for w in g[v]:
if comp[w] == 0:
dfs(g, comp, w, component)
# after child finished processing
def compStrs(comps, g):
return ' '.join([''.join([numToChar(i, g) for i in c]) for c in comps])
if __name__ == '__main__':
driver(DFSUndirectedComponents, 'A:G B:F C:D D:CFH E: F:BDH G:A H:DF')