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

Serialize and deserialize graphs change order of the edges #585

Closed
binh-vu opened this issue Apr 12, 2022 · 2 comments · Fixed by #589
Closed

Serialize and deserialize graphs change order of the edges #585

binh-vu opened this issue Apr 12, 2022 · 2 comments · Fixed by #589
Assignees
@binh-vu
Labels
bug Something isn't working stable-backport-potential This PR or issue is potentially worth backporting for inclusion in a stable branch

Comments

@binh-vu
Copy link
Contributor

binh-vu commented Apr 12, 2022 •
edited
Loading

What is the expected enhancement?

The current serialization mechanism of PyDiGraph doesn't keep the original order of edges in the graph. This creates an issue for libraries that store the edge index inside the edge weight object (why need to store the edge index inside the edge weight object? it is easier to work with for graphs in which nodes/edges have lots of properties such as Wikidata). A graph is serialized and deserialized when using it in a multiprocess environment. After deserializing, the order of the edges changes and so edge indices stored inside edge weights do not match the new indices, thus messing up the graph.

I took a look at the serialization code here: https://github.com/Qiskit/retworkx/blob/a0aaa1f93ef21fe77dccee63cd37fdb8f43c7cee/src/digraph.rs#L283-L291 and I think we can maintain the original order by dumping the edges in a separated loop. This won't increase the runtime and maybe faster.

If you are okay with my propose, I am happy to create a PR for this if you don't have time. Thanks.
@mtreinish mtreinish added bug Something isn't working stable-backport-potential This PR or issue is potentially worth backporting for inclusion in a stable branch labels Apr 12, 2022
@mtreinish
Copy link
Member

Yeah, this is a good catch. We should be reconstructing the edge indices exactly via __getstate__ and __setstate__ right now it doesn't do that. I think probe the only catch will be for graphs with edge removals we'll have to reconstruct the holes in the indices caused by the removal. We do that for nodes already so we can adapt that code to work with edges too.

If you're willing to open a pr to fix this please go ahead, that would be great! We can target for get this out in a 0.11.1 release.

@mtreinish mtreinish assigned mtreinish and binh-vu and unassigned mtreinish Apr 12, 2022
binh-vu pushed a commit to binh-vu/retworkx that referenced this issue Apr 18, 2022
fix issue Qiskit#585 that pickling graph & digraph do not preserve or…
f3bc9f3 
…iginal edge index
@binh-vu binh-vu mentioned this issue Apr 18, 2022
Merged
@binh-vu
Copy link
Contributor Author

binh-vu commented Apr 18, 2022 •
edited
Loading

Ok, I submitted a PR that deals with the hole issue as you mentioned.

petgraph also has an implementation for serializing its internal state, but since PyObject doesn't implement Serialize trait, I can't use petgraph serialization. They has a function into_serializable that can be used as a work around for the PyObject issue and I think it will be faster. But unfortunately, their IntoSerializable trait is private.

