networkx/networkx — pull request #886 by etrain (2013-06-08 06:00:47+00:00)
Title: Added option to return negative cycles from Bellman-Ford algorithm.

This patch adds an option to return the results of the Bellman-Ford algorithm when negative weight cycles are detected.

One of the advantages of the Bellman-Ford algorithm is its ability to detect negative-weight cycles in a directed graph. http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

Currently Networkx raises an exception when a negative weight cycle is detected. However, in some problems (the one I'm looking at has to do with foreign currency arbitrage) it is useful to identify the negative weight cycles and the paths that cause them. Currently, there are no facilities in Networkx to do this.

This change should not impact user code at all, because it adds a default keyword argument to an existing function. The function will return the same output as before in the default case, and similar output to before in the case where the option is turned on. New tests added and all tests pass.