Add EdgeList and WeightedEdgeList return types #204

mtreinish · 2020-11-19T19:44:56Z

This commit adds 2 new return types EdgeList and WeightedEdgeList
that are used as the return type for functions that return
Vec<(usize, usize)> and Vec<(usize, usize, PyObject)> respectively.
This custom type implements the Python sequence protocol and can be
used as the list which was previously returned except for where
explicit type checking was used. Just as in #185 and #198 the
advantage here is that for large edge lists the conversion from
Rust to a Python type becomes a large bottleneck. This avoids that
conversion and only does it per element on access.

This commit adds 2 new return types EdgeList and WeightedEdgeList that are used as the return type for functions that return Vec<(usize, usize)> and Vec<(usize, usize, PyObject)> respectively. This custom type implements the Python sequence protocol and can be used as the list which was previously returned except for where explicit type checking was used. Just as in Qiskit#185 and Qiskit#198 the advantage here is that for large edge lists the conversion from Rust to a Python type becomes a large bottleneck. This avoids that conversion and only does it per element on access.

coveralls · 2020-11-19T20:00:30Z

Pull Request Test Coverage Report for Build 396070856

106 of 109 (97.25%) changed or added relevant lines in 5 files are covered.
No unchanged relevant lines lost coverage.
Overall coverage increased (+0.02%) to 94.729%

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
src/iterators.rs	54	57	94.74%

Totals
Change from base Build 390508636:	0.02%
Covered Lines:	3019
Relevant Lines:	3187

💛 - Coveralls

In Qiskit/rustworkx#204 the return type of the edge_list() method will be returned as a custom sequence type the defer the type conversion from rust to python. So casting to a list no longer will be a no-op after that point so this commit removes the cast. At the same time in the sabre swap pass one of the bottlenecks at large qubit counts is traversing that edge list looking for edges, this updates that to use the has_edge() method which should be faster than a full list traversal every iteration.

src/lib.rs

lcapelluto · 2020-12-01T22:02:48Z

src/union.rs

@@ -62,7 +62,7 @@ pub fn digraph_union(
        node_map.insert(node.index(), node_index);
    }

