CS201 Finale

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)