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

competitive/graph/
sparse_graph.rs
