Implement condensation graph generation #1337

kazuki0824 · 2024-12-08T17:02:50Z

This pull request adds functionality to generate condensation graphs. The Rust implementation is copied and slightly modified from https://github.com/petgraph/petgraph because the original petgraph implementation cannot be applied as it is. Condensation graphs represent strongly connected components of a directed graph as single nodes. The update includes a new implementation and its test to support this feature.

I ran rustfmt locally
I have added the tests to cover my changes.
I have updated the documentation accordingly.
I have read the CONTRIBUTING document.

coveralls · 2024-12-09T16:19:46Z

Pull Request Test Coverage Report for Build 14777358700

Details

80 of 112 (71.43%) changed or added relevant lines in 2 files are covered.
2 unchanged lines in 1 file lost coverage.
Overall coverage decreased (-0.1%) to 95.236%

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
src/connectivity/mod.rs	78	110	70.91%

Files with Coverage Reduction	New Missed Lines	%
rustworkx-core/src/generators/random_graph.rs	2	70.57%

Totals
Change from base Build 14760218172:	-0.1%
Covered Lines:	18730
Relevant Lines:	19667

💛 - Coveralls

kazuki0824 · 2024-12-22T05:58:24Z

@IvanIsCoding can anyone review this code?

IvanIsCoding · 2024-12-22T06:06:46Z

@IvanIsCoding can anyone review this code?

Sorry I haven’t acknowledged the PR. I haven’t had time to review it.

I will do the review after Christmas, it might still make the cut for rustworkx 0.16.

kazuki0824 · 2024-12-22T13:14:42Z

@IvanIsCoding can anyone review this code?

Sorry I haven’t acknowledged the PR. I haven’t had time to review it.

I will do the review after Christmas, it might still make the cut for rustworkx 0.16.

Thank you for your quick response.

alexanderivrii · 2024-12-29T13:52:46Z

src/connectivity/mod.rs

+    g: Graph<N, E, Ty, Ix>,
+    make_acyclic: bool,
+    sccs: Option<Vec<Vec<usize>>>,
+) -> StableGraph<PyObject, PyObject, Ty, Ix>


I am wondering if it would make sense to also return a map between the nodes of the condensed graph and the (sets of) nodes of the original graph, so that information computed for the condensed graph could be lifted to the original graph as well?

alexanderivrii · 2024-12-29T13:53:38Z

tests/digraph/test_strongly_connected.py

+        self.graph.add_edge(self.node_h, self.node_e, "h->e")  # サイクル: e -> f -> g -> h -> e
+
+    def test_condensation(self):
+        # condensation関数を呼び出し


It would be nice to translate all comments to English.

alexanderivrii

This is not a review, but I was wondering: would it make sense to move this functionality to rustworkx-core? would it make sense to implement this both for directed and undirected graphs? would it make sense to return additional information relating the nodes of the original and the condensed graphs (see in-place comment).

IvanIsCoding

Overall the condensation logic looks good to me. I left comments that are mostly to simplify the existing code and make it more maintainable in the long run. I don't think you'll need to change much for the algorithm

I think the only debate left is how to return the node mappings. I personally like the short return type signature, so for me a graph attribute with the mapping seems like a good compromise.

IvanIsCoding · 2024-12-30T18:16:19Z

src/connectivity/mod.rs

+        check_cycle: false,
+        node_removed: false,
+        multigraph: true,
+        attrs: py.None(),


Either the attrs should contain the node mapping like in NetworkX. Or we need to update the signature to return a mapping

IvanIsCoding · 2024-12-30T18:16:40Z

src/connectivity/mod.rs

