Naive lowest common ancestor implementation (#5736)

* Add naive lca methods

* Naive algorithm implementation for LCA

* Modify naive lca functions

* Correct parameters of nx.ancestors

* Update lowest_common_ancestors.py

* Parametrize tests

* Apply suggestions from code review

Co-authored-by: Dan Schult <dschult@colgate.edu>

* Yield instead of append

* Tests for naive lca

* Correct test cases for naive lca algorithms

* Apply suggestions from code review

Co-authored-by: Mridul Seth <mail@mriduls.com>

* Fix function name -when calling

* Make requested changes

* Inlining _get_a_lowest_common_ancestor

Co-authored-by: dtuncturk <dilaramemis@sabanciuniv.edu>
Co-authored-by: Dan Schult <dschult@colgate.edu>
Co-authored-by: Mridul Seth <mail@mriduls.com>

2 files changed, 227 insertions, 3 deletions

diff --git a/networkx/algorithms/lowest_common_ancestors.py b/networkx/algorithms/lowest_common_ancestors.py
index e21f9b1b..b276a44d 100644
--- a/networkx/algorithms/lowest_common_ancestors.py
+++ b/networkx/algorithms/lowest_common_ancestors.py
@@ -1,7 +1,7 @@
 """Algorithms for finding the lowest common ancestor of trees and DAGs."""
 from collections import defaultdict
 from collections.abc import Mapping, Set
-from itertools import chain, count
+from itertools import chain, combinations_with_replacement, count
 
 import networkx as nx
 from networkx.utils import UnionFind, arbitrary_element, not_implemented_for
@@ -10,11 +10,116 @@ __all__ = [
     "all_pairs_lowest_common_ancestor",
     "tree_all_pairs_lowest_common_ancestor",
     "lowest_common_ancestor",
+    "naive_lowest_common_ancestor",
+    "naive_all_pairs_lowest_common_ancestor",
 ]
 
 
 @not_implemented_for("undirected")
 @not_implemented_for("multigraph")
+def naive_all_pairs_lowest_common_ancestor(G, pairs=None):
+    """Return the lowest common ancestor of all pairs or the provided pairs
+
+    Parameters
+    ----------
+    G : NetworkX directed graph
+
+    pairs : iterable of pairs of nodes, optional (default: all pairs)
+        The pairs of nodes of interest.
+        If None, will find the LCA of all pairs of nodes.
+
+    Returns
+    -------
+    An iterator over ((node1, node2), lca) where (node1, node2) are
+    the pairs specified and lca is a lowest common ancestor of the pair.
+    Note that for the default of all pairs in G, we consider
+    unordered pairs, e.g. you will not get both (b, a) and (a, b).
+
+    Notes
+    -----
+    Only defined on non-null directed acyclic graphs.
+
+    See Also
+    --------
+    naive_lowest_common_ancestor
+    """
+    if not nx.is_directed_acyclic_graph(G):
+        raise nx.NetworkXError("LCA only defined on directed acyclic graphs.")
+    elif len(G) == 0:
+        raise nx.NetworkXPointlessConcept("LCA meaningless on null graphs.")
+    elif None in G:
+        raise nx.NetworkXError("None is not a valid node.")
+
+    ancestor_cache = {}
+
+    if pairs is None:
+
+        pairs = combinations_with_replacement(G, 2)
+
+    for v, w in pairs:
+        if v not in ancestor_cache:
+            ancestor_cache[v] = nx.ancestors(G, v)
+            ancestor_cache[v].add(v)
+        if w not in ancestor_cache:
+            ancestor_cache[w] = nx.ancestors(G, w)
+            ancestor_cache[w].add(w)
+
+        common_ancestors = ancestor_cache[v] & ancestor_cache[w]
+
+        if common_ancestors:
+            common_ancestor = next(iter(common_ancestors))
+            while True:
+                successor = None
+                for lower_ancestor in G.successors(common_ancestor):
+                    if lower_ancestor in common_ancestors:
+                        successor = lower_ancestor
+                        break
+                if successor is None:
+                    break
+                common_ancestor = successor
+            yield ((v, w), common_ancestor)
+
+
+@not_implemented_for("undirected")
+@not_implemented_for("multigraph")
+def naive_lowest_common_ancestor(G, node1, node2, default=None):
+    """Compute the lowest common ancestor of the given pair of nodes.
+
+    Parameters
+    ----------
+    G : NetworkX directed graph
+
+    node1, node2 : nodes in the graph.
+
+    default : object
+        Returned if no common ancestor between `node1` and `node2`
+
+    Returns
+    -------
+    The lowest common ancestor of node1 and node2,
+    or default if they have no common ancestors.
+
+    Example
+    -------
+    >>> G = nx.DiGraph()
+    >>> nx.add_path(G, (0, 1, 2, 3))
+    >>> nx.add_path(G, (0, 4, 3))
+    >>> nx.naive_lowest_common_ancestor(G, 2, 4)
+    0
+
+    See Also
+    --------
+    naive_all_pairs_lowest_common_ancestor"""
+
+    ans = list(naive_all_pairs_lowest_common_ancestor(G, pairs=[(node1, node2)]))
+    if ans:
+        assert len(ans) == 1
+        return ans[0][1]
+    return default
+
+
+@not_implemented_for("undirected")
+@not_implemented_for("multigraph")
 def tree_all_pairs_lowest_common_ancestor(G, root=None, pairs=None):
     r"""Yield the lowest common ancestor for sets of pairs in a tree.
 
@@ -181,8 +286,7 @@ def lowest_common_ancestor(G, node1, node2, default=None):
     if ans:
         assert len(ans) == 1
         return ans[0][1]
-    else:
-        return default
+    return default
 
 
 @not_implemented_for("undirected")
diff --git a/networkx/algorithms/tests/test_lowest_common_ancestors.py b/networkx/algorithms/tests/test_lowest_common_ancestors.py
index acb23365..be3b9fe5 100644
--- a/networkx/algorithms/tests/test_lowest_common_ancestors.py
+++ b/networkx/algorithms/tests/test_lowest_common_ancestors.py
@@ -6,6 +6,8 @@ import networkx as nx
 
 tree_all_pairs_lca = nx.tree_all_pairs_lowest_common_ancestor
 all_pairs_lca = nx.all_pairs_lowest_common_ancestor
+naive_lca = nx.naive_lowest_common_ancestor
+naive_all_pairs_lca = nx.naive_all_pairs_lowest_common_ancestor
 
 
 def get_pair(dictionary, n1, n2):
@@ -311,3 +313,121 @@ class TestDAGLCA:
         G = nx.DiGraph()
         G.add_node(3)
         assert nx.lowest_common_ancestor(G, 3, 3) == 3
+
+
+class TestNaiveLCA:
+    @classmethod
+    def setup_class(cls):
+        cls.DG = nx.DiGraph()
+        cls.DG.add_nodes_from(range(5))
+        cls.DG.add_edges_from([(1, 0), (2, 0), (3, 2), (4, 1), (4, 3)])
+
+        cls.root_distance = nx.shortest_path_length(cls.DG, source=4)
+
+        cls.gold = {
+            (0, 0): 0,
+            (0, 1): 1,
+            (0, 2): 2,
+            (0, 3): 3,
+            (0, 4): 4,
+            (1, 1): 1,
+            (1, 2): 4,
+            (1, 3): 4,
+            (1, 4): 4,
+            (2, 2): 2,
+            (2, 3): 3,
+            (2, 4): 4,
+            (3, 3): 3,
+            (3, 4): 4,
+            (4, 4): 4,
+        }
+
+    def assert_lca_dicts_same(self, d1, d2, G=None):
+        """Checks if d1 and d2 contain the same pairs and
+        have a node at the same distance from root for each.
+        If G is None use self.DG."""
+        if G is None:
+            G = self.DG
+            root_distance = self.root_distance
+        else:
+            roots = [n for n, deg in G.in_degree if deg == 0]
+            assert len(roots) == 1
+            root_distance = nx.shortest_path_length(G, source=roots[0])
+
+        for a, b in ((min(pair), max(pair)) for pair in chain(d1, d2)):
+            assert (
+                root_distance[get_pair(d1, a, b)] == root_distance[get_pair(d2, a, b)]
+            )
+
+    def test_naive_all_pairs_lowest_common_ancestor1(self):
+        """Produces the correct results."""
+        self.assert_lca_dicts_same(dict(naive_all_pairs_lca(self.DG)), self.gold)
+
+    def test_naive_all_pairs_lowest_common_ancestor2(self):
+        """Produces the correct results when all pairs given."""
+        all_pairs = list(product(self.DG.nodes(), self.DG.nodes()))
+        ans = naive_all_pairs_lca(self.DG, pairs=all_pairs)
+        self.assert_lca_dicts_same(dict(ans), self.gold)
+
+    def test_naive_all_pairs_lowest_common_ancestor3(self):
+        """Produces the correct results when all pairs given as a generator."""
+        all_pairs = product(self.DG.nodes(), self.DG.nodes())
+        ans = naive_all_pairs_lca(self.DG, pairs=all_pairs)
+        self.assert_lca_dicts_same(dict(ans), self.gold)
+
+    def test_naive_all_pairs_lowest_common_ancestor4(self):
+        """Test that LCA on null graph bails."""
+        with pytest.raises(nx.NetworkXPointlessConcept):
+            gen = naive_all_pairs_lca(nx.DiGraph())
+            next(gen)
+
+    def test_naive_all_pairs_lowest_common_ancestor5(self):
+        """Test that LCA on non-dags bails."""
+        with pytest.raises(nx.NetworkXError):
+            gen = naive_all_pairs_lca(nx.DiGraph([(3, 4), (4, 3)]))
+            next(gen)
+
+    def test_naive_all_pairs_lowest_common_ancestor6(self):
+        """Test that pairs with no LCA specified emits nothing."""
+        G = self.DG.copy()
+        G.add_node(-1)
+        gen = naive_all_pairs_lca(G, [(-1, -1), (-1, 0)])
+        assert dict(gen) == {(-1, -1): -1}
+
+    def test_naive_lowest_common_ancestor1(self):
+        """Test that the one-pair function works for issue #4574."""
+        G = nx.DiGraph()
+        G.add_nodes_from(range(17))
+        G.add_edges_from(
+            [
+                (2, 0),
+                (1, 2),
+                (3, 2),
+                (5, 2),
+                (8, 2),
+                (11, 2),
+                (4, 5),
+                (6, 5),
+                (7, 8),
+                (10, 8),
+                (13, 11),
+                (14, 11),
+                (15, 11),
+                (9, 10),
+                (12, 13),
+                (16, 15),
+            ]
+        )
+
+        assert naive_lca(G, 7, 9) == None
+
+    def test_naive_lowest_common_ancestor2(self):
+        """Test that the one-pair function works for issue #4942."""
+        G = nx.DiGraph()
+        G.add_edge(0, 1)
+        G.add_edge(2, 0)
+        G.add_edge(2, 3)
+        G.add_edge(4, 0)
+        G.add_edge(5, 2)
+
+        assert naive_lca(G, 1, 3) == 2