competitive/graph/
sparse_graph.rs

1use super::{
2    Adjacencies, AdjacenciesWithEindex, AdjacencyIndex, AdjacencyIndexWithEindex, AdjacencyView,
3    AdjacencyViewIterFromEindex, EIndexedGraph, EdgeMap, EdgeSize, EdgeView, GraphBase, IterScan,
4    MarkedIterScan, VertexMap, VertexSize, VertexView, Vertices,
5};
6use std::{iter::Cloned, marker::PhantomData, ops, slice};
7
8type Marker<T> = PhantomData<fn() -> T>;
9#[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd, Hash)]
10pub enum DirectedEdge {}
11#[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd, Hash)]
12pub enum UndirectedEdge {}
13#[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd, Hash)]
14pub enum BidirectionalEdge {}
15
16#[derive(Clone, Copy, Debug, Default, Eq, PartialEq, Ord, PartialOrd, Hash)]
17pub struct Adjacency {
18    pub id: usize,
19    pub to: usize,
20}
21impl Adjacency {
22    pub fn new(id: usize, to: usize) -> Adjacency {
23        Adjacency { id, to }
24    }
25}
26
27/// Static Sparse Graph represented as Compressed Sparse Row.
28#[derive(Debug, Clone)]
29pub struct SparseGraph<D> {
30    vsize: usize,
31    pub start: Vec<usize>,
32    pub elist: Vec<Adjacency>,
33    pub edges: Vec<(usize, usize)>,
34    _marker: Marker<D>,
35}
36
37impl<D> SparseGraph<D> {
38    /// Return the number of vertices.
39    pub fn vertices_size(&self) -> usize {
40        self.vsize
41    }
42    /// Return the number of edges.
43    pub fn edges_size(&self) -> usize {
44        self.edges.len()
45    }
46    /// Return an iterator over graph vertices.
47    pub fn vertices(&self) -> ops::Range<usize> {
48        0..self.vertices_size()
49    }
50    /// Return a slice of adjacency vertices.
51    pub fn adjacencies(&self, v: usize) -> slice::Iter<'_, Adjacency> {
52        self.elist[self.start[v]..self.start[v + 1]].iter()
53    }
54    pub fn builder<T>(vsize: usize) -> SparseGraphBuilder<T, D> {
55        SparseGraphBuilder::new(vsize)
56    }
57    pub fn builder_with_esize<T>(vsize: usize, esize: usize) -> SparseGraphBuilder<T, D> {
58        SparseGraphBuilder::new_with_esize(vsize, esize)
59    }
60}
61
62pub trait SparseGraphConstruction: Sized {
63    fn construct_graph(vsize: usize, edges: Vec<(usize, usize)>) -> SparseGraph<Self>;
64}
65
66impl<D> SparseGraph<D>
67where
68    D: SparseGraphConstruction,
69{
70    /// Construct graph from edges.
71    pub fn from_edges(vsize: usize, edges: Vec<(usize, usize)>) -> Self {
72        D::construct_graph(vsize, edges)
73    }
74}
75
76impl SparseGraphConstruction for DirectedEdge {
77    fn construct_graph(vsize: usize, edges: Vec<(usize, usize)>) -> SparseGraph<Self> {
78        let mut start: Vec<_> = vec![0usize; vsize + 1];
79        for (from, _) in edges.iter().cloned() {
80            start[from] += 1;
81        }
82        for i in 1..=vsize {
83            start[i] += start[i - 1];
84        }
85        let mut elist = Vec::<Adjacency>::with_capacity(edges.len());
86        let ptr = elist.as_mut_ptr();
87        for (id, (from, to)) in edges.iter().cloned().enumerate() {
88            start[from] -= 1;
89            unsafe { ptr.add(start[from]).write(Adjacency::new(id, to)) };
90        }
91        unsafe { elist.set_len(edges.len()) };
92        SparseGraph {
93            vsize,
94            start,
95            elist,
96            edges,
97            _marker: PhantomData,
98        }
99    }
100}
101
102impl SparseGraphConstruction for UndirectedEdge {
103    fn construct_graph(vsize: usize, edges: Vec<(usize, usize)>) -> SparseGraph<Self> {
104        let mut start: Vec<_> = vec![0usize; vsize + 1];
105        for (from, to) in edges.iter().cloned() {
106            start[to] += 1;
107            start[from] += 1;
108        }
109        for i in 1..=vsize {
110            start[i] += start[i - 1];
111        }
112        let mut elist = Vec::<Adjacency>::with_capacity(edges.len() * 2);
113        let ptr = elist.as_mut_ptr();
114        for (id, (from, to)) in edges.iter().cloned().enumerate() {
115            start[from] -= 1;
116            unsafe { ptr.add(start[from]).write(Adjacency::new(id, to)) };
117            start[to] -= 1;
118            unsafe { ptr.add(start[to]).write(Adjacency::new(id, from)) };
119        }
120        unsafe { elist.set_len(edges.len() * 2) };
121        SparseGraph {
122            vsize,
123            start,
124            elist,
125            edges,
126            _marker: PhantomData,
127        }
128    }
129}
130
131impl SparseGraphConstruction for BidirectionalEdge {
132    fn construct_graph(vsize: usize, edges: Vec<(usize, usize)>) -> SparseGraph<Self> {
133        let mut start: Vec<_> = vec![0usize; vsize + 1];
134        for (from, to) in edges.iter().cloned() {
135            start[to] += 1;
136            start[from] += 1;
137        }
138        for i in 1..=vsize {
139            start[i] += start[i - 1];
140        }
141        let mut elist = Vec::<Adjacency>::with_capacity(edges.len() * 2);
142        let ptr = elist.as_mut_ptr();
143        for (id, (from, to)) in edges.iter().cloned().enumerate() {
144            start[from] -= 1;
145            unsafe { ptr.add(start[from]).write(Adjacency::new(id * 2, to)) };
146            start[to] -= 1;
147            unsafe { ptr.add(start[to]).write(Adjacency::new(id * 2 + 1, from)) };
148        }
149        unsafe { elist.set_len(edges.len() * 2) };
150        SparseGraph {
151            vsize,
152            start,
153            elist,
154            edges,
155            _marker: PhantomData,
156        }
157    }
158}
159
160pub type DirectedSparseGraph = SparseGraph<DirectedEdge>;
161pub type UndirectedSparseGraph = SparseGraph<UndirectedEdge>;
162pub type BidirectionalSparseGraph = SparseGraph<BidirectionalEdge>;
163
164pub struct SparseGraphBuilder<T, D> {
165    vsize: usize,
166    edges: Vec<(usize, usize)>,
167    rest: Vec<T>,
168    _marker: Marker<D>,
169}
170impl<T, D> SparseGraphBuilder<T, D> {
171    pub fn new(vsize: usize) -> Self {
172        Self {
173            vsize,
174            edges: Default::default(),
175            rest: Default::default(),
176            _marker: PhantomData,
177        }
178    }
179    pub fn new_with_esize(vsize: usize, esize: usize) -> Self {
180        Self {
181            vsize,
182            edges: Vec::with_capacity(esize),
183            rest: Vec::with_capacity(esize),
184            _marker: PhantomData,
185        }
186    }
187    pub fn add_edge(&mut self, u: usize, v: usize, w: T) {
188        self.edges.push((u, v));
189        self.rest.push(w);
190    }
191}
192impl<T, D> SparseGraphBuilder<T, D>
193where
194    D: SparseGraphConstruction,
195{
196    pub fn build(self) -> (SparseGraph<D>, Vec<T>) {
197        let graph = SparseGraph::from_edges(self.vsize, self.edges);
198        (graph, self.rest)
199    }
200}
201
202pub struct SparseGraphScanner<U, T, D>
203where
204    U: IterScan<Output = usize>,
205    T: IterScan,
206{
207    vsize: usize,
208    esize: usize,
209    _marker: Marker<(U, T, D)>,
210}
211
212impl<U, T, D> SparseGraphScanner<U, T, D>
213where
214    U: IterScan<Output = usize>,
215    T: IterScan,
216{
217    pub fn new(vsize: usize, esize: usize) -> Self {
218        Self {
219            vsize,
220            esize,
221            _marker: PhantomData,
222        }
223    }
224}
225
226impl<U, T, D> MarkedIterScan for SparseGraphScanner<U, T, D>
227where
228    U: IterScan<Output = usize>,
229    T: IterScan,
230    D: SparseGraphConstruction,
231{
232    type Output = (SparseGraph<D>, Vec<<T as IterScan>::Output>);
233    fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
234        let mut builder = SparseGraphBuilder::new_with_esize(self.vsize, self.esize);
235        for _ in 0..self.esize {
236            builder.add_edge(U::scan(iter)?, U::scan(iter)?, T::scan(iter)?);
237        }
238        Some(builder.build())
239    }
240}
241
242pub type DirectedGraphScanner<U, T = ()> = SparseGraphScanner<U, T, DirectedEdge>;
243pub type UndirectedGraphScanner<U, T = ()> = SparseGraphScanner<U, T, UndirectedEdge>;
244pub type BidirectionalGraphScanner<U, T = ()> = SparseGraphScanner<U, T, BidirectionalEdge>;
245
246pub struct TreeGraphScanner<U, T = ()>
247where
248    U: IterScan<Output = usize>,
249    T: IterScan,
250{
251    vsize: usize,
252    _marker: Marker<(U, T)>,
253}
254impl<U, T> TreeGraphScanner<U, T>
255where
256    U: IterScan<Output = usize>,
257    T: IterScan,
258{
259    pub fn new(vsize: usize) -> Self {
260        Self {
261            vsize,
262            _marker: PhantomData,
263        }
264    }
265}
266impl<U, T> MarkedIterScan for TreeGraphScanner<U, T>
267where
268    U: IterScan<Output = usize>,
269    T: IterScan,
270{
271    type Output = (UndirectedSparseGraph, Vec<<T as IterScan>::Output>);
272    fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
273        UndirectedGraphScanner::<U, T>::new(self.vsize, self.vsize - 1).mscan(iter)
274    }
275}
276
277impl<D> GraphBase for SparseGraph<D> {
278    type VIndex = usize;
279}
280impl<D> EIndexedGraph for SparseGraph<D> {
281    type EIndex = usize;
282}
283
284impl<D> VertexSize for SparseGraph<D> {
285    fn vsize(&self) -> usize {
286        self.vsize
287    }
288}
289impl<D> EdgeSize for SparseGraph<D> {
290    fn esize(&self) -> usize {
291        self.edges.len()
292    }
293}
294
295impl<D> Vertices for SparseGraph<D> {
296    type VIter<'g>
297        = ops::Range<usize>
298    where
299        D: 'g;
300    fn vertices(&self) -> Self::VIter<'_> {
301        0..self.vsize
302    }
303}
304impl<D> Adjacencies for SparseGraph<D> {
305    type AIndex = Adjacency;
306    type AIter<'g>
307        = Cloned<slice::Iter<'g, Adjacency>>
308    where
309        D: 'g;
310    fn adjacencies(&self, vid: Self::VIndex) -> Self::AIter<'_> {
311        self.elist[self.start[vid]..self.start[vid + 1]]
312            .iter()
313            .cloned()
314    }
315}
316impl<D> AdjacenciesWithEindex for SparseGraph<D> {
317    type AIndex = Adjacency;
318    type AIter<'g>
319        = Cloned<slice::Iter<'g, Adjacency>>
320    where
321        D: 'g;
322    fn adjacencies_with_eindex(&self, vid: Self::VIndex) -> Self::AIter<'_> {
323        self.elist[self.start[vid]..self.start[vid + 1]]
324            .iter()
325            .cloned()
326    }
327}
328
329impl AdjacencyIndex for Adjacency {
330    type VIndex = usize;
331    fn vindex(&self) -> Self::VIndex {
332        self.to
333    }
334}
335impl AdjacencyIndexWithEindex for Adjacency {
336    type EIndex = usize;
337    fn eindex(&self) -> Self::EIndex {
338        self.id
339    }
340}
341
342impl<D, T> VertexMap<T> for SparseGraph<D> {
343    type Vmap = Vec<T>;
344    fn construct_vmap<F>(&self, f: F) -> Self::Vmap
345    where
346        F: FnMut() -> T,
347    {
348        let mut v = Vec::with_capacity(self.vsize);
349        v.resize_with(self.vsize, f);
350        v
351    }
352    fn vmap_get<'a>(&self, map: &'a Self::Vmap, vid: Self::VIndex) -> &'a T {
353        assert!(vid < self.vsize, "expected 0..{}, but {}", self.vsize, vid);
354        unsafe { map.get_unchecked(vid) }
355    }
356    fn vmap_get_mut<'a>(&self, map: &'a mut Self::Vmap, vid: Self::VIndex) -> &'a mut T {
357        assert!(vid < self.vsize, "expected 0..{}, but {}", self.vsize, vid);
358        unsafe { map.get_unchecked_mut(vid) }
359    }
360}
361impl<D, T> VertexView<Vec<T>, T> for SparseGraph<D>
362where
363    T: Clone,
364{
365    fn vview(&self, map: &Vec<T>, vid: Self::VIndex) -> T {
366        self.vmap_get(map, vid).clone()
367    }
368}
369impl<D, T> VertexView<[T], T> for SparseGraph<D>
370where
371    T: Clone,
372{
373    fn vview(&self, map: &[T], vid: Self::VIndex) -> T {
374        assert!(vid < self.vsize, "expected 0..{}, but {}", self.vsize, vid);
375        unsafe { map.get_unchecked(vid) }.clone()
376    }
377}
378
379impl<D, T> EdgeMap<T> for SparseGraph<D> {
380    type Emap = Vec<T>;
381    fn construct_emap<F>(&self, f: F) -> Self::Emap
382    where
383        F: FnMut() -> T,
384    {
385        let mut v = Vec::with_capacity(self.vsize);
386        v.resize_with(self.vsize, f);
387        v
388    }
389    fn emap_get<'a>(&self, map: &'a Self::Emap, eid: Self::EIndex) -> &'a T {
390        let esize = self.edges.len();
391        assert!(eid < esize, "expected 0..{}, but {}", esize, eid);
392        unsafe { map.get_unchecked(eid) }
393    }
394    fn emap_get_mut<'a>(&self, map: &'a mut Self::Emap, eid: Self::EIndex) -> &'a mut T {
395        let esize = self.edges.len();
396        assert!(eid < esize, "expected 0..{}, but {}", esize, eid);
397        unsafe { map.get_unchecked_mut(eid) }
398    }
399}
400impl<D, T> EdgeView<Vec<T>, T> for SparseGraph<D>
401where
402    T: Clone,
403{
404    fn eview(&self, map: &Vec<T>, eid: Self::EIndex) -> T {
405        self.emap_get(map, eid).clone()
406    }
407}
408
409impl<D, T> EdgeView<[T], T> for SparseGraph<D>
410where
411    T: Clone,
412{
413    fn eview(&self, map: &[T], eid: Self::EIndex) -> T {
414        let esize = self.edges.len();
415        assert!(eid < esize, "expected 0..{}, but {}", esize, eid);
416        unsafe { map.get_unchecked(eid) }.clone()
417    }
418}
419
420impl<'a, D, M, T> AdjacencyView<'a, M, T> for SparseGraph<D>
421where
422    Self: AdjacenciesWithEindex + EdgeView<M, T>,
423    T: Clone,
424    M: 'a,
425{
426    type AViewIter<'g>
427        = AdjacencyViewIterFromEindex<'g, 'a, Self, M, T>
428    where
429        D: 'g;
430    fn aviews<'g>(&'g self, map: &'a M, vid: Self::VIndex) -> Self::AViewIter<'g> {
431        AdjacencyViewIterFromEindex::new(self.adjacencies_with_eindex(vid), self, map)
432    }
433}
competitive/graph/sparse_graph.rs

competitive/graph/
sparse_graph.rs
