使用 Python 查找元组数组中循环的长度

Question

我有一个元组数组；说，

[(1,2), (2,1), (3,4), (4,5), (5,3)]

上面有两个循环；其中一个长度为 2，一个长度为 3。Python 中是否有内置函数（或包）允许我 return 所有周期长度的列表？对于上面的例子，应该是 return [2, 3].

Answer 1

可以使用第三方库networkx:

import networkx as nx

edges = [(1, 2), (2, 1), (3, 4), (4, 5), (5, 3)]
G = nx.DiGraph(edges)

[len(cycle) for cycle in list(nx.simple_cycles(G))] # [3, 2]

Answer 2

演示了 NetworkX，这也是我在这里的选择。但那是一个第 3 方项目，既然你特别要求：

Is there a built-in function (or package) ...

实际上有一个标准库可以提供帮助：graphlib（Python 3.9 中的新增功能）。

里面还没有太多内容。它没有从图中提取循环长度的功能，但有一个 TopologicalSorter class 可以在 非循环 图中产生节点的拓扑排序。当拓扑排序器在输入中检测到循环时引发 CycleError 异常：

class CycleError(ValueError):
    """Subclass of ValueError raised by TopologicalSorter.prepare if cycles
    exist in the working graph.

    If multiple cycles exist, only one undefined choice among them will be reported
    and included in the exception. The detected cycle can be accessed via the second
    element in the *args* attribute of the exception instance and consists in a list
    of nodes, such that each node is, in the graph, an immediate predecessor of the
    next node in the list. In the reported list, the first and the last node will be
    the same, to make it clear that it is cyclic.
    """

需要特别注意的是，错误实际上揭示了循环，因此无需太多额外工作，您就可以通过拓扑排序器从图中提取循环长度。创建图形排序器：

import graphlib

edges = [(1,2), (2,1), (3,4), (4,5), (5,3)]
ts = graphlib.TopologicalSorter()
for edge in edges:
    ts.add(*edge)

然后编写辅助函数从失败的 prepare() 调用中提取一个循环：

def get_cycle(ts):
    try:
        ts.prepare()
    except graphlib.CycleError as err:
        msg, cycle = err.args
        return list(zip(cycle[1:], cycle))

示例：

>>> cycle = get_cycle(ts)
>>> print(cycle)
[(2, 1), (1, 2)]
>>> print(len(cycle))
2

注意这只是returns遇到的第一个循环。要找到另一个循环，请从图中删除检测到的循环的边缘（打破该循环）并重复此过程，直到找到所有循环。

>>> edges.remove(cycle[0])
>>> ts = ...
>>> get_cycle(ts)
[(5, 3), (4, 5), (3, 4)]

NetworkX 可能更简单，所以如果可以就使用它吧！

使用 Python 查找元组数组中循环的长度

Using Python to find the length of a cycle in array of tuples

python

tuples

cycle