'''procedural graph traversal basic algorithm, showing beginning and ending
of processing on each vertex. Includes conversion from string representation.
The graph data structure g
vertices are labeled internaly as integer indices 1..n,
and external vertex names (generally a single character) are also stored.
g is a list encoded as follows for a graph with n vertices:
g[0] a sequence: g[0][0] is ':' or '>' indicating undirected or directed
g[0][i], i=1..n is the external vertex name for vertex i
g[i], i = 1..n: A list of integer indices of neighbors of i
For example, the graph g from string "A:BC B:AD C:A D:B" is
[[':', 'A', 'B', 'C', 'D'], # undirected, vertex names
[ 2 , 3], # vertex 1's (A's) neighbors (BC)
[ 1 , 4], # vertex 2's (B's) neighbors (AD)
[ 1], # vertex 3's (C's) neighbors (A)
[ 2] # vertex 4's (D's) neighbors (B)
]
An alternate OO approach for weighted graphs is in graph.py, discussed later.
'''
def DFSSweep(g):
'''g is a list for a graph, see the module data structure explanation.
'''
n = len(g) - 1 # the number of nodes
visited = [False]*(n+1) # list of n+1 False: extra so can number from 1
for i in range(1, n+1):
if not visited[i]:
dfs(g, visited, i)
def dfs(g, visited, v):
'''g is the basic list for a graph.
visited is a list showing which nodes are visited so far,
v is the starting vertex index >= 1, for the search
'''
visited[v] = True
print("visiting", g[0][v]) # or other first visit code
for w in g[v]:
if not visited[w]:
dfs(g, visited, w)
# optional code after child finished processing
print("finishing", g[0][v]) # or other vertex completion processing
#########################################################################
# rest is testing routines, standard in all procedural examples
def charToNum(ch, g):
'''Given a vertex label character ch and the list g for a graph,
return the index of the vertex >= 1. '''
return g[0].index(ch)
def numToChar(i, g):
'''Given a vertex index i >= 1, and the list g for a graph,
return the vertex label character. '''
return g[0][i]
def getArgs(default):
'''return an argument string from the command line or use the default.'''
import sys
args = sys.argv[1:]
if args:
return ' '.join(args)
return default
lastStr = '?:' # lastStr is global that remembers the last legal graphStr.
def getLastStr():
'''Return the last legal graphStr passed to fromStr.'''
return lastStr
def vertexStr(vList, g):
'''Convert a list of indices of g to a string of vertex labels.'''
return ''.join([numToChar(j, g) for j in vList])
def toStr(g):
'''Convert a list g for a graph to a string; g == fromStr(toStr(g)).'''
return ' '.join([g[0][i]+g[0][0]+vertexStr(g[i], g)
for i in range(1, len(g))])
def vertexStrToList(s, g):
'''Return a list of vertex indices for a string of vertex labelsin graph g.
'''
return [charToNum(ch, g) for ch in s]
def fromStr(graphStr=None, verbose=True):
'''Return the graph data structure for string representation graphStr
or None if there is a parsing error.
graphStr is a string of blank/comma separated tokens.
Tokens give vertex letter names and adjacency
lists for each vertex, in a form like D:CFH
meaning vertex D is adjacent to C, F, and H, and the graph is undirected.
Replace all ':' by '>' for a directed graph.
In an undirected graph adds reverse edges to vertex lists for consistency.
Announces the revised adjacency lists if verbose.
A *pair* of inequality characters, '<' or '>', may be appended.
If the first character is '<', the vertex order for the sweep is reversed.
If the last character is '<', then all neighbor orders are reversed.
If the only two characters are the inequality characters,
the last graph that was used is reordered.
'''
global lastStr
graphStr = graphStr.strip()
if not graphStr:
graphStr = lastStr
if len(graphStr) == 1:
print('String format error: Need two characters at least')
return
rev = '>>' # default is no reversals
if graphStr[-1] in '<>' and graphStr[-2] in '<>': # see if reversals at end
rev = graphStr[-2:]
graphStr = graphStr[:-2]
if not graphStr: # if reversals were the only characters, use lastStr
graphStr = lastStr
if ':' not in graphStr and '>' not in graphStr:
print("String format error: Must indicate directedness with ':' or '>'")
return
if ':' in graphStr and '>' in graphStr:
print("String format error: Must only have one of ':' and '>'")
return
if ':' in graphStr:
dirChar = ':'
else:
dirChar = '>'
if ',' in graphStr:
vertStringList = graphStr.replace(' ', '').split(',')
else:
vertStringList = graphStr.split()
for s in vertStringList:
if s.count(dirChar) != 1 or s.find(dirChar) != 1:
print('Bad syntax in string token', s)
return
verts = ''.join([dirChar] + [s[0] for s in vertStringList]) # dirchar+labels
g = [verts] # need first part of g for vertexStrToList
g += [vertexStrToList(s.split(dirChar)[1], g) for s in vertStringList]
lim = len(g)
if dirChar == ':': # look for and add inferred backwards edges
added = 0
for i in range(1, lim):
if i in g[i]:
print('Cannot link vertex to self in undirected graph:',
g[0][i])
return
inferred = [j for j in range(1, i)
if j not in g[i] and i in g[j]]
g[i][0:0] = inferred # early omitted vertices added at beginning
added += len(inferred)
inferred = [j for j in range(i+1, lim)
if j not in g[i] and i in g[j]]
g[i] += inferred # later omited vertices added at end
added += len(inferred)
if added and verbose:
print('Added', added, 'inferred vertices in undirected graph:',
'\n'+toStr(g))
if rev[0] == '<': # reverse vertex order
g[0] = g[0][0] + ''.join(list(reversed(g[0][1:]))) # vertices backwards
for i in range(1, lim): # fix neighbor references to new index
g[i] = [lim - j for j in g[i]]
g[1:] = reversed(g[1:]) # match neighbor lists to right vertices
if rev[1] == '<': # reverse neighbor order for each vertex
for i in range(1, len(g)):
g[i].reverse()
lastStr = toStr(g)
if rev != '>>' and verbose:
print('Reordered graph:', lastStr)
return g
def fromStrDisplay(graphStr):
g = fromStr(graphStr)
if g is not None:
print('Use vertices and edges:\n ', getLastStr())
return g
def test(func, graphStr):
'''If no eror in converting graphStr string to a list g for a graph,
run func(g). See fromStr for graphStr syntax.
'''
g = fromStrDisplay(graphStr)
if g is not None:
return func(g)
def driver(func, defaultGraphStr):
'''Run func on a list for a graph derived from the commandline
or if no arguments, use defaultGraphStr.'''
return test(func, getArgs(defaultGraphStr))
if __name__ == '__main__':
driver(DFSSweep, 'A:BCF B:ACD C:ABDF D:BC E:G F:AC G:E')