graphfind_rs/petgraph/
graph.rs

1use petgraph::graph::EdgeIndex;
2use petgraph::graph::NodeIndex;
3use petgraph::visit::EdgeRef;
4use petgraph::Direction::Incoming;
5use petgraph::Direction::Outgoing;
6
7use crate::graph::Graph;
8/// Example implementation for in memory graphs stored using the petgraph library.
9///
10/// Both undirected and directed graphs are supported.
11///
12/// Node and Edge indices are by default 32-bit unsigned integers. Valid indices are
13/// {0, ..., n - 1} and {0, ..., m - 1}, where n is the number of nodes, and m the
14/// number of edges stored in this graph implementation.
15impl<NodeWeight, EdgeWeight, Direction, IndexType> Graph<NodeWeight, EdgeWeight>
16    for petgraph::graph::Graph<NodeWeight, EdgeWeight, Direction, IndexType>
17where
18    IndexType: petgraph::graph::IndexType,
19    Direction: petgraph::EdgeType,
20{
21    type NodeRef = NodeIndex<IndexType>;
22    type EdgeRef = EdgeIndex<IndexType>;
23    fn is_directed(&self) -> bool {
24        petgraph::graph::Graph::is_directed(self)
25    }
26
27    fn is_directed_edge(&self, edge: Self::EdgeRef) -> bool {
28        assert!(edge.index() < self.edge_count());
29        // petgraph doesn't support mixing directed and undirected edges.
30        self.is_directed()
31    }
32
33    type AdjacentEdgesIterator<'a> = impl Iterator<Item = Self::EdgeRef> + 'a where Self: 'a;
34    fn adjacent_edges(&self, node: Self::NodeRef) -> Self::AdjacentEdgesIterator<'_> {
35        self.edges_directed(node, Incoming)
36            .chain(
37                self.edges_directed(node, Outgoing)
38                    .filter(|_| self.is_directed()),
39            )
40            .map(|e| e.id())
41    }
42
43    type IncomingEdgesIterator<'a> = impl Iterator<Item = Self::EdgeRef> + 'a where Self: 'a;
44    fn incoming_edges(&self, node: Self::NodeRef) -> Self::IncomingEdgesIterator<'_> {
45        Box::new(self.edges_directed(node, Incoming).map(|e| e.id()))
46    }
47
48    type OutgoingEdgesIterator<'a> = impl Iterator<Item = Self::EdgeRef> + 'a where Self: 'a;
49    fn outgoing_edges(&self, node: Self::NodeRef) -> Self::OutgoingEdgesIterator<'_> {
50        Box::new(self.edges_directed(node, Outgoing).map(|e| e.id()))
51    }
52
53    fn adjacent_nodes(&self, edge: Self::EdgeRef) -> (Self::NodeRef, Self::NodeRef) {
54        self.edge_endpoints(edge)
55            .expect("Couldn't find edge endpoint references: Edge reference invalid.")
56    }
57
58    fn node_weight(&self, node: Self::NodeRef) -> &NodeWeight {
59        petgraph::graph::Graph::node_weight(self, node)
60            .expect("Couldn't find node weight: Node reference invalid.")
61    }
62
63    fn edge_weight(&self, edge: Self::EdgeRef) -> &EdgeWeight {
64        petgraph::graph::Graph::edge_weight(self, edge)
65            .expect("Couldn't find edge weight: Edge reference invalid.")
66    }
67
68    fn node_weights(&self) -> Self::NodeWeightsIterator<'_> {
69        petgraph::graph::Graph::node_weights(self)
70    }
71
72    fn edge_weights(&self) -> Self::EdgeWeightsIterator<'_> {
73        petgraph::graph::Graph::edge_weights(self)
74    }
75
76    type NodesIterator<'a> = impl Iterator<Item = Self::NodeRef> + 'a where Self: 'a;
77    fn nodes(&self) -> Self::NodesIterator<'_> {
78        // This works with the petgraph Graph type due to implementation details of petgraph, see https://docs.rs/petgraph/latest/petgraph/graph/struct.Graph.html#graph-indices
79        (0..self.node_count()).map(NodeIndex::new)
80    }
81
82    type EdgesIterator<'a> = impl Iterator<Item = Self::EdgeRef> + 'a where Self: 'a;
83    fn edges(&self) -> Self::EdgesIterator<'_> {
84        (0..self.edge_count()).map(EdgeIndex::new)
85    }
86
87    type NodeWeightsIterator<'a>
88     = impl Iterator<Item = &'a NodeWeight> + 'a where Self: 'a, Self: 'a, NodeWeight: 'a;
89
90    type EdgeWeightsIterator<'a>
91     = impl Iterator<Item = &'a EdgeWeight> + 'a where Self: 'a, Self: 'a, EdgeWeight: 'a;
92
93    fn count_edges(&self) -> usize {
94        self.edge_count()
95    }
96
97    fn count_nodes(&self) -> usize {
98        self.node_count()
99    }
100}
graphfind_rs/petgraph/graph.rs

graphfind_rs/petgraph/
graph.rs