-    for edge in b.weighted_edge_list(py) {
+    for edge in b.weighted_edge_list(py).edges {


Why is this the only place where .edges is needed? Is this the only place where weighted_edge_list() was used?

Yeah, this is the only place weighted_edge_list() is called from inside rust. Normally it's only used from python but this function uses it instead of calling b.graph..edge_references(). We probably should update this to just use the petgraph api directly, but it's not a big deal and an easy followup thing we can change later.

src/iterators.rs

Co-authored-by: Lauren Capelluto <laurencapelluto@gmail.com>

itoko · 2020-12-02T08:07:33Z

LGTM. Just out of curiosity, I found pub fn in_edges(&self, node: usize) -> Vec<(usize, usize, &PyObject)>, which is not touched in this PR. Although I think it's ok because the type &PyObject is different from PyObject (weight type in EdgeWeightList), where does this difference in weight types come from?

mtreinish · 2020-12-02T12:07:52Z

LGTM. Just out of curiosity, I found pub fn in_edges(&self, node: usize) -> Vec<(usize, usize, &PyObject)>, which is not touched in this PR. Although I think it's ok because the type &PyObject is different from PyObject (weight type in EdgeWeightList), where does this difference in weight types come from?

Oh I missed that, I just searched for the exact matches on the return and did a find replace on them. The difference is really just between where reference counting increments happen. I'll update that when I fix the remaining docstring issues @lcapelluto pointed out.

That function retuning &PyObject (it originally comes from the petgraph method since it's returning a reference to the weight object in the graph not moving it out from the graph struct) means for any rust code callers they get a borrowed PyObject and have to managed the lifetime of that borrow. But for python it doesn't matter because pyo3's #[pymethods] macro generates a wrapper for us to handle the borrow and return the pyobject properly to python. The WeightedEdgeList struct can only have a Vec with owned PyObject it's a current limitation with pyo3. The change here is simple I think, we should just need to call clone()/clone_ref() on the weight to increment the python refcount when creating the Vec.

mtreinish · 2020-12-02T12:41:44Z

I've updated in_edges and out_edges to use the new return type in: 407bd59 there was a small complication with merge_nodes which was using those functions directly. I had to update that to use the petgraph api directly because of the rust side changes to those methods.

lcapelluto · 2020-12-02T18:42:53Z

src/digraph.rs

-                }
-
-                for edge in edges {
+                for edge in self.graph.edges_directed(NodeIndex::new(u), *dir) {


lcapelluto · 2020-12-02T18:43:51Z

src/digraph.rs

+                        edges_to_add.push((
+                            v,
+                            d.index(),
+                            edge.weight().clone_ref(py),


Why clone_ref? Also, why does index() have to be added here but not before?

Oh, is it just because in the previous commits this hadn't been added yet, and so the type was just changed? I'd have thought some tests would fail in that case, though.

This was working before because it was using clone() instead of clone_ref() Before this PR in_edges() and out_edges() were returning a Vec(usize, usize, &PyObject) and edges_to_add was a Vec(usize, usize, &PyObject) (it's just being used as a temp storage Vec before its used later to add edges). So prior to the changing in_edges() and out_edges() this worked by the 2 usizes implement copy so can efficiently be used in place without moving, but to store &PyObject as a PyObject (which is neededt for creating a new edge in the graph) it needs to take ownership of the object being borrowed. We can't do *edge.weight() since it would move the weight out of the graph (and would fail) so we need to clone/copy it which for PyObject isn't a big deal because it just increments the ref counter.

The change I made here (besides switching to petgraph method edges_directed instead of using in_edges and out_edges) is to switch just switch from clone() to clone_ref(py). There isn't a functional difference between them as they both increment the python reference counter for the object, except that you give a gil handle to clone_ref if you have it: https://github.com/PyO3/pyo3/blob/v0.12.4/src/instance.rs#L196-L200 while clone() will queue it for when there is one it doesn't already have it: https://github.com/PyO3/pyo3/blob/v0.12.4/src/instance.rs#L517-L524. In the context of this method I don't think there is any performance difference since it has a gil reference, I just prefer it to be explicit and use clone_ref when we already have py

Oh I missed the second half of the question. The index() calls are needed because the edges_to_add vec is defined as Vec<(usize, usize, PyObject)> and self.graph.edges_directed() returns an iterator yielding petgraph EdgeReference objects. Those objects return NodeIndex objects for source() and target() instead of usize ints. So to get the usize from the NodeIndex I had to call index() on it which returns a usize (since NodeIndex is just a wrapper around a usize anyay). This wasn't necessary before because in_edges() and out_edges returned a Vec<usize, usize, &PyObject)> and had already done the conversion from NodeIndex -> usize for us.

* WIP: Use retworkx for CouplingMap This commit migrates Terra's CouplingMap class to us retworkx internally instead of networkx providing >10x speed improvement for CouplingMap operations. Requires: Qiskit/rustworkx#157 Qiskit/rustworkx#156 Qiskit/rustworkx#144 Qiskit/rustworkx#143 Qiskit/rustworkx#147 Qiskit/rustworkx#158 Qiskit/rustworkx#162 Qiskit/rustworkx#161 all be applied to the retworkx version installed. * DNM: Install retworkx from source * DNM: Add retworkx custom branch to travis * Fix draw() copy paste error * Fix typo * DNK: Add source retworkx to docs build * Fix lint * Use graph_distance_matrix instead of floyd warshall * DNM also add retworkx from source for image test job * Use Gnm random function from retworkx in token swapper tests * Remove nx import from token swapper tests * Fix lint * Remove install from git from CI config since retworkx 0.6.0 is released * Fix api call * Use retworkx generators where possible for constructors * Remvoe source install from travis config * Bump version in setup.py too * Use extend_from_edge_list for from_full * Update qiskit/transpiler/coupling.py * Use edge_list() return and has_edge() in sabre In Qiskit/rustworkx#204 the return type of the edge_list() method will be returned as a custom sequence type the defer the type conversion from rust to python. So casting to a list no longer will be a no-op after that point so this commit removes the cast. At the same time in the sabre swap pass one of the bottlenecks at large qubit counts is traversing that edge list looking for edges, this updates that to use the has_edge() method which should be faster than a full list traversal every iteration. * Fix issue in layout_transformation pass In #5281 the layout transformation pass was updated to handle the case where the coupling map was not defined. In those cases for the purposes of the layout transformation it treats the coupling map as being fully connected. So it creates a new full coupling map to use for the token swapper. However, it neglects that the token swapper expects an undirected graph and was passing in a directed graph. This didn't matter too much for the networkx based coupling map object because networkx can handle directed or undirected in the same function. But, for retworkx directed graphs and undirected graphs are different types an can't be used interchangeably. This commit fixes this issue in that pass. * Update qiskit/transpiler/passes/routing/algorithms/token_swapper.py Co-authored-by: Julien Gacon <gaconju@gmail.com> * Fix Lint Co-authored-by: Julien Gacon <gaconju@gmail.com> Co-authored-by: Kevin Krsulich <kevin.krsulich@ibm.com> Co-authored-by: mergify[bot] <37929162+mergify[bot]@users.noreply.github.com>

mtreinish requested review from lcapelluto and itoko November 19, 2020 19:44

Add new return types to docs

fe00f51

mtreinish requested a review from kdk November 23, 2020 16:55

Merge branch 'master' into edgelist-types

d40a14f

Merge branch 'master' into edgelist-types

7483ee4

mtreinish added this to the 0.7.0 milestone Nov 29, 2020

Merge branch 'master' into edgelist-types

ca8db71

lcapelluto requested changes Dec 1, 2020

View reviewed changes

Apply suggestions from code review

44742c5

Co-authored-by: Lauren Capelluto <laurencapelluto@gmail.com>

lcapelluto self-assigned this Dec 1, 2020

mtreinish added 2 commits December 2, 2020 07:10

Fix docstring mistakes

a8d71c9

Update in_edges and out_edges to use WeightedEdgeList

407bd59

mtreinish requested a review from lcapelluto December 2, 2020 12:56

lcapelluto reviewed Dec 2, 2020

View reviewed changes

src/digraph.rs

}

for edge in edges {

for edge in self.graph.edges_directed(NodeIndex::new(u), *dir) {

Copy link

Collaborator

lcapelluto Dec 2, 2020

Choose a reason for hiding this comment

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

👍

lcapelluto reviewed Dec 2, 2020

View reviewed changes

lcapelluto approved these changes Dec 2, 2020

View reviewed changes

mtreinish merged commit c97afd2 into Qiskit:master Dec 2, 2020

mtreinish deleted the edgelist-types branch December 2, 2020 20:45

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Add EdgeList and WeightedEdgeList return types #204

Add EdgeList and WeightedEdgeList return types #204

Uh oh!

mtreinish commented Nov 19, 2020 •

edited

Loading

Uh oh!

coveralls commented Nov 19, 2020 •

edited

Loading

Uh oh!

Uh oh!

lcapelluto Dec 1, 2020

Uh oh!

mtreinish Dec 1, 2020

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

itoko commented Dec 2, 2020 •

edited

Loading

Uh oh!

mtreinish commented Dec 2, 2020

Uh oh!

mtreinish commented Dec 2, 2020

Uh oh!

lcapelluto Dec 2, 2020

Uh oh!

lcapelluto Dec 2, 2020

Uh oh!

lcapelluto Dec 2, 2020

Uh oh!

mtreinish Dec 2, 2020

Uh oh!

mtreinish Dec 2, 2020

Uh oh!

lcapelluto Dec 3, 2020

Uh oh!

Uh oh!

Add EdgeList and WeightedEdgeList return types #204

Add EdgeList and WeightedEdgeList return types #204

Uh oh!

Conversation

mtreinish commented Nov 19, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

coveralls commented Nov 19, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pull Request Test Coverage Report for Build 396070856

💛 - Coveralls

Uh oh!

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!

itoko commented Dec 2, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

mtreinish commented Dec 2, 2020

Uh oh!

mtreinish commented Dec 2, 2020

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!

mtreinish commented Nov 19, 2020 •

edited

Loading

coveralls commented Nov 19, 2020 •

edited

Loading

itoko commented Dec 2, 2020 •

edited

Loading