class Edge:
def __init__(self,sv,dv,d): # constructor
self.srcVert = sv
self.destVert = dv
self.distance = d
class PriorityQ:
def __init__(self):
# constructor
self.queArray = []
self.size = 0
def insert(self,item): # insert item in sorted order
self.queArray.append(item)
b = self.size
for j in range(self.size): # find place to insert
if( item.distance >= self.queArray[j].distance ):
b = j
break
for k in range(self.size-1,b-1,-1):#=self.size-1 k>=j k--) # move items up
self.queArray[k+1] = self.queArray[k]
self.queArray[b] = item
# insert item
self.size += 1
def removeMin(self): # remove minimum item
self.size -= 1
return self.queArray[self.size]
def removeN(self,n): # remove item at n
for j in range(n,self.size-1): # move items down
self.queArray[j] = self.queArray[j+1]
self.size -= 1
def peekMin(self): # peek at minimum item
return self.self.queArray[self.size-1]
def size(self): # return number of items
return self.size
def isEmpty(self): # true if queue is empty
return (self.size==0)
def peekN(self,n): # peek at item n
return self.queArray[n]
def find(self,findDex): # find item with specified
# self.destVert value
for j in range(self.size-1):
if(self.queArray[j].destVert == findDex):
return j
return -1
class Vertex:
def __init__(self,lab): # constructor
self.label = lab
self.isInTree = False
class Graph:
def __init__(self):
self.vertexList = [] # adjacency matrix
self.adjMat = []
self.nVerts = 0
for j in range(20): # set adjacency
l = []
for k in range(20):
l.append(1000000)
self.adjMat.append(l)
self.thePQ = PriorityQ()
self.nTree = 0
self.currentVert = 0
def addVertex(self,lab):
self.vertexList.append( Vertex(lab))
self.nVerts += 1
def addEdge(self,start, end,weight):
self.adjMat[start][end] = weight
self.adjMat[end][start] = weight
def displayVertex(self,v):
print self.vertexList[v].label ,
def mstw(self):
self.currentVert = 0 # minimum spanning tree
# start at 0
while(self.nTree < self.nVerts-1): # while not all verts in tree
# put self.currentVert in tree
self.vertexList[self.currentVert].isInTree = True
self.nTree += 1
# insert edges adjacent to self.currentVert into PQ
for j in range(self.nVerts): # for each vertex,
if(j==self.currentVert): # skip if its us
continue
if(self.vertexList[j].isInTree): # skip if in the tree
continue
self.distance = self.adjMat[self.currentVert][j]
if( self.distance == 1000000): # skip if no edge
continue
self.putInPQ(j, self.distance) # put it in PQ (maybe)
if(self.thePQ.size==0): # no vertices in PQ?
print 'GRAPH NOT CONNECTED',
return
# remove edge with minimum self.distance, from PQ
theEdge = self.thePQ.removeMin()
sourceVert = theEdge.srcVert
self.currentVert = theEdge.destVert
# display edge from source to current
print self.vertexList[sourceVert].label ,self.vertexList[self.currentVert].label, " ",
for j in range(self.nVerts): # unmark vertices
self.vertexList[j].isIsTree = False
def putInPQ(self,newVert,newDist): # is there another edge with the same destination vertex?
queueIndex = self.thePQ.find(newVert)
if(queueIndex != -1): # got edges index
tempEdge = self.thePQ.peekN(queueIndex) # get edge
oldDist = tempEdge.distance
if(oldDist > newDist): # if new edge shorter,
self.thePQ.removeN(queueIndex) # remove old edge
theEdge = Edge(self.currentVert, newVert, newDist)
self.thePQ.insert(theEdge)# insert new edge
# else no action just leave the old vertex there
else: # no edge with same destination vertex
# so insert new one
theEdge = Edge(self.currentVert, newVert, newDist)
self.thePQ.insert(theEdge)
theGraph = Graph()
theGraph.addVertex('A') # 0 (start for mst)
theGraph.addVertex('B') # 1
theGraph.addVertex('C') # 2
theGraph.addVertex('D') # 3
theGraph.addVertex('E') # 4
theGraph.addVertex('F') # 5
theGraph.addEdge(0, 1, 16) # AB
theGraph.addEdge(0, 3, 24) # AD
theGraph.addEdge(1,2,1)
theGraph.addEdge(1,3,5)
theGraph.addEdge(1,4,2)
theGraph.addEdge(2,3,6)
theGraph.addEdge(2,4,8)
theGraph.addEdge(2,5,26)
theGraph.addEdge(3,4,142)
theGraph.addEdge(4,5,17)
print 'Minimum spanning tree: ',
theGraph.mstw() # minimum spanning tree
class DistPar:
def __init__(self,pv,d): # constructor
self.distance = d
self.parentVert = pv
class Vertex:
def __init__(self,lab): # constructor
self.label = lab
self.isInTree = False
class Graph:
def __init__(self): # constructor
self.vertexList = [] # adjacency matrix
self.adjMat = []
self.nVerts = 0
self.nTree = 0
for j in range(20): # set adjacency
l = []
for k in range(20):
l.append(1000000)
self.adjMat.append(l)
self.currentVert = 0
self.sPath = [] # shortest paths
self.startToCurrent = 0
def addVertex(self,lab):
self.vertexList.append( Vertex(lab))
self.nVerts += 1
def addEdge(self,start, end,weight):
self.adjMat[start][end] = weight
def displayVertex(self,v):
print self.vertexList[v].label ,
def path(self): # find all shortest paths
startTree = 0 # start at vertex 0
self.vertexList[startTree].isInTree = True
self.nTree = 1 # put it in tree
# transfer row of distances from adjMat to sPath
for j in range(self.nVerts):
tempDist = self.adjMat[startTree][j]
try:
self.sPath[j] = DistPar(startTree, tempDist)
except:
self.sPath.append(DistPar(startTree, tempDist))
# until all vertices are in the tree
while(self.nTree < self.nVerts):
indexMin = self.getMin() # get minimum from sPath
minDist = self.sPath[indexMin].distance
if(minDist == 1000000): # if all infinite
# or in tree,
print 'There are unreachable vertices'
break # sPath is complete
else:
# reset self.currentVert
self.currentVert = indexMin # to closest vert
self.startToCurrent = self.sPath[indexMin].distance
# minimum distance from startTree is
# to self.currentVert, and is self.startToCurrent
# put current vertex in tree
self.vertexList[self.currentVert].isInTree = True
self.nTree += 1
self.adjust_sPath() # update sPath[] array
self.displayPaths() # display sPath[] contents
self.nTree = 0 # clear tree
for j in range(self.nVerts):
self.vertexList[j].isInTree = False
def getMin(self): # get entry from sPath
minDist = 1000000 # assume minimum
indexMin = 0
for j in range(self.nVerts): # for each vertex,
# if its in tree and
if( not self.vertexList[j].isInTree and self.sPath[j].distance < minDist ):
minDist = self.sPath[j].distance
indexMin = j # update minimum
return indexMin
def adjust_sPath(self):
# adjust values in shortest-path array sPath
column = 1
# skip starting vertex
while(column < self.nVerts): # go across columns
# if this columns vertex already in tree, skip it
if( self.vertexList[column].isInTree ):
column += 1
continue
# calculate distance for one sPath entry get edge from self.currentVert to column
currentToFringe = self.adjMat[self.currentVert][column]
# add distance from start
startToFringe = self.startToCurrent + currentToFringe
# get distance of current sPath entry
sPathDist = self.sPath[column].distance
# compare distance from start with sPath entry
if(startToFringe < sPathDist): # if shorter,
# update sPath
self.sPath[column].parentVert = self.currentVert
self.sPath[column].distance = startToFringe
column += 1
def displayPaths(self):
for j in range(self.nVerts): # display contents of sPath[]
print self.vertexList[j].label ,' ='
if(self.sPath[j].distance == 1000000):
print 'inf', # inf
else:
print self.sPath[j].distance , # 50
parent = self.vertexList[ self.sPath[j].parentVert ].label
print '(' , parent , ')' , # (A)
print ''
theGraph = Graph()
theGraph.addVertex('A') # 0 (start)
theGraph.addVertex('C') # 2
theGraph.addVertex('B') # 1
theGraph.addVertex('D') # 3
theGraph.addVertex('E') # 4
theGraph.addEdge(0,1,50)
theGraph.addEdge(0,3,80)
theGraph.addEdge(1,2,60)
theGraph.addEdge(1,3,90)
theGraph.addEdge(2,4,40)
theGraph.addEdge(3,2,20)
theGraph.addEdge(3,4,70)
theGraph.addEdge(4,1,50)
print 'Shortest paths' ,
theGraph.path() # shortest paths