Warning
This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.
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