competitive/graph/
steiner_tree.rs

1use super::{
2    AdjacencyIndex, AdjacencyIndexWithValue, AdjacencyView, BitDpExt, PartialIgnoredOrd,
3    ShortestPathSemiRing, VertexMap, Vertices,
4};
5use std::{cmp::Reverse, collections::BinaryHeap, iter::repeat_with};
6
7pub trait SteinerTreeExt: Vertices {
8    fn steiner_tree<'a, S, M, I>(&self, terminals: I, weight: &'a M) -> SteinerTreeOutput<S, Self>
9    where
10        Self: VertexMap<S::T> + AdjacencyView<'a, M, S::T>,
11        S: ShortestPathSemiRing,
12        I: IntoIterator<Item = Self::VIndex> + ExactSizeIterator,
13    {
14        let tsize = terminals.len();
15        if tsize == 0 {
16            return SteinerTreeOutput {
17                g: self,
18                dp: vec![],
19            };
20        }
21        let mut dp: Vec<_> = repeat_with(|| self.construct_vmap(S::inf))
22            .take(1 << tsize)
23            .collect();
24        for (i, t) in terminals.into_iter().enumerate() {
25            *self.vmap_get_mut(&mut dp[1 << i], t) = S::source();
26        }
27        for bit in 1..1 << tsize {
28            for u in self.vertices() {
29                for sub in bit.subsets() {
30                    if sub != 0 {
31                        let cost =
32                            S::mul(self.vmap_get(&dp[sub], u), self.vmap_get(&dp[bit ^ sub], u));
33                        S::add_assign(self.vmap_get_mut(&mut dp[bit], u), &cost);
34                    }
35                }
36            }
37            let dp = &mut dp[bit];
38            let mut heap: BinaryHeap<_> = self
39                .vertices()
40                .map(|u| PartialIgnoredOrd(Reverse(self.vmap_get(dp, u).clone()), u))
41                .collect();
42            while let Some(PartialIgnoredOrd(Reverse(d), u)) = heap.pop() {
43                if self.vmap_get(dp, u) != &d {
44                    continue;
45                }
46                for a in self.aviews(weight, u) {
47                    let v = a.vindex();
48                    let nd = S::mul(&d, &a.avalue());
49                    if S::add_assign(self.vmap_get_mut(dp, v), &nd) {
50                        heap.push(PartialIgnoredOrd(Reverse(nd), v));
51                    }
52                }
53            }
54        }
55        SteinerTreeOutput { g: self, dp }
56    }
57}
58impl<G> SteinerTreeExt for G where G: Vertices {}
59pub struct SteinerTreeOutput<'g, S, G>
60where
61    G: VertexMap<S::T> + ?Sized,
62    S: ShortestPathSemiRing,
63{
64    g: &'g G,
65    dp: Vec<G::Vmap>,
66}
67impl<S, G> SteinerTreeOutput<'_, S, G>
68where
69    G: VertexMap<S::T> + ?Sized,
70    S: ShortestPathSemiRing,
71{
72    pub fn minimum_from_source(&self, source: G::VIndex) -> S::T {
73        match self.dp.last() {
74            Some(dp) => self.g.vmap_get(dp, source).clone(),
75            None => S::source(),
76        }
77    }
78}
competitive/graph/steiner_tree.rs

competitive/graph/
steiner_tree.rs
