This Proposal/RFC is not slated for 0.7 but is something we should consider for 0.8+, thanks to @pnevyk for the initial idea.

Abstract

This does not intend to replace #552, but rather supplement it.

Instead of having a single type for every single type of "storage" (which is what we currently have), we have a new entry point: Graph, not to be confused with the current Graph, which is generic over its storage and implements all traits.

This has several upsides:

1. Instead of needing to implement every single trait (which is quite a lot of boilerplate), we instead only need to implement them once and expose a minimal subset to interact with the graph over the storage API
2. Implementing new representations is a lot easier.
3. The disparity between different representations and what they implement is removed.

The goal is to keep the traits in petgraph-core and simply implement them, this way graph types that cannot adhere to the storage API, due to limitations, can still be used and integrations outside of petgraph are easily possible.

Explanation

petgraph-core introduces a new trait Storage. petgraph-csr, petgraph-adjacency-matrix, petgraph-graph all implement Storage, and deprecate the old implementations.

ideally we'd also be able to port petgraph-graphmap over.

We introduce a new type (in a new crate, or replace the existing petgraph-graph crate), which exposes a single type Graph<S>, Graph<S> would implement all traits necessary.

pub struct Graph<S: Storage> {
	inner: S
}

impl<S> Graph<S> where S: Storage {
	fn new_in(storage: S) -> Self;
}

impl GraphLen for S {}

the Storage trait is a minimal representation and interface into the underlying storage, looking somewhat like this:

// already in core
pub enum Direction {}
// proposed in iterator rework
pub trait GraphIndex<T> {
    type Ref<'a> where T: 'a, Self: 'a;
    type Mut<'a> where T: 'a, Self: 'a;
}

// proposed in fundamentals rework
pub struct NodeEntry<Index, Weight> {
    id: Index,
    
	weight: Weight,
}

// proposed in iterator rework
pub struct EdgeEntry<Index, Weight, NodeIndex> {
    id: Index,
	weight: Weight,
	
	source: NodeIndex,
	target: NodeIndex
}

pub trait Storage: Sized {
	const DIRECTED: bool;

	type NodeIndex: GraphIndex<Self>;
	type NodeWeight;

	type EdgeIndex: GraphIndex<Self>;
	type EdgeWeight;

	// potentially split up into `get_node`, `get_edge`, etc.
	fn get<I>(&self, index: I) -> Option<I::Ref<'_>> where I: GraphIndex<Self>;
	fn get_mut<I>(&mut self, index: I) -> Option<I::Mut<'_>> where I: GraphIndex<Self>;

	fn insert_node(&mut self, weight: Self::NodeWeight) -> Self::NodeIndex;
	fn remove_node(&mut self, index: Self::NodeIndex) -> Option<Self::NodeWeight>;
	
	fn insert_edge(&mut self, a: Self::NodeIndex, b: Self::NodeIndex, weight: Self::EdgeWeight) -> Self::EdgeIndex;
	fn remove_edge(&mut self, index: Self::EdgeIndex) -> Option<Self::EdgeWeight>;

	// don't know if this will work for all cases
	type NodeIterator<T>: Iterator<Item = NodeEntry<Self::NodeIndex, T>>;

	fn nodes(&self) -> Self::NodeIterator<&Self::NodeWeight>;
	fn nodes_mut(&self) -> Self::NodeIterator<&mut Self::NodeWeight>;

	// don't know if this will work for all cases
	type EdgeIterator<T>: Iterator<Item = EdgeEntry<Self::EdgeIndex, T, Self::NodeIndex>>;

	fn edges(&self) -> Self::EdgeIterator<&Self::EdgeWeight>;
	fn edges_mut(&self) -> Self::EdgeIterator<&mut Self::EdgeWeight>;

    // these likely will need separate types for the iterator
	fn edges_undirected(&self, source: Self::NodeIndex) -> Self::EdgeIterator<&Self::EdgeWeight>;
	fn edges_directed(&self, source: Self::NodeIndex, direction: Direction) -> Self::EdgeIterator<&Self::EdgeWeight>;
	// if const expr in bounds is stabilized we could also do:
	// fn edges_directed(&self, source: Self::NodeIndex, direction: Direction) -> Self::EdgeIterator<&Self::EdgeWeight> where DIRECTED: true;
}

While still complex, there is much less surface area to cover with the type when implementing traits. I'd be willing to give this a shot to try to get this to work in 0.7. While this would be even more breaking than my initial proposal, I think this has sufficient promise; it would also cut down on the number of crates we'd need to publish as csr and friends are likely small enough to be able to be included in the new petgraph-graph

If we end up accepting this proposal, the only fear I have is that when delaying this to 0.8 and adding it, we A) have quite a lot of breaking changes; people will first upgrade to 0.7, then an already planned significant breaking change in 0.8. Is that too much? B) end up with crates that we potentially deprecate immediately if we end up with the, e.g., the CSR storage implementation directly in petgraph-graph.

Impact

This is a breaking change, but this could make maintaining the different graph representations much easier, and for users, it'd be a lot easier to swap between different graph representations.

CC for opinions.