从元组列表生成所有可能的路径

Question

给定一个元组列表，我需要从该列表中查找所有唯一路径：

输入：[('a','b'),('b','c'),('c','d'),('g','i'),('d','e'),('e','f'),('f','g'),('c','g')]
输出：[['a','b','c','d','e','f','g'],['a','b','c','g','i']] （2个可能的唯一路径）

如果元组的第二个元素与另一个元组的第一个元素匹配，则两个元组可以连接，即：一个元组是(_,a)，另一个元组像(a,_)。你知道吗

这里已经提出了这个问题：Getting Unique Paths from list of tuple但是解决方案是用haskell实现的（我对这种语言一无所知）。你知道吗

但是你知道在Python中有没有一种有效的方法来实现这一点吗？
我知道库itertools有许多高效的内置函数来处理类似的内容，但我对此不太熟悉。你知道吗

Answer 1

您可以构建一个dict，将每个父节点映射到一个已连接子节点的列表，这样您就可以以平均时间复杂度O（n）递归地生成来自每个父节点的路径：

def get_paths(parent, mapping):
    if parent not in mapping:
        yield [parent]
        return
    for child in mapping[parent]:
        for path in get_paths(child, mapping):
            yield [parent, *path]

edges = [('a','b'),('b','c'),('c','d'),('g','i'),('d','e'),('e','f'),('f','g'),('c','g')]
parents = set()
children = set()
mapping = {}
for a, b in edges:
    mapping.setdefault(a, []).append(b)
    parents.add(a)
    children.add(b)
print([path for parent in parents - children for path in get_paths(parent, mapping)])

这将输出：

[['a', 'b', 'c', 'd', 'e', 'f', 'g', 'i'], ['a', 'b', 'c', 'g', 'i']]

Answer 2

您希望找到图形中的所有simple paths。你知道吗

Python有一个惊人的图形处理库：networkx。你可以用几行代码来解决你的问题：

import networkx as nx

a = [('a','b'),('b','c'),('c','d'),('g','i'),('d','e'),('e','f'),('f','g'),('c','g')]

# Create graph
G = nx.Graph()
# Fill graph with data
G.add_edges_from(a)

# Get all simple paths from node 'a' to node 'i'
list(nx.all_simple_paths(G, 'a', 'i'))

将返回给您：

[['a', 'b', 'c', 'g', 'i'], ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'i']]

---

如果需要所有可能的路径，只需将最后一行替换为：

for start in G.nodes:
    for end in G.nodes:
        if start != end:
            print(list(nx.all_simple_paths(G, start, end)))

Answer 3

可以对生成器使用递归：

d = [('a','b'),('b','c'),('c','d'),('g','i'),('d','e'),('e','f'),('f','g'),('c','g')]
def get_paths(start, c = []):
   r = [b for a, b in d if a == start]
   if r:
     for i in r:
        yield from get_paths(i, c+[i])
   else:
     yield c

print(list(get_paths('a', ['a'])))

输出：

[['a', 'b', 'c', 'd', 'e', 'f', 'g', 'i'], ['a', 'b', 'c', 'g', 'i']]