Add `periodic` to `hexagonal_lattice_graph` #1213

jpacold · 2024-06-10T03:53:26Z

Implements one of the features needed to close #803. I think this is complementary to PR #1207, which looks like it starts implementing the other part (with_positions).

Rust changes:

Moved calls to graph.add_edge into a closure to make the code more readable
Added periodic argument. The comments on Add support to hexagonal_lattice_graph for periodcity and position coordinates #803 suggest implementing this by following the logic in networkx, which constructs a non-periodic graph and then contracts pairs of nodes on the lattice boundaries. I chose to instead create a smaller number of nodes up front.
Added tests.

Python changes:

Updated stub file.
Added tests, including a check for isomorphism with the periodic lattices generated by networkx.

coveralls · 2024-06-10T11:29:18Z

Pull Request Test Coverage Report for Build 9442230137

Details

52 of 55 (94.55%) changed or added relevant lines in 2 files are covered.
3 unchanged lines in 2 files lost coverage.
Overall coverage increased (+0.008%) to 95.849%

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
rustworkx-core/src/generators/hexagonal_lattice_graph.rs	45	46	97.83%
src/generators.rs	7	9	77.78%

Files with Coverage Reduction	New Missed Lines	%
rustworkx-core/src/generators/hexagonal_lattice_graph.rs	1	97.5%
rustworkx-core/src/generators/random_graph.rs	2	85.04%

Totals
Change from base Build 9429147177:	0.008%
Covered Lines:	17339
Relevant Lines:	18090

💛 - Coveralls

IvanIsCoding

I will let people that made the feature request review the content, but overall the Rust code is looking pretty good! I left some minor comments

IvanIsCoding · 2024-06-10T12:05:05Z

rustworkx-core/src/generators/hexagonal_lattice_graph.rs

+    // Number of nodes in each vertical chain
+    let rowlen = if periodic {
+        2 * rows
+    } else {
+        // Note: in the non-periodic case the first and
+        // last vertical chains have (2 * rows + 1) nodes
+        2 * rows + 2
+    };
+
+    // Number of vertical chains
+    let collen = if periodic { cols } else { cols + 1 };
+
+    let num_nodes = if periodic {
+        rowlen * collen
+    } else {
+        rowlen * collen - 2
+    };


You can rewrite all the variables with a single match on that condition using destructuring e.g. https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=ef7020b44cc19135583d87a1dcf6d1b2

Forgot to mention that I did this as well in 6497d44.

IvanIsCoding · 2024-06-10T12:08:46Z

rustworkx-core/src/generators/hexagonal_lattice_graph.rs

+        assert_eq!(
+            expected_edges,
+            g.edge_references()
+                .map(|edge| (edge.source().index(), edge.target().index()))
+                .collect::<Vec<(usize, usize)>>(),
+        );


I wouldn't assert the order of the edges in the generated list because that is something we reserve the right to change. You might want to compare the equality with a HashSet or a sorted list though.

I am glad the hard-coded edge order didn't affect your PR though.

Thanks for the feedback -- I ended up adding two functions to do this for directed and undirected graphs.

rustworkx-core/src/generators/hexagonal_lattice_graph.rs

mtreinish · 2024-06-13T12:00:24Z

Can you leave a comment on #803 so we can assign the issue to you for unitaryhack?

coveralls · 2024-06-13T12:20:49Z

Pull Request Test Coverage Report for Build 9459717092

Warning: This coverage report may be inaccurate.

This pull request's base commit is no longer the HEAD commit of its target branch. This means it includes changes from outside the original pull request, including, potentially, unrelated coverage changes.

For more information on this, see Tracking coverage changes with pull request builds.
To avoid this issue with future PRs, see these Recommended CI Configurations.
For a quick fix, rebase this PR at GitHub. Your next report should be accurate.

Details

52 of 53 (98.11%) changed or added relevant lines in 2 files are covered.
7 unchanged lines in 2 files lost coverage.
Overall coverage decreased (-0.004%) to 95.866%

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
src/generators.rs	8	9	88.89%

Files with Coverage Reduction	New Missed Lines	%
rustworkx-core/src/generators/hexagonal_lattice_graph.rs	1	98.72%
src/shortest_path/all_pairs_bellman_ford.rs	6	95.53%

Totals
Change from base Build 9450395122:	-0.004%
Covered Lines:	17369
Relevant Lines:	18118

💛 - Coveralls

jpacold · 2024-06-13T13:31:50Z

Hi @mtreinish -- I can do that, though I'm not sure about closing the issue since the with_positions part of this is still not done. It's fine with me if that ends up taking longer than the unitaryhack deadline.

jpacold · 2024-06-18T07:00:45Z

I tried adding the with_positions argument, and got something that works. However, I think I need some help here since it seems like there should be a better way to do this.

In Rust we started with this function

