Struct SteinerTreeBuilder 

pub struct SteinerTreeBuilder<'g, G, S = (), P = NoParent>
where
    G: Graph,
    P: SteinerTreeParentPolicy<G>,
{
    graph: &'g G,
    _marker: PhantomData<fn() -> (S, P)>,
}

Fields

graph: &'g G

_marker: PhantomData<fn() -> (S, P)>

Implementations

impl<'g, G, S, P> SteinerTreeBuilder<'g, G, S, P>

where G: Graph, P: SteinerTreeParentPolicy<G>,

pub fn with_sp<T>(self) -> SteinerTreeBuilder<'g, G, T, P>

where T: ShortestPathSemiRing,

Examples found in repository

crates/competitive/src/graph/steiner_tree.rs (line 108)

    pub fn with_standard_sp<M>(self) -> SteinerTreeBuilder<'g, G, StandardSp<M>, P>
    where
        M: Monoid<T: Bounded + Ord>,
    {
        self.with_sp()
    }

    pub fn with_standard_sp_additive<T>(
        self,
    ) -> SteinerTreeBuilder<'g, G, StandardSp<AdditiveOperation<T>>, P>
    where
        T: Clone + Zero + Add<Output = T> + Bounded + Ord,
    {
        self.with_sp()
    }

    pub fn with_option_sp<M>(self) -> SteinerTreeBuilder<'g, G, OptionSp<M>, P>
    where
        M: Monoid<T: Ord>,
    {
        self.with_sp()
    }

    pub fn with_option_sp_additive<T>(
        self,
    ) -> SteinerTreeBuilder<'g, G, OptionSp<AdditiveOperation<T>>, P>
    where
        T: Clone + Zero + Add<Output = T> + Ord,
    {
        self.with_sp()
    }

pub fn with_standard_sp<M>(self) -> SteinerTreeBuilder<'g, G, StandardSp<M>, P>

where M: Monoid<T: Bounded + Ord>,

pub fn with_standard_sp_additive<T>( self, ) -> SteinerTreeBuilder<'g, G, StandardSp<AdditiveOperation<T>>, P>

where T: Clone + Zero + Add<Output = T> + Bounded + Ord,

Examples found in repository

crates/library_checker/src/graph/minimum_steiner_tree.rs (line 11)

pub fn minimum_steiner_tree(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, m, (graph, weights): @UndirectedGraphScanner::<usize, u64>::new(n, m));
    sc!(k, terminals: [usize; k]);
    let tree = graph
        .steiner_tree()
        .with_standard_sp_additive()
        .with_parent()
        .solve(terminals[1..].iter().copied(), |eid| weights[eid]);
    let edges = tree.edges_from_source(terminals[0]).unwrap();
    pp!(tree.minimum_from_source(terminals[0]), edges.len(); @it edges);
}

pub fn with_option_sp<M>(self) -> SteinerTreeBuilder<'g, G, OptionSp<M>, P>

where M: Monoid<T: Ord>,

pub fn with_option_sp_additive<T>( self, ) -> SteinerTreeBuilder<'g, G, OptionSp<AdditiveOperation<T>>, P>

where T: Clone + Zero + Add<Output = T> + Ord,

impl<'g, G, S> SteinerTreeBuilder<'g, G, S>

where G: Graph,

pub fn with_parent(self) -> SteinerTreeBuilder<'g, G, S, RecordParent>

where RecordParent: SteinerTreeParentPolicy<G>,

Examples found in repository

crates/library_checker/src/graph/minimum_steiner_tree.rs (line 12)

pub fn minimum_steiner_tree(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, m, (graph, weights): @UndirectedGraphScanner::<usize, u64>::new(n, m));
    sc!(k, terminals: [usize; k]);
    let tree = graph
        .steiner_tree()
        .with_standard_sp_additive()
        .with_parent()
        .solve(terminals[1..].iter().copied(), |eid| weights[eid]);
    let edges = tree.edges_from_source(terminals[0]).unwrap();
    pp!(tree.minimum_from_source(terminals[0]), edges.len(); @it edges);
}

impl<'g, G, S, P> SteinerTreeBuilder<'g, G, S, P>

where G: Graph + VertexMap<S::T>, S: ShortestPathSemiRing, P: SteinerTreeParentPolicy<G>,

pub fn solve<M, I>( &self, terminals: I, weight: M, ) -> SteinerTreeOutput<'g, S, G, P>

where M: Fn(G::Label) -> S::T, I: ExactSizeIterator<Item = G::Vertex>,

Requires commutative multiplication and nonnegative edge weights.

Examples found in repository

crates/library_checker/src/graph/minimum_steiner_tree.rs (line 13)

pub fn minimum_steiner_tree(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, m, (graph, weights): @UndirectedGraphScanner::<usize, u64>::new(n, m));
    sc!(k, terminals: [usize; k]);
    let tree = graph
        .steiner_tree()
        .with_standard_sp_additive()
        .with_parent()
        .solve(terminals[1..].iter().copied(), |eid| weights[eid]);
    let edges = tree.edges_from_source(terminals[0]).unwrap();
    pp!(tree.minimum_from_source(terminals[0]), edges.len(); @it edges);
}