Naive lowest common ancestor implementation by dtekinoglu · Pull Request #5736 · networkx/networkx

dtekinoglu · 2022-06-15T14:00:17Z

No description provided.

dschult · 2022-06-15T21:28:47Z

Looks like nx.ancestors has two arguments: nx.ancestors(G, v)

networkx/algorithms/tests/test_lowest_common_ancestors.py

dschult

I went through the code and made some suggestions. Looks good!

networkx/algorithms/lowest_common_ancestors.py

dschult · 2022-06-19T17:08:29Z

networkx/algorithms/tests/test_lowest_common_ancestors.py

        G = nx.DiGraph([(3, 4), (5, 4)])
        pytest.raises(nx.NetworkXError, list, tree_all_pairs_lca(G))

+    # HOW TO PARAMETRIZE THIS ONE?


@rossbar do you have any magic to handle parametrizing this test method?

I would say that for this test it makes more sense to parametrize on the inputs since some of the tested objects are generators (i.e. some require next in order to trigger there behavior) and some are functions. For example, I'd probably write this test like so:

@pytest.mark.parametrize("graph_type", (nx.Graph, nx.MultiGraph, nx.MultiDiGraph)) def test_not_implemented(self, graph_type): G = graph_type([(0, 1)]) with pytest.raises(nx.NetworkxNotImplemented): next(tree_all_pairs_lca(G)) with pytest.raises(nx.NetworkxNotImplemented): next(all_pairs_lca(G)) with pytest.raises(nx.NetworkxNotImplemented): nx.lowest_common_ancestor(G, 0, 1)

... and if you wanted to add more generators/functions, you could add more with statements (e.g.

with pytest.raises(nx.NetworkxNotImplemented): nx.naive_lowest_common_ancestor(G, 0, 1)

The other thing you could do is split this up into two separate tests, one for generators and one for functions, that would allow you to stacked parametrizations (see the end of this section). That might look something like:

@pytest.mark.parametrize("graph_type", (nx.Graph, nx.MultiGraph, nx.MultiDiGraph)) @pytest.mark.parametrize("lca_gen", (tree_all_pairs_lca, all_pairs_lca)) def test_not_implemented_generator(self, graph_type, lca_gen): G = graph_type([(0, 1)]) with pytest.raises(nx.NetworkxNotImplemented): next(lca_gen(G)) @pytest.mark.parametrize("graph_type", (nx.Graph, nx.MultiGraph, nx.MultiDiGraph)) @pytest.mark.parametrize("lca_fn", (tree_all_pairs_lca, all_pairs_lca)) def test_not_implemented_function(self, graph_type, lca_fn): G = graph_type([(0, 1)]) with pytest.raises(nx.NetworkxNotImplemented): lca_fn(G, 0, 1)

The trick with parametrizing tests (IMO) is to strike a balance between utility and readability - of course, where that balance lies is usually pretty subjective :)

dtekinoglu · 2022-07-04T20:49:27Z

Ready for review @MridulS @dschult @rossbar

MridulS

This looks great @dtekinoglu! added some little nit picks :)

MridulS · 2022-07-05T10:47:57Z

networkx/algorithms/lowest_common_ancestors.py

+                    pairs.add((u, v))
+    else:
+        if type(pairs) != list:
+            pairs = list(pairs)


Not too sure if this check is required. Even if pairs isn't a list (and just an iterator), the for loop below should work just fine.

If I don't include this check test_naive_all_pairs_lowest_common_ancestor3 fails and I cannot figure out what else to do.

Ahhh yes, this is happening because the iterator is being consumed in this checking loop. So the next loop over pairs ends up just being a loop over an empty iterator. Maybe we shouldn't even check this at all here. If nx.ancestors is used with a node which is not in the graph it gives a nice clean error, something like

.... .... NetworkXError: The node 1100 is not in the digraph.

What do you think about removing this else condition here?

Something like this https://github.com/networkx/networkx/pull/5736/files#r914724794

networkx/algorithms/lowest_common_ancestors.py

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

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

networkx/algorithms/lowest_common_ancestors.py

MridulS

This is great! Thanks @dtekinoglu :)

dschult

This looks good to me! I have some comments below about possibly different ways of arranging loops in python. See what you think. None are critical. If you'd like the current code just reply with that and we'll merge it. :}

networkx/algorithms/lowest_common_ancestors.py

rossbar

Excellent, thanks @dtekinoglu ! This LGTM, just a stray comment about the tests.

rossbar · 2022-07-14T09:50:34Z

networkx/algorithms/tests/test_lowest_common_ancestors.py

+    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)]
+            )


