networkx/networkx — pull request #1193 by chebee7i (2014-06-11 17:47:09+00:00)
Title: Add DFS over edges.

As mentioned in #1120, many of the algorithms for traversals are not sufficiently general for multigraphs. In this PR, I've implemented a variant of a depth-first-search that traverses edges rather than nodes. Unlike the standard DFS, as implemented in `nx.dfs_edges`, this version does not stop once all nodes have been visited. Instead, it continues searching until all edges have been visited. This turns out to be especially important for multigraphs, since knowing the head and tail of an edge is not enough to uniquely identify an edge. So this properly outputs the keys of edges when appropriate. Note, that tweaking the existing implementation so that it return edges keys is not a sufficient fix, since it does not visit each edge.

# Existing
>>> G = nx.MultiDiGraph([(0,1), (1,0), (1,0)])
>>> list(nx.dfs_edges(G))
[(0, 1)]

# Feature from this PR
>>> G = nx.MultiDiGraph([(0,1), (1,0), (1,0)])
>>> list(nx.edge_dfs(G))
[(0, 1, 0), (1, 0, 0), (1, 0, 1)]

Also, when dealing with directed graphs, one is often interested in traversals that do not respect edge orientation. So we also add the ability to 'ignore' or 'respect' the edge orientations during the traversal. An extra element is added to each yielded each which is 1 if the edge was traversed in a way that respects its orientation and 0 if not.

# Ignoring edge orientation
>>> G = nx.MultiDiGraph([(0,1), (1,0), (1,0)])
>>> list(nx.edge_dfs(G, orientation='ignore'))
[(0, 1, 0, 1), (1, 0, 0, 1), (1, 0, 1, 0)]

So here we went from 0 to 1, then from 1 to 0 while obeying the edge orientation. Finally, we go from 0 back to 1 again, but this time ignoring the orientation of the edge (u,v,key) = (1,0,1).

The interface to all of this could be cleaned up quite a bit if NetworkX had a formal edge object and if all edges had a unique indentifier. Alas, we are not in that situation, and so I think this strikes a reasonable balance, but I'm certainly open to suggestions. Also the name is confusingly similar to `dfs_edges`. Anyone have a better idea?