Struct SteinerTreeOutput 

pub struct SteinerTreeOutput<'g, S, G, P = NoParent>
where
    G: Graph + VertexMap<S::T>,
    S: ShortestPathSemiRing,
    P: SteinerTreeParentPolicy<G>,
{
    graph: &'g G,
    dp: Vec<<G as VertexMap<S::T>>::Vmap>,
    parent: Vec<P::State>,
}

Fields

graph: &'g G

dp: Vec<<G as VertexMap<S::T>>::Vmap>

parent: Vec<P::State>

Implementations

impl<S, G, P> SteinerTreeOutput<'_, S, G, P>

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

pub fn minimum_from_source(&self, source: G::Vertex) -> S::T

Examples found in repository

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

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);
}

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

    pub fn edges_from_source(&self, source: G::Vertex) -> Option<Vec<G::Label>> {
        if self.dp.is_empty() {
            return Some(vec![]);
        }
        if self.minimum_from_source(source) == S::inf() {
            return None;
        }
        let graph = self.graph;
        let mut index = graph.construct_vmap(|| 0usize);
        for (i, u) in graph.vertices().enumerate() {
            *graph.vmap_get_mut(&mut index, u) = i;
        }
        let mut uf = UnionFind::new(graph.vsize());
        let mut edges = vec![];
        let mut stack = vec![(self.dp.len() - 1, source)];
        while let Some((bit, u)) = stack.pop() {
            match graph.vmap_get(&self.parent[bit], u) {
                SteinerTreeParent::None => {}
                &SteinerTreeParent::Split(sub) => {
                    stack.push((sub, u));
                    stack.push((bit ^ sub, u));
                }
                SteinerTreeParent::Edge(v, label) => {
                    if uf.unite(*graph.vmap_get(&index, u), *graph.vmap_get(&index, *v)) {
                        edges.push(label.clone());
                    }
                    stack.push((bit, *v));
                }
            }
        }
        Some(edges)
    }

impl<S, G> SteinerTreeOutput<'_, S, G, RecordParent>

where G: Graph<Label: Clone> + VertexMap<S::T> + VertexMap<usize> + VertexMap<SteinerTreeParent<<G as Graph>::Vertex, <G as Graph>::Label>>, S: ShortestPathSemiRing,

pub fn edges_from_source(&self, source: G::Vertex) -> Option<Vec<G::Label>>

For undirected graphs with nonnegative additive weights. Returns None when the terminals cannot be connected to source.

Examples found in repository

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

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);
}