coauthorGraph/Annealing.cpp at master · Paul566/coauthorGraph · GitHub

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
86
87
88
//
// Created by paul on 1/8/22.
//

#include "Annealing.h"

Annealing::Annealing(const std::string &adjList_filename, const std::string &ErdosIndex_filename, float _initTemp,
                     long _numSteps, long _updateTempEveryThisManyTimesteps) : Analyser(adjList_filename,
                                                                                        ErdosIndex_filename) {
    std::random_device rd;
    gen = std::mt19937(rd());
    stepChoiceDistribution = std::uniform_real_distribution<>(0., 1.);
    nodeIndexDistribution = std::uniform_int_distribution<>(0, size - 1);
    curTemp = _initTemp;
    initTemp = _initTemp;
    curStep = 0;
    numSteps = _numSteps;
    updateTempEveryThisManyTimesteps = _updateTempEveryThisManyTimesteps;
    guess = std::vector<bool>(size, false);
    curCutEdges = 0;
    trueVolume = 0;
    for (int i = 0; i < size / 2; i++) {
        int vertex = nodeIndexDistribution(gen);
        if (guess[vertex])
            continue;
        guess[vertex] = true;
        trueVolume += adjList[vertex].size();
    }
    bestGuess = guess;
    curConductance = computeConductanceManually(guess);
    curCutEdges = int(curConductance * std::min(trueVolume, volume - trueVolume));
    bestConductance = curConductance;
}

void Annealing::anneal() {
    std::cout << "starting annealing...\n";
    while (curStep < numSteps) {
        if (curStep % (10000 * updateTempEveryThisManyTimesteps) == 0) {
            int minSize = 0;
            for (auto b: guess)
                minSize += b;
            printf("step\t%ld\ttemperature\t%.9f\tbest conductance\t%.6f\tcurrent conductance\t%.6f\tcurrent sizes of the parts:\t%d\t%d\n",
                   curStep, curTemp, bestConductance, curConductance, minSize, size - minSize);
        }
        for (int i = 0; i < updateTempEveryThisManyTimesteps; i++)
            makeStep();
        updateTemp();
    }
}

void Annealing::updateTemp() {
    curTemp = initTemp - initTemp * curStep / numSteps;
}

void Annealing::makeStep() {
    int vertex = nodeIndexDistribution(gen);
    int deltaEdges = 0;
    for (int to: adjList[vertex]) {
        if (guess[vertex] != guess[to])
            deltaEdges--;
        else
            deltaEdges++;
    }
    int newTrueVolume;
    if (guess[vertex])
        newTrueVolume = trueVolume - adjList[vertex].size();
    else
        newTrueVolume = trueVolume + adjList[vertex].size();
    if ((newTrueVolume == 0) || (newTrueVolume == volume))
        return;
    float newResult = float(curCutEdges + deltaEdges) / std::min(newTrueVolume, volume - newTrueVolume);
    if (doWeAccept(newResult)) {
        guess[vertex] = not guess[vertex];
        trueVolume = newTrueVolume;
        curConductance = newResult;
        curCutEdges += deltaEdges;
        if (curConductance < bestConductance) {
            bestConductance = curConductance;
            if (curTemp < initTemp / 2) //in order not to spend too much time in the beginning
                bestGuess = guess;
        }
    }
    curStep++;
}

bool Annealing::doWeAccept(float newResult) {
    return expf((curConductance - newResult) / curTemp) > stepChoiceDistribution(gen);
}