mtreinish added a commit that referenced this issue May 9, 2023
@binh-vu @mtreinish
Fix pickle/deepcopy not preserve original edge indices (#589)
8686896 
* fix issue #585 that pickling graph & digraph do not preserve original edge index

* fix clippy lints - collapsible_else_if

* Simplify logic in __setstate__

* Add release note

* Fix lint

---------

Co-authored-by: Matthew Treinish <mtreinish@kortar.org>
IvanIsCoding pushed a commit to IvanIsCoding/rustworkx that referenced this issue May 12, 2023
@binh-vu @mtreinish @IvanIsCoding
Fix pickle/deepcopy not preserve original edge indices (Qiskit#589)
4c9d26e 
* fix issue Qiskit#585 that pickling graph & digraph do not preserve original edge index

* fix clippy lints - collapsible_else_if

* Simplify logic in __setstate__

* Add release note

* Fix lint

---------

Co-authored-by: Matthew Treinish <mtreinish@kortar.org>
mergify bot pushed a commit that referenced this issue May 12, 2023
@IvanIsCoding @mtreinish
@Eric-Arellano @binh-vu @dependabot @matanco64
Check if nodes exist on add_edge methods (#862)
e538391 
* Add tests from the example

* Fix bug

* Fix tests

* Add release note

* Update release note

* Apply suggestions from code review

Co-authored-by: Matthew Treinish <mtreinish@kortar.org>

* Fix docs to work with Sphinx Theme 1.11 (#867)

* Fix docs to work with Sphinx Theme 1.11

* Update docs/source/_templates/sidebar.html

Co-authored-by: Matthew Treinish <mtreinish@kortar.org>

* Turn off CI for forks (#868)

Co-authored-by: Matthew Treinish <mtreinish@kortar.org>

* Fix pickle/deepcopy not preserve original edge indices (#589)

* fix issue #585 that pickling graph & digraph do not preserve original edge index

* fix clippy lints - collapsible_else_if

* Simplify logic in __setstate__

* Add release note

* Fix lint

---------

Co-authored-by: Matthew Treinish <mtreinish@kortar.org>

* Bump serde from 1.0.160 to 1.0.162 (#863)

Bumps [serde](https://github.com/serde-rs/serde) from 1.0.160 to 1.0.162.
- [Release notes](https://github.com/serde-rs/serde/releases)
- [Commits](serde-rs/serde@v1.0.160...1.0.162)

---
updated-dependencies:
- dependency-name: serde
  dependency-type: direct:production
  update-type: version-update:semver-patch
...

Signed-off-by: dependabot[bot] <support@github.com>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
Co-authored-by: Matthew Treinish <mtreinish@kortar.org>

* Add reverse inplace function for digraph (#853)

* added a reverse_inplace function in digraph,

the function reverses the direction of the edges in the digraph
implemented by switching the indices of the nodes in an edge.

* added python tests for the reverse_inplace function.

testing a simple case and a case for a large graph.

* ran rust fmt and clippy, also added more detailed documentation

* rename reverse_inplace to reverse

* change excepts to unwraps (If this fails is because of PyO3. It panics and there is not much point in printing a message)

* added tests for empty graph and graph with node removed in the middle

* added interface signature for IDEs

* ran cargo fmt

* Fix doc syntax

---------

Co-authored-by: Matthew Treinish <mtreinish@kortar.org>

* Bump serde from 1.0.162 to 1.0.163 (#869)

Bumps [serde](https://github.com/serde-rs/serde) from 1.0.162 to 1.0.163.
- [Release notes](https://github.com/serde-rs/serde/releases)
- [Commits](serde-rs/serde@v1.0.162...v1.0.163)

---
updated-dependencies:
- dependency-name: serde
  dependency-type: direct:production
  update-type: version-update:semver-patch
...

Signed-off-by: dependabot[bot] <support@github.com>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>

* Extend fixes to add_edges_from and add_edges_from_no_data

* Lower amount of nodes in test

---------

Signed-off-by: dependabot[bot] <support@github.com>
Co-authored-by: Matthew Treinish <mtreinish@kortar.org>
Co-authored-by: Eric Arellano <14852634+Eric-Arellano@users.noreply.github.com>
Co-authored-by: Binh Vu <binh-vu@users.noreply.github.com>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
Co-authored-by: matanco64 <38103422+matanco64@users.noreply.github.com>
IvanIsCoding added a commit to IvanIsCoding/rustworkx that referenced this issue May 26, 2023
@IvanIsCoding @mtreinish
@Eric-Arellano @binh-vu @dependabot @matanco64
Check if nodes exist on add_edge methods (Qiskit#862)
71890f2 
* Add tests from the example

* Fix bug

* Fix tests

* Add release note

* Update release note

* Apply suggestions from code review

Co-authored-by: Matthew Treinish <mtreinish@kortar.org>

* Fix docs to work with Sphinx Theme 1.11 (Qiskit#867)

* Fix docs to work with Sphinx Theme 1.11

* Update docs/source/_templates/sidebar.html

Co-authored-by: Matthew Treinish <mtreinish@kortar.org>

* Turn off CI for forks (Qiskit#868)

Co-authored-by: Matthew Treinish <mtreinish@kortar.org>

* Fix pickle/deepcopy not preserve original edge indices (Qiskit#589)

* fix issue Qiskit#585 that pickling graph & digraph do not preserve original edge index

* fix clippy lints - collapsible_else_if

* Simplify logic in __setstate__

* Add release note

* Fix lint

---------

Co-authored-by: Matthew Treinish <mtreinish@kortar.org>

* Bump serde from 1.0.160 to 1.0.162 (Qiskit#863)

Bumps [serde](https://github.com/serde-rs/serde) from 1.0.160 to 1.0.162.
- [Release notes](https://github.com/serde-rs/serde/releases)
- [Commits](serde-rs/serde@v1.0.160...1.0.162)

---
updated-dependencies:
- dependency-name: serde
  dependency-type: direct:production
  update-type: version-update:semver-patch
...

Signed-off-by: dependabot[bot] <support@github.com>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
Co-authored-by: Matthew Treinish <mtreinish@kortar.org>

* Add reverse inplace function for digraph (Qiskit#853)

* added a reverse_inplace function in digraph,

the function reverses the direction of the edges in the digraph
implemented by switching the indices of the nodes in an edge.

* added python tests for the reverse_inplace function.

testing a simple case and a case for a large graph.

* ran rust fmt and clippy, also added more detailed documentation

* rename reverse_inplace to reverse

* change excepts to unwraps (If this fails is because of PyO3. It panics and there is not much point in printing a message)

* added tests for empty graph and graph with node removed in the middle

* added interface signature for IDEs

* ran cargo fmt

* Fix doc syntax

---------

Co-authored-by: Matthew Treinish <mtreinish@kortar.org>

* Bump serde from 1.0.162 to 1.0.163 (Qiskit#869)

Bumps [serde](https://github.com/serde-rs/serde) from 1.0.162 to 1.0.163.
- [Release notes](https://github.com/serde-rs/serde/releases)
- [Commits](serde-rs/serde@v1.0.162...v1.0.163)

---
updated-dependencies:
- dependency-name: serde
  dependency-type: direct:production
  update-type: version-update:semver-patch
...

Signed-off-by: dependabot[bot] <support@github.com>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>

* Extend fixes to add_edges_from and add_edges_from_no_data

* Lower amount of nodes in test

---------

Signed-off-by: dependabot[bot] <support@github.com>
Co-authored-by: Matthew Treinish <mtreinish@kortar.org>
Co-authored-by: Eric Arellano <14852634+Eric-Arellano@users.noreply.github.com>
Co-authored-by: Binh Vu <binh-vu@users.noreply.github.com>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
Co-authored-by: matanco64 <38103422+matanco64@users.noreply.github.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@binh-vu binh-vu

Labels
bug Something isn't working stable-backport-potential This PR or issue is potentially worth backporting for inclusion in a stable branch
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Fix pickle/deepcopy not preserve original edge indices binh-vu/retworkx
2 participants
@mtreinish @binh-vu