Skip to content

Conversation

singhmeet11
Copy link
Contributor

This pull request adds a random regular graph function in rustworkx-core(this partly resolves - #1391). I will be adding the PyO3 connection and this functionality to rustworkx in a bit. Just wanted to get review on this first.

  • 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.

Copy link
Collaborator

@IvanIsCoding IvanIsCoding left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I will review the algorithm from NetworkX more closely, but currently the implementation LGTM.

I left a couple Rust comments. The majority are about using IndexSet and DictMap.

In Rust, HashMap and HashSet have random iteration order. That means that calling the same function twice with the same seeds would generate different graphs. Despite random in the name, when users pass a seed the expect a reproducible result. So let's stick with DictMap and IndexSet as they will preserve the iteration order.

I also added a minor comment to make the test slightly stronger. Also, remember to run cargo fmt it will fix the failure in CI.

Last but not least: congrats on your first contribution! I think the strategy of starting with the rustworkx-core is best. This PR is very close to getting merged.

edit: use DictMap instead of IndexMap, it is our alias for IndexMap with the hasher rustworkx uses

singhmeet11 and others added 6 commits April 10, 2025 20:59
Co-authored-by: Ivan Carvalho <8753214+IvanIsCoding@users.noreply.github.com>
…graph.rs

Co-authored-by: Ivan Carvalho <8753214+IvanIsCoding@users.noreply.github.com>
Co-authored-by: Ivan Carvalho <8753214+IvanIsCoding@users.noreply.github.com>
Co-authored-by: Ivan Carvalho <8753214+IvanIsCoding@users.noreply.github.com>
Co-authored-by: Ivan Carvalho <8753214+IvanIsCoding@users.noreply.github.com>
@singhmeet11
Copy link
Contributor Author

Hi @IvanIsCoding, I have made the required changes. Let me know if there is anything else.

@IvanIsCoding
Copy link
Collaborator

There are some cargo clippy failures, you can see them on CI or run the command locally like I’m CONTRIBUTING.md.

You’ll need to fix the lint findings first before I can merge

Copy link
Collaborator

@IvanIsCoding IvanIsCoding left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Minor suggestions to make CI pass

@IvanIsCoding
Copy link
Collaborator

We got one test failure on CI:

failures:

---- rustworkx-core/src/generators/random_graph.rs - generators::random_graph::random_regular_graph (line 68) stdout ----
Test executable failed (exit status: 101).

stderr:

thread 'main' panicked at rustworkx-core/src/generators/random_graph.rs:16:1:
assertion `left == right` failed
  left: 4
 right: 2
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace



failures:
    rustworkx-core/src/generators/random_graph.rs - generators::random_graph::random_regular_graph (line 68)

test result: FAILED. 85 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out; finished in 9.93s

You'll need to investigate the bug. I will also try to found out why

@IvanIsCoding
Copy link
Collaborator

So there were two mistakes:

  • For n=4, d=2, we expect there to be 4 edges. ((n*d)/2 is the number of edges)
  • The algorithms sometimes generates 4 edges, sometimes it doesn't. For the seed 2025, it looks like it doesn't. So I fixed the seed and let's focus on making it pass

@singhmeet11
Copy link
Contributor Author

Oh sorry, forgot to fix the number of edges generated in the doctest place. However, the particular error post that arises due to a bug. We switched from

*potential_edges.entry(u).or_insert(0) += 1;
*potential_edges.entry(v).or_insert(0) += 1;

to

*potential_edges.entry(u).or_insert(1);
*potential_edges.entry(v).or_insert(1);

this led to some of the edges being ignored, so I am reverting this back and will see if this help pass the tests

@IvanIsCoding
Copy link
Collaborator

Indeed, I introduced a bug with that comment. It turns out that the .contains() was a check in another hashmap... Well, I think it should be good to go now.

I am also happy the tests caught it.

@IvanIsCoding IvanIsCoding enabled auto-merge April 12, 2025 14:24
@coveralls
Copy link

Pull Request Test Coverage Report for Build 14420374667

Details

  • 0 of 96 (0.0%) changed or added relevant lines in 1 file are covered.
  • No unchanged relevant lines lost coverage.
  • Overall coverage decreased (-0.5%) to 95.369%

Changes Missing Coverage Covered Lines Changed/Added Lines %
rustworkx-core/src/generators/random_graph.rs 0 96 0.0%
Totals Coverage Status
Change from base Build 14391902387: -0.5%
Covered Lines: 18637
Relevant Lines: 19542

💛 - Coveralls

@IvanIsCoding IvanIsCoding added this pull request to the merge queue Apr 12, 2025
Merged via the queue into Qiskit:main with commit cc6229c Apr 12, 2025
31 checks passed
SILIZ4 pushed a commit to SILIZ4/rustworkx that referenced this pull request Jul 4, 2025
* adding random regular graph generator

* correct spelling rustworkx-core/src/generators/random_graph.rs

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

* Update from HashSet to IndexSet rustworkx-core/src/generators/random_graph.rs

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

* Correct spelling rustworkx-core/src/generators/random_graph.rs

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

* Hashset to indexset rustworkx-core/src/generators/random_graph.rs

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

* Index Set  rustworkx-core/src/generators/random_graph.rs

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

* corrected formatting, replaced HashSet and Hashmap to IndexSet and DictMap, added test case

* fixing bug

* Apply suggestions from code review

* Make doctest failure reproducible

* fixed bug leading to doctest issue

* fix hyperlink

---------

Co-authored-by: Ivan Carvalho <8753214+IvanIsCoding@users.noreply.github.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

3 participants