Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Graph:
- cycles=[]
- visited = []
- spanningTree = {}
- edges = {}
- def getCycle(self, node, ancestor):
- path = []
- while (node != ancestor):
- if node is None:
- return []
- path.append(node)
- node = self.spanningTree[node]
- path.append(node)
- return path
- def dfs(self, node):
- self.visited.append(node)
- for each in self.edges[node]:
- if each not in self.visited:
- self.spanningTree[each] = node
- self.dfs(each)
- else:
- cycle = self.getCycle(node, each)
- if len(cycle) > 2:
- self.cycles.append(cycle)
- def getCycles(self):
- for each in self.edges:
- if each not in self.visited:
- self.spanningTree[each] = None
- self.dfs(each)
- g = Graph()
- 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]}
- g.getCycles()
- print g.cycles
- #[[4, 3, 2, 1], [6, 7, 4, 3], [5, 6, 7, 4, 3, 2]]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement