minimum_diameter_spanning_tree.hpp¶
Construct a minimum-diameter spanning tree of a connected graph. The center of an optimal tree can be placed at a vertex or inside one graph edge. All-pairs shortest paths give every vertex eccentricity. For an edge center, sorting vertices by distance from one endpoint makes the maximum of the two endpoint-distance envelopes change monotonically, so one sweep tests its best split point. Doubling edge weights keeps every half-integral center exact. Finally, a shortest-path tree rooted at the best absolute center realizes the selected minimum diameter.
Verified by minimum_diameter_spanning_tree.
在带权无向图中求直径最小的生成树，并构造对应树边。
Implementation¶
#ifndef NOYA_MINIMUM_DIAMETER_SPANNING_TREE_HPP
#define NOYA_MINIMUM_DIAMETER_SPANNING_TREE_HPP 1
/// @complexity Time: O(V(E + V) log V + VE + V^2 log V).
/// Space: O(V^2 + V + E).
#include <algorithm>
#include <cassert>
#include <functional>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
template <class Weight> struct minimum_diameter_spanning_tree_result {
Weight diameter{};
std::vector<int> edge_ids;
};
/// @brief Construct a minimum-diameter spanning tree of a connected graph.
/// The center of an optimal tree can be placed at a vertex or inside one
/// graph edge. All-pairs shortest paths give every vertex eccentricity. For
/// an edge center, sorting vertices by distance from one endpoint makes the
/// maximum of the two endpoint-distance envelopes change monotonically, so
/// one sweep tests its best split point. Doubling edge weights keeps every
/// half-integral center exact. Finally, a shortest-path tree rooted at the
/// best absolute center realizes the selected minimum diameter.
template <class Weight>
minimum_diameter_spanning_tree_result<Weight>
minimum_diameter_spanning_tree(
int vertex_count,
const std::vector<std::tuple<int, int, Weight>> &edges) {
assert(vertex_count > 0);
struct adjacent_edge {
int to;
Weight weight;
int id;
};
std::vector<std::vector<adjacent_edge>> graph(vertex_count);
for (int id = 0; id < int(edges.size()); id++) {
auto [first, second, weight] = edges[id];
assert(0 <= first && first < vertex_count);
assert(0 <= second && second < vertex_count);
assert(weight >= Weight{});
weight *= Weight(2);
graph[first].push_back({second, weight, id});
graph[second].push_back({first, weight, id});
}
const Weight infinity = std::numeric_limits<Weight>::max() / 4;
struct shortest_path_result {
std::vector<Weight> distance;
std::vector<int> predecessor;
std::vector<int> predecessor_edge;
};
auto shortest_paths = [&](int source,
const std::vector<std::vector<adjacent_edge>>
¤t_graph) {
int size = int(current_graph.size());
shortest_path_result result{std::vector<Weight>(size, infinity),
std::vector<int>(size, -1),
std::vector<int>(size, -1)};
using state = std::pair<Weight, int>;
std::priority_queue<state, std::vector<state>, std::greater<state>> queue;
result.distance[source] = Weight{};
queue.emplace(Weight{}, source);
while (!queue.empty()) {
auto [distance, vertex] = queue.top();
queue.pop();
if (distance != result.distance[vertex]) {
continue;
}
for (auto [to, weight, id] : current_graph[vertex]) {
Weight candidate = distance + weight;
if (candidate < result.distance[to]) {
result.distance[to] = candidate;
result.predecessor[to] = vertex;
result.predecessor_edge[to] = id;
queue.emplace(candidate, to);
}
}
}
return result;
};
std::vector<std::vector<Weight>> distance(
vertex_count, std::vector<Weight>(vertex_count));
for (int source = 0; source < vertex_count; source++) {
distance[source] = shortest_paths(source, graph).distance;
for (Weight value : distance[source]) {
assert(value != infinity);
}
}
std::vector<std::vector<int>> order(vertex_count,
std::vector<int>(vertex_count));
Weight best_vertex_score = infinity;
int best_vertex = 0;
for (int vertex = 0; vertex < vertex_count; vertex++) {
for (int other = 0; other < vertex_count; other++) {
order[vertex][other] = other;
}
std::stable_sort(order[vertex].begin(), order[vertex].end(),
[&](int first, int second) {
return distance[vertex][first] >
distance[vertex][second];
});
Weight score = distance[vertex][order[vertex][0]] * Weight(2);
if (score < best_vertex_score) {
best_vertex_score = score;
best_vertex = vertex;
}
}
Weight best_edge_score = infinity;
int best_edge = -1;
int best_first = -1;
int best_second = -1;
Weight center_to_first{};
Weight center_to_second{};
for (int id = 0; id < int(edges.size()); id++) {
auto [first, second, original_weight] = edges[id];
if (first == second) {
continue;
}
Weight weight = original_weight * Weight(2);
int previous = order[first][0];
for (int vertex : order[first]) {
if (distance[second][vertex] > distance[second][previous]) {
Weight score = distance[second][previous] +
distance[first][vertex] + weight;
if (score < best_edge_score) {
best_edge_score = score;
best_edge = id;
best_first = first;
best_second = second;
center_to_first = score / Weight(2) - distance[first][vertex];
center_to_second = weight - center_to_first;
}
previous = vertex;
}
}
}
minimum_diameter_spanning_tree_result<Weight> result;
if (best_edge_score < best_vertex_score) {
int center = vertex_count;
auto augmented = graph;
augmented.emplace_back();
augmented[center].push_back(
{best_first, center_to_first, -1});
augmented[center].push_back(
{best_second, center_to_second, -1});
auto tree = shortest_paths(center, augmented);
result.diameter = best_edge_score / Weight(2);
result.edge_ids.reserve(vertex_count - 1);
for (int vertex = 0; vertex < vertex_count; vertex++) {
if (vertex != best_first && vertex != best_second) {
assert(tree.predecessor_edge[vertex] >= 0);
result.edge_ids.push_back(tree.predecessor_edge[vertex]);
}
}
result.edge_ids.push_back(best_edge);
} else {
auto tree = shortest_paths(best_vertex, graph);
result.diameter = best_vertex_score / Weight(2);
result.edge_ids.reserve(vertex_count - 1);
for (int vertex = 0; vertex < vertex_count; vertex++) {
if (vertex != best_vertex) {
assert(tree.predecessor_edge[vertex] >= 0);
result.edge_ids.push_back(tree.predecessor_edge[vertex]);
}
}
}
return result;
}
} // namespace noya
#endif // NOYA_MINIMUM_DIAMETER_SPANNING_TREE_HPP
#include <algorithm>
#include <cassert>
#include <functional>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
/// @complexity Time: O(V(E + V) log V + VE + V^2 log V).
/// Space: O(V^2 + V + E).
namespace noya {
template <class Weight> struct minimum_diameter_spanning_tree_result {
Weight diameter{};
std::vector<int> edge_ids;
};
/// @brief Construct a minimum-diameter spanning tree of a connected graph.
/// The center of an optimal tree can be placed at a vertex or inside one
/// graph edge. All-pairs shortest paths give every vertex eccentricity. For
/// an edge center, sorting vertices by distance from one endpoint makes the
/// maximum of the two endpoint-distance envelopes change monotonically, so
/// one sweep tests its best split point. Doubling edge weights keeps every
/// half-integral center exact. Finally, a shortest-path tree rooted at the
/// best absolute center realizes the selected minimum diameter.
template <class Weight>
minimum_diameter_spanning_tree_result<Weight>
minimum_diameter_spanning_tree(
int vertex_count,
const std::vector<std::tuple<int, int, Weight>> &edges) {
assert(vertex_count > 0);
struct adjacent_edge {
int to;
Weight weight;
int id;
};
std::vector<std::vector<adjacent_edge>> graph(vertex_count);
for (int id = 0; id < int(edges.size()); id++) {
auto [first, second, weight] = edges[id];
assert(0 <= first && first < vertex_count);
assert(0 <= second && second < vertex_count);
assert(weight >= Weight{});
weight *= Weight(2);
graph[first].push_back({second, weight, id});
graph[second].push_back({first, weight, id});
}
const Weight infinity = std::numeric_limits<Weight>::max() / 4;
struct shortest_path_result {
std::vector<Weight> distance;
std::vector<int> predecessor;
std::vector<int> predecessor_edge;
};
auto shortest_paths = [&](int source,
const std::vector<std::vector<adjacent_edge>>
¤t_graph) {
int size = int(current_graph.size());
shortest_path_result result{std::vector<Weight>(size, infinity),
std::vector<int>(size, -1),
std::vector<int>(size, -1)};
using state = std::pair<Weight, int>;
std::priority_queue<state, std::vector<state>, std::greater<state>> queue;
result.distance[source] = Weight{};
queue.emplace(Weight{}, source);
while (!queue.empty()) {
auto [distance, vertex] = queue.top();
queue.pop();
if (distance != result.distance[vertex]) {
continue;
}
for (auto [to, weight, id] : current_graph[vertex]) {
Weight candidate = distance + weight;
if (candidate < result.distance[to]) {
result.distance[to] = candidate;
result.predecessor[to] = vertex;
result.predecessor_edge[to] = id;
queue.emplace(candidate, to);
}
}
}
return result;
};
std::vector<std::vector<Weight>> distance(
vertex_count, std::vector<Weight>(vertex_count));
for (int source = 0; source < vertex_count; source++) {
distance[source] = shortest_paths(source, graph).distance;
for (Weight value : distance[source]) {
assert(value != infinity);
}
}
std::vector<std::vector<int>> order(vertex_count,
std::vector<int>(vertex_count));
Weight best_vertex_score = infinity;
int best_vertex = 0;
for (int vertex = 0; vertex < vertex_count; vertex++) {
for (int other = 0; other < vertex_count; other++) {
order[vertex][other] = other;
}
std::stable_sort(order[vertex].begin(), order[vertex].end(),
[&](int first, int second) {
return distance[vertex][first] >
distance[vertex][second];
});
Weight score = distance[vertex][order[vertex][0]] * Weight(2);
if (score < best_vertex_score) {
best_vertex_score = score;
best_vertex = vertex;
}
}
Weight best_edge_score = infinity;
int best_edge = -1;
int best_first = -1;
int best_second = -1;
Weight center_to_first{};
Weight center_to_second{};
for (int id = 0; id < int(edges.size()); id++) {
auto [first, second, original_weight] = edges[id];
if (first == second) {
continue;
}
Weight weight = original_weight * Weight(2);
int previous = order[first][0];
for (int vertex : order[first]) {
if (distance[second][vertex] > distance[second][previous]) {
Weight score = distance[second][previous] +
distance[first][vertex] + weight;
if (score < best_edge_score) {
best_edge_score = score;
best_edge = id;
best_first = first;
best_second = second;
center_to_first = score / Weight(2) - distance[first][vertex];
center_to_second = weight - center_to_first;
}
previous = vertex;
}
}
}
minimum_diameter_spanning_tree_result<Weight> result;
if (best_edge_score < best_vertex_score) {
int center = vertex_count;
auto augmented = graph;
augmented.emplace_back();
augmented[center].push_back(
{best_first, center_to_first, -1});
augmented[center].push_back(
{best_second, center_to_second, -1});
auto tree = shortest_paths(center, augmented);
result.diameter = best_edge_score / Weight(2);
result.edge_ids.reserve(vertex_count - 1);
for (int vertex = 0; vertex < vertex_count; vertex++) {
if (vertex != best_first && vertex != best_second) {
assert(tree.predecessor_edge[vertex] >= 0);
result.edge_ids.push_back(tree.predecessor_edge[vertex]);
}
}
result.edge_ids.push_back(best_edge);
} else {
auto tree = shortest_paths(best_vertex, graph);
result.diameter = best_vertex_score / Weight(2);
result.edge_ids.reserve(vertex_count - 1);
for (int vertex = 0; vertex < vertex_count; vertex++) {
if (vertex != best_vertex) {
assert(tree.predecessor_edge[vertex] >= 0);
result.edge_ids.push_back(tree.predecessor_edge[vertex]);
}
}
}
return result;
}
} // namespace noya