pub fn hexagonal_lattice_graph<G, T, F, H, M>(
    rows: usize,
    cols: usize,
    default_node_weight: F,
    default_edge_weight: H,
    bidirectional: bool,
    periodic: bool,
) -> Result<G, InvalidInputError>
where
    G: Build + Create + Data<NodeWeight = T, EdgeWeight = M> + NodeIndexable,
    F: FnMut() -> T,
    H: FnMut() -> M,
    G::NodeId: Eq + Hash,

Coming from C++, I really wanted to change the argument default_node_weight to something analogous to std::variant<FNoArgs, FTwoArgs>, where FNoArgs would be constrained to FnMut() -> T and FTwoArgs would be constrained to FnMut(usize, usize) -> T. However, I couldn't find a way to do this with the Rust traits system.

I ended up adding a second function

pub fn hexagonal_lattice_graph_weighted<G, T, F, H, M>(
    rows: usize,
    cols: usize,
    node_weight: F,
    default_edge_weight: H,
    bidirectional: bool,
    periodic: bool,
) -> Result<G, InvalidInputError>
where
    G: Build + Create + Data<NodeWeight = T, EdgeWeight = M> + NodeIndexable,
    F: FnMut(usize, usize) -> T,
    H: FnMut() -> M,
    G::NodeId: Eq + Hash,

and factoring out as much of the shared logic as possible into a builder object. This makes it possible to match the functionality in networkx, but seems like an awkward design and leads to some really messy code in generators.rs.

coveralls · 2024-06-18T18:59:24Z

Pull Request Test Coverage Report for Build 9567412491

Details

126 of 212 (59.43%) changed or added relevant lines in 2 files are covered.
3 unchanged lines in 1 file lost coverage.
Overall coverage decreased (-0.4%) to 95.41%

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
src/generators.rs	20	49	40.82%
rustworkx-core/src/generators/hexagonal_lattice_graph.rs	106	163	65.03%

Files with Coverage Reduction	New Missed Lines	%
rustworkx-core/src/generators/hexagonal_lattice_graph.rs	3	66.85%

Totals
Change from base Build 9565715860:	-0.4%
Covered Lines:	17419
Relevant Lines:	18257

💛 - Coveralls

IvanIsCoding

The test cases look pretty strong and give me confidence that this code is correct.

There are some minor details like using the utils module, leaving ToDos, we don't have a release note, etc. But in the grand scheme of things, this is a great addition I want to be in the 0.15 release

IvanIsCoding · 2024-06-26T01:32:42Z

rustworkx-core/src/generators/hexagonal_lattice_graph.rs

@@ -17,19 +17,200 @@ use petgraph::visit::{Data, NodeIndexable};

 use super::InvalidInputError;

