Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import copy
- class Graph:
- def __init__(self):
- self.vertices = {}
- self.invVertices = []
- self.adjList = []
- self.size = 0
- def insert_node(self, name):
- self.invVertices.append(name)
- self.vertices[name] = self.size
- self.adjList.append([])
- self.size += 1
- def insert_edge(self, src, dest, weight = 1):
- self.adjList[self.vertices[src]].append((self.vertices[dest], weight))
- def bfs(self, source):
- source = self.vertices[source]
- visit = [True for i in xrange(self.size)]
- queue = [source]
- visit[source] = False
- pi = {source : source}
- while len(queue) != 0:
- c = queue.pop()
- print "Node: ", self.invVertices[c], "\t Pi(", self.invVertices[c], "): ", self.invVertices[pi[c]]
- for n,w in self.adjList[c]:
- if visit[n]:
- queue.insert(0, n)
- pi[n] = c
- visit[n] = False
- def dfs_iterative(self, source):
- source = self.vertices[source]
- visit = [True for i in xrange(self.size)]
- stack = [source]
- pi = {source : source}
- while len(stack) != 0:
- c = stack.pop()
- if visit[c]:
- print "Node: ", self.invVertices[c], "\t Pi(", self.invVertices[c], "): ", self.invVertices[pi[c]]
- visit[c] = False
- for n,w in self.adjList[c]:
- if visit[n]:
- stack.append(n)
- pi[n] = c
- def vertices_decreasing_finish_time_visit(self, root, visit, sortedVertices):
- visit[root] = False
- for node, wt in self.adjList[root]:
- if visit[node]:
- self.vertices_decreasing_finish_time_visit(node, visit, sortedVertices)
- sortedVertices.insert(0, root)
- def vertices_decreasing_finish_time(self):
- visit = [True for i in xrange(self.size)]
- sortedVertices = []
- for i in xrange(self.size):
- if visit[i]:
- self.vertices_decreasing_finish_time_visit(i, visit, sortedVertices)
- return sortedVertices
- def get_transpose(self):
- transpose = copy.deepcopy(self)
- transpose.adjList = [[] for i in xrange(transpose.size)]
- for i in xrange(self.size):
- for node, wt in self.adjList[i]:
- transpose.adjList[node].append((i, wt))
- return transpose
- def strongly_connected_components(self):
- transpose = self.get_transpose()
- visit = [True for i in xrange(self.size)]
- scc = []
- for i in self.vertices_decreasing_finish_time():
- if visit[i]:
- l = []
- transpose.vertices_decreasing_finish_time_visit(i, visit, l)
- scc.append(l)
- return scc
- def dijkstra(self, rt):
- root = self.vertices[rt]
- size = self.size
- INF = float('inf')
- m = Heap(size = size, inf = INF)
- dist = [INF for i in xrange(size)]
- pi = [0 for i in xrange(size)]
- m.update(root, 0)
- pi[root] = root
- dist[root] = 0
- for i in xrange(size):
- root = m.extract_top()
- if dist[root] == INF:
- break
- for node, wt in self.adjList[root]:
- if dist[root] + wt < dist[node]:
- dist[node] = dist[root] + wt
- m.update(node, dist[node])
- pi[node] = root
- for i in xrange(size):
- if dist[i] != INF:
- print "Node: ", self.invVertices[i],"\tDistance: ",dist[i],"\tPi(",self.invVertices[i],"): ",self.invVertices[pi[i]]
- class UndirectedGraph(Graph):
- def __init__(self):
- Graph.__init__(self)
- def insert_edge(self, node1, node2, wt = 1):
- Graph.insert_edge(self, node1, node2, wt)
- Graph.insert_edge(self, node2, node1, wt)
- def span_tree_prim(self, rt, isMin = True):
- root = self.vertices[rt]
- size = self.size
- INF = float('inf') * (1 if isMin else -1)
- m = Heap(size = size, inf = INF, isMin = isMin)
- dist = [INF for i in xrange(size)]
- pi = [0 for i in xrange(size)]
- visit = [True for i in xrange(size)]
- m.update(root, 0)
- pi[root] = root
- dist[root] = 0
- for i in xrange(size):
- root = m.extract_top()
- visit[root] = False
- if dist[root] == INF:
- break
- for node, wt in self.adjList[root]:
- if visit[node] and (wt < dist[node] if isMin else wt > dist[node]):
- dist[node] = wt
- m.update(node, dist[node])
- pi[node] = root
- for i in xrange(size):
- if dist[i] != INF:
- print "Node: ", self.invVertices[i],"\tEdge Weight: ",dist[i],"\tPi(",self.invVertices[i],"): ",self.invVertices[pi[i]]
- def span_forest_kruskal(self, isMin = True):
- edgeList = []
- for i in xrange(self.size):
- for node, wt in self.adjList[i]:
- if node >= i:
- edgeList.append((i, node, wt))
- sorted(edgeList, key = lambda x: x[2], reverse = isMin)
- spanForest = [[] for i in xrange(self.size)]
- getComp = [i for i in xrange(self.size)]
- sizeComp = [1 for i in xrange(self.size)]
- for curredge in edgeList:
- if getComp[curredge[0]] != getComp[curredge[1]]:
- minSizeComp = getComp[curredge[0]]
- maxSizeComp = getComp[curredge[1]]
- if sizeComp[minSizeComp] > sizeComp[maxSizeComp]:
- minSizeComp, maxSizeComp = maxSizeComp, minSizeComp
- for edge in spanForest[minSizeComp]:
- getComp[edge[0]] = maxSizeComp
- getComp[edge[1]] = maxSizeComp
- sizeComp[maxSizeComp] += sizeComp[minSizeComp]
- sizeComp[minSizeComp] = 0
- spanForest[maxSizeComp].append(curredge)
- getComp[curredge[0]] = maxSizeComp
- getComp[curredge[1]] = maxSizeComp
- spanForest[minSizeComp] = []
- for tree in spanForest:
- if tree:
- print "Tree:"
- for edge in tree:
- print "Node 1: ",self.invVertices[edge[0]],"\tNode 2: ",self.invVertices[edge[1]],"\tEdge Weight: ",edge[2]
- class Heap:
- @staticmethod
- def parent(n):
- return (n-1)/2
- @staticmethod
- def left(n):
- return 2*n + 1
- @staticmethod
- def right(n):
- return 2*n + 2
- def compare(self, a, b):
- return (a < b if self.isMin else a > b)
- def swap(self, i, j):
- self.pos[self.heap[i][0]] = j
- self.pos[self.heap[j][0]] = i
- self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
- def __init__(self, size, inf, isMin = True):
- self.pos = [i for i in xrange(size)]
- self.heap = [[i, inf] for i in xrange(size)]
- self.size = size
- self.isMin = isMin
- def update(self, i, newVal):
- if self.compare(self.heap[self.pos[i]][1], newVal):
- self.heap[self.pos[i]][1] = newVal
- self.top_down_heapify(self.pos[i])
- else:
- self.heap[self.pos[i]][1] = newVal
- self.bottom_up_heapify(self.pos[i])
- def extract_top(self):
- retVal = self.heap[0][0]
- self.size -= 1
- self.swap(0, self.size)
- self.heap.pop()
- self.top_down_heapify(0)
- return retVal
- def top_down_heapify(self, i):
- l = Heap.left(i)
- r = Heap.right(i)
- j = i
- while r < self.size:
- j = l if self.compare(self.heap[l][1], self.heap[r][1]) else r
- if self.compare(self.heap[i][1], self.heap[j][1]):
- break
- else:
- self.swap(i, j)
- i = j
- l = Heap.left(i)
- r = Heap.right(i)
- if l == self.size - 1 and self.compare(self.heap[l][1], self.heap[j][1]):
- self.swap(l, j)
- def bottom_up_heapify(self, i):
- p = Heap.parent(i)
- while(p >= 0):
- if self.compare(self.heap[i][1], self.heap[p][1]):
- self.swap(i, p)
- i = p
- p = Heap.parent(i)
- else:
- break
- if __name__ == "__main__":
- a = UndirectedGraph()
- a.insert_node('A')
- a.insert_node('B')
- a.insert_node('C')
- a.insert_node('D')
- a.insert_node('E')
- a.insert_node('F')
- a.insert_node('G')
- a.insert_node('H')
- a.insert_node('I')
- a.insert_edge('A', 'B', 4)
- a.insert_edge('B', 'C')
- a.insert_edge('D', 'B', 3)
- a.insert_edge('E', 'D', 7)
- a.insert_edge('E', 'C', 8)
- a.insert_edge('C', 'F')
- a.insert_edge('E', 'A', 3)
- a.insert_edge('G', 'H', 5)
- a.insert_edge('G', 'I', 10)
- a.insert_edge('H', 'I', 4)
- print "BFS:"
- a.bfs('A')
- print "\nDFS:"
- a.dfs_iterative('A')
- print "\nDijkstra:"
- a.dijkstra('A')
- print "\nMinimum Span Tree Prim's:"
- a.span_tree_prim('A')
- print "\nMaximum Span Tree Prim's:"
- a.span_tree_prim('A', False)
- print "\nMinimum Span Forest Kruskal's:"
- a.span_forest_kruskal()
- print "\nMaximum Span Tree Kruskal's:"
- a.span_forest_kruskal(False)
- print "\nStrongly Connected Components:"
- print a.strongly_connected_components()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement