Rabbit House

# Graph Algorithms

def isGraph(edge):
    a=len(edge)
    for i in edge:
        if len(i)!=a:
            return False
    return True

def findMatrixMin(edge):
    row=999999
    col=999999
    MIN=999999
    for i in range(len(edge)):
        for j in range(len(edge)):
            if edge[i][j]<MIN and edge[i][j]!=0:
                MIN=edge[i][j]
                row=i+1 
                col=j+1 
    return MIN,[row,col]

#print findMatrixMin(edge)

class graph:
    edge=None 
    v=0
    visited=[]
    def __init__(self,edge):
        if isGraph(edge)==True:
            self.edge=[]
            for i in edge:
                newlist=i[:]
                self.edge.append(newlist)

            self.v=len(edge)
            self.visited=[0]*self.v 
        else:
            raise "Error!"
    def addVertex(self,contact):
        if len(contact)==self.v:
            for i in range(len(contact)):
                self.edge[i].append(contact[i])
            contact.append(0)
            self.edge.append(contact)
            v=v+1
        else:
            raise "Error!"
    def delVertex(self,vnum):
        # vnum=1~v 
        if vnum>=1 and vnum<=self.v:
            self.edge.pop(vnum-1)
            for i in self.edge:
                i.pop(vnum-1)
        else:
            raise "Error!"
    def viewGraph(self):
        for i in self.edge:
            print i 
    def cutEdge(self,v1,v2):
        # v1,v2=1~v 
        self.edge[v1-1][v2-1]=0
        self.edge[v2-1][v1-1]=0
    def DFS(self,root):
        # root=1~v
        if root>=1 and root<=self.v:
            self.visited[root-1]=1
            print root,
            for i in range(self.v):
                if self.edge[root-1][i]!=0 and self.visited[i]==0:
                        self.DFS(i+1)
        else:
            raise "Error!"
    def DFS_nr(self,root):
        # root=1~v 
        # Non-recursive
        stack=[]
        result=[]
        if root>=1 and root<=self.v:
            stack.append(root)
            while stack!=[]:
                peek=stack.pop()
                if self.visited[peek-1]==0:
                    result.append(peek)
                    self.visited[peek-1]=1 
                for i in range(self.v):
                    if self.edge[peek-1][self.v-1-i]!=0 and self.visited[self.v-1-i]==0:
                        stack.append(self.v-i)
        else:
            raise "Error!"
        return result
    def BFS_nr(self,root):
        # root=1~v
        # Non-recursive
        queue=[]
        result=[]
        if root>=1 and root<=self.v:
            queue.append(root)
            self.visited[root-1]=1 
            while queue!=[]:
                node=queue.pop(0)
                result.append(node)
                for i in range(self.v):
                    if self.edge[node-1][i]!=0 and self.visited[i]==0:
                        self.visited[i]=1 
                        queue.append(i+1)
        else:
            raise "Error!"
        return result
    def Kruskal(self):
        if self.v<=1:
            return 0,None 
        def findSet(element,forest):
            for i in forest:
                if i!=None:
                    if element in i:
                        return i 
            return None
        forest=[]
        for i in range(self.v):
            forest.append([i+1])
        minST=0
        minEdges=[]
        while len(forest)>1:
            m,[v1,v2]=findMatrixMin(self.edge)
            set1=findSet(v1,forest)
            set2=findSet(v2,forest)
            #print m,set1,set2
            if set1!=set2:
                self.edge[v1-1][v2-1]=0
                self.edge[v2-1][v1-1]=0
                minST+=m 
                minEdges.append([v1,v2])
                newTree=set1+set2
                forest.remove(set1)
                forest.remove(set2)
                forest.append(newTree)
        return minST,minEdges
    def Prim(self):
        if self.v<=1:
            return 0,None 
        minEdges=[]
        minST=0
        notInTree=[]
        prim=[]
        for i in range(self.v):
            notInTree.append(i+1)
        # start with node 1 
        notInTree.remove(1)
        prim.append(1)
        while notInTree:
            minEdge=[999999,999999]
            minL=999999
            for i in prim:
                for j in notInTree:
                    if self.edge[i-1][j-1]<minL and self.edge[i-1][j-1]!=0:
                        minL=self.edge[i-1][j-1]
                        minEdge=[i,j]
            minST+=minL
            minEdges.append(minEdge)
            prim.append(minEdge[1])
            notInTree.remove(minEdge[1])
        return minST,minEdges
    def Floyd_Warshall(self):
        dist=self.edge 
        for i in range(self.v):
            for j in range(self.v):
                if dist[i][j]==0:
                    dist[i][j]=999999
        for i in range(self.v):
            dist[i][i]=0
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    if dist[i][j]>dist[i][k]+dist[k][j]:
                        dist[i][j]=dist[i][k]+dist[k][j]
        return dist
    def Dijkstra(self,s):
        dist=self.edge 
        result=[999999]*self.v 
        result[s-1]=0
        for i in range(self.v):
            for j in range(self.v):
                if i!=j and dist[i][j]==0:
                    dist[i][j]=999999
        S=[]
        U=[]
        for i in range(self.v):
            U.append(i+1)
        while U!=[]:
            MIN=999999
            index=0
            for i in S:
                for j in U:
                    dist[s-1][j-1]=min(dist[s-1][j-1],dist[s-1][i-1]+dist[i-1][j-1])
            for j in U:
                if dist[s-1][j-1]<MIN:
                    MIN=dist[s-1][j-1]
                    index=j
            S.append(index)
            U.remove(index)
        return dist[s-1]

edge=[[0,3,2,4,0,0,0],
      [3,0,4,0,0,0,6],
      [2,4,0,0,0,1,0],
      [4,0,0,0,5,0,0],
      [0,0,0,5,0,3,0],
      [0,0,1,0,3,0,2],
      [0,6,0,0,0,2,0]]
# 0 3 2 4 0 0 0
# 3 0 4 0 0 0 6
# 2 4 0 0 0 0 1
# 4 0 0 0 5 0 0
# 0 0 0 5 0 3 0
# 0 0 1 0 3 0 2
# 0 6 0 0 0 2 0    

Graph=graph(edge)
print Graph.DFS_nr(1)
Graph=graph(edge)
print Graph.BFS_nr(1)
Graph=graph(edge)
minST,minEdges=Graph.Kruskal()
print "Kruskal:",minEdges,"  Min:",minST
Graph=graph(edge)
minST,minEdges=Graph.Prim()
print "Prim:",minEdges,"  Min:",minST
Graph=graph(edge)
dist=Graph.Floyd_Warshall()
for i in dist:
    print i 
Graph=graph(edge)
print "Dijstrak(1):",Graph.Dijkstra(1)

Python 2.7.10 (default, Jul 14 2015, 19:46:27)
[GCC 4.8.2] on linux

[1, 2, 3, 6, 5, 4, 7]
[1, 2, 3, 4, 7, 6, 5]
Kruskal: [[3, 6], [1, 3], [6, 7], [1, 2], [5, 6], [1, 4]]   Min: 15
Prim: [[1, 3], [3, 6], [6, 7], [1, 2], [6, 5], [1, 4]]   Min: 15
[0, 3, 2, 4, 6, 3, 5]
[3, 0, 4, 7, 8, 5, 6]
[2, 4, 0, 6, 4, 1, 3]
[4, 7, 6, 0, 5, 7, 9]
[6, 8, 4, 5, 0, 3, 5]
[3, 5, 1, 7, 3, 0, 2]
[5, 6, 3, 9, 5, 2, 0]
Dijstrak(1): [0, 3, 2, 4, 6, 3, 5]

Basic Graph Algorithms