+mod utils {


I don't really think we need this module, it could be include with the rest of the code. But that is a minor detail for now

IvanIsCoding · 2024-06-26T01:33:38Z

tests/generators/test_hexagonal.py

+        """In a periodic hexagonal lattice, all nodes must have
+        degree 3 (idea copied from the networkx test suite)."""
+        for nRows in range(2, 8):
+            for nCols in range(2, 8, 2):


These should be subtests but it's something we can fix later

IvanIsCoding · 2024-06-26T01:33:50Z

tests/generators/test_hexagonal.py

+        lattice graph, so here we check that the results from rustworkx and
+        networkx are isomorphic for a few cases."""
+        for nRows in range(2, 8):
+            for nCols in range(2, 8, 2):


These should be subtests but it's something we can fix later

coveralls · 2024-06-26T01:51:47Z

Pull Request Test Coverage Report for Build 9672159077

Details

126 of 212 (59.43%) changed or added relevant lines in 2 files are covered.
3 unchanged lines in 1 file lost coverage.
Overall coverage decreased (-0.4%) to 95.445%

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
src/generators.rs	20	49	40.82%
rustworkx-core/src/generators/hexagonal_lattice_graph.rs	106	163	65.03%

Files with Coverage Reduction	New Missed Lines	%
rustworkx-core/src/generators/hexagonal_lattice_graph.rs	3	66.85%

Totals
Change from base Build 9664932909:	-0.4%
Covered Lines:	17936
Relevant Lines:	18792

💛 - Coveralls

jpacold · 2024-06-26T07:57:50Z

Thanks for approving the PR -- should I open another issue for the remaining ToDos or just open a second PR once I get to them?

IvanIsCoding · 2024-06-26T10:16:22Z

Thanks for approving the PR -- should I open another issue for the remaining ToDos or just open a second PR once I get to them?

Sure, you can make a second PR if you want to clean up the code

* use closure for `graph.add_edge` calls * Add periodicity * check input, adjust Python exception type * add Rust tests * Update type annotations, add Python tests * Test for isomorphism with networkx graphs * make tests insensitive to edge order * move construction of graph and nodes into a builder * move construction of edges into builder * add `hexagonal_lattice_graph_weighted`, update tests * add `with_positions` argument to Python functions * add visualization tests, fix lattice position bug --------- Co-authored-by: Ivan Carvalho <8753214+IvanIsCoding@users.noreply.github.com>

jpacold added 8 commits June 7, 2024 00:45

use closure for graph.add_edge calls

7ca8c99

Add periodicity

b6391f7

check input, adjust Python exception type

24eba5e

Merge branch 'Qiskit:main' into main

e81cf1a

Merge branch 'main' of https://github.com/jpacold/rustworkx into main

fc28fe8

add Rust tests

05b1570

Update type annotations, add Python tests

1156b89

Test for isomorphism with networkx graphs

659c2df

IvanIsCoding reviewed Jun 10, 2024

View reviewed changes

jpacold added 2 commits June 10, 2024 22:37

make tests insensitive to edge order

6497d44

Merge branch 'main' into main

16d32fb

jpacold marked this pull request as ready for review June 13, 2024 13:32

jpacold mentioned this pull request Jun 13, 2024

Add support to hexagonal_lattice_graph for periodcity and position coordinates #803

Closed

jpacold added 5 commits June 17, 2024 16:33

move construction of graph and nodes into a builder

f9c2374

move construction of edges into builder

eae3aa9

add hexagonal_lattice_graph_weighted, update tests

f6cef80

add with_positions argument to Python functions

03b053b

add visualization tests, fix lattice position bug

393e0e2

Merge branch 'Qiskit:main' into main

03a078a

mtreinish added this to the 0.15.0 milestone Jun 21, 2024

mtreinish requested a review from IvanIsCoding June 25, 2024 17:29

mtreinish assigned IvanIsCoding Jun 25, 2024

IvanIsCoding approved these changes Jun 26, 2024

View reviewed changes

Merge branch 'main' into main

9acd776

IvanIsCoding added the automerge Queue a approved PR for merging label Jun 26, 2024

IvanIsCoding merged commit ed3cb8f into Qiskit:main Jun 26, 2024

IvanIsCoding mentioned this pull request Jun 26, 2024

Add periodic, with_positions to hexagonal_lattice_graph #1207

Closed

IvanIsCoding mentioned this pull request Jun 27, 2024

Prepare 0.15.0 release #1228

Merged

1 task

jpacold mentioned this pull request Jun 28, 2024

Hexagonal lattice followup #1232

Merged

		@@ -17,19 +17,200 @@ use petgraph::visit::{Data, NodeIndexable};

		use super::InvalidInputError;

		mod utils {

Add periodic to hexagonal_lattice_graph #1213

Add periodic to hexagonal_lattice_graph #1213

Uh oh!

Conversation

jpacold commented Jun 10, 2024

Uh oh!

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

Uh oh!

Pull Request Test Coverage Report for Build 9442230137

Details

💛 - Coveralls

Uh oh!

IvanIsCoding left a comment

Choose a reason for hiding this comment

Uh oh!

IvanIsCoding Jun 10, 2024

Choose a reason for hiding this comment

Uh oh!

jpacold Jun 13, 2024

Choose a reason for hiding this comment

Uh oh!

IvanIsCoding Jun 10, 2024

Choose a reason for hiding this comment

Uh oh!

jpacold Jun 11, 2024

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

mtreinish commented Jun 13, 2024

Uh oh!

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

Uh oh!

Pull Request Test Coverage Report for Build 9459717092

Warning: This coverage report may be inaccurate.

Details

💛 - Coveralls

Uh oh!

jpacold commented Jun 13, 2024

Uh oh!

jpacold commented Jun 18, 2024

Uh oh!

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

Uh oh!

Pull Request Test Coverage Report for Build 9567412491

Details

💛 - Coveralls

Uh oh!

IvanIsCoding left a comment

Choose a reason for hiding this comment

Uh oh!

IvanIsCoding Jun 26, 2024

Choose a reason for hiding this comment

Uh oh!

IvanIsCoding Jun 26, 2024

Choose a reason for hiding this comment

Uh oh!

IvanIsCoding Jun 26, 2024

Choose a reason for hiding this comment

Uh oh!

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

Uh oh!

Pull Request Test Coverage Report for Build 9672159077

Details

💛 - Coveralls

Uh oh!

jpacold commented Jun 26, 2024

Uh oh!

IvanIsCoding commented Jun 26, 2024

Uh oh!

Uh oh!

Add `periodic` to `hexagonal_lattice_graph` #1213

Add `periodic` to `hexagonal_lattice_graph` #1213

coveralls commented Jun 10, 2024 •

edited

Loading

coveralls commented Jun 13, 2024 •

edited

Loading

coveralls commented Jun 18, 2024 •

edited

Loading

coveralls commented Jun 26, 2024 •

edited

Loading