graph_rs/
lib.rs

1extern crate collections_rs as collections;
2
3pub mod vec;
4mod map;
5
6pub use map::MapGraph;
7
8/// A directed graph with edge weights. The efficiency of the different
9/// operations is highly dependent on the backend used.
10pub trait DirectedWeightedGraph<'g, N, W>
11where
12    N: 'g + Eq,
13    W: 'g,
14{
15    /// An iterator that iterates over all edges.
16    type AllWeightedEdges: Iterator<Item = (&'g N, &'g N, &'g W)>;
17    /// An iterator that iterates over all edges, giving mutable access to the
18    /// weight.
19    type AllWeightedEdgesMut: Iterator<Item = (&'g N, &'g N, &'g mut W)>;
20
21    /// Returns an iterator over all the edges in this graph.
22    fn all_edges(&'g self) -> Self::AllWeightedEdges;
23
24    /// Returns an iterator over all the ediges in this graph, with mutable
25    /// access to the weight.
26    fn all_edges_mut(&'g mut self) -> Self::AllWeightedEdgesMut;
27
28    /// Adds an edge to this graph.
29    fn add_edge(&'g mut self, N, N, W) -> Option<(N, N, W)>;
30
31    /// Removes an edge from the graph.
32    fn remove_edge(&'g mut self, &N, &N) -> Option<(N, N, W)>;
33
34    /// Checks if a graph has an edge or not.
35    ///
36    /// # Complexity
37    /// The default implementation runs in O(|E|) time.
38    fn has_edge(&'g self, source: &N, sink: &N) -> bool {
39        self.edge_weight(source, sink).is_some()
40    }
41
42    /// Gets a borrow to the weight of the requested edge, if it exist.
43    ///
44    /// # Complexity
45    /// The default implementation runs in O(|E|).
46    fn edge_weight(&'g self, source: &N, sink: &N) -> Option<&W> {
47        self.all_edges()
48            .find(|&(n1, n2, _)| n1 == source && n2 == sink)
49            .map(|(_, _, weight)| weight)
50    }
51
52    /// Gets a mutable borrow to the weight of the requested edge, if it exist.
53    ///
54    /// # Complexity
55    /// The default implementation runs in O(|E|) time.
56    fn edge_weight_mut(&'g mut self, source: &N, sink: &N) -> Option<&mut W> {
57        self.all_edges_mut()
58            .find(|&(n1, n2, _)| n1 == source && n2 == sink)
59            .map(|(_, _, weight)| weight)
60    }
61}
graph_rs/lib.rs

graph_rs/
lib.rs
