﻿

python graph class

a guest
Apr 23rd, 2013
180
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