networkx/networkx — pull request #869 by calmofthestorm (2013-05-10 17:10:05+00:00)
Title: Added lowest common ancestor algorithm for trees and DAGs.

This adds LCA for trees and DAGs, using Tarjan's offline lowest common ancestors algorithm and the DAG algorithm described in Bender et al (2005).

In addition to the included unit tests, this was tested against a naive algorithm on a bunch of random graphs, and run (not compared to a naive) in on a ~40,000 node subgraph of the Wikipedia category graph to check for crashes and sanity of output (this was done as 40,000 different compute tasks on PiCloud; I need the data anyway.)

Two points of interest for the code review:
1) I have attempted to follow the style of many NetworkX algorithms of minimizing names (even _ ones) in the namespace. As such, this file is two long functions. If appropriate, I could split them into smaller, focused private helpers to make the code more clear.
2) Please take a look at lines 64 and 165; this is my attempt to balance generality and efficiency (especially since the DAG algorithm makes use of the tree algorithm). I know it violates the spirit of duck typing, but I would like to avoid an unnecessary double copy of large data structures.