networkx/networkx — pull request #1194 by chebee7i (2014-06-11 18:24:12+00:00)
Title: Add method to find a single cycle.

This PR depends on #1193. It adds the ability to find a single cycle, if one exists, on a graph of any type. As for existing functionality: `simple_cycles` does not work for undirected graphs, but is also not suitable for multidigraphs because it does not provide key data. Similarly, `cycle_basis` is only meant for simple undirected graphs. This new function `find_cycle` works for any graph and returns a single cycle found via a depth-first traversal of the edges. It inherits the ability to ignore edge orientations as well, greatly extending the functionality for directed graphs.

One example where this function can be useful is when calculating the intersection of weighted matroids. In that situation, one must add edges in a directed graph until an undirected cycle is formed. Then you must find that cycle, and remove an offending edge.

An example usage:

>>> G = nx.DiGraph([(0,1), (0,2), (1,2)])
>>> list(find_cycle(G, orientation='respect'))
[]
>>> list(find_cycle(G, orientation='ignore'))
[(0, 1, 1), (1, 2, 1), (0, 2, 0)]

`G` is a DAG and so, it has no directed cycles. So `find_cycle` returns an empty cycle. If we allow `find_cycle` to ignore edge orientations, then it finds an undirected cycle in the directed graph. Thus, `G` is not a directed tree.