Skip to main content
Warning: You are using the test version of PyPI. This is a pre-production deployment of Warehouse. Changes made here affect the production instance of TestPyPI (testpypi.python.org).
Help us improve Python packaging - Donate today!

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.
  • nodes : list - Nodes in a negative edge cycle (in order) if one exists; otherwise nodes in a shortest path.
  • 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)
Release History

Release History

This version
History Node

0.1

Supported By

WebFaction WebFaction Technical Writing Elastic Elastic Search Pingdom Pingdom Monitoring Dyn Dyn DNS Sentry Sentry Error Logging CloudAMQP CloudAMQP RabbitMQ Heroku Heroku PaaS Kabu Creative Kabu Creative UX & Design Fastly Fastly CDN DigiCert DigiCert EV Certificate Rackspace Rackspace Cloud Servers DreamHost DreamHost Log Hosting