Skip to main content

Small extensions of the Bellman-Ford routines in NetworkX, primarily for convenience (https://networkx.github.io).

Project description

This package provides a few small extensions of the Bellman-Ford routines in NetworkX, primarily for convenience.

Installation

bellmanford is available on PyPI:

pip install bellmanford

Usage

bellman_ford

length, nodes, negative_cycle = bellman_ford(G, source, target, weight='weight')

Compute shortest path and shortest path lengths between a source node and target node in weighted graphs using the Bellman-Ford algorithm.

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)

negative_edge_cycle

length, nodes, negative_cycle = negative_edge_cycle(G, weight='weight')

If there is a negative edge cycle anywhere in G, returns True. Also returns the total weight of the cycle and the nodes in the cycle.

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)

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Filename, size & hash SHA256 hash help File type Python version Upload date
bellmanford-0.2.1.tar.gz (5.2 kB) Copy SHA256 hash SHA256 Source None

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page