Entering edit mode
2.7 years ago
octpus616
▴
100
Hi， Let me use a quiz from Python data structure and algorithm analysis by Bradley .N Miller and David L. Ranum to expain my qusetion.
Quesion: Consider the task of converting the word FOOL to SAGE, also called word ladder problem. In solving In the word ladder problem, only one letter must be replaced at a time, and the result of each step must be a word, not non-existent.
Input:
FOUL FOOL FOIL FAIL COOL FALL POOL PALL POLL POLE PALE PAGE SALE POPE POPE SAGE
note: I dont kown why the words list not show correct wrap in biostars，please manually change the above list to one word per line if need.
We can easily find the path from FOOL to SAGE, as Bradley showed:
and I used Breadth First Search (BFS) to solve probem:
class Vertex:
def __init__(self, key, value = None):
self.id = key
self.connectedTo = {}
self.color = 'white'
self.dist = sys.maxsize
self.pred = []
self.disc = 0
self.fin = 0
self.value = value,
#self.GraphBulided = False
self.traverseIndex = 0
self.predNum = 0
def addNeighbor(self, nbr, weight=0):
self.connectedTo[nbr] = weight
def __str__(self):
return '{} connectedTo: {}'.format(self.id, \
str([x.id for x in self.connectedTo]))
def setColor(self, color):
self.color = color
def setDistance(self, d):
self.dist = d
#I want store all Pred for next traverse so I use a list to do it
def setPred(self, p, list = False):
if not list:
self.pred = p
else:
self.pred.append(p)
self.predNum += 1
def setDiscovery(self,dtime):
self.disc = dtime
def setFinish(self,ftime):
self.fin = ftime
#def setGraphBulided(self, tag = True):
# self.GraphBulided = tag
def getFinish(self):
return self.fin
def getDiscovery(self):
return self.disc
def getPred(self):
if isinstance(self.pred, list):
if self.traverseIndex < self.predNum:
return self.pred[self.traverseIndex]
else:
return self.pred[-1]
else:
return self.pred
def __hash__(self):
return hash(self.id)
def getPredById(self):
if self.traverseIndex < self.predNum and isinstance(self.pred, list):
pred = self.pred[self.traverseIndex]
self.traverseIndex += 1
print("vertix {}: {} of {} preds".format(self.id, self.traverseIndex, self.predNum))
return [pred, self.traverseIndex]
else:
pred = None
return [pred, None]
def getCurrPredStaus(self):
#if not self.pred:
# return None
return self.predNum - self.traverseIndex
def getDistance(self):
return self.dist
def getColor(self):
return self.color
def getConnections(self):
return self.connectedTo.keys()
def getId(self):
return self.id
def getWeight(self, nbr):
return self.connectedTo[nbr]
def getValue(self):
return self.value
def findPath(self, dest):
pass
class Graph:
def __init__(self):
self.vertList = {}
self.numVertics = 0
self.verticsInSerach = set()
self.GraphBulided = False
def addVertex(self, key, value = None):
self.numVertics = self.numVertics + 1
newVertex = Vertex(key, value=value)
self.vertList[key] = newVertex
return newVertex
def getVertex(self, n):
if n in self.vertList:
return self.vertList[n]
else:
return None
def __contains__(self, n):
return n in self.vertList
def addEdge(self, f, t, cost = 0, fvalue = None, tvalue = None):
if f not in self.vertList:
nv = self.addVertex(f, fvalue)
if t not in self.vertList:
nv = self.addVertex(t, tvalue)
self.vertList[f].addNeighbor(self.vertList[t], cost)
def setGraphBulided(self, tag = True):
self.GraphBulided = tag
def getVertices(self):
return self.vertList.keys()
def setGraphBulided(self, tag = True):
self.GraphBulided = tag
def setSerachedVertixs(self, vertix):
self.verticsInSerach.add(vertix)
def getGraphBulided(self):
return self.GraphBulided
def getSerachedVertixs(self):
return self.verticsInSerach
def __iter__(self):
return iter(self.vertList.values())
def __hash__(self):
hashIds = [x for x in self.getVertices()]
if len(hashIds) > 0 and hashIds[0]:
return hash(', '.join(hashIds))
else:
return None
Here are some additional functions for building graphs
def buildGraph(wordFile, DFSgraph = False):
d = {}
g = Graph()
if DFSgraph:
g = DFSGraph()
wfile = open(wordFile)
for line in wfile:
word = line[:-1]
for i in range(len(word)):
bucket = word[:i] + '_' + word[i+1:]
if bucket in d:
d[bucket].append(word)
else:
d[bucket] = [word]
for bucket in d.keys():
for word1 in d[bucket]:
for word2 in d[bucket]:
if word1 != word2:
g.addEdge(word1, word2)
wfile.close()
return g
class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0,item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
def bfs(g, start, listpred = False):
start.setDistance(0)
start.setPred(None)
vertQueue = Queue()
vertQueue.enqueue(start)
while (vertQueue.size() > 0):
currentVert = vertQueue.dequeue()
if currentVert.getConnections():
g.setSerachedVertixs(currentVert)
for nbr in currentVert.getConnections():
#print('sreach {}'.format(currentVert.getId()))
if (nbr.getColor() == 'white' or nbr.getColor() == 'gray'):
nbr.setColor('gray')
nbr.setDistance(currentVert.getDistance() + 1)
if nbr.predNum > 0 and currentVert.getId() not in [x.getId() for x in nbr.pred]:
nbr.setPred(currentVert, listpred)
elif nbr.predNum == 0:
nbr.setPred(currentVert, listpred)
vertQueue.enqueue(nbr)
currentVert.setColor('black')
Therefore, we can easily find the shortest path we need (If we only store one pred for one vertix).
wordGraph = buildGraph('fourletterwords1.txt', DFSgraph=False)
bfs(wordGraph, wordGraph.getVertex('FOOL'), listpred=True)
def traverse(y):
x=y
while(x.getPred()):
print(x.getPred())
x = x.getPred()
print(x.getId())
traverse(wordGraph.getVertex('SAGE'))
However, I still don't know how to trace all the paths correctly, can you give me some suggestions?
