traitgraph/implementation/
petgraph_impl.rs

1use crate::index::{GraphIndex, GraphIndices};
2use crate::interface::{
3    Edge, GraphBase, ImmutableGraphContainer, MutableGraphContainer, NavigableGraph, Neighbor,
4};
5use num_traits::{PrimInt, ToPrimitive};
6use petgraph::graph::{DiGraph, Edges, EdgesConnecting};
7use petgraph::visit::EdgeRef;
8use petgraph::{Directed, Direction};
9use std::iter::Map;
10
11use crate::interface::subgraph::SubgraphBase;
12pub use petgraph;
13
14/// A wrapper around the [petgraph::graph::Graph] type replacing its methods with implementations of our traits.
15#[derive(Debug, Clone)]
16pub struct PetGraph<NodeData, EdgeData>(DiGraph<NodeData, EdgeData, usize>);
17
18impl<NodeData, EdgeData> PetGraph<NodeData, EdgeData> {
19    /// Create a new graph implemented using the `petgraph::graph::Graph` type.
20    pub fn new() -> PetGraph<NodeData, EdgeData> {
21        PetGraph(DiGraph::<NodeData, EdgeData, usize>::default())
22    }
23}
24
25impl<NodeData, EdgeData> GraphBase for PetGraph<NodeData, EdgeData> {
26    type NodeData = NodeData;
27    type EdgeData = EdgeData;
28    type OptionalNodeIndex = crate::index::OptionalNodeIndex<usize>;
29    type OptionalEdgeIndex = crate::index::OptionalEdgeIndex<usize>;
30    type NodeIndex = crate::index::NodeIndex<usize>;
31    type EdgeIndex = crate::index::EdgeIndex<usize>;
32}
33
34impl<NodeData, EdgeData> ImmutableGraphContainer for PetGraph<NodeData, EdgeData> {
35    type NodeIndices<'a>
36        = GraphIndices<Self::NodeIndex, Self::OptionalNodeIndex>
37    where
38        Self: 'a;
39    type EdgeIndices<'a>
40        = GraphIndices<Self::EdgeIndex, Self::OptionalEdgeIndex>
41    where
42        Self: 'a;
43
44    type NodeIndicesCopied =
45        GraphIndices<<Self as GraphBase>::NodeIndex, <Self as GraphBase>::OptionalNodeIndex>;
46    type EdgeIndicesCopied =
47        GraphIndices<<Self as GraphBase>::EdgeIndex, <Self as GraphBase>::OptionalEdgeIndex>;
48
49    fn node_indices(&self) -> Self::NodeIndices<'_> {
50        GraphIndices::from((0, self.node_count()))
51    }
52    fn edge_indices(&self) -> Self::EdgeIndices<'_> {
53        GraphIndices::from((0, self.edge_count()))
54    }
55
56    fn node_indices_copied(&self) -> Self::NodeIndicesCopied {
57        GraphIndices::from((0, self.node_count()))
58    }
59
60    fn edge_indices_copied(&self) -> Self::EdgeIndicesCopied {
61        GraphIndices::from((0, self.edge_count()))
62    }
63
64    fn contains_node_index(&self, node_id: Self::NodeIndex) -> bool {
65        self.0.node_weight(node_id.into()).is_some()
66    }
67
68    fn contains_edge_index(&self, edge_id: Self::EdgeIndex) -> bool {
69        self.0.edge_weight(edge_id.into()).is_some()
70    }
71
72    fn node_count(&self) -> usize {
73        self.0.node_count()
74    }
75
76    fn edge_count(&self) -> usize {
77        self.0.edge_count()
78    }
79
80    fn node_data(&self, node_id: Self::NodeIndex) -> &Self::NodeData {
81        self.0.node_weight(node_id.into()).unwrap()
82    }
83
84    fn edge_data(&self, edge_id: Self::EdgeIndex) -> &Self::EdgeData {
85        self.0.edge_weight(edge_id.into()).unwrap()
86    }
87
88    fn edge_endpoints(&self, edge_id: Self::EdgeIndex) -> Edge<Self::NodeIndex> {
89        let endpoints = self.0.edge_endpoints(edge_id.into()).unwrap();
90        Edge {
91            from_node: endpoints.0.index().into(),
92            to_node: endpoints.1.index().into(),
93        }
94    }
95}
96
97impl<NodeData, EdgeData> MutableGraphContainer for PetGraph<NodeData, EdgeData> {
98    fn node_data_mut(&mut self, node_id: Self::NodeIndex) -> &mut Self::NodeData {
99        self.0.node_weight_mut(node_id.into()).unwrap()
100    }
101
102    fn edge_data_mut(&mut self, edge_id: Self::EdgeIndex) -> &mut Self::EdgeData {
103        self.0.edge_weight_mut(edge_id.into()).unwrap()
104    }
105
106    fn add_node(&mut self, node_data: NodeData) -> Self::NodeIndex {
107        self.0.add_node(node_data).index().into()
108    }
109
110    fn add_edge(
111        &mut self,
112        from: Self::NodeIndex,
113        to: Self::NodeIndex,
114        edge_data: EdgeData,
115    ) -> Self::EdgeIndex {
116        self.0
117            .add_edge(from.into(), to.into(), edge_data)
118            .index()
119            .into()
120    }
121
122    fn remove_node(&mut self, node_id: Self::NodeIndex) -> Option<NodeData> {
123        self.0.remove_node(node_id.into())
124    }
125
126    fn remove_edge(&mut self, edge_id: Self::EdgeIndex) -> Option<EdgeData> {
127        self.0.remove_edge(edge_id.into())
128    }
129
130    fn remove_edges_sorted(&mut self, edge_ids: &[Self::EdgeIndex]) {
131        edge_ids.windows(2).for_each(|w| debug_assert!(w[0] < w[1]));
132
133        for edge_id in edge_ids.iter().rev() {
134            self.remove_edge(*edge_id);
135        }
136    }
137
138    fn clear(&mut self) {
139        self.0.clear();
140    }
141}
142
143impl<NodeData, EdgeData> SubgraphBase for PetGraph<NodeData, EdgeData> {
144    type RootGraph = Self;
145
146    fn root(&self) -> &Self::RootGraph {
147        self
148    }
149}
150
151type PetgraphNeighborTranslator<'a, EdgeData, NodeIndex, EdgeIndex> = Map<
152    Edges<'a, EdgeData, Directed, usize>,
153    fn(petgraph::graph::EdgeReference<'a, EdgeData, usize>) -> Neighbor<NodeIndex, EdgeIndex>,
154>;
155
156type PetgraphRestrictedNeighborTranslator<'a, EdgeData, EdgeIndex> = Map<
157    EdgesConnecting<'a, EdgeData, Directed, usize>,
158    fn(petgraph::graph::EdgeReference<'a, EdgeData, usize>) -> EdgeIndex,
159>;
160
161impl<NodeData, EdgeData> NavigableGraph for PetGraph<NodeData, EdgeData> {
162    type OutNeighbors<'a>
163        = PetgraphNeighborTranslator<
164        'a,
165        EdgeData,
166        <Self as GraphBase>::NodeIndex,
167        <Self as GraphBase>::EdgeIndex,
168    >
169    where
170        NodeData: 'a,
171        EdgeData: 'a;
172    type InNeighbors<'a>
173        = PetgraphNeighborTranslator<
174        'a,
175        EdgeData,
176        <Self as GraphBase>::NodeIndex,
177        <Self as GraphBase>::EdgeIndex,
178    >
179    where
180        NodeData: 'a,
181        EdgeData: 'a;
182    type EdgesBetween<'a>
183        = PetgraphRestrictedNeighborTranslator<'a, EdgeData, <Self as GraphBase>::EdgeIndex>
184    where
185        NodeData: 'a,
186        EdgeData: 'a;
187
188    fn out_neighbors(&self, node_id: <Self as GraphBase>::NodeIndex) -> Self::OutNeighbors<'_> {
189        debug_assert!(self.contains_node_index(node_id));
190        self.0
191            .edges_directed(node_id.into(), Direction::Outgoing)
192            .map(|edge| Neighbor {
193                edge_id: <Self as GraphBase>::EdgeIndex::from(edge.id().index()),
194                node_id: <Self as GraphBase>::NodeIndex::from(edge.target().index()),
195            })
196    }
197
198    fn in_neighbors(&self, node_id: <Self as GraphBase>::NodeIndex) -> Self::InNeighbors<'_> {
199        debug_assert!(self.contains_node_index(node_id));
200        self.0
201            .edges_directed(node_id.into(), Direction::Incoming)
202            .map(|edge| Neighbor {
203                edge_id: <Self as GraphBase>::EdgeIndex::from(edge.id().index()),
204                node_id: <Self as GraphBase>::NodeIndex::from(edge.source().index()),
205            })
206    }
207
208    fn edges_between(
209        &self,
210        from_node_id: <Self as GraphBase>::NodeIndex,
211        to_node_id: <Self as GraphBase>::NodeIndex,
212    ) -> Self::EdgesBetween<'_> {
213        debug_assert!(self.contains_node_index(from_node_id));
214        debug_assert!(self.contains_node_index(to_node_id));
215        self.0
216            .edges_connecting(from_node_id.into(), to_node_id.into())
217            .map(|edge| <Self as GraphBase>::EdgeIndex::from(edge.id().index()))
218    }
219
220    fn contains_edge_between(&self, from: Self::NodeIndex, to: Self::NodeIndex) -> bool {
221        self.0
222            .edges_connecting(from.into(), to.into())
223            .next()
224            .is_some()
225    }
226
227    fn edge_count_between(&self, from: Self::NodeIndex, to: Self::NodeIndex) -> usize {
228        self.0.edges_connecting(from.into(), to.into()).count()
229    }
230}
231
232impl<IndexType: PrimInt + ToPrimitive + petgraph::graph::IndexType>
233    From<crate::index::NodeIndex<IndexType>> for petgraph::graph::NodeIndex<IndexType>
234{
235    fn from(index: crate::index::NodeIndex<IndexType>) -> Self {
236        petgraph::graph::NodeIndex::new(index.as_usize())
237    }
238}
239
240impl<IndexType: PrimInt + ToPrimitive + petgraph::graph::IndexType>
241    From<crate::index::EdgeIndex<IndexType>> for petgraph::graph::EdgeIndex<IndexType>
242{
243    fn from(index: crate::index::EdgeIndex<IndexType>) -> Self {
244        petgraph::graph::EdgeIndex::new(index.as_usize())
245    }
246}
247
248impl<NodeData: PartialEq, EdgeData: PartialEq> PartialEq for PetGraph<NodeData, EdgeData> {
249    fn eq(&self, other: &Self) -> bool {
250        self.node_count() == other.node_count()
251            || self.edge_count() == other.edge_count()
252                && self
253                    .node_indices()
254                    .zip(other.node_indices())
255                    .all(|(a, b)| a == b && self.node_data(a) == other.node_data(b))
256                && self.edge_indices().zip(other.edge_indices()).all(|(a, b)| {
257                    a == b
258                        && self.edge_endpoints(a) == other.edge_endpoints(b)
259                        && self.edge_data(a) == other.edge_data(b)
260                })
261    }
262}
263
264impl<NodeData: Eq, EdgeData: Eq> Eq for PetGraph<NodeData, EdgeData> {}
265
266impl<NodeData, EdgeData> Default for PetGraph<NodeData, EdgeData> {
267    fn default() -> Self {
268        Self(Default::default())
269    }
270}
traitgraph/implementation/petgraph_impl.rs

traitgraph/implementation/
petgraph_impl.rs
