| 57 | |
| 58 | |
| 59 | class TreeFinder(object): |
| 60 | def __init__(self): |
| 61 | self.has_duplicate_edges = False |
| 62 | self.inv_g = DirectedGraph() |
| 63 | self.roots = set() |
| 64 | |
| 65 | def add_edges(self, edges): |
| 66 | if len(edges) != len(set(edges)): |
| 67 | self.has_duplicate_edges = True |
| 68 | |
| 69 | for u,v in edges: |
| 70 | self.inv_g.add_edge(v,u) # here, the most tricky part!! |
| 71 | |
| 72 | def find_roots(self, v, visited): |
| 73 | ''' @return: False, if failed to find the root, |
| 74 | starting with vertex 'v' and past path 'visited' |
| 75 | True, otherwise. |
| 76 | ''' |
| 77 | adjs = self.inv_g.adjacents(v) |
| 78 | if not adjs: |
| 79 | self.roots.add(v) |
| 80 | return True |
| 81 | if len(adjs)>1: |
| 82 | return False # With bifurcation |
| 83 | else: |
| 84 | u = adjs[0] |
| 85 | visited[v] = True |
| 86 | if not visited.get(u, False): |
| 87 | return self.find_roots(u, visited) |
| 88 | else: |
| 89 | return False # With cycle |
| 90 | return True |
| 91 | |
| 92 | def isTree(self): |
| 93 | if not self.inv_g.vertices: |
| 94 | return True |
| 95 | if self.has_duplicate_edges: |
| 96 | return False |
| 97 | |
| 98 | isATree = True |
| 99 | for v in self.inv_g.vertices: |
| 100 | if not self.find_roots(v, {}): |
| 101 | isATree = False |
| 102 | if not isATree: |
| 103 | return False |
| 104 | |
| 105 | if len(self.roots) != 1: |
| 106 | return False |
| 107 | |
| 108 | return True |
| 109 | |
| 110 | class Reader(object): |
| 111 | def __init__(self, fd): |