competitive/graph/
graph_base.rs

1/// A neighboring vertex and the label of the arc used to reach it.
2#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
3pub struct Neighbor<V, L> {
4    pub to: V,
5    pub label: L,
6}
7
8impl<V, L> Neighbor<V, L> {
9    #[inline]
10    pub fn new(to: V, label: L) -> Self {
11        Self { to, label }
12    }
13}
14
15impl<V, L> From<(V, L)> for Neighbor<V, L> {
16    #[inline]
17    fn from((to, label): (V, L)) -> Self {
18        Self::new(to, label)
19    }
20}
21
22/// A finite graph whose outgoing arcs can be iterated without allocation.
23pub trait Graph {
24    type Vertex: Copy + Eq;
25    type Label;
26    type Vertices<'g>: Iterator<Item = Self::Vertex>
27    where
28        Self: 'g;
29    type Neighbors<'g>: Iterator<Item = Neighbor<Self::Vertex, Self::Label>>
30    where
31        Self: 'g;
32
33    fn vsize(&self) -> usize;
34    fn vertices(&self) -> Self::Vertices<'_>;
35    fn neighbors(&self, vertex: Self::Vertex) -> Self::Neighbors<'_>;
36}
37
38/// A graph whose adjacency relation represents directed arcs.
39pub trait DirectedGraph: Graph {}
40
41pub trait VertexMap<T>: Graph {
42    type Vmap;
43
44    fn construct_vmap<F>(&self, f: F) -> Self::Vmap
45    where
46        F: FnMut() -> T;
47
48    fn vmap_get<'a>(&self, map: &'a Self::Vmap, vertex: Self::Vertex) -> &'a T;
49    fn vmap_get_mut<'a>(&self, map: &'a mut Self::Vmap, vertex: Self::Vertex) -> &'a mut T;
50
51    #[inline]
52    fn vmap_set(&self, map: &mut Self::Vmap, vertex: Self::Vertex, value: T) {
53        *self.vmap_get_mut(map, vertex) = value;
54    }
55}
56
57pub trait EdgeMap<T>: Graph {
58    type Emap;
59
60    fn construct_emap<F>(&self, f: F) -> Self::Emap
61    where
62        F: FnMut() -> T;
63
64    fn emap_get<'a>(&self, map: &'a Self::Emap, eid: Self::Label) -> &'a T;
65    fn emap_get_mut<'a>(&self, map: &'a mut Self::Emap, eid: Self::Label) -> &'a mut T;
66
67    #[inline]
68    fn emap_set(&self, map: &mut Self::Emap, eid: Self::Label, value: T) {
69        *self.emap_get_mut(map, eid) = value;
70    }
71}
competitive/graph/graph_base.rs

competitive/graph/
graph_base.rs
