minimum steiner tree

ソースコード

 1#include <vector>
 2#include <algorithm>
 3#include "titan_cpplib/graph/warshall_floyd_path.cpp"
 4using namespace std;
 5
 6// MinimumSteinerTree
 7namespace titan23 {
 8
 9    /**
10     * @brief 最小シュタイナー木など
11     * @details プリム法を用いた近似解法の実装
12     * 時間 O(|V|^3), 空間 O(|V|^2)
13     */
14    template<typename T>
15    class MinimumSteinerTree {
16      private:
17        int n;
18        T INF;
19        titan23::warshall_floyd_path<T> dist_path;
20
21      public:
22        MinimumSteinerTree() {}
23
24        // 時間 O(|V|^3), 空間 O(|V|^2)
25        MinimumSteinerTree(const vector<vector<pair<int, T>>> &G, const T INF) :
26                n((int)G.size()), INF(INF) {
27            dist_path = titan23::warshall_floyd_path<T>(G, INF);
28        }
29
30        // terminal を含むシュタイナー木の辺集合を返す
31        vector<pair<int, int>> build_prim(vector<int> terminal) {
32            if (terminal.empty()) return {};
33            vector<int> used_vertex;
34            used_vertex.reserve(terminal.size());
35            vector<pair<int, int>> edges;
36
37            used_vertex.emplace_back(terminal[0]);
38            terminal.erase(terminal.begin());
39
40            while (!terminal.empty()) {
41                T min_dist = INF;
42                int min_tree_indx = -1;
43                int min_terminal_indx = -1;
44                for (const int v: used_vertex) {
45                    for (int i = 0; i < terminal.size(); ++i) {
46                        T c = dist_path.get_dist(v, terminal[i]);
47                        if (c < min_dist) {
48                            min_dist = c;
49                            min_tree_indx = v;
50                            min_terminal_indx = i;
51                        }
52                    }
53                }
54                int min_terminal = terminal[min_terminal_indx];
55                terminal.erase(terminal.begin() + min_terminal_indx);
56                const vector<int> &path = dist_path.get_path(min_tree_indx, min_terminal);
57                for (int i = 0; i < path.size(); ++i) {
58                    auto it = find(terminal.begin(), terminal.end(), path[i]);
59                    if (it != terminal.end()) terminal.erase(it);
60                    if (i+1 < path.size()) edges.emplace_back(minmax(path[i], path[i+1]));
61                    used_vertex.emplace_back(path[i]);
62                }
63            }
64            sort(edges.begin(), edges.end());
65            edges.erase(unique(edges.begin(), edges.end()), edges.end());
66            return edges;
67        }
68    };
69}  // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/graph/minimum_steiner_tree.cpp