The core traits Vertices{Base,Mut,}, Edges{Base,Mut,} and Neighbors contain default implementations for some methods that can be expressed in the means of others. These implementations are often inefficient, however, and should be overridden by reasonable implementations in each graph storage.
This applies both to graph storages (AdjList, AdjMatrix, EdgeList) and their adapters (Stable, Frozen, operators, ...). The latter should always explicitly delegate the behavior to the underlying graph (i.e., implementing fn <function>(...) { self.graph.<function>(...) } or equivalent), but this is often guaranteed because of using derive macros.
A few known examples:
[ ] VerticesBase::contains_vertex -- after 4229680f96ce3883a2b2c1060aa8dc9cc4e1ac61 the default implementation changed to going through all vertex indices and checking if there is the vertex of interest. This definitely should be overridden in all graph storages to self.vertex(index).is_some()
[ ] Neighbors::degree{,_directed} in AdjList -- the degree can be computed in constant time by getting the number of outgoing and/or incoming edges which is stored in the vertices.
[ ] Neighbors::degree{,_directed} in Complement -- the degree can be computed by subtracting the real degree from the maximum possible degree of a vertex
Recommended approach to find the optimization opportunities:
Find an impl Trait for Storage item, where Trait is any graph-related trait and Storage is AdjList, AdjMatrix, etc.
Use your Rust Analyzer (or a different tool with equivalent functionality) to "implement default members", which inlines the default implementations to the concrete impl Trait for Storage.
Knowing the internal representation of the storage at hand, determine whether the default implementation can be improved. If so, improve it. If not, delete it.
The core traits
Vertices{Base,Mut,}
,Edges{Base,Mut,}
andNeighbors
contain default implementations for some methods that can be expressed in the means of others. These implementations are often inefficient, however, and should be overridden by reasonable implementations in each graph storage.This applies both to graph storages (
AdjList
,AdjMatrix
,EdgeList
) and their adapters (Stable
,Frozen
, operators, ...). The latter should always explicitly delegate the behavior to the underlying graph (i.e., implementingfn <function>(...) { self.graph.<function>(...) }
or equivalent), but this is often guaranteed because of using derive macros.A few known examples:
VerticesBase::contains_vertex
-- after 4229680f96ce3883a2b2c1060aa8dc9cc4e1ac61 the default implementation changed to going through all vertex indices and checking if there is the vertex of interest. This definitely should be overridden in all graph storages toself.vertex(index).is_some()
Neighbors::degree{,_directed}
in AdjList -- the degree can be computed in constant time by getting the number of outgoing and/or incoming edges which is stored in the vertices.Neighbors::degree{,_directed}
in Complement -- the degree can be computed by subtracting the real degree from the maximum possible degree of a vertex