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

Question

我有一个包含节点 V = [1,2,3,4,5,6]:

的图的边列表 (E)

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

其中每个元组(a,b)分别指代边的起始节点和结束节点。

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

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

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

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

如何在 python 中有效地编码？

Answer 1

您正在您的（子）图中寻找 directed Eulerian circuit。欧拉回路是一条恰好访问每条边一次的轨迹。

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)])

documentation cites a 1973 paper, if you're interested in understanding how the algorithm works. You can also take a look at the source code here。请注意，我们在这里使用多重图，因为您可以有多个具有相同源节点和目标节点的边。 Internet 上可能还有其他实现，但它们可能适用于也可能不适用于多图。

Answer 2

The networkx package has a function that can generate the desired circuit for you in linear time...

有可能 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

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

Finding a closed path from list of start and end nodes

python

tree

graph

anytree