Skip to content

Commit ec1b5bc

Browse files
authored
Organize visit trait implementations (#448)
* Move graph trait impls out of visit Some graphs had their visit trait implementations in the visit modules, while others had them in the graph module (and normally it was a mix between the two). This commit moves all the impls to the respective graph modules, to make the organization of the code more consistent. * Add table listing each graph traits in visit doc The visit:: traits can be a bit confusing at first. This change to the visit module documentation adds a quick overview over which graph implements which trait. It may come useful when deciding the traits to require for a new generic algorithm.
1 parent 2bfdefa commit ec1b5bc

7 files changed

Lines changed: 557 additions & 572 deletions

File tree

‎src/csr.rs‎

Lines changed: 14 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -7,9 +7,9 @@ use std::ops::{Index, IndexMut, Range};
77
use std::slice::Windows;
88

99
use crate::visit::{
10-
Data, EdgeRef, GetAdjacencyMatrix, GraphBase, GraphProp, IntoEdgeReferences, IntoEdges,
11-
IntoNeighbors, IntoNodeIdentifiers, IntoNodeReferences, NodeCompactIndexable, NodeCount,
12-
NodeIndexable, Visitable,
10+
Data, EdgeCount, EdgeRef, GetAdjacencyMatrix, GraphBase, GraphProp, IntoEdgeReferences,
11+
IntoEdges, IntoNeighbors, IntoNodeIdentifiers, IntoNodeReferences, NodeCompactIndexable,
12+
NodeCount, NodeIndexable, Visitable,
1313
};
1414

1515
use crate::util::zip;
@@ -719,6 +719,17 @@ where
719719
}
720720
}
721721

722+
impl<N, E, Ty, Ix> EdgeCount for Csr<N, E, Ty, Ix>
723+
where
724+
Ty: EdgeType,
725+
Ix: IndexType,
726+
{
727+
#[inline]
728+
fn edge_count(&self) -> usize {
729+
self.edge_count()
730+
}
731+
}
732+
722733
impl<N, E, Ty, Ix> GraphProp for Csr<N, E, Ty, Ix>
723734
where
724735
Ty: EdgeType,

‎src/graph_impl/frozen.rs‎

Lines changed: 11 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -5,8 +5,9 @@ use crate::data::{DataMap, DataMapMut};
55
use crate::graph::Graph;
66
use crate::graph::{GraphIndex, IndexType};
77
use crate::visit::{
8-
Data, EdgeCount, EdgeIndexable, GetAdjacencyMatrix, GraphProp, IntoEdges, IntoEdgesDirected,
9-
IntoNeighborsDirected, IntoNodeIdentifiers, NodeCompactIndexable, NodeCount, NodeIndexable,
8+
Data, EdgeCount, EdgeIndexable, GetAdjacencyMatrix, GraphBase, GraphProp, IntoEdges,
9+
IntoEdgesDirected, IntoNeighborsDirected, IntoNodeIdentifiers, NodeCompactIndexable, NodeCount,
10+
NodeIndexable,
1011
};
1112
use crate::visit::{IntoEdgeReferences, IntoNeighbors, IntoNodeReferences, Visitable};
1213
use crate::{Direction, EdgeType};
@@ -78,6 +79,14 @@ macro_rules! access0 {
7879
};
7980
}
8081

