negative_edge_cycle¶

negative_edge_cycle(G, weight='weight')[source]¶

Return True if there exists a negative edge cycle anywhere in G.

Parameters:

G : NetworkX graph

weight: string, optional (default=’weight’)

Edge data key corresponding to the edge weight

Returns:

negative_cycle : bool

True if a negative edge cycle exists, otherwise False.

Notes

Edge weight attributes must be numerical. Distances are calculated as sums of weighted edges traversed.

This algorithm uses bellman_ford() but finds negative cycles on any component by first adding a new node connected to every node, and starting bellman_ford on that node. It then removes that extra node.

Examples

>>> import networkx as nx
>>> 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