# Chapter 14 : Weighted Graphs¶

### Example 14.1 Page no: 681¶

In [ ]:

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.nVerts = 0
for j in range(20): # set adjacency
l = []
for k in range(20):
l.append(1000000)
self.thePQ =  PriorityQ()
self.nTree = 0
self.currentVert = 0

self.vertexList.append( Vertex(lab))
self.nVerts += 1

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
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)

print 'Minimum spanning tree: ',
theGraph.mstw() # minimum spanning tree


### Example 14.2 Page 703¶

In [2]:

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.nVerts = 0
self.nTree = 0
for j in range(20): # set adjacency
l = []
for k in range(20):
l.append(1000000)
self.currentVert = 0
self.sPath = [] # shortest paths
self.startToCurrent = 0

self.vertexList.append( Vertex(lab))
self.nVerts += 1

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):
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.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

# 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
startToFringe = self.startToCurrent + currentToFringe
# get distance of current sPath entry
sPathDist = self.sPath[column].distance
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()

Shortest paths A  =