from itertools import product
def extend_expanded_path(ori, new):
if isinstance(new, list):
if len(new) == 0:
return ori
else:
return [i + j for i, j in product(ori, new)]
else:
return [i + [new] for i in ori]
def print_node_list(node_list):
p_str = ''
for node in node_list:
if isinstance(node, Graph):
p_str += node.name + ','
else:
p_str += node + ','
return p_str
def find_all_paths(graph, start, end, path=None, path_expanded=None, sub_graph_flag=False):
# path_expanded list(list)
# print('当前图名： %s。位于节点：%s。后续节点：[%s]。' % (graph.name, start, print_node_list(graph[start]) if start in graph else None))
if path is None:
path = []
if path_expanded is None:
path_expanded = [[]]
if not isinstance(start, Graph):
if sub_graph_flag:
if start not in ('Start', 'End'):
path = path + [start]
path_expanded = [i + [start] for i in path_expanded]
else:
path = path + [start]
path_expanded = [i + [start] for i in path_expanded]
if start == end:
return [path], path_expanded
if start not in graph:
return [], []
paths = []
paths_expanded = []
for node in graph[start]:
if node not in path:
if isinstance(node, Graph):
sub_path, sub_expanded_path = find_all_paths(node, "Start", "End", None, None, True)
path = path + [sub_path]
path_expanded = extend_expanded_path(path_expanded, sub_expanded_path)
new_paths, new_paths_expanded = find_all_paths(graph, node, end, path, path_expanded, sub_graph_flag)
for new_path in new_paths:
paths.append(new_path)
for new_path_expanded in new_paths_expanded:
paths_expanded.append(new_path_expanded)
return paths, paths_expanded
print(find_all_paths(g3, "Start", "End")[0])
print(find_all_paths(g3, "Start", "End")[1])
print(find_all_paths(g1, "Start", "End")[1])