python - 从发电机外部控制发电机(networkx simple_cycles)

Question

我使用 NetworkX 的 simple_cycles 来生成所有循环，并且如果找到大小为 k 的循环(k 由用户提供)，则在中断的条件下进行迭代。

try:
    for cycle in nx.simple_cycles(G):
        if len(cycle) == k:
            checkval = True
            break
    if not checkval:
        print "no path of size k"
except nx.NetworkXNoPath:
    print "There was no path of size k"
    checkval = False

根据图表的不同，simple_cycles 可能基本上需要永远尝试找到大小为 k 的循环。我想在一段时间后停止检查。我不能根据发现的周期数量停止，因为那是不可靠的。有时一分钟就能找到1个周期，30秒就能找到100000个周期。

我的问题是是否有一种方法可以根据经过的一定时间量从生成器外部停止生成器..或者唯一的方法是修改生成器本身的代码。

(对于我正在尝试做的任何一般性建议，我们将不胜感激。)

Answer 1

问题在于存在病态的极端情况......例如，一个巨大的零周期图，以至于在 nx.simple_cycles(G) 的第一次迭代之前都需要太多时间。即可完成。

因此，除非您将执行放入另一个可以终止的上下文中，否则无法从生成器外部执行此操作，例如单独的 Process来自multiprocessing ，或running the coroutine with asyncio .

然后，对于异步获取的每个周期(从进程或线程)，您可以检查长度条件和总运行时间量的条件，并选择终止另一个进程/线程如果超过时间限制。

另一方面，如果您不关心这种类型的极端情况，并且您有理由确定 nx.simple_cycles(G) 生成的值将在合理的时间内返回，然后您可以包装该生成器来制作您自己的限时生成器:

import time


def time_limited_cycles(G, time_limit=100.0):
    elapsed, cycle_generator = 0.0, nx.simple_cycles(G)
    while elapsed <= time_limit:
        start_time = time.time()
        try:
            # crucial assumption here, that calling next on
            # the original generator never takes too long.
            cycle = next(cycle_generator)
        except StopIteration:
            break
        yield cycle
        elapsed += time.time() - start_time 
        # move elapsed above the yield line if you are looking
        # to limit the internal runtime of the generator, rather
        # than overall time spent processing cycles.

通过上面的内容，你可以替换你原来使用的nx.simple_cycles调用time_limited_cycles相反(按照您想要的时间限制)，其余代码将同样工作，因为 time_limited_cycles产生与 nx.simple_cycles 相同的循环结果会屈服，直到停止。