82+
impl<'a, G> GraphBase for Frozen<'a, G>
83+
where
84+
G: GraphBase,
85+
{
86+
type NodeId = G::NodeId;
87+
type EdgeId = G::EdgeId;
88+
}
89+
8190
Data! {delegate_impl [['a, G], G, Frozen<'a, G>, deref_twice]}
8291
DataMap! {delegate_impl [['a, G], G, Frozen<'a, G>, deref_twice]}
8392
DataMapMut! {delegate_impl [['a, G], G, Frozen<'a, G>, access0]}

‎src/graph_impl/mod.rs‎

Lines changed: 132 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -7,13 +7,14 @@ use std::mem::size_of;
77
use std::ops::{Index, IndexMut, Range};
88
use std::slice;
99

10+
use fixedbitset::FixedBitSet;
11+
1012
use crate::{Directed, Direction, EdgeType, Incoming, IntoWeightedEdge, Outgoing, Undirected};
1113

1214
use crate::iter_format::{DebugMap, IterFormatExt, NoPretty};
1315

1416
use crate::util::enumerate;
15-
use crate::visit::EdgeRef;
16-
use crate::visit::{EdgeIndexable, IntoEdges, IntoEdgesDirected, IntoNodeReferences};
17+
use crate::visit;
1718

1819
#[cfg(feature = "serde-1")]
1920
mod serialization;
@@ -1598,7 +1599,7 @@ where
15981599
}
15991600
}
16001601

1601-
impl<'a, N, E, Ty, Ix> IntoEdges for &'a Graph<N, E, Ty, Ix>
1602+
impl<'a, N, E, Ty, Ix> visit::IntoEdges for &'a Graph<N, E, Ty, Ix>
16021603
where
16031604
Ty: EdgeType,
16041605
Ix: IndexType,
@@ -1609,7 +1610,7 @@ where
16091610
}
16101611
}
16111612

1612-
impl<'a, N, E, Ty, Ix> IntoEdgesDirected for &'a Graph<N, E, Ty, Ix>
1613+
impl<'a, N, E, Ty, Ix> visit::IntoEdgesDirected for &'a Graph<N, E, Ty, Ix>
16131614
where
16141615
Ty: EdgeType,
16151616
Ix: IndexType,
@@ -2119,7 +2120,131 @@ where
21192120
}
21202121
}
21212122

