我有一个定向网络,它可能有周期,也可能没有周期。我要找到他们,去掉自行车。如果我有一个networkx有向图(G),我可以找到所有的循环
cycle_nodes = nx.simple_cycles(G)
从而产生一个循环发电机。你知道吗
但是,我不想返回所有循环,因为许多循环都是彼此的子集,修复一个循环将修复另一个循环。相反,我只想找到循环的第一个实例。因为cycle_nodes
是一个生成器,所以我试着
next(cycle_nodes)
只返回第一个实例。但是,我发现返回第一个实例所需的时间与返回所有实例所需的时间相比并没有小多少:
list(cycle_nodes) : 58s
next(cycle_nodes) : 44s
这仅仅是因为我的图的性质(即第一个循环沿搜索顺序很远),还是有更有效的方法返回任何循环(不一定是第一个循环)?你知道吗
我之所以怀疑有更快的方法,是因为当我运行nx.is_directed_acyclic_graph(G)
时,它只需要一两秒钟并返回False,所以很明显,它在一秒钟左右的时间内至少找到了一个周期。你知道吗
答案很明显。算法nx.find\u循环()如果没有提供起始节点,将返回它找到的第一个循环,并且速度很快。我的印象是需要提供一个起始节点,RTFM!你知道吗
相关问题 更多 >
编程相关推荐