时间戳

首页 > 解决方案 > 使用 Python 在元组数组中查找循环的长度

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

问题描述

我有一个元组数组；说，

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

上面有两个循环；长度为 2 和长度为 3 之一。Python 中是否有内置函数（或包）允许我返回所有循环长度的列表？对于上面的示例，它应该返回 [2, 3]。

标签： pythontuplescycle

解决方案

另一个答案展示了 NetworkX，这也是我在这里的选择。但这是一个第 3 方项目，因为您特别问：

是否有内置函数（或包）...

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

里面还没有多少。它没有从图中提取循环长度的功能，但是有一个TopologicalSorter类可以在非循环图中产生节点的拓扑排序。当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

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

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

NetworkX 可能更容易，所以如果可以的话就使用它！

推荐阅读