Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Add max_weight_matching function #216

Closed
mtreinish opened this issue Dec 7, 2020 · 1 comment · Fixed by #229
Closed

Add max_weight_matching function #216

mtreinish opened this issue Dec 7, 2020 · 1 comment · Fixed by #229
Assignees
@mtreinish
Labels
enhancement New feature or request
Milestone
0.8.0

Comments

@mtreinish
Copy link
Member

What is the expected enhancement?

retworkx is missing a max_weight_matching() function, similar to networkx's function: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.matching.max_weight_matching.html?highlight=max_weight_matching#networkx.algorithms.matching.max_weight_matching

This is currently a blocker from removing the last networkx usage from qiskit in qiskit-ignis. Specifically this function is used here:: https://github.com/Qiskit/qiskit-ignis/blob/master/qiskit/ignis/verification/topological_codes/fitters.py#L298
@mtreinish mtreinish added enhancement New feature or request good first issue Good for newcomers labels Dec 7, 2020
mtreinish added a commit to mtreinish/qiskit-ignis that referenced this issue Dec 7, 2020
@mtreinish
Add missing networkx dependency
1443042 
The topological_code fitters module relies on networkx and has had a
hard dependency on it since it was first introduced in qiskit-community#211. However, it
was never added to the requirements list. This was never caught because
historically qiskit-terra (which is in the requirements list) has
required networkx too so installing qiskit-terra would install networkx.
But, in Qiskit/qiskit#5183 the dependency on networkx was removed
from terra. This commit corrects the issue so that we're properly
listing networkx as an ignis requirement moving forward. Longer term we
should migrate the topological codes fitter to use retworkx for better
performance and consistency with the rest of Qiskit. However, before we
can do that Qiskit/rustworkx#216 must be fixed first.
@mtreinish mtreinish mentioned this issue Dec 7, 2020
Merged
@mtreinish
Copy link
Member Author

The networkx implementation of this function is here: https://github.com/networkx/networkx/blob/3351206a3ce5b3a39bb2fc451e93ef545b96c95b/networkx/algorithms/matching.py

