competitive/graph/
adjacency_list.rs

1use super::{IterScan, MarkedIterScan};
2use std::{marker::PhantomData, ops::Range};
3
4#[derive(Clone, Copy, Debug, Default, Eq, PartialEq, Ord, PartialOrd, Hash)]
5pub struct Adjacency {
6    pub id: usize,
7    pub to: usize,
8}
9impl Adjacency {
10    pub fn new(id: usize, to: usize) -> Adjacency {
11        Adjacency { id, to }
12    }
13}
14#[derive(Clone, Debug, Default)]
15pub struct AdjacencyListGraph {
16    pub vsize: usize,
17    pub esize: usize,
18    pub graph: Vec<Vec<Adjacency>>,
19}
20impl AdjacencyListGraph {
21    pub fn new(vsize: usize) -> AdjacencyListGraph {
22        AdjacencyListGraph {
23            vsize,
24            esize: 0,
25            graph: vec![vec![]; vsize],
26        }
27    }
28    pub fn add_edge(&mut self, from: usize, to: usize) {
29        self.graph[from].push(Adjacency::new(self.esize, to));
30        self.esize += 1;
31    }
32    pub fn add_undirected_edge(&mut self, u: usize, v: usize) {
33        self.graph[u].push(Adjacency::new(self.esize, v));
34        self.graph[v].push(Adjacency::new(self.esize, u));
35        self.esize += 1;
36    }
37    pub fn vertices(&self) -> Range<usize> {
38        0..self.vsize
39    }
40    pub fn adjacency(&self, from: usize) -> &Vec<Adjacency> {
41        &self.graph[from]
42    }
43}
44
45pub struct AdjacencyListGraphScanner<U: IterScan<Output = usize>, T: IterScan> {
46    vsize: usize,
47    esize: usize,
48    directed: bool,
49    _marker: PhantomData<fn() -> (U, T)>,
50}
51
52impl<U: IterScan<Output = usize>, T: IterScan> AdjacencyListGraphScanner<U, T> {
53    pub fn new(vsize: usize, esize: usize, directed: bool) -> Self {
54        Self {
55            vsize,
56            esize,
57            directed,
58            _marker: PhantomData,
59        }
60    }
61}
62
63impl<U: IterScan<Output = usize>, T: IterScan> MarkedIterScan for AdjacencyListGraphScanner<U, T> {
64    type Output = (AdjacencyListGraph, Vec<<T as IterScan>::Output>);
65    fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
66        let mut graph = AdjacencyListGraph::new(self.vsize);
67        let mut rest = Vec::with_capacity(self.esize);
68        for _ in 0..self.esize {
69            let (from, to) = (U::scan(iter)?, U::scan(iter)?);
70            if self.directed {
71                graph.add_edge(from, to);
72            } else {
73                graph.add_undirected_edge(from, to);
74            }
75            rest.push(T::scan(iter)?);
76        }
77        Some((graph, rest))
78    }
79}
competitive/graph/adjacency_list.rs

competitive/graph/
adjacency_list.rs
