Struct SparseGraphBuilder 

pub struct SparseGraphBuilder<T, D> {
    vsize: usize,
    edges: Vec<(usize, usize)>,
    rest: Vec<T>,
    _marker: PhantomData<fn() -> D>,
}

Fields

vsize: usize

edges: Vec<(usize, usize)>

rest: Vec<T>

_marker: PhantomData<fn() -> D>

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 39)

    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 42)

    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)
    }
    pub fn reverse_graph(&self) -> SparseGraph<D> {
        let edges = self.edges.iter().map(|&(from, to)| (to, from)).collect();
        D::construct_graph(self.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 neighbors = Vec::<Neighbor<usize, usize>>::with_capacity(edges.len());
        let ptr = neighbors.as_mut_ptr();
        for (id, (from, to)) in edges.iter().cloned().enumerate() {
            start[from] -= 1;
            unsafe { ptr.add(start[from]).write(Neighbor::new(to, id)) };
        }
        unsafe { neighbors.set_len(edges.len()) };
        SparseGraph {
            vsize,
            start,
            neighbors,
            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 neighbors = Vec::<Neighbor<usize, usize>>::with_capacity(edges.len() * 2);
        let ptr = neighbors.as_mut_ptr();
        for (id, (from, to)) in edges.iter().cloned().enumerate() {
            start[from] -= 1;
            unsafe { ptr.add(start[from]).write(Neighbor::new(to, id)) };
            start[to] -= 1;
            unsafe { ptr.add(start[to]).write(Neighbor::new(from, id)) };
        }
        unsafe { neighbors.set_len(edges.len() * 2) };
        SparseGraph {
            vsize,
            start,
            neighbors,
            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 neighbors = Vec::<Neighbor<usize, usize>>::with_capacity(edges.len() * 2);
        let ptr = neighbors.as_mut_ptr();
        for (id, (from, to)) in edges.iter().cloned().enumerate() {
            start[from] -= 1;
            unsafe { ptr.add(start[from]).write(Neighbor::new(to, id * 2)) };
            start[to] -= 1;
            unsafe { ptr.add(start[to]).write(Neighbor::new(from, id * 2 + 1)) };
        }
        unsafe { neighbors.set_len(edges.len() * 2) };
        SparseGraph {
            vsize,
            start,
            neighbors,
            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: Scan<Output = usize>,
    T: Scan,
{
    vsize: usize,
    esize: usize,
    _marker: Marker<(U, T, D)>,
}

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

impl<U, T, D> MarkedScan for SparseGraphScanner<U, T, D>
where
    U: Scan<Output = usize>,
    T: Scan,
    D: SparseGraphConstruction,
{
    type Output = (SparseGraph<D>, Vec<<T as Scan>::Output>);
    fn mscan<I: ScanSource>(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 224)

    fn mscan<I: ScanSource>(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 226)

    fn mscan<I: ScanSource>(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())
    }