从开始节点和结束节点列表中查找闭合路径

Question

我有一个节点为V = [1,2,3,4,5,6]:的图的边(E(列表

E = [(1,2), (1,5), (2,3), (3,1), (5,6), (6,1)]

其中每个元组CCD_ 3是指起始&分别为边的末端节点。

如果我知道图G中的边形成闭合路径，我能恢复路径吗？

注意，E不是图的所有边的集合。这只是一组边。

在本例中，路径为1->2->3->1->5->6->1

我可以想到的一种天真的方法是使用一个树，我从一个节点开始，比如1，然后我查看所有以1开始的元组，这里是(1,2)和(1,5)。然后我有两个分支，节点为2&5，我继续这个过程，直到我在分支的起始节点结束。

如何在python中高效地进行编码？

Answer 1

networkx包具有一个函数，可以在线性时间内为您生成所需的电路。。。

可能nx.MultiDiGraph()的构建速度较慢，效率也不高，或者只为一个功能使用外部包的情况相当严重。如果是这样，还有另一种方法。

计划：首先，我们将找到从start_node到start_node的某种方式，然后我们将插入所有尚未访问的循环。

from itertools import chain
from collections import defaultdict, deque
from typing import Tuple, List, Iterable, Iterator, DefaultDict, Deque

def retrieve_closed_path(arcs: List[Tuple[int, int]], start_node: int = 1) -> Iterator[int]:
if not arcs:
return iter([])
# for each node `u` carries queue of its
# neighbours to be visited from node `u`
d: DefaultDict[int, Deque[int]] = defaultdict(deque)
for u, v in arcs:
# deque pop and append complexity is O(1)
d[u].append(v)
def _dfs(node) -> Iterator[int]:
out: Iterator[int] = iter([])
# guarantee, that all queues
# will be emptied at the end
while d[node]:
# chain returns an iterator and helps to
# avoid unnecessary memory reallocations
out = chain([node], _dfs(d[node].pop()), out)
# if we return in this loop from recursive call, then
# `out` already carries some (node, ...) and we need
# only to insert all other loops which start at `node`
return out
return chain(_dfs(start_node), [start_node])

def path_to_string(path: Iterable[int]) -> str:
return '->'.join(str(x) for x in path)

示例：

E = [(1, 2), (2, 1)]
p = retrieve_closed_path(E, 1)
print(path_to_string(p))
>> 1->2->1
E = [(1, 2), (1, 5), (2, 3), (3, 1), (5, 6), (6, 1)]
p = retrieve_closed_path(E, 1)
print(path_to_string(p))
>> 1->5->6->1->2->3->1
E = [(1, 2), (2, 3), (3, 4), (4, 2), (2, 1)]
p = retrieve_closed_path(E, 1)
print(path_to_string(p))
>> 1->2->3->4->2->1

E = [(5, 1), (1, 5), (5, 2), (2, 5), (5, 1), (1, 4), (4, 5)]
p = retrieve_closed_path(E, 1)
print(path_to_string())
>> 1->4->5->1->5->2->5->1

Answer 2

您正在(子(图中寻找有向欧拉回路。欧拉回路是一条轨迹，它只访问每一个边缘一次。

networkx封装有一个功能，可以在线性时间内为您生成所需的电路：

import networkx as nx
edges = [(1,2), (1,5), (2,3), (3,1), (5,6), (6,1)]
G = nx.MultiDiGraph()
G.add_edges_from(edges)
# Prints [(1, 5), (5, 6), (6, 1), (1, 2), (2, 3), (3, 1)]
# which matches the desired output (as asked in the comments).
print([edge for edge in nx.algorithms.euler.eulerian_circuit(G)])

如果你有兴趣了解算法的工作原理，文档引用了1973年的一篇论文。您也可以在这里查看源代码。请注意，我们在这里使用的是多重图，因为可以有多条具有相同源节点和目标节点的边。互联网上可能还有其他实现，但它们可能对多重图有效，也可能不适用。