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

## Release history Release notifications

## 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 | May 7, 2018 |