word ladder in python

代码多是参照这里的：http://interactivepython.org/run ... dLadderProblem.html

首先是Graph 和Vertex 类

点击(此处)折叠或打开

1. class Vertex:
   
2.     def __init__(self,key,distance=0,pred=None,color="white"):
   
3.         self.id=key
   
4.         self.connectedTo={} #dict which contains all the other vertices it is connected to
   
5.         self.pred=pred #for BFS tree/a list because we are dealing with cycles
   
6.         self.color=color #for BFS tree
   
7.         self.distance=distance
   
8. 
   
9.     def addNeighbor(self,nbr,weight=0):
   
10.         self.connectedTo[nbr]=weight
    
11. 
    
12.     def __str__(self):
    
13.         return str(self.id)+' connectedTo: '+str([x.id for x in self.connectedTo])
    
14.         
    
15.     def getConnections(self):
    
16.         return self.connectedTo.keys()
    
17. 
    
18.     def getId(self):
    
19.         return self.id
    
20. 
    
21.     def getWeight(self,nbr):
    
22.         return self.connectedTo[nbr]
    
23.     
    
24.     def setPred(self,node):
    
25.         self.pred=node
    
26. 
    
27.     def getPred(self):
    
28.         return self.pred
    
29.     
    
30.     def setDistance(self,distance):
    
31.         self.distance=distance
    
32. 
    
33.     def getDistance(self):
    
34.         return self.distance
    
35.     
    
36.     def setColor(self,color):
    
37.         self.color=color
    
38. 
    
39.     def getColor(self):
    
40.         return self.color
    
41. 
    
42. 
    
43. #adjacency list implemented of the graph
    
44. class Graph:
    
45.     def __init__(self):
    
46.         self.vertList={}
    
47.         self.numVertices=0
    
48. 
    
49.     def addVertex(self,key):
    
50.         self.numVertices=self.numVertices+1
    
51.         newVertice=Vertex(key)
    
52.         self.vertList[key]=newVertice
    
53.         return newVertice
    
54. 
    
55.     def getVertex(self,n):
    
56.         if n in self.vertList:
    
57.             return self.vertList[n]
    
58.         else:
    
59.             return None
    
60. 
    
61.     def __contains__(self,n):
    
62.         return n in self.vertList
    
63. 
    
64.     def addEdge(self,f,t,cost=0):
    
65.         if f not in self.vertList:
    
66.             nv=self.addVertex(f)
    
67.         if t not in self.vertList:
    
68.             nv=self.addVertex(t)
    
69.         self.vertList[f].addNeighbor(self.vertList[t],cost)
    
70. 
    
71.     def getVertices(self):
    
72.         return self.vertList.keys()
    
73. 
    
74.     def __iter__(self):
    
75.         return iter(self.vertList.values())

下面是具体的实现。words.txt 是由4个字母组成的单词共有3686个，每行一个。

点击(此处)折叠或打开

1. wc -l words.txt
   
2. 3685 words.txt

点击(此处)折叠或打开

1. #build thw word Ladder Graph
   
2. def buildGraph(wordFile="words.txt"):
   
3.     d={}
   
4.     g=Graph()
   
5.     wfile=open(wordFile,"r")
   
6.     #create bucket of words that differ by one letter
   
7.     for line in wfile:
   
8.         word=line[:-1]
   
9.         for i in range(len(word)):
   
10.             bucket=word[:i]+'_'+word[i+1:]
    
11.             if bucket in d:
    
12.                 d[bucket].append(word)
    
13.             else:
    
14.                 d[bucket]=[word]
    
15. 
    
16.     #add vertices and edges for words in the same bucket
    
17.     for bucket in d.keys():
    
18.         for word1 in d[bucket]:
    
19.             for word2 in d[bucket]:
    
20.                 if word1!=word2:
    
21.                     g.addEdge(word1,word2)
    
22.     return g
    
23. 
    
24. def test_buildGraph():
    
25.     g=buildGraph()
    
26.     for v in g:
    
27.         print(v)
    
28.         #for w in v.getConnections():
    
29.         # print(v.getId(),w.getId())
    
30. 
    
31. #test_buildGraph()
    
32. 
    
33. #BFS traverse Graph
    
34. def bfs(g,start):
    
35.     start.setDistance(0)
    
36.     start.setPred(None)
    
37.     vertQueue=[]
    
38.     vertQueue.append(start)
    
39.     while len(vertQueue) > 0:
    
40.         currentVert=vertQueue.pop(0)
    
41.         for nbr in currentVert.getConnections():
    
42.             if (nbr.getColor()=='white'):
    
43.                 nbr.setColor("gray")
    
44.                 nbr.setDistance(currentVert.getDistance()+1)
    
45.                 nbr.setPred(currentVert)
    
46.                 vertQueue.append(nbr)
    
47.         currentVert.setColor('black')
    
48. 
    
49. 
    
50. def bfs2(g,start,stop):
    
51.     parents={}
    
52.     q=[]
    
53.     q.append(start)
    
54.     parents[start.id]=None
    
55. 
    
56.     while len(q)> 0:
    
57.         node=q.pop(0)
    
58.         for neighbour in node.getConnections():
    
59.             n=neighbour.id
    
60. 
    
61.             if n not in parents:
    
62.                 parents[n]=node.id
    
63.                 if n==stop.id:
    
64.                     return parents
    
65.                 q.append(neighbour)
    
66.     return parents
    
67. 
    
68. 
    
69. def traverse(y):
    
70.     #y: vertex
    
71.     x=y
    
72.     while(x.getPred()):
    
73.         print(x.getId())
    
74.         x=x.getPred()
    
75.     print(x.getId())
    
76. 
    
77. def test_traverse_with_bfs():
    
78.     g=buildGraph()
    
79.     start=g.getVertex("fool")
    
80.     bfs(g,start)
    
81.     traverse(g.getVertex("sage"))
    
82. 
    
83. test_traverse_with_bfs()
    
84. 
    
85. 
    
86. def getPath(start,finish,parents):
    
87.     finish=finish.id
    
88.     path=[finish]
    
89.     if finish in parents:
    
90.         node=parents[finish]
    
91.         while(node!=start.id):
    
92.             path.append(node)
    
93.             node=parents[node]
    
94.     else:
    
95.         "No Path "
    
96.     path.append(start.id)
    
97.     return path[::-1]
    
98. 
    
99. def test_traverse_withbfs2():
    
100.     g=buildGraph()
     
101.     start=g.getVertex("fool")
     
102.     stop=g.getVertex("sage")
     
103.     parents=bfs2(g,start,stop)
     
104.     #print(parents.keys())
     
105.     path=getPath(start,stop,parents)
     
106.     print(path)
     
107. 
     
108. test_traverse_withbfs2()