+    py: Python,
+    graph: &digraph::PyDiGraph,
+    sccs: Option<Vec<Vec<usize>>>,
+) -> digraph::PyDiGraph {


Sibling comment to either update the signature or return the node mapping somewhere else

src/connectivity/mod.rs

rustworkx/rustworkx.pyi

src/connectivity/mod.rs

tests/digraph/test_strongly_connected.py

IvanIsCoding · 2024-12-30T18:35:54Z

Some notes to myself:

Add a release note for this once the code is ready (https://github.com/Qiskit/rustworkx/blob/main/CONTRIBUTING.md#release-notes)
Add a docstring to the method once the code is ready

Feel free to do those on your own too. But I don't mind doing the documentation for you, it is fine to focus on the code.

Again, thanks for your repeated contributions to rustworkx

kazuki0824 · 2025-04-20T15:58:46Z

@IvanIsCoding Now ready to review. I also added Rust doc and release notes. Please check them too.

@IvanIsCoding

thanks @IvanIsCoding Co-authored-by: Ivan Carvalho <8753214+IvanIsCoding@users.noreply.github.com>

@IvanIsCoding

thanks @IvanIsCoding Co-authored-by: Ivan Carvalho <8753214+IvanIsCoding@users.noreply.github.com>

Update mod.rs

Update mod.rs Update mod.rs Update mod.rs

Update mod.rs ok ok wip Update mod.rs Reformat Reformat

IvanIsCoding · 2025-04-26T16:36:22Z

I plan to take a look at this soon, sorry for the delay

kazuki0824 · 2025-04-27T11:29:05Z

I plan to take a look at this soon, sorry for the delay

Thank you for your response.

IvanIsCoding

Some comments. Overall this works but there are some things that can be improved.

The tests look good though. You can keep them as they are.

IvanIsCoding · 2025-04-30T02:03:44Z

src/connectivity/mod.rs

+#[pyo3(text_signature = "(graph, /, sccs=None)", signature=(graph, sccs=None))]
+pub fn condensation(
+    py: Python,
+    graph: PyObject,


We generally have the split at __init__.py with a Python function with @_rustworkx_dispatch and then two Rust functions with digraph_* and graph_*:

rustworkx/rustworkx/__init__.py

Line 148 in 217d58d

def distance_matrix(graph, parallel_threshold=300, as_undirected=False, null_value=0.0):

I'd rather keep the existing pattern, of course this one works but consistency in the library is important

We generally have the split at __init__.py with a Python function with @_rustworkx_dispatch and then two Rust functions with digraph_* and graph_*:

rustworkx/rustworkx/__init__.py

Line 148 in 217d58d

def distance_matrix(graph, parallel_threshold=300, as_undirected=False, null_value=0.0):

I'd rather keep the existing pattern, of course this one works but consistency in the library is important

@IvanIsCoding I got it, and where do we place two Rust functions with digraph_* and graph_*, and a new python function with decorator?

Rust functions with digraph_* and graph_*: maybe 'src/connectivity/mod.rs', replacing current 'condensation' function
Python function with decorator: sorry but no idea

The Python function goes here:

rustworkx/rustworkx/__init__.py

Line 852 in 30f2907

def complement(graph):

It’s in __init__.py, there’s not a lot of code there just the doc string essentially.

The Rust code can stay where it is right now

I just tried to address this issue following other code.

IvanIsCoding · 2025-04-30T02:06:57Z

src/connectivity/mod.rs

+        let node_map_py = node_map.into_pyobject(py)?;
+        let attrs = PyDict::new(py);


I believe you can use a DictMap instead of a PyDict and just call into_pyobject() at the end. In general, working with Rust primitives might be easier. In general the Python APIs force you to handle errors that don't happen very often. For Rust, putting an item in the hashmap would "just work"

IvanIsCoding · 2025-04-30T02:07:58Z

src/connectivity/mod.rs

+        let attrs = PyDict::new(py);
+        attrs.set_item("node_map", node_map_py)?;
+        result.attrs = attrs.into();
+        Ok(result.into_pyobject(py)?.into())


If you split the Rust methods in digraph_condensation and graph_condensation, you'll be able to just return the PyDiGraph or PyGraph object without needing this conversion

IvanIsCoding · 2025-04-30T02:10:23Z

src/connectivity/mod.rs

+        StableGraph::with_capacity(components_usize.len(), g.edge_count());
+
+    // Build a map from old indices to new ones.
+    let mut node_map = vec![usize::MAX; g.node_count()];


Prefer using None instead of usize::MAX to represent missing objects

src/connectivity/mod.rs

IvanIsCoding · 2025-04-30T02:11:38Z

src/connectivity/mod.rs

+        let source = node_map
+            .get(edge.source().index())
+            .copied()
+            .unwrap_or(usize::MAX);


Same comment about prefering Option<usize> instead of using usize::MAX as a replacement for None

src/connectivity/mod.rs

Co-authored-by: Ivan Carvalho <8753214+IvanIsCoding@users.noreply.github.com>

Update lib.rs

Reformat

Reformat Update __init__.py

IvanIsCoding

LGTM, thanks for addressing the comments

@IvanIsCoding

* Implement condensation tentatively * Update test_strongly_connected.py * Update src/connectivity/mod.rs thanks @IvanIsCoding Co-authored-by: Ivan Carvalho <8753214+IvanIsCoding@users.noreply.github.com> * Update rustworkx/rustworkx.pyi thanks @IvanIsCoding Co-authored-by: Ivan Carvalho <8753214+IvanIsCoding@users.noreply.github.com> * Update mod.rs Update mod.rs * Update mod.rs Update mod.rs Update mod.rs Update mod.rs * Update test_strongly_connected.py * Create condensation-undirected-support-apr2025.yaml * Use pyobject and bound Update mod.rs ok ok wip Update mod.rs Reformat Reformat * Update rustworkx.pyi * Update test_strongly_connected.py * Update test_strongly_connected.py * Replace MAX with None Co-authored-by: Ivan Carvalho <8753214+IvanIsCoding@users.noreply.github.com> * Separate digraph and graph function Update lib.rs * Add stub definition Reformat * Update __init__.py * Replace MAX with None (2) Reformat Update __init__.py * Reformat --------- Co-authored-by: Ivan Carvalho <8753214+IvanIsCoding@users.noreply.github.com>

kazuki0824 force-pushed the feat/generate_condensation_graph branch from eed8af1 to fada9a1 Compare December 8, 2024 17:38

kazuki0824 marked this pull request as ready for review December 15, 2024 08:01

kazuki0824 force-pushed the feat/generate_condensation_graph branch from 8754ccd to 9c026b2 Compare December 15, 2024 08:06

kazuki0824 force-pushed the feat/generate_condensation_graph branch from 57dc3fe to 5045623 Compare December 22, 2024 06:03

alexanderivrii reviewed Dec 29, 2024

View reviewed changes

IvanIsCoding reviewed Dec 30, 2024

View reviewed changes

kazuki0824 force-pushed the feat/generate_condensation_graph branch 3 times, most recently from 162ef11 to dc8b154 Compare April 20, 2025 13:19

kazuki0824 requested a review from IvanIsCoding April 20, 2025 15:59

kazuki0824 and others added 12 commits April 26, 2025 13:11

Implement condensation tentatively

69f18b5

Update test_strongly_connected.py

d502a5a

Update src/connectivity/mod.rs

736bbfe

thanks @IvanIsCoding Co-authored-by: Ivan Carvalho <8753214+IvanIsCoding@users.noreply.github.com>

Update rustworkx/rustworkx.pyi

be9d392

thanks @IvanIsCoding Co-authored-by: Ivan Carvalho <8753214+IvanIsCoding@users.noreply.github.com>

Update mod.rs

08c58c4

Update mod.rs

Update mod.rs

841320f

Update mod.rs Update mod.rs Update mod.rs

Update test_strongly_connected.py

6cfd7f7

Create condensation-undirected-support-apr2025.yaml

bb426dc

Use pyobject and bound

2d593b9

Update mod.rs ok ok wip Update mod.rs Reformat Reformat

Update rustworkx.pyi

475beb8

Update test_strongly_connected.py

3fcefbf

Update test_strongly_connected.py

571cd81

kazuki0824 force-pushed the feat/generate_condensation_graph branch from c8feb98 to 571cd81 Compare April 26, 2025 04:11

IvanIsCoding mentioned this pull request Apr 27, 2025

Adding fuzz target for contraction #1435

Merged

IvanIsCoding reviewed Apr 30, 2025

View reviewed changes

Replace MAX with None

10d9685

Co-authored-by: Ivan Carvalho <8753214+IvanIsCoding@users.noreply.github.com>

kazuki0824 force-pushed the feat/generate_condensation_graph branch 2 times, most recently from 8e7beb2 to 2f7f62a Compare May 1, 2025 13:07

Separate digraph and graph function

e0df743

Update lib.rs

kazuki0824 force-pushed the feat/generate_condensation_graph branch from 2f7f62a to bc221d6 Compare May 1, 2025 14:09

Add stub definition

29ff0a1

Reformat

kazuki0824 force-pushed the feat/generate_condensation_graph branch from bc221d6 to 3e5b320 Compare May 1, 2025 14:13

kazuki0824 added 2 commits May 1, 2025 23:40

Update __init__.py

b38fc2c

Replace MAX with None (2)

3da19fe

Reformat Update __init__.py

kazuki0824 force-pushed the feat/generate_condensation_graph branch from 3e5b320 to 3da19fe Compare May 1, 2025 14:41

Reformat

baa433f

kazuki0824 requested a review from IvanIsCoding May 1, 2025 14:56

IvanIsCoding approved these changes May 1, 2025

View reviewed changes

IvanIsCoding added this pull request to the merge queue May 1, 2025

Merged via the queue into Qiskit:main with commit 62181fb May 1, 2025
31 checks passed

		let node_map_py = node_map.into_pyobject(py)?;
		let attrs = PyDict::new(py);

Implement condensation graph generation #1337

Implement condensation graph generation #1337

Uh oh!

Conversation

kazuki0824 commented Dec 8, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

coveralls commented Dec 9, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pull Request Test Coverage Report for Build 14777358700

Details

💛 - Coveralls

Uh oh!

kazuki0824 commented Dec 22, 2024

Uh oh!

IvanIsCoding commented Dec 22, 2024

Uh oh!

kazuki0824 commented Dec 22, 2024

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

alexanderivrii left a comment

Choose a reason for hiding this comment

Uh oh!

IvanIsCoding 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!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

IvanIsCoding commented Dec 30, 2024

Uh oh!

kazuki0824 commented Apr 20, 2025

Uh oh!

IvanIsCoding commented Apr 26, 2025

Uh oh!

kazuki0824 commented Apr 27, 2025

Uh oh!

IvanIsCoding left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

kazuki0824 May 1, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

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!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

IvanIsCoding left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

kazuki0824 commented Dec 8, 2024 •

edited

Loading

coveralls commented Dec 9, 2024 •

edited

Loading

kazuki0824 May 1, 2025 •

edited

Loading