Enhance docstrings for topological sort methods #1413

eumiro · 2025-04-04T19:16:14Z

I realized the lexicographical_topological_sort method does not raise DAGHasCycle if it gets a graph with cycles. It just ignores the participating nodes and returns the rest.

For instance:

G = rx.PyDiGraph()
G.add_nodes_from(["A", "B"])
G.add_edges_from_no_data([(0, 1), (1, 0)])
rx.lexicographical_topological_sort(G, key=str)

returns an empty list.

I tried to add a check into the code, but did not succeed. The test in would be:

tests/digraph/test_nodes.py (line 611)

    def test_lexicographical_topological_sort_with_cycle(self):
        G = rustworkx.PyDiGraph()
        G.add_nodes_from(("A", "B"))
        G.add_edges_from_no_data(((0, 1), (1, 0)))
        self.assertRaises(rustworkx.DAGHasCycle, rustworkx.lexicographical_topological_sort, G, str)

IvanIsCoding

This is blocked until I merge a fix for clippy lints, which hopefully is soon

IvanIsCoding

LGTM with a minor caveat

IvanIsCoding · 2025-04-05T00:45:00Z

src/dag_algo/mod.rs

+///   >>> G.add_nodes_from(["A", "B", "C", "D", "E", "F", "G"])
+///   >>> G.add_edges_from_no_data([(0, 6), (1, 6), (2, 6), (3, 6), (4, 6), (5, 6)])


Nitpicking, but you can unpack this as:

a, b, c, d, e, f, g = .add_nodes_from(["A", "B", "C", "D", "E", "F", "G"])

And then do e.g. edges_from_no_data[(a, g)...]

In this case it seems to be useful. Updated, thanks.

IvanIsCoding · 2025-04-05T00:45:13Z

src/dag_algo/mod.rs

-/// :param PyDiGraph graph: The DAG to get the topological generations from
+///   >>> G = rx.PyDiGraph()
+///   >>> G.add_nodes_from([0, 1, 2, 3, 4])
+///   >>> G.add_edges_from_no_data([(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)])


The same as below. Here even more: perfectly matching numbers only.

IvanIsCoding · 2025-04-05T00:45:25Z

src/dag_algo/mod.rs

 ///
+///   >>> G = rx.PyDiGraph()
+///   >>> G.add_nodes_from(["A", "B", "C", "D", "E", "F", "G"])
+///   >>> G.add_edges_from_no_data([(0, 1),(1, 2), (2, 3), (3, 4), (5, 2), (6, 3)])


This is true for many of other examples and I'll be happy to update them later.

However, since this method returns a numerical list of indices NodeIndices[6, 5, 0, 1, 2, 3, 4], I find it easier for the reader to match these numbers and the arguments to add_edges_from_no_data.

IvanIsCoding · 2025-04-05T00:51:10Z

And about raising an error: that would probably be the correct behaviour. It should be pretty easy to check after the fact as well, if the rustworxk-core lexicographical topological sort did not return all the nodes we'd raise.

coveralls · 2025-04-05T01:00:14Z

Pull Request Test Coverage Report for Build 14289021126

Details

0 of 0 changed or added relevant lines in 0 files are covered.
No unchanged relevant lines lost coverage.
Overall coverage remained the same at 95.34%

Totals
Change from base Build 14284910943:	0.0%
Covered Lines:	18515
Relevant Lines:	19420

💛 - Coveralls

eumiro · 2025-04-05T04:57:38Z

And about raising an error: that would probably be the correct behaviour. It should be pretty easy to check after the fact as well, if the rustworxk-core lexicographical topological sort did not return all the nodes we'd raise.

Actually, it is unfortunately correct, as it is. Because of the optional initial argument, we cannot expect to have all nodes of the graph returned. And with initial, it will “only include those nodes and any nodes that are dominated by them”, so the rest should not be tested for cycles at all.

IvanIsCoding · 2025-04-05T17:48:08Z

Just FYI, I think the error from the CI is actionable:

/home/runner/work/rustworkx/rustworkx/.nox/docs-3/lib/python3.10/site-packages/rustworkx/__init__.py:docstring of rustworkx.topological_generations:16:Unknown interpreted text role "cls".

If the fix is trivial, I can try patching it after I merge #1403

IvanIsCoding · 2025-04-06T04:51:53Z

Once https://status.coveralls.io/ is back we should be able to merge this

IvanIsCoding reviewed Apr 4, 2025

View reviewed changes

IvanIsCoding reviewed Apr 5, 2025

View reviewed changes

eumiro force-pushed the topological-sorts branch 2 times, most recently from 5c65617 to c3baa27 Compare April 5, 2025 04:55

eumiro force-pushed the topological-sorts branch from c3baa27 to 0ef6e00 Compare April 6, 2025 04:28

Enhance docstrings for topological sort methods

ba25dd2

eumiro force-pushed the topological-sorts branch from 0ef6e00 to ba25dd2 Compare April 6, 2025 04:32

IvanIsCoding added this to the 0.17.0 milestone Apr 6, 2025

IvanIsCoding approved these changes Apr 6, 2025

View reviewed changes

IvanIsCoding enabled auto-merge April 6, 2025 23:25

IvanIsCoding added this pull request to the merge queue Apr 6, 2025

github-merge-queue bot removed this pull request from the merge queue due to failed status checks Apr 7, 2025