mtreinish added a commit to qiskit-community/qiskit-ignis that referenced this issue Dec 7, 2020
@mtreinish
Add missing networkx dependency (#543)
2775689 
The topological_code fitters module relies on networkx and has had a
hard dependency on it since it was first introduced in #211. However, it
was never added to the requirements list. This was never caught because
historically qiskit-terra (which is in the requirements list) has
required networkx too so installing qiskit-terra would install networkx.
But, in Qiskit/qiskit#5183 the dependency on networkx was removed
from terra. This commit corrects the issue so that we're properly
listing networkx as an ignis requirement moving forward. Longer term we
should migrate the topological codes fitter to use retworkx for better
performance and consistency with the rest of Qiskit. However, before we
can do that Qiskit/rustworkx#216 must be fixed first.
@mtreinish mtreinish modified the milestones: 0.7.0, 0.8.0 Jan 11, 2021
mtreinish added a commit to mtreinish/retworkx that referenced this issue Jan 17, 2021
@mtreinish
Add max weight matching function
b231289 
This commit adds a new python function max_weight_function() for
computing the maximum-weighted matching of a PyGraph object. The
implementation of this function is based on “Efficient Algorithms for
Finding Maximum Matching in Graphs”, Zvi Galil, ACM Computing Surveys,
1986. [1] It is basically a porting of the networkx implementation of
the algorithm [2] with some additional inspiration from the prototype for
the networkx version (it's basically the same code but some aspects were
a bit clearer to figure out from the prototype rather than networkx's
copy of it). [3][4]

Fixes Qiskit#216

[1] https://dl.acm.org/doi/10.1145/6462.6502
[2] https://github.com/networkx/networkx/blob/3351206a3ce5b3a39bb2fc451e93ef545b96c95b/networkx/algorithms/matching.py
[3] http://jorisvr.nl/article/maximum-matching
[4] http://jorisvr.nl/files/graphmatching/20130407/mwmatching.py
@mtreinish mtreinish mentioned this issue Jan 17, 2021
Merged
2 tasks
mtreinish added a commit to mtreinish/retworkx that referenced this issue Jan 17, 2021
@mtreinish
Add max weight matching function
481f99a 
This commit adds a new python function max_weight_function() for
computing the maximum-weighted matching of a PyGraph object. The
implementation of this function is based on “Efficient Algorithms for
Finding Maximum Matching in Graphs”, Zvi Galil, ACM Computing Surveys,
1986. [1] It is basically a porting of the networkx implementation of
the algorithm [2] with some additional inspiration from the prototype for
the networkx version (it's basically the same code but some aspects were
a bit clearer to figure out from the prototype rather than networkx's
copy of it). [3][4]

Fixes Qiskit#216

[1] https://dl.acm.org/doi/10.1145/6462.6502
[2] https://github.com/networkx/networkx/blob/3351206a3ce5b3a39bb2fc451e93ef545b96c95b/networkx/algorithms/matching.py
[3] http://jorisvr.nl/article/maximum-matching
[4] http://jorisvr.nl/files/graphmatching/20130407/mwmatching.py
mtreinish added a commit to mtreinish/retworkx that referenced this issue Jan 17, 2021
@mtreinish
Add max weight matching function
98fa26e 
This commit adds a new python function max_weight_function() for
computing the maximum-weighted matching of a PyGraph object. The
implementation of this function is based on “Efficient Algorithms for
Finding Maximum Matching in Graphs”, Zvi Galil, ACM Computing Surveys,
1986. [1] It is basically a porting of the networkx implementation of
the algorithm [2] with some additional inspiration from the prototype for
the networkx version (it's basically the same code but some aspects were
a bit clearer to figure out from the prototype rather than networkx's
copy of it). [3][4]

Fixes Qiskit#216

[1] https://dl.acm.org/doi/10.1145/6462.6502
[2] https://github.com/networkx/networkx/blob/3351206a3ce5b3a39bb2fc451e93ef545b96c95b/networkx/algorithms/matching.py
[3] http://jorisvr.nl/article/maximum-matching
[4] http://jorisvr.nl/files/graphmatching/20130407/mwmatching.py
@mtreinish mtreinish removed the good first issue Good for newcomers label Jan 17, 2021
@mtreinish mtreinish self-assigned this Jan 17, 2021
mtreinish added a commit to mtreinish/qiskit-ignis that referenced this issue Feb 5, 2021
@mtreinish
Add missing networkx dependency (qiskit-community#543)
30a385f 
The topological_code fitters module relies on networkx and has had a
hard dependency on it since it was first introduced in qiskit-community#211. However, it
was never added to the requirements list. This was never caught because
historically qiskit-terra (which is in the requirements list) has
required networkx too so installing qiskit-terra would install networkx.
But, in Qiskit/qiskit#5183 the dependency on networkx was removed
from terra. This commit corrects the issue so that we're properly
listing networkx as an ignis requirement moving forward. Longer term we
should migrate the topological codes fitter to use retworkx for better
performance and consistency with the rest of Qiskit. However, before we
can do that Qiskit/rustworkx#216 must be fixed first.

(cherry picked from commit 2775689)
mtreinish added a commit that referenced this issue Feb 25, 2021
@mtreinish @itoko
Add max weight matching function (#229)
7e889b2 
* Add max weight matching function

This commit adds a new python function max_weight_function() for
computing the maximum-weighted matching of a PyGraph object. The
implementation of this function is based on “Efficient Algorithms for
Finding Maximum Matching in Graphs”, Zvi Galil, ACM Computing Surveys,
1986. [1] It is basically a porting of the networkx implementation of
the algorithm [2] with some additional inspiration from the prototype for
the networkx version (it's basically the same code but some aspects were
a bit clearer to figure out from the prototype rather than networkx's
copy of it). [3][4]

Fixes #216

[1] https://dl.acm.org/doi/10.1145/6462.6502
[2] https://github.com/networkx/networkx/blob/3351206a3ce5b3a39bb2fc451e93ef545b96c95b/networkx/algorithms/matching.py
[3] http://jorisvr.nl/article/maximum-matching
[4] http://jorisvr.nl/files/graphmatching/20130407/mwmatching.py

* Fix most of the test panics

This commit fixes all but 2 of the test panics. There were 2 classes of
issues that his commit fixes (both were artifacts of sloppy porting from
Python). The first is that in add_blossom() we were not updating the
global blossom_children or the global blossom_endpoints while iterating
over the list. Instead we were just setting a local. The second issue
was negative indices for Vecs. The python code was iterating over
elements in a vec in expand_blossom() and augment_blossom() by
subtracting a length or step from the index which could result in a
negative value. In Python this is fine since a negative index is just
the from the last element. But, for rust we need to handle this behavior
manually because the Index trait only deals with usize.

* Fix panic in one test

* Remove unused verify_optimum() function

* Remove unnecessary BlossomList struct and just use Vec<Vec<usize>>

* Fix tests

* Fix docs build

* Fix typos in code comments

* Fix handling of holes in node indices and add test

This commit fixes an issue when running max_weight_matching on a graph
with holes in the node indices (i.e. when
'node_count() != max(node_indices)'). The in_blossoms vec was being
initialized from the contents of the node_indices iterator of the graph
but the algorithm remaps the indices to be a contiguous list for the
internals to work. When a hole was encountered accessing in_blossoms
would panic because the index returned wouldn't match the expecated
state. This is fixed and a test added to make sure we have coverage on
input graphs with holes.

* Add test to compare output with random graph to networkx

* Use tox for non-x86 travis ci jobs

* Add networkx to coverage job

* Update src/max_weight_matching.rs

Co-authored-by: itoko <itoko@jp.ibm.com>

* Also reset label_ends on each stage iteration

* Update src/max_weight_matching.rs

Co-authored-by: itoko <itoko@jp.ibm.com>

* Add more details to dual_var comment

* Add more random graph test cases

This commit adds more random graph test cases that catch some failures.
These tests still fail and will need to be fixed before we can move
forward on this.

* Change output format to a set of tuples

* Clean up from review comments

Co-authored-by: itoko <itoko@jp.ibm.com>

* Add back verify_optimum() function and make it an optional flag

This commit adds back the verify_optimum solution to check that the
found matching is a optimum solution. An earlier draft of this function
was included in prior commits but was removed because it was never run.
This fixes the issues with the earlier draft and also makes it an opt-in
option for users. By default it is not run, but if a user specifies they
want the verification run there is a flag on the python API function to
enable it. This flag is then used on all the tests calls (except where
it's explicitly tested as False to exercise that code path).

* Fix test lint

* Fallback to checking valid matching and optimum result

In the unit tests that compare the output of running against networkx if
there are multiple valid maximum weight matchings in the random graph
the results between networkx and retworkx can differ but both still be
valid. This commit modifies the tests to validate in those cases that
the output from retworkx is still a valid maximal matching and relying
on the verify_optimum flag to ensure the output result is optimal we
should have confidence that the result is valid.

* Fix test lint

* Use HashMap for mate instead of Vec

* Switch best_edge_to to HashMap

* Add test with weights

* Fix nx miss check

* Add max cardinality random weight test

* Add random test cases with negative weights too

* Use subtest for each iteration of random loop

* Add missing tox install to travis config

Co-authored-by: itoko <itoko@jp.ibm.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@mtreinish mtreinish

Labels
enhancement New feature or request
Projects
None yet
Milestone
0.8.0
Development

Successfully merging a pull request may close this issue.

Add max weight matching function mtreinish/retworkx
1 participant
@mtreinish