competitive/graph/
adjacency_list.rs

1use super::{EdgeMap, Graph, MarkedScan, Neighbor, Scan, ScanSource, VertexMap};
2use std::{iter::Copied, marker::PhantomData, ops::Range, slice};
3
4#[derive(Clone, Debug, Default)]
5pub struct AdjacencyListGraph {
6    pub vsize: usize,
7    pub esize: usize,
8    pub graph: Vec<Vec<Neighbor<usize, usize>>>,
9}
10impl AdjacencyListGraph {
11    pub fn new(vsize: usize) -> AdjacencyListGraph {
12        AdjacencyListGraph {
13            vsize,
14            esize: 0,
15            graph: vec![vec![]; vsize],
16        }
17    }
18    pub fn add_edge(&mut self, from: usize, to: usize) {
19        self.graph[from].push(Neighbor::new(to, self.esize));
20        self.esize += 1;
21    }
22    pub fn add_undirected_edge(&mut self, u: usize, v: usize) {
23        self.graph[u].push(Neighbor::new(v, self.esize));
24        self.graph[v].push(Neighbor::new(u, self.esize));
25        self.esize += 1;
26    }
27    pub fn vertices(&self) -> Range<usize> {
28        0..self.vsize
29    }
30}
31
32impl Graph for AdjacencyListGraph {
33    type Vertex = usize;
34    type Label = usize;
35    type Vertices<'g> = Range<usize>;
36    type Neighbors<'g> = Copied<slice::Iter<'g, Neighbor<usize, usize>>>;
37
38    #[inline]
39    fn vsize(&self) -> usize {
40        self.vsize
41    }
42
43    #[inline]
44    fn vertices(&self) -> Self::Vertices<'_> {
45        0..self.vsize
46    }
47
48    #[inline]
49    fn neighbors(&self, vertex: Self::Vertex) -> Self::Neighbors<'_> {
50        self.graph[vertex].iter().copied()
51    }
52}
53
54impl<T> EdgeMap<T> for AdjacencyListGraph {
55    type Emap = Vec<T>;
56
57    #[inline]
58    fn construct_emap<F>(&self, f: F) -> Self::Emap
59    where
60        F: FnMut() -> T,
61    {
62        let mut map = Vec::with_capacity(self.esize);
63        map.resize_with(self.esize, f);
64        map
65    }
66
67    #[inline]
68    fn emap_get<'a>(&self, map: &'a Self::Emap, eid: Self::Label) -> &'a T {
69        &map[eid]
70    }
71
72    #[inline]
73    fn emap_get_mut<'a>(&self, map: &'a mut Self::Emap, eid: Self::Label) -> &'a mut T {
74        &mut map[eid]
75    }
76}
77
78impl<T> VertexMap<T> for AdjacencyListGraph {
79    type Vmap = Vec<T>;
80
81    #[inline]
82    fn construct_vmap<F>(&self, f: F) -> Self::Vmap
83    where
84        F: FnMut() -> T,
85    {
86        let mut map = Vec::with_capacity(self.vsize);
87        map.resize_with(self.vsize, f);
88        map
89    }
90
91    #[inline]
92    fn vmap_get<'a>(&self, map: &'a Self::Vmap, vertex: Self::Vertex) -> &'a T {
93        &map[vertex]
94    }
95
96    #[inline]
97    fn vmap_get_mut<'a>(&self, map: &'a mut Self::Vmap, vertex: Self::Vertex) -> &'a mut T {
98        &mut map[vertex]
99    }
100}
101
102pub struct AdjacencyListGraphScanner<U: Scan<Output = usize>, T: Scan> {
103    vsize: usize,
104    esize: usize,
105    directed: bool,
106    _marker: PhantomData<fn() -> (U, T)>,
107}
108
109impl<U: Scan<Output = usize>, T: Scan> AdjacencyListGraphScanner<U, T> {
110    pub fn new(vsize: usize, esize: usize, directed: bool) -> Self {
111        Self {
112            vsize,
113            esize,
114            directed,
115            _marker: PhantomData,
116        }
117    }
118}
119
120impl<U: Scan<Output = usize>, T: Scan> MarkedScan for AdjacencyListGraphScanner<U, T> {
121    type Output = (AdjacencyListGraph, Vec<<T as Scan>::Output>);
122    fn mscan<I: ScanSource>(self, iter: &mut I) -> Option<Self::Output> {
123        let mut graph = AdjacencyListGraph::new(self.vsize);
124        let mut rest = Vec::with_capacity(self.esize);
125        for _ in 0..self.esize {
126            let (from, to) = (U::scan(iter)?, U::scan(iter)?);
127            if self.directed {
128                graph.add_edge(from, to);
129            } else {
130                graph.add_undirected_edge(from, to);
131            }
132            rest.push(T::scan(iter)?);
133        }
134        Some((graph, rest))
135    }
136}
competitive/graph/adjacency_list.rs

competitive/graph/
adjacency_list.rs