2122-
impl<'a, N, E, Ty, Ix> IntoNodeReferences for &'a Graph<N, E, Ty, Ix>
2123+
impl<N, E, Ty, Ix> visit::GraphBase for Graph<N, E, Ty, Ix>
2124+
where
2125+
Ix: IndexType,
2126+
{
2127+
type NodeId = NodeIndex<Ix>;
2128+
type EdgeId = EdgeIndex<Ix>;
2129+
}
2130+
2131+
impl<N, E, Ty, Ix> visit::Visitable for Graph<N, E, Ty, Ix>
2132+
where
2133+
Ty: EdgeType,
2134+
Ix: IndexType,
2135+
{
2136+
type Map = FixedBitSet;
2137+
fn visit_map(&self) -> FixedBitSet {
2138+
FixedBitSet::with_capacity(self.node_count())
2139+
}
2140+
2141+
fn reset_map(&self, map: &mut Self::Map) {
2142+
map.clear();
2143+
map.grow(self.node_count());
2144+
}
2145+
}
2146+
2147+
impl<N, E, Ty, Ix> visit::GraphProp for Graph<N, E, Ty, Ix>
2148+
where
2149+
Ty: EdgeType,
2150+
Ix: IndexType,
2151+
{
2152+
type EdgeType = Ty;
2153+
}
2154+
2155+
impl<'a, N, E: 'a, Ty, Ix> visit::IntoNodeIdentifiers for &'a Graph<N, E, Ty, Ix>
2156+
where
2157+
Ty: EdgeType,
2158+
Ix: IndexType,
2159+
{
2160+
type NodeIdentifiers = NodeIndices<Ix>;
2161+
fn node_identifiers(self) -> NodeIndices<Ix> {
2162+
Graph::node_indices(self)
2163+
}
2164+
}
2165+
2166+
impl<N, E, Ty, Ix> visit::NodeCount for Graph<N, E, Ty, Ix>
2167+
where
2168+
Ty: EdgeType,
2169+
Ix: IndexType,
2170+
{
2171+
fn node_count(&self) -> usize {
2172+
self.node_count()
2173+
}
2174+
}
2175+
2176+
impl<N, E, Ty, Ix> visit::NodeIndexable for Graph<N, E, Ty, Ix>
2177+
where
2178+
Ty: EdgeType,
2179+
Ix: IndexType,
2180+
{
2181+
#[inline]
2182+
fn node_bound(&self) -> usize {
2183+
self.node_count()
2184+
}
2185+
#[inline]
2186+
fn to_index(&self, ix: NodeIndex<Ix>) -> usize {
2187+
ix.index()
2188+
}
2189+
#[inline]
2190+
fn from_index(&self, ix: usize) -> Self::NodeId {
2191+
NodeIndex::new(ix)
2192+
}
2193+
}
2194+
2195+
impl<N, E, Ty, Ix> visit::NodeCompactIndexable for Graph<N, E, Ty, Ix>
2196+
where
2197+
Ty: EdgeType,
2198+
Ix: IndexType,
2199+
{
2200+
}
2201+
2202+
impl<'a, N, E: 'a, Ty, Ix> visit::IntoNeighbors for &'a Graph<N, E, Ty, Ix>
2203+
where
2204+
Ty: EdgeType,
2205+
Ix: IndexType,
2206+
{
2207+
type Neighbors = Neighbors<'a, E, Ix>;
2208+
fn neighbors(self, n: NodeIndex<Ix>) -> Neighbors<'a, E, Ix> {
2209+
Graph::neighbors(self, n)
2210+
}
2211+
}
2212+
2213+
impl<'a, N, E: 'a, Ty, Ix> visit::IntoNeighborsDirected for &'a Graph<N, E, Ty, Ix>
2214+
where
2215+
Ty: EdgeType,
2216+
Ix: IndexType,
2217+
{
2218+
type NeighborsDirected = Neighbors<'a, E, Ix>;
2219+
fn neighbors_directed(self, n: NodeIndex<Ix>, d: Direction) -> Neighbors<'a, E, Ix> {
2220+
Graph::neighbors_directed(self, n, d)
2221+
}
2222+
}
2223+
2224+
impl<'a, N: 'a, E: 'a, Ty, Ix> visit::IntoEdgeReferences for &'a Graph<N, E, Ty, Ix>
2225+
where
2226+
Ty: EdgeType,
2227+
Ix: IndexType,
2228+
{
2229+
type EdgeRef = EdgeReference<'a, E, Ix>;
2230+
type EdgeReferences = EdgeReferences<'a, E, Ix>;
2231+
fn edge_references(self) -> Self::EdgeReferences {
2232+
(*self).edge_references()
2233+
}
2234+
}
2235+
2236+
impl<N, E, Ty, Ix> visit::EdgeCount for Graph<N, E, Ty, Ix>
2237+
where
2238+
Ty: EdgeType,
2239+
Ix: IndexType,
2240+
{
2241+
#[inline]
2242+
fn edge_count(&self) -> usize {
2243+
self.edge_count()
2244+
}
2245+
}
2246+
2247+
impl<'a, N, E, Ty, Ix> visit::IntoNodeReferences for &'a Graph<N, E, Ty, Ix>
21232248
where
21242249
Ty: EdgeType,
21252250
Ix: IndexType,
@@ -2182,7 +2307,7 @@ where
21822307
}
21832308
}
21842309

2185-
impl<'a, Ix, E> EdgeRef for EdgeReference<'a, E, Ix>
2310+
impl<'a, Ix, E> visit::EdgeRef for EdgeReference<'a, E, Ix>
21862311
where
21872312
Ix: IndexType,
21882313
{
@@ -2244,7 +2369,7 @@ where
22442369

22452370
impl<'a, E, Ix> ExactSizeIterator for EdgeReferences<'a, E, Ix> where Ix: IndexType {}
22462371

2247-
impl<N, E, Ty, Ix> EdgeIndexable for Graph<N, E, Ty, Ix>
2372+
impl<N, E, Ty, Ix> visit::EdgeIndexable for Graph<N, E, Ty, Ix>
22482373
where
22492374
Ty: EdgeType,
22502375
Ix: IndexType,

0 commit comments

Comments
 (0)