Guest User

python graph class

a guest
Apr 23rd, 2013
174
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Graph:
  2.     cycles=[]
  3.     visited = []
  4.     spanningTree = {}
  5.     edges = {}
  6.    
  7.     def getCycle(self, node, ancestor):
  8.         path = []
  9.         while (node != ancestor):
  10.             if node is None:
  11.                 return []
  12.             path.append(node)
  13.             node = self.spanningTree[node]
  14.         path.append(node)
  15.         return path
  16.        
  17.     def dfs(self, node):
  18.         self.visited.append(node)
  19.         for each in self.edges[node]:
  20.             if each not in self.visited:
  21.                 self.spanningTree[each] = node
  22.                 self.dfs(each)
  23.             else:
  24.                 cycle = self.getCycle(node, each)
  25.                 if len(cycle) > 2:
  26.                     self.cycles.append(cycle)
  27.                    
  28.     def getCycles(self):
  29.         for each in self.edges:
  30.             if each not in self.visited:
  31.                 self.spanningTree[each] = None
  32.                 self.dfs(each)
  33.                
  34. g = Graph()
  35. g.edges = {1:[2,4], 2:[1,3,5], 3:[2,4,6], 4:[1,3,7], 5:[2,6], 6:[3,5,7], 7:[4,6]}
  36.  
  37. g.getCycles()
  38.  
  39. print g.cycles
  40. #[[4, 3, 2, 1], [6, 7, 4, 3], [5, 6, 7, 4, 3, 2]]
RAW Paste Data