negative_edge_cycle

negative_edge_cycle(G, weight='weight', heuristic=True)

如果图 G 中存在负权边环，则返回 True。

参数：

GNetworkX 图

weight字符串或函数

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

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

heuristic布尔值

确定是否使用启发法以可忽略的成本提前检测负权环。对于存在负权环的图，检测性能至少提高一个数量级。

返回值：

negative_cycle布尔值

如果存在负权边环，则为 True，否则为 False。

说明

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

该算法使用 bellman_ford_predecessor_and_distance()，但通过首先添加一个连接到所有节点的新节点，并从该节点开始 bellman_ford_predecessor_and_distance 算法，来查找任何连通分量中的负权环。然后移除该额外节点。

示例

>>> 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
----

其他后端实现了此函数

graphblas : 启用 OpenMP 的稀疏线性代数后端。