Hi!

Thank you all for creating such an incredible library. I use petgraph nearly on a day-to-day basis in both my professional and personal projects. After observing progress (and the different issues) over the last couple of months, I thought that it might make sense for me to contribute to petgraph itself, not only potentially adding some new functionality but also maybe lead petgraph into a new direction while maintaining its usefulness and broad adoption.

After thinking about it, I have come up with some action points I'd like to realize, and I know they are pretty drastic. Nevertheless, to not duplicate work or implementation, it makes sense to build onto the foundation of the existing petgraph.

If this is suitable for this crate, please let me know, and I'll start working on it. I still have some open questions, like:

• How would we go about code review/PRs? Do I create intermittent PRs that add functionality, slowly transforming everything, or have one big blob that will then be reviewed/merged?
• Should this be done on the main branch? (maybe a dedicated next branch might make sense)
• I want to commit to being a long-term maintainer of the crate. Is this alright? Is this okay?

Thank you so much for considering all of this! (and I guess this is where I need to mention @bluss?) I look forward to working with you all!

I am open to having a lively discussion and going more in-depth, potentially leading to a change in plans.

Plan

1. Reorganization

Split up the crate:

• petgraph-core: Includes all traits. To reduce churn, we should consider stabilizing this first and avoid breaking changes. This way, other crates can feel comfortable implementing their algorithms onto it.
• petgraph-graph: includes Graph and StableGraph (as they are commonly used interchangeably, I'd bundle them in a single crate)
• petgraph-adjacency-list: includes List
• petgraph-csr: includes CSR graph
• petgraph-graphmap: includes GraphMap
• petgraph-matrix: includes MatrixGraph (name might need changes, to not confuse with matrices in a non-graph type sense)
• petgraph-algorithms: includes all algorithms currently in petgraph; we might want to feature gate them (not only scc and friends, but also, if possible, Bfs)
• petgraph-dot: support for dot writing (and maybe reading in the future)
• petgraph: re-export of all sub-crates, main entry point for binaries

(names are ofc up to debate)

2. GATification (#552)

This would raise the MSRV to 1.65 but enable a lot more flexibility; every trait that could benefit from this should be converted into its GAT form, allowing things like mutable vs. reference access.

3. Trait rework (#552)

Think if we can extend the current set of traits to enable more flexible approaches, things like: Filter, FilterMap, and Map as traits.

IMO there are a lot of valuable traits that are hidden or need to be correctly explained. I want to surface traits more as well as adequately describe them. Some traits, like IntoNeighbours, are (again IMO) named quite misleading. While technically correct, it is only implemented for &Graph and friends, meaning it is non-consuming (even tho Into as a trait is consuming).

We should also look at all functions implemented directly and see if we can reconcile them into traits. Even marker traits may be of use.

4. Backlog Bonanza

Over the past few months (/ year?), many issues and pull requests have been opened once the new foundation of the crate has been created. I want to go through all issues and address (or close them).

5. My friend, my foe NetworkX

I enjoy the NetworkX library from Python, and I miss some of the capabilities it provided; as a long-term plan, I'd love to be able to use similar functionality in Rust. I think petgraph has the potential to live up to it.

This includes the rich set of graph algorithms it provides. I want petgraph to be able to do most of the possible things in NetworkX. I want to implement most of the functions and generators that NetworkX provides (and even some novel ones?) so that petgraph is a comprehensive toolkit for graph analysis.

6. no-std

Judging from the issues (and my own selfish needs), I think no-std is a somewhat important goal for such a "fundamental" library and enables the use of petgraph in many more use cases. Initially, I'd like petgraph to be available with alloc (I don't think that should be too hard™). In the future, we might be able also to make alloc opt-in, creating a separate crate for, e.g., fixed-size graphs or use of the nightly allocator API.

7. CI

While doing some major rework on the library itself, I'd like to touch up some areas, adding more tests, benchmarks, and coverage statistics, as well as tests using cargo-hack to ensure that all feature permutations work.

8. Documentation Touchup

I think the existing documentation is already excellent, but the docs in the lib.rs file do not adequately introduce the available traits, etc.; while doing this rework, I'd like to review the docs and add some sections.

Timeline

This would most definitely be a breaking change (warranting a 0.7.0 release). 1-3 are more immediate goals, while I'd like to focus on 4-8 longer term.

I guess that 1-3 might take one to three months maximum, depending on review speed, discussions, etc., for 4-8, as they are more of an ongoing effort, I have no time guesstimate.