networkx multiple LCA in DAG

user_12394459 0
Viewed 217

I am trying to use the networkx package in python to find the lowest common ancestor for 2 nodes in a graph. When I use the built in method for this it only retrieves one LCA when there are multiple. Any ideas of how to retrieve all LCAs?

Example: 

G = nx.DiGraph()
G.add_node(1)
G.add_node(2)
G.add_node(3)
G.add_node(4)
G.add_edge(1,3)
G.add_edge(1,2)
nx.all_pairs_lowest_common_ancestor(G, 2,3) # returns 1
G.add_edge(4,3)
G.add_edge(4,2)
nx.all_pairs_lowest_common_ancestor(G, 2,3) # returns 4 # desired return should be 1 and 4
networkx graph python
1 Answers

What is probably confusing you is that nx.all_pairs_lowest_common_ancestor returns a single lowest common ancestor (only one, even if there are several on the same level). What is meant by all_pairs... is that it finds the common ancestor for all pairs of specified nodes. That means that, considering for instance the following graph, we could do:

enter image description here

list(nx.all_pairs_lowest_common_ancestor(G, [('pine','eucaliptus'), ('pine','daisy')]))
# [(('pine', 'daisy'), 'plant'), (('pine', 'eucaliptus'), 'tree')]

And get the lowest common ancestor for all the specified pairs. But in your example, since you've only specified one pair, you get its corresponding LCA:

G = nx.DiGraph()
G.add_node(1)
G.add_node(2)
G.add_node(3)
G.add_node(4)
G.add_edge(1,3)
G.add_edge(1,2)
G.add_edge(4,3)
G.add_edge(4,2)

enter image description here

list(nx.all_pairs_lowest_common_ancestor(G, pairs=[(2, 3)]))
# [((2, 3), 4)]

Which is the same as:

nx.lowest_common_ancestor(G, 2,3)
# 4
user_96986840
Related