Wrong output for all_pairs_lowest_common_ancestor #4458
Description
I found a counterexample for the algorithm all_pairs_lowest_common_ancestor (docs here).
The LCA of (i,i) must always be i regardless of the given DAG, but for the following DAG, it fails to meet this condition:
import networkx as nx
from networkx.algorithms.lowest_common_ancestors import all_pairs_lowest_common_ancestor
print(nx.__version__)
G = nx.DiGraph()
G.add_nodes_from(range(5))
G.add_edges_from([(1, 0), (2, 0), (3, 2), (4, 1), (4, 3)])
for (i,j),a in all_pairs_lowest_common_ancestor(G):
if i==j:
assert a==i==j, f'Expected {i}. Got lca({i},{j}) = {a}'Prints 2.5 and raises AssertionError: Expected 0. Got lca(0,0) = 2
You can check that the input is indeed a DAG manually, or like this:
from networkx.algorithms.cycles import simple_cycles
assert list(simple_cycles(G))==[], 'Cycle found'