Repository navigation
Expand file tree
/
Copy pathmaxcut.cpp
More file actions
72 lines (59 loc) · 2.23 KB
/
Copy pathmaxcut.cpp
File metadata and controls
72 lines (59 loc) · 2.23 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
#include "sms/instance/maxcut.hpp"
#include "sms/auxiliary/math.hpp"
#include "sms/graph/graphs.hpp"
namespace sms {
MaxCut::MaxCut(const NetworKit::Graph &g, int shuffleVertices) : scalingFactor_(1.0), offset_(0.0) {
auto res = compactGraph(g, shuffleVertices);
graph_ = std::move(res.compactGraph);
graph_.indexEdges();
originalToNewNode_ = std::move(res.orig2compact);
newToOriginalNode_ = std::move(res.compact2orig);
for (auto e : graph_.edgeWeightRange()) {
if (!isInteger(e.weight)) {
integerSolutions_ = false;
break;
}
}
}
double MaxCut::getSolutionValue(const std::vector<uint8_t> &solVector) const {
assert(std::all_of(solVector.begin(), solVector.end(), [](auto i) { return i == 0 || i == 1; }));
double res = 0;
for (auto e : graph_.edgeWeightRange()) {
res += (solVector[e.u] ^ solVector[e.v]) * e.weight;
}
return res + offset_;
}
nlohmann::ordered_json MaxCut::getInstanceInformation() {
nlohmann::ordered_json j;
j["num nodes"] = getNumberOfVertices();
j["num edges"] = getNumberOfEdges();
j["scaling factor"] = scalingFactor_;
j["offset"] = offset_;
return j;
}
NetworKit::edgeweight MaxCut::scale() {
auto edgeWeightBasedDivisor = edgeWeightDivisor(graph_);
if (edgeWeightBasedDivisor != 1.) {
for (auto e : graph_.edgeWeightRange()) {
auto newWeight = e.weight / edgeWeightBasedDivisor;
graph_.setWeight(e.u, e.v, newWeight);
}
scalingFactor_ *= edgeWeightBasedDivisor;
}
auto degreeBasedDivisor = degreeBasedScaling(graph_);
if (degreeBasedDivisor != 1.0) {
for (auto e : graph_.edgeWeightRange()) {
auto newWeight = e.weight / degreeBasedDivisor;
graph_.setWeight(e.u, e.v, newWeight);
}
scalingFactor_ *= degreeBasedDivisor;
}
return edgeWeightBasedDivisor * degreeBasedDivisor;
}
void MaxCut::printInstanceInformation(std::ostream &out) {
out << "---------- MaxCut instance statistics -----------------" << std::endl;
auto j = getInstanceInformation();
out << j.dump(4) << std::endl;
out << "-------------------------------------------------------" << std::endl;
}
} // namespace sms