Find all simple paths between `s_i` and `e_i` in the graph. Notes ----- Uses breadth-first search. Ignores all paths with repeated vertices. Parameters ---------- s_i: Int The interal index of the start vertex e_i: Int
(self, s_i, e_i)
| 130 | return False |
| 131 | |
| 132 | def all_paths(self, s_i, e_i): |
| 133 | """ |
| 134 | Find all simple paths between `s_i` and `e_i` in the graph. |
| 135 | |
| 136 | Notes |
| 137 | ----- |
| 138 | Uses breadth-first search. Ignores all paths with repeated vertices. |
| 139 | |
| 140 | Parameters |
| 141 | ---------- |
| 142 | s_i: Int |
| 143 | The interal index of the start vertex |
| 144 | e_i: Int |
| 145 | The internal index of the end vertex |
| 146 | |
| 147 | Returns |
| 148 | ------- |
| 149 | complete_paths : list of lists |
| 150 | A list of all paths from `s_i` to `e_i`. Each path is represented |
| 151 | as a list of interal vertex indices. |
| 152 | """ |
| 153 | complete_paths = [] |
| 154 | queue = [(s_i, [s_i])] |
| 155 | |
| 156 | while len(queue): |
| 157 | c_i, path = queue.pop(0) |
| 158 | nbrs_not_on_path = set(self.get_neighbors(c_i)) - set(path) |
| 159 | |
| 160 | for n_i in nbrs_not_on_path: |
| 161 | if n_i == e_i: |
| 162 | complete_paths.append(path + [n_i]) |
| 163 | else: |
| 164 | queue.append((n_i, path + [n_i])) |
| 165 | |
| 166 | return complete_paths |
| 167 | |
| 168 | @abstractmethod |
| 169 | def _build_adjacency_list(self): |