SHARE
TWEET

python graph class

a guest Apr 23rd, 2013 135 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top