Re: [networkx-discuss] Lowest common ancestor?

[Aric Hagberg]

On Tue, Apr 30, 2013 at 7:12 AM, Pau Ruŀlan Ferragut
<paur...@gmail.com> wrote:
> hi there!
>
> I need to get the lowest common ancestor of two nodes
> http://en.wikipedia.org/wiki/Lowest_common_ancestor
> and find very strange that there is not implementation in networkx.
>
> I am missing something or I should make my own?

You are right, we are missing that. If you want to contribute some
code we would be glad to include it.
Best Wishes,
Aric

[Pau Ruŀlan Ferragut]

On Sun, May 05, 2013 at 12:08:24PM -0700, Alex Roper wrote:

>https://github.com/calmofthestorm/networkx/blob/master/networkx/algorithms/lowest_common_ancestor.py

Wow, thanks; I will study it and see how we can get it done.

>I still need to update the documentation and write tests, so any
>feedback you have is appreciated, especially on the api.

Couple of comments:

1. the indentation with two-spaces will bring you pain, better stick
to 4-spaces and PEP8

2. pass a pylint and you will see a couple of potential errors and
problems (such as non-initialized variables)

3. This �depths� is really root_distance, is not it?

depths = nx.shortest_path_length(G, source=root)
feasible = ancestors1.intersection(ancestors2)
if feasible:
return max(feasible, key=depths.get)

4. I would probably add a:
def lca(G, node1, node2, root=None):
if not root:
roots = [n for n in G.nodes() if G.predecessors(n) == 0]

[Alex Roper]

On Sunday, May 5, 2013 5:24:34 PM UTC-4, Pau Ruŀlan Ferragut wrote:

On Sun, May 05, 2013 at 12:08:24PM -0700, Alex Roper wrote:

 

1. the indentation with two-spaces will bring you pain, better stick
   to 4-spaces and PEP8

The final version will have 4 spaces to match the rest of networkx.

 

2. pass a pylint and you will see a couple of potential errors and
   problems (such as non-initialized variables)

Definitely on the todo list; I'm still in the writing-tests-and-fixing bugs stage.

3. This �depths� is really root_distance, is not it?

The paper I based my implementation on refers to it as depths, but you are correct. I agree root_distance is more intuitive. One thing I worry about is "why am I getting no LCA when there is one?" when the user specifies the wrong root. The original paper preprocesses the graph by adding a single root node with out edges to all sources.

 

4. I would probably add a:
   def lca(G, node1, node2, root=None):
       if not root:
          roots = [n for n in G.nodes() if G.predecessors(n) == 0] 

Ah I see. So this would interpret all roots as of equal depth 0? I believe this is possible, however I would need to implement this by adding a virtual root as discussed in the original paper. This means either modifying the user's graph (not an option) or copying it. I suppose we could make a copy iff there are multiple roots and none is specified. 

My original thinking was to scrap the roots param entirely and either use the singular source as roots, or copy the graph + add virtual root if the user specifies a graph with multiple sources. I need to do more thinking and testing anyway to ensure the root parameter works correctly; the original paper mentions nothing of it but I think it should work.

One other question: The current version needs O(n^2) space for the precomputation. There's no getting around this if you want all pairs LCA for the obvious reason, but it's possible that a user might want the LCA of a small number of pairs -- big enough to justify some precomputation, but small enough relative to the size of the graph that O(n^2) space is not an option -- essentially a DAG analog to how Tarjan's tree algorithm works. I'd have to think about it more to figure out how to implement it and whether it's even possible, so consider it a future idea rather than one for the current version; I don't know how much time I'll have for this after today, and I want to get this cleaned up and submit a pull request.

[Alex Roper]

I'm basically done. Mind giving it another look? If everything looks good I'll submit a pull request.