bellmanford 0.2.1

Parameters

• G : NetworkX graph

• pred : dict - Keyed by node to predecessor in the path

• dist : dict - Keyed by node to the distance from the source

• source: node label - Source node

• target: node label - Target node

• weight : string - Edge data key corresponding to the edge weight

Returns

• length : numeric - Length of a negative cycle if one exists. Otherwise, length of a shortest path. Length is inf if source and target are not connected.

• nodes : list - Nodes in a negative edge cycle (in order) if one exists. Otherwise nodes in a shortest path. List is empty if source and target are not connected.

• negative_cycle : bool - True if a negative edge cycle exists, otherwise False.

Examples

>>> import networkx as nx
>>> G = nx.path_graph(5, create_using = nx.DiGraph())
>>> bf.bellman_ford(G, source=0, target=4)
(3, [1, 2, 3, 4], False)

Parameters

• G : NetworkX graph

• weight : string, optional (default = 'weight') - Edge data key corresponding to the edge weight

Returns

• length : numeric - Length of a negative edge cycle if one exists, otherwise None.

• nodes : list - Nodes in a negative edge cycle (in order) if one exists, otherwise None.

• negative_cycle : bool - True if a negative edge cycle exists, otherwise False.

Examples

>>> import networkx as nx
>>> import bellmanford as bf
>>> G = nx.cycle_graph(5, create_using = nx.DiGraph())
>>> print(bf.negative_edge_cycle(G))
(None, [], False)
>>> G[1][2]['weight'] = -7
>>> print(bf.negative_edge_cycle(G))
(-3, [4, 0, 1, 2, 3, 4], True)