Skip to content

Instantly share code, notes, and snippets.

@tdgunes

tdgunes/CS201 Finale

Created Jan 18, 2014
Embed
What would you like to do?
class queue:
def __init__(self):
self.temp = []
def enqueue(self, obj):
self.temp.append(obj)
def dequeue(self):
return self.temp.pop(0)
def isEmpty(self):
if len(self.temp) == 0:
return True
else:
return False
class graph:
def __init__(self, vertices):
self.vertices = vertices # 3 of them
self.adjacencyMatrix = [[] for i in range(0,vertices)]
self.verticesStatus = {i:0 for i in range(0,vertices)}
for i in range(0,self.vertices):
for j in range(0, self.vertices):
self.adjacencyMatrix[j].append(False)
def setVertexStatus(self, v1, status):
self.verticesStatus[v1] = status
def getVertexStatus(self, v1):
return self.verticesStatus[v1]
def getVertexCount(self):
return self.vertices
def showVertexStatus(self):
print self.verticesStatus
def showMatrix(self):
for i in range(0,self.vertices):
acc = " | "
for j in range(0, self.vertices):
temp = self.adjacencyMatrix[i][j]
if(temp):
acc += "True "
else:
acc += "False"
acc += " | "
print acc
def addEdge(self, v1, v2):
self.adjacencyMatrix[v1][v2] = True
def removeEdge(self, v1, v2):
self.adjacencyMatrix[v1][v2] = False
def isEdge(self, v1, v2):
return self.adjacencyMatrix[v1][v2]
#g is the graph v1 -> v2 is searched
def reachable(g, v1, v2):
q = queue();
reachable = False
for i in range(0,g.getVertexCount()):
g.setVertexStatus(i,0)
g.setVertexStatus(v1,1)
q.enqueue(v1)
while(q.isEmpty() is False):
visitedVertex = q.dequeue()
#adjacent ones are
for v in range(0,g.getVertexCount()):
if(g.isEdge(visitedVertex,v) and g.getVertexStatus(v) == 0):
g.setVertexStatus(v,1)
q.enqueue(v)
else:
if visitedVertex == v2:
return True
return False
a = graph(9)
a.showMatrix()
a.addEdge(0,1)
a.addEdge(1,2)
a.addEdge(2,7)
a.addEdge(7,3)
a.addEdge(3,8)
print ""
a.showMatrix()
a.showVertexStatus()
print reachable(a, 0, 8)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.