Struct SparseGraphBuilder

pub struct SparseGraphBuilder<T, D> { /* private fields */ }

Implementations

impl<T, D> SparseGraphBuilder<T, D>

pub fn new(vsize: usize) -> Self

Examples found in repository

crates/competitive/src/graph/sparse_graph.rs (line 55)

    pub fn builder<T>(vsize: usize) -> SparseGraphBuilder<T, D> {
        SparseGraphBuilder::new(vsize)
    }

pub fn new_with_esize(vsize: usize, esize: usize) -> Self

Examples found in repository

crates/competitive/src/graph/sparse_graph.rs (line 58)

    pub fn builder_with_esize<T>(vsize: usize, esize: usize) -> SparseGraphBuilder<T, D> {
        SparseGraphBuilder::new_with_esize(vsize, esize)
    }
}

pub trait SparseGraphConstruction: Sized {
    fn construct_graph(vsize: usize, edges: Vec<(usize, usize)>) -> SparseGraph<Self>;
}

impl<D> SparseGraph<D>
where
    D: SparseGraphConstruction,
{
    /// Construct graph from edges.
    pub fn from_edges(vsize: usize, edges: Vec<(usize, usize)>) -> Self {
        D::construct_graph(vsize, edges)
    }
}

impl SparseGraphConstruction for DirectedEdge {
    fn construct_graph(vsize: usize, edges: Vec<(usize, usize)>) -> SparseGraph<Self> {
        let mut start: Vec<_> = vec![0usize; vsize + 1];
        for (from, _) in edges.iter().cloned() {
            start[from] += 1;
        }
        for i in 1..=vsize {
            start[i] += start[i - 1];
        }
        let mut elist = Vec::<Adjacency>::with_capacity(edges.len());
        let ptr = elist.as_mut_ptr();
        for (id, (from, to)) in edges.iter().cloned().enumerate() {
            start[from] -= 1;
            unsafe { ptr.add(start[from]).write(Adjacency::new(id, to)) };
        }
        unsafe { elist.set_len(edges.len()) };
        SparseGraph {
            vsize,
            start,
            elist,
            edges,
            _marker: PhantomData,
        }
    }
}

impl SparseGraphConstruction for UndirectedEdge {
    fn construct_graph(vsize: usize, edges: Vec<(usize, usize)>) -> SparseGraph<Self> {
        let mut start: Vec<_> = vec![0usize; vsize + 1];
        for (from, to) in edges.iter().cloned() {
            start[to] += 1;
            start[from] += 1;
        }
        for i in 1..=vsize {
            start[i] += start[i - 1];
        }
        let mut elist = Vec::<Adjacency>::with_capacity(edges.len() * 2);
        let ptr = elist.as_mut_ptr();
        for (id, (from, to)) in edges.iter().cloned().enumerate() {
            start[from] -= 1;
            unsafe { ptr.add(start[from]).write(Adjacency::new(id, to)) };
            start[to] -= 1;
            unsafe { ptr.add(start[to]).write(Adjacency::new(id, from)) };
        }
        unsafe { elist.set_len(edges.len() * 2) };
        SparseGraph {
            vsize,
            start,
            elist,
            edges,
            _marker: PhantomData,
        }
    }
}

impl SparseGraphConstruction for BidirectionalEdge {
    fn construct_graph(vsize: usize, edges: Vec<(usize, usize)>) -> SparseGraph<Self> {
        let mut start: Vec<_> = vec![0usize; vsize + 1];
        for (from, to) in edges.iter().cloned() {
            start[to] += 1;
            start[from] += 1;
        }
        for i in 1..=vsize {
            start[i] += start[i - 1];
        }
        let mut elist = Vec::<Adjacency>::with_capacity(edges.len() * 2);
        let ptr = elist.as_mut_ptr();
        for (id, (from, to)) in edges.iter().cloned().enumerate() {
            start[from] -= 1;
            unsafe { ptr.add(start[from]).write(Adjacency::new(id * 2, to)) };
            start[to] -= 1;
            unsafe { ptr.add(start[to]).write(Adjacency::new(id * 2 + 1, from)) };
        }
        unsafe { elist.set_len(edges.len() * 2) };
        SparseGraph {
            vsize,
            start,
            elist,
            edges,
            _marker: PhantomData,
        }
    }
}

pub type DirectedSparseGraph = SparseGraph<DirectedEdge>;
pub type UndirectedSparseGraph = SparseGraph<UndirectedEdge>;
pub type BidirectionalSparseGraph = SparseGraph<BidirectionalEdge>;

pub struct SparseGraphBuilder<T, D> {
    vsize: usize,
    edges: Vec<(usize, usize)>,
    rest: Vec<T>,
    _marker: Marker<D>,
}
impl<T, D> SparseGraphBuilder<T, D> {
    pub fn new(vsize: usize) -> Self {
        Self {
            vsize,
            edges: Default::default(),
            rest: Default::default(),
            _marker: PhantomData,
        }
    }
    pub fn new_with_esize(vsize: usize, esize: usize) -> Self {
        Self {
            vsize,
            edges: Vec::with_capacity(esize),
            rest: Vec::with_capacity(esize),
            _marker: PhantomData,
        }
    }
    pub fn add_edge(&mut self, u: usize, v: usize, w: T) {
        self.edges.push((u, v));
        self.rest.push(w);
    }
}
impl<T, D> SparseGraphBuilder<T, D>
where
    D: SparseGraphConstruction,
{
    pub fn build(self) -> (SparseGraph<D>, Vec<T>) {
        let graph = SparseGraph::from_edges(self.vsize, self.edges);
        (graph, self.rest)
    }
}

pub struct SparseGraphScanner<U, T, D>
where
    U: IterScan<Output = usize>,
    T: IterScan,
{
    vsize: usize,
    esize: usize,
    _marker: Marker<(U, T, D)>,
}

impl<U, T, D> SparseGraphScanner<U, T, D>
where
    U: IterScan<Output = usize>,
    T: IterScan,
{
    pub fn new(vsize: usize, esize: usize) -> Self {
        Self {
            vsize,
            esize,
            _marker: PhantomData,
        }
    }
}

impl<U, T, D> MarkedIterScan for SparseGraphScanner<U, T, D>
where
    U: IterScan<Output = usize>,
    T: IterScan,
    D: SparseGraphConstruction,
{
    type Output = (SparseGraph<D>, Vec<<T as IterScan>::Output>);
    fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
        let mut builder = SparseGraphBuilder::new_with_esize(self.vsize, self.esize);
        for _ in 0..self.esize {
            builder.add_edge(U::scan(iter)?, U::scan(iter)?, T::scan(iter)?);
        }
        Some(builder.build())
    }

pub fn add_edge(&mut self, u: usize, v: usize, w: T)

Examples found in repository

crates/competitive/src/graph/sparse_graph.rs (line 236)

    fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
        let mut builder = SparseGraphBuilder::new_with_esize(self.vsize, self.esize);
        for _ in 0..self.esize {
            builder.add_edge(U::scan(iter)?, U::scan(iter)?, T::scan(iter)?);
        }
        Some(builder.build())
    }

impl<T, D> SparseGraphBuilder<T, D>

where D: SparseGraphConstruction,

pub fn build(self) -> (SparseGraph<D>, Vec<T>)

Examples found in repository

crates/competitive/src/graph/sparse_graph.rs (line 238)

    fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
        let mut builder = SparseGraphBuilder::new_with_esize(self.vsize, self.esize);
        for _ in 0..self.esize {
            builder.add_edge(U::scan(iter)?, U::scan(iter)?, T::scan(iter)?);
        }
        Some(builder.build())
    }