Summary

Long-time listener, first-time caller here. I am a happy user of GraphMap, as it is proving invaluable in a project I'm working on. However, it's a bit unwieldy to apply concurrent algorithms to it. Petgraph would be even better if it had easy to use parallel algorithms. Adding Rayon-based parallel iterators to petgraph's public API will let users take advantage of multi-core systems. I'm happy to do this myself and submit PRs, but I'd like to gauge the community's interest first.

Motivation

The motivation is improving performance of GraphMap on multi-core systems. Under the hood, GraphMap uses indexmap, which already exposes parallel iterators, behind a feature flag, and that feature flag causes indexmap to take a dependency on rayon.

Details

• What code needs to change? New traits? Which modules?

  • A dependency on Rayon must be added.
    • Behind a feature flag, just like indexmap, so that users can opt in and don't require a dependency on rayon.
  • The public API of GraphMap should expose parallel iterators over nodes and edges.
    • by either hoisting indexmap's parallel iterators or through some layer of indirection that prevents the need to re-export indexmap's types.

• Is this a new graph algorithm? Include links to papers, Wikipedia, or other
  implementations of this algorithm that exist.

  • No.

• Are you willing to implement this yourself? Mentor someone else and help them
  implement it?

  • Yes.