A DAG representation of caffe2 graph, each vertice is a versioned blob.
| 780 | |
| 781 | |
| 782 | class DiGraph: |
| 783 | """ A DAG representation of caffe2 graph, each vertice is a versioned blob. """ |
| 784 | |
| 785 | def __init__(self): |
| 786 | self.vertices = set() |
| 787 | self.graph = collections.defaultdict(list) |
| 788 | |
| 789 | def add_edge(self, u, v): |
| 790 | self.graph[u].append(v) |
| 791 | self.vertices.add(u) |
| 792 | self.vertices.add(v) |
| 793 | |
| 794 | # grab from https://www.geeksforgeeks.org/find-paths-given-source-destination/ |
| 795 | def get_all_paths(self, s, d): |
| 796 | visited = {k: False for k in self.vertices} |
| 797 | path = [] |
| 798 | all_paths = [] |
| 799 | |
| 800 | def _get_all_paths_util(graph, u, d, visited, path): |
| 801 | visited[u] = True |
| 802 | path.append(u) |
| 803 | if u == d: |
| 804 | all_paths.append(copy.deepcopy(path)) |
| 805 | else: |
| 806 | for i in graph[u]: |
| 807 | if not visited[i]: |
| 808 | _get_all_paths_util(graph, i, d, visited, path) |
| 809 | path.pop() |
| 810 | visited[u] = False |
| 811 | |
| 812 | _get_all_paths_util(self.graph, s, d, visited, path) |
| 813 | return all_paths |
| 814 | |
| 815 | @staticmethod |
| 816 | def from_ssa(ssa): |
| 817 | graph = DiGraph() |
| 818 | for op_id in range(len(ssa)): |
| 819 | for inp in ssa[op_id][0]: |
| 820 | for outp in ssa[op_id][1]: |
| 821 | graph.add_edge(inp, outp) |
| 822 | return graph |
| 823 | |
| 824 | |
| 825 | def _get_dependency_chain(ssa, versioned_target, versioned_source): |