competitive/graph/
edge_list.rs

1use super::{IterScan, MarkedIterScan};
2use std::{marker::PhantomData, ops::Range, slice::Iter};
3
4#[derive(Clone, Debug)]
5/// Graph represented by a list of edges.
6pub struct EdgeListGraph {
7    vsize: usize,
8    edges: Vec<(usize, usize)>,
9}
10impl EdgeListGraph {
11    /// Construct empty graph.
12    pub fn new(vsize: usize) -> Self {
13        Self {
14            vsize,
15            edges: Vec::new(),
16        }
17    }
18    /// Return the number of vertices.
19    pub fn vertices_size(&self) -> usize {
20        self.vsize
21    }
22    /// Return the number of edges.
23    pub fn edges_size(&self) -> usize {
24        self.edges.len()
25    }
26    /// Return an iterator over graph vertices.
27    pub fn vertices(&self) -> Range<usize> {
28        0..self.vertices_size()
29    }
30    pub fn edges(&self) -> Iter<'_, (usize, usize)> {
31        self.edges.iter()
32    }
33    /// Construct graph from edges.
34    pub fn from_edges(vsize: usize, edges: Vec<(usize, usize)>) -> Self {
35        Self { vsize, edges }
36    }
37}
38impl std::ops::Index<usize> for EdgeListGraph {
39    type Output = (usize, usize);
40    fn index(&self, index: usize) -> &Self::Output {
41        &self.edges[index]
42    }
43}
44
45pub struct EdgeListGraphScanner<U: IterScan<Output = usize>, T: IterScan> {
46    vsize: usize,
47    esize: usize,
48    _marker: PhantomData<fn() -> (U, T)>,
49}
50
51impl<U: IterScan<Output = usize>, T: IterScan> EdgeListGraphScanner<U, T> {
52    pub fn new(vsize: usize, esize: usize) -> Self {
53        Self {
54            vsize,
55            esize,
56            _marker: PhantomData,
57        }
58    }
59}
60
61impl<U: IterScan<Output = usize>, T: IterScan> MarkedIterScan for EdgeListGraphScanner<U, T> {
62    type Output = (EdgeListGraph, Vec<<T as IterScan>::Output>);
63    fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
64        let mut edges = Vec::with_capacity(self.esize);
65        let mut rest = Vec::with_capacity(self.esize);
66        for _ in 0..self.esize {
67            edges.push((U::scan(iter)?, U::scan(iter)?));
68            rest.push(T::scan(iter)?);
69        }
70        let graph = EdgeListGraph::from_edges(self.vsize, edges);
71        Some((graph, rest))
72    }
73}
competitive/graph/edge_list.rs

competitive/graph/
edge_list.rs
