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.

Source Distribution

bellmanford-0.2.1.tar.gz (5.2 kB view hashes)

Uploaded Source

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page