(graph='')
| 114 | return elem[0] |
| 115 | |
| 116 | def rareness_paths(graph=''): |
| 117 | # ------- |
| 118 | # Function definition: 'top_k_rareness_paths()' |
| 119 | # (1) find top k rareness paths in DAG |
| 120 | # ------- |
| 121 | # Required parameters: |
| 122 | # (1) 'graph': a directed aryclic graph DAG |
| 123 | # (2) 'k': the number of rareness paths |
| 124 | # ------- |
| 125 | # Return: top k rareness paths |
| 126 | # ------- |
| 127 | print("nodes size ", len(graph.nodes())) |
| 128 | all_paths = [] |
| 129 | |
| 130 | roots = [v for v, d in graph.in_degree() if d == 0] |
| 131 | print("root size is", len(roots)) |
| 132 | # for root in graph.nodes(): |
| 133 | for root in roots: |
| 134 | que = queue.Queue() |
| 135 | vis = set() |
| 136 | # vis.add(root) |
| 137 | que.put([root]) |
| 138 | while not que.empty(): |
| 139 | path = que.get() |
| 140 | nex_node = path[-1] |
| 141 | # print("~~~~~~~~~~~~~~~~~") |
| 142 | # print(path) |
| 143 | # print(nex_node) |
| 144 | if nex_node in vis: |
| 145 | # all_paths.append(path) |
| 146 | continue |
| 147 | vis.add(nex_node) |
| 148 | # print(nex_node in graph.nodes()) |
| 149 | # print(graph.neighbors(nex_node)) |
| 150 | if len(list(graph.neighbors(nex_node))) == 0: |
| 151 | if len(path) <5: |
| 152 | continue |
| 153 | all_paths.append(path) |
| 154 | # print(len(path)) |
| 155 | continue |
| 156 | for nex in graph.neighbors(nex_node): |
| 157 | # print(nex) |
| 158 | # print(nex in graph.nodes()) |
| 159 | nex_path = copy.deepcopy(path) |
| 160 | nex_path.append(nex) |
| 161 | # nex_path[0] *= graph[nex_node][nex]['weight'] |
| 162 | # print(nex_path[0]) |
| 163 | que.put(nex_path) |
| 164 | |
| 165 | # print("~~~~~~~~~~~~~~~~~") |
| 166 | all_paths.sort(key=len, reverse=True) |
| 167 | |
| 168 | # 由于新方法会导致groundTruth丢失，手动添加groundTruth |
| 169 | st_pos = 0 |
| 170 | lim = 50 |
| 171 | for i, path in enumerate(all_paths): |
| 172 | is_warn = False |
| 173 | for j in range(1, len(path)): |
no outgoing calls
no test coverage detected