Repository navigation
Expand file tree
/
Copy pathmc_solution.cpp
More file actions
85 lines (68 loc) · 2.35 KB
/
Copy pathmc_solution.cpp
File metadata and controls
85 lines (68 loc) · 2.35 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include "sms/instance/mc_solution.hpp"
#include "nlohmann/json.hpp"
namespace sms {
nlohmann::json partitionToJson(const NetworKit::Graph &g, const std::vector<bool> &part) {
nlohmann::json save;
std::vector<NetworKit::node> part0nodes{};
std::vector<NetworKit::node> part1nodes{};
for (auto u : g.nodeRange()) {
if (part[u]) {
part0nodes.push_back(u);
} else {
part1nodes.push_back(u);
}
}
save[kPartitionZeroName] = part0nodes;
save[kPartitionOneName] = part1nodes;
return save;
}
nlohmann::json partitionToJson(const std::vector<NetworKit::node> &existingNodes, const std::vector<bool> &part) {
nlohmann::json save;
std::vector<NetworKit::node> part0nodes{};
std::vector<NetworKit::node> part1nodes{};
for (auto u : existingNodes) {
if (part[u]) {
part0nodes.push_back(u);
} else {
part1nodes.push_back(u);
}
}
save[kPartitionZeroName] = part0nodes;
save[kPartitionOneName] = part1nodes;
return save;
}
std::vector<bool> partitionFromJson(const nlohmann::json &j) {
auto numNodes = j[kPartitionZeroName].size() + j[kPartitionOneName].size();
std::vector<bool> part(numNodes, false);
for (auto u : j[kPartitionOneName]) {
part[u] = true;
}
return part;
}
NetworKit::edgeweight solutionValue(const NetworKit::Graph &g, const std::vector<Partition> &part) {
NetworKit::edgeweight totalCutWeight = 0.0;
for (auto e : g.edgeWeightRange()) {
assert(part[e.u] != Partition::kUNASSIGNED);
assert(part[e.v] != Partition::kUNASSIGNED);
NetworKit::edgeweight value = e.weight * (part[e.u] ^ part[e.v]);
totalCutWeight += value;
}
return totalCutWeight;
}
NetworKit::edgeweight solutionValue(const NetworKit::Graph &g, const std::vector<bool> &part) {
NetworKit::edgeweight totalCutWeight = 0.0;
for (auto e : g.edgeWeightRange()) {
NetworKit::edgeweight value = e.weight * (part[e.u] ^ part[e.v]);
totalCutWeight += value;
}
return totalCutWeight;
}
std::vector<NetworKit::node> allIds(const std::vector<bool> &values, bool match) {
std::vector<NetworKit::node> ids;
for (unsigned int i = 0; i < values.size(); ++i) {
if (!(values[i] ^ match))
ids.push_back(i);
}
return ids;
}
} // namespace sms