If I'm not missing anything, it looks like the G=None arg isn't used in any of the following tests. If so, then this check could be made easier to understand by removing the unused kwarg and associated scaffolding, e.g.

Suggested change

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 assert_lca_dicts_same(self, d1, d2):

"""Checks if d1 and d2 contain the same pairs and

have a node at the same distance from root for each.

"""

for a, b in ((min(pair), max(pair)) for pair in chain(d1, d2)):

assert (

self.root_distance[get_pair(d1, a, b)] ==

self.root_distance[get_pair(d2, a, b)]

)

Ah - so I just looked at the rest of the file and realized that this method (along with most of the other patterns, e.g. the test method names) were taken from the existing test classes, which makes total sense. I think there's actually a lot to clean up in the existing tests, so let's not worry about this here... I will create a followup issue so that we can handle this separately and not block this PR.

I'm going to switch my previous comment to an approval, sorry for the noise @dtekinoglu !

* 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>

dschult reviewed Jun 16, 2022

View reviewed changes

networkx/algorithms/tests/test_lowest_common_ancestors.py Outdated Show resolved Hide resolved

dschult reviewed Jun 19, 2022

View reviewed changes

dtekinoglu force-pushed the fix-for-issue-5547 branch from 7d3dfd2 to 771d0af Compare July 4, 2022 20:42

dtekinoglu marked this pull request as ready for review July 4, 2022 20:48

MridulS requested changes Jul 5, 2022

View reviewed changes

dtuncturk and others added 11 commits July 6, 2022 11:31

Add naive lca methods

865b5d3

Naive algorithm implementation for LCA

ff69d46

Modify naive lca functions

a8b622f

Correct parameters of nx.ancestors

f8fef14

Update lowest_common_ancestors.py

1b31dd2

Parametrize tests

ecb0ffa

Apply suggestions from code review

47ef008

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

Yield instead of append

426c2a6

Tests for naive lca

a7c73b0

Correct test cases for naive lca algorithms

987d285

Apply suggestions from code review

295bbe1

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

dtekinoglu force-pushed the fix-for-issue-5547 branch from 6e4a182 to 295bbe1 Compare July 6, 2022 08:32

Fix function name -when calling

ab0bc4f

MridulS reviewed Jul 6, 2022

View reviewed changes

networkx/algorithms/lowest_common_ancestors.py Outdated Show resolved Hide resolved

dtekinoglu force-pushed the fix-for-issue-5547 branch from c698191 to ab0bc4f Compare July 7, 2022 13:44

Make requested changes

0799cc5

MridulS approved these changes Jul 8, 2022

View reviewed changes

dschult reviewed Jul 8, 2022

View reviewed changes

networkx/algorithms/lowest_common_ancestors.py Outdated Show resolved Hide resolved

networkx/algorithms/lowest_common_ancestors.py Outdated Show resolved Hide resolved

Inlining _get_a_lowest_common_ancestor

e32d9f7

rossbar reviewed Jul 14, 2022

View reviewed changes

rossbar approved these changes Jul 14, 2022

View reviewed changes

This was referenced Jul 14, 2022

Update all_pairs_lca docstrings #5862

Closed

Cleanup LCA tests #5863

Closed

dschult merged commit b2f91c3 into networkx:main Jul 14, 2022

rossbar mentioned this pull request Jul 15, 2022

Replace existing LCA functions with "naive" implementations? #5869

Closed

This was referenced Jul 17, 2022

Lowest common ancestor returns incomplete result #5628

Closed

nx.lowest_common_ancestor incorrectly returns None for this DAG #4942

Closed

rossbar mentioned this pull request Jul 22, 2022

Replace LCA with naive implementations #5883

Merged

jarrodmillman added this to the networkx-2.8.6 milestone Aug 21, 2022

This was referenced Nov 15, 2022

Adds LCA test case for self-ancestors from gh-4458. #6218

Merged

Wrong output for all_pairs_lowest_common_ancestor #4458

Closed

dschult mentioned this pull request Nov 22, 2022

Implementation of LCA algorithm does not match with referenced paper #5547

Closed

rossbar mentioned this pull request Oct 1, 2024

Lowest Common Ancestors (LCA) algorithm does not return the correct ancestor for every spanning tree #7655

Closed

Uh oh!

Conversation

dtekinoglu commented Jun 15, 2022

Uh oh!

dschult commented Jun 15, 2022

Uh oh!

Uh oh!

dschult left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

dtekinoglu commented Jul 4, 2022

Uh oh!

MridulS left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

MridulS left a comment

Choose a reason for hiding this comment

Uh oh!

dschult left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

rossbar left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Milestone

Development

Uh oh!

5 participants