negative_edge_cycle#

negative_edge_cycle(G, weight='weight', heuristic=True)[source]#

如果图 ( G ) 中存在任何负边循环，则返回 True。

Parameters:
GNetworkX 图
weight字符串或函数

如果这是一个字符串，则将通过具有此键的边属性访问边权重（即，连接 u 到 v 的边的权重将是 G.edges[u, v][weight] ）。如果没有这样的边属性存在，则假定边的权重为 1。

如果这是一个函数，则边的权重是该函数返回的值。该函数必须接受恰好三个位置参数：一条边的两个端点和该边的边属性字典。该函数必须返回一个数字。

heuristic布尔值

确定是否使用启发式方法以忽略不计的成本提前检测负循环。在存在负循环的图中，检测性能至少提高一个数量级。

Returns:
negative_cycle布尔值

如果存在负边循环，则返回 True，否则返回 False。

Notes

边权重属性必须是数值。 距离计算为遍历的加权边之和。

此算法使用 bellman_ford_predecessor_and_distance()，但通过首先添加一个连接到所有节点的新节点，并在该节点上启动 bellman_ford_predecessor_and_distance 来在任何组件上找到负循环。然后移除该额外节点。

Examples

>>> G = nx.cycle_graph(5, create_using=nx.DiGraph())
>>> print(nx.negative_edge_cycle(G))
False
>>> G[1][2]["weight"] = -7
>>> print(nx.negative_edge_cycle(G))
True

Additional backends implement this function

graphblas : OpenMP-enabled sparse linear algebra backend.

On this page