steiner_tree.hpp¶
Construct a minimum Steiner tree in an undirected graph. Subset DP first joins two terminal groups at a common vertex, then a multi-source Dijkstra closure moves that root through the graph. Parent records replay both transitions and recover the selected original edge indices.
Verified by minimum_steiner_tree.
用子集 DP 求连接给定终端点的最小权 Steiner 树；适合终端数量较小的图上连通代价。
Implementation¶
#ifndef NOYA_STEINER_TREE_HPP
#define NOYA_STEINER_TREE_HPP 1
/// @complexity Time: O(3^k V + 2^k E log V) for k terminals.
/// Space: O(2^k V).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
template <class Weight> struct steiner_tree_edge {
int first;
int second;
Weight weight;
};
template <class Weight> struct steiner_tree_result {
Weight weight;
std::vector<int> edge_ids;
};
/// @brief Construct a minimum Steiner tree in an undirected graph. Subset DP
/// first joins two terminal groups at a common vertex, then a multi-source
/// Dijkstra closure moves that root through the graph. Parent records replay
/// both transitions and recover the selected original edge indices.
template <class Weight>
steiner_tree_result<Weight>
steiner_tree_with_edges(int n, const std::vector<steiner_tree_edge<Weight>> &edges,
std::vector<int> terminals) {
assert(n >= 0);
struct adjacent_edge {
int next;
Weight weight;
int id;
};
std::vector<std::vector<adjacent_edge>> graph(n);
for (int id = 0; id < int(edges.size()); id++) {
auto [first, second, weight] = edges[id];
assert(0 <= first && first < n && 0 <= second && second < n);
assert(!(weight < Weight{}));
graph[first].push_back({second, weight, id});
graph[second].push_back({first, weight, id});
}
for (int terminal : terminals) {
assert(0 <= terminal && terminal < n);
}
std::sort(terminals.begin(), terminals.end());
terminals.erase(std::unique(terminals.begin(), terminals.end()),
terminals.end());
const int terminal_count = int(terminals.size());
assert(terminal_count < int(sizeof(unsigned) * 8));
if (terminal_count == 0) {
return {Weight{}, {}};
}
const Weight infinity = std::numeric_limits<Weight>::max();
const int mask_count = 1 << terminal_count;
struct parent_record {
int subset = 0;
int previous_vertex = -1;
int edge_id = -1;
};
std::vector<std::vector<Weight>> distance(mask_count,
std::vector<Weight>(n, infinity));
std::vector<std::vector<parent_record>> parent(
mask_count, std::vector<parent_record>(n));
for (int id = 0; id < terminal_count; id++) {
distance[1 << id][terminals[id]] = Weight{};
}
for (int mask = 1; mask < mask_count; mask++) {
for (int subset = (mask - 1) & mask; subset > 0;
subset = (subset - 1) & mask) {
int other = mask ^ subset;
if (subset > other) {
continue;
}
for (int vertex = 0; vertex < n; vertex++) {
if (distance[subset][vertex] == infinity ||
distance[other][vertex] == infinity) {
continue;
}
Weight candidate = distance[subset][vertex] + distance[other][vertex];
if (candidate < distance[mask][vertex]) {
distance[mask][vertex] = candidate;
parent[mask][vertex] = {subset, -1, -1};
}
}
}
using state = std::pair<Weight, int>;
std::priority_queue<state, std::vector<state>, std::greater<>> queue;
for (int vertex = 0; vertex < n; vertex++) {
if (distance[mask][vertex] != infinity) {
queue.emplace(distance[mask][vertex], vertex);
}
}
while (!queue.empty()) {
auto [current, vertex] = queue.top();
queue.pop();
if (current != distance[mask][vertex]) {
continue;
}
for (auto edge : graph[vertex]) {
if (current <= infinity - edge.weight &&
current + edge.weight < distance[mask][edge.next]) {
distance[mask][edge.next] = current + edge.weight;
parent[mask][edge.next] = {0, vertex, edge.id};
queue.emplace(distance[mask][edge.next], edge.next);
}
}
}
}
int root = int(std::min_element(distance.back().begin(),
distance.back().end()) -
distance.back().begin());
if (distance.back()[root] == infinity) {
return {infinity, {}};
}
std::vector<bool> used(edges.size());
auto recover = [&](auto &&self, int mask, int vertex) -> void {
parent_record record = parent[mask][vertex];
if (record.edge_id != -1) {
self(self, mask, record.previous_vertex);
used[record.edge_id] = true;
} else if (record.subset != 0) {
self(self, record.subset, vertex);
self(self, mask ^ record.subset, vertex);
}
};
recover(recover, mask_count - 1, root);
std::vector<int> selected;
Weight selected_weight{};
for (int id = 0; id < int(edges.size()); id++) {
if (used[id]) {
selected.push_back(id);
selected_weight += edges[id].weight;
}
}
assert(selected_weight == distance.back()[root]);
return {selected_weight, std::move(selected)};
}
/// @brief Minimum weight of a connected subgraph containing all terminals in
/// an undirected nonnegative-weight graph, using O(3^k n + 2^k m log n).
template <class Weight>
Weight
steiner_tree(const std::vector<std::vector<std::pair<int, Weight>>> &graph,
std::vector<int> terminals) {
const int n = int(graph.size());
for (int terminal : terminals) {
assert(0 <= terminal && terminal < n);
}
for (int vertex = 0; vertex < n; vertex++) {
for (auto [next, weight] : graph[vertex]) {
assert(0 <= next && next < n);
assert(!(weight < Weight{}));
}
}
std::sort(terminals.begin(), terminals.end());
terminals.erase(std::unique(terminals.begin(), terminals.end()),
terminals.end());
const int terminal_count = int(terminals.size());
assert(terminal_count < int(sizeof(unsigned) * 8));
if (terminal_count == 0) {
return Weight{};
}
const Weight infinity = std::numeric_limits<Weight>::max();
const int mask_count = 1 << terminal_count;
std::vector<std::vector<Weight>> distance(mask_count,
std::vector<Weight>(n, infinity));
for (int id = 0; id < terminal_count; id++) {
distance[1 << id][terminals[id]] = Weight{};
}
for (int mask = 1; mask < mask_count; mask++) {
for (int subset = (mask - 1) & mask; subset > 0;
subset = (subset - 1) & mask) {
int other = mask ^ subset;
if (subset > other) {
continue;
}
for (int vertex = 0; vertex < n; vertex++) {
if (distance[subset][vertex] == infinity ||
distance[other][vertex] == infinity) {
continue;
}
distance[mask][vertex] =
std::min(distance[mask][vertex],
distance[subset][vertex] + distance[other][vertex]);
}
}
using state = std::pair<Weight, int>;
std::priority_queue<state, std::vector<state>, std::greater<>> queue;
for (int vertex = 0; vertex < n; vertex++) {
if (distance[mask][vertex] != infinity) {
queue.emplace(distance[mask][vertex], vertex);
}
}
while (!queue.empty()) {
auto [current, vertex] = queue.top();
queue.pop();
if (current != distance[mask][vertex]) {
continue;
}
for (auto [next, weight] : graph[vertex]) {
if (current <= infinity - weight &&
current + weight < distance[mask][next]) {
distance[mask][next] = current + weight;
queue.emplace(distance[mask][next], next);
}
}
}
}
return *std::min_element(distance.back().begin(), distance.back().end());
}
} // namespace noya
#endif // NOYA_STEINER_TREE_HPP
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
/// @complexity Time: O(3^k V + 2^k E log V) for k terminals.
/// Space: O(2^k V).
namespace noya {
template <class Weight> struct steiner_tree_edge {
int first;
int second;
Weight weight;
};
template <class Weight> struct steiner_tree_result {
Weight weight;
std::vector<int> edge_ids;
};
/// @brief Construct a minimum Steiner tree in an undirected graph. Subset DP
/// first joins two terminal groups at a common vertex, then a multi-source
/// Dijkstra closure moves that root through the graph. Parent records replay
/// both transitions and recover the selected original edge indices.
template <class Weight>
steiner_tree_result<Weight>
steiner_tree_with_edges(int n, const std::vector<steiner_tree_edge<Weight>> &edges,
std::vector<int> terminals) {
assert(n >= 0);
struct adjacent_edge {
int next;
Weight weight;
int id;
};
std::vector<std::vector<adjacent_edge>> graph(n);
for (int id = 0; id < int(edges.size()); id++) {
auto [first, second, weight] = edges[id];
assert(0 <= first && first < n && 0 <= second && second < n);
assert(!(weight < Weight{}));
graph[first].push_back({second, weight, id});
graph[second].push_back({first, weight, id});
}
for (int terminal : terminals) {
assert(0 <= terminal && terminal < n);
}
std::sort(terminals.begin(), terminals.end());
terminals.erase(std::unique(terminals.begin(), terminals.end()),
terminals.end());
const int terminal_count = int(terminals.size());
assert(terminal_count < int(sizeof(unsigned) * 8));
if (terminal_count == 0) {
return {Weight{}, {}};
}
const Weight infinity = std::numeric_limits<Weight>::max();
const int mask_count = 1 << terminal_count;
struct parent_record {
int subset = 0;
int previous_vertex = -1;
int edge_id = -1;
};
std::vector<std::vector<Weight>> distance(mask_count,
std::vector<Weight>(n, infinity));
std::vector<std::vector<parent_record>> parent(
mask_count, std::vector<parent_record>(n));
for (int id = 0; id < terminal_count; id++) {
distance[1 << id][terminals[id]] = Weight{};
}
for (int mask = 1; mask < mask_count; mask++) {
for (int subset = (mask - 1) & mask; subset > 0;
subset = (subset - 1) & mask) {
int other = mask ^ subset;
if (subset > other) {
continue;
}
for (int vertex = 0; vertex < n; vertex++) {
if (distance[subset][vertex] == infinity ||
distance[other][vertex] == infinity) {
continue;
}
Weight candidate = distance[subset][vertex] + distance[other][vertex];
if (candidate < distance[mask][vertex]) {
distance[mask][vertex] = candidate;
parent[mask][vertex] = {subset, -1, -1};
}
}
}
using state = std::pair<Weight, int>;
std::priority_queue<state, std::vector<state>, std::greater<>> queue;
for (int vertex = 0; vertex < n; vertex++) {
if (distance[mask][vertex] != infinity) {
queue.emplace(distance[mask][vertex], vertex);
}
}
while (!queue.empty()) {
auto [current, vertex] = queue.top();
queue.pop();
if (current != distance[mask][vertex]) {
continue;
}
for (auto edge : graph[vertex]) {
if (current <= infinity - edge.weight &&
current + edge.weight < distance[mask][edge.next]) {
distance[mask][edge.next] = current + edge.weight;
parent[mask][edge.next] = {0, vertex, edge.id};
queue.emplace(distance[mask][edge.next], edge.next);
}
}
}
}
int root = int(std::min_element(distance.back().begin(),
distance.back().end()) -
distance.back().begin());
if (distance.back()[root] == infinity) {
return {infinity, {}};
}
std::vector<bool> used(edges.size());
auto recover = [&](auto &&self, int mask, int vertex) -> void {
parent_record record = parent[mask][vertex];
if (record.edge_id != -1) {
self(self, mask, record.previous_vertex);
used[record.edge_id] = true;
} else if (record.subset != 0) {
self(self, record.subset, vertex);
self(self, mask ^ record.subset, vertex);
}
};
recover(recover, mask_count - 1, root);
std::vector<int> selected;
Weight selected_weight{};
for (int id = 0; id < int(edges.size()); id++) {
if (used[id]) {
selected.push_back(id);
selected_weight += edges[id].weight;
}
}
assert(selected_weight == distance.back()[root]);
return {selected_weight, std::move(selected)};
}
/// @brief Minimum weight of a connected subgraph containing all terminals in
/// an undirected nonnegative-weight graph, using O(3^k n + 2^k m log n).
template <class Weight>
Weight
steiner_tree(const std::vector<std::vector<std::pair<int, Weight>>> &graph,
std::vector<int> terminals) {
const int n = int(graph.size());
for (int terminal : terminals) {
assert(0 <= terminal && terminal < n);
}
for (int vertex = 0; vertex < n; vertex++) {
for (auto [next, weight] : graph[vertex]) {
assert(0 <= next && next < n);
assert(!(weight < Weight{}));
}
}
std::sort(terminals.begin(), terminals.end());
terminals.erase(std::unique(terminals.begin(), terminals.end()),
terminals.end());
const int terminal_count = int(terminals.size());
assert(terminal_count < int(sizeof(unsigned) * 8));
if (terminal_count == 0) {
return Weight{};
}
const Weight infinity = std::numeric_limits<Weight>::max();
const int mask_count = 1 << terminal_count;
std::vector<std::vector<Weight>> distance(mask_count,
std::vector<Weight>(n, infinity));
for (int id = 0; id < terminal_count; id++) {
distance[1 << id][terminals[id]] = Weight{};
}
for (int mask = 1; mask < mask_count; mask++) {
for (int subset = (mask - 1) & mask; subset > 0;
subset = (subset - 1) & mask) {
int other = mask ^ subset;
if (subset > other) {
continue;
}
for (int vertex = 0; vertex < n; vertex++) {
if (distance[subset][vertex] == infinity ||
distance[other][vertex] == infinity) {
continue;
}
distance[mask][vertex] =
std::min(distance[mask][vertex],
distance[subset][vertex] + distance[other][vertex]);
}
}
using state = std::pair<Weight, int>;
std::priority_queue<state, std::vector<state>, std::greater<>> queue;
for (int vertex = 0; vertex < n; vertex++) {
if (distance[mask][vertex] != infinity) {
queue.emplace(distance[mask][vertex], vertex);
}
}
while (!queue.empty()) {
auto [current, vertex] = queue.top();
queue.pop();
if (current != distance[mask][vertex]) {
continue;
}
for (auto [next, weight] : graph[vertex]) {
if (current <= infinity - weight &&
current + weight < distance[mask][next]) {
distance[mask][next] = current + weight;
queue.emplace(distance[mask][next], next);
}
}
}
}
return *std::min_element(distance.back().begin(), distance.back().end());
}
} // namespace noya