mbfWalks/MonotoneBooleanFunction.cpp at main · AlexFihman/mbfWalks · 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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include "MonotoneBooleanFunction.h"

const int rsize = 8;
const int size = 512;

MonotoneBooleanFunction::MonotoneBooleanFunction(int dim, std::mt19937& rng) :
         dimension(dim), min_cuts(rng), rng(rng), weight(0) {

    functionArray = new bool[1 << dim](); // Initialize all values to false
    for (int i=0; i< (1 << dim); i++) functionArray[i] = false;
    updateMinCuts();
}

MonotoneBooleanFunction::~MonotoneBooleanFunction() {
    delete[] functionArray;
}

bool MonotoneBooleanFunction::getFunctionValue(int index) const {
    return functionArray[index];
}

void MonotoneBooleanFunction::setFunctionValue(int index, bool value) {
    functionArray[index] = value;
    updateMinCuts();
}

void MonotoneBooleanFunction::flip(int index) {
    functionArray[index] = !functionArray[index];
    weight += functionArray[index]? 1 : -1;
    updateMinCutsFast(index);
}

void MonotoneBooleanFunction::flipRandom() {
    int index = getRandomMinCut();
    functionArray[index] = !functionArray[index];
    weight += functionArray[index]? 1 : -1;
    updateMinCutsFast(index);
}

void MonotoneBooleanFunction::step() {
    do {
        flipRandom();
    } while (rng() % minCutSize() != 0);
}

bool MonotoneBooleanFunction::checkMinCut(int index) const {
    for (int k=0; k < dimension; k++) {
      int idx2 = index ^ (1 << k);
      //std::cout << "idx2: " << idx2 << "\t" << "value: " << functionArray[index] << std::endl;
      if (idx2 < index && functionArray[idx2]) return false;
      if (idx2 > index && !functionArray[idx2]) return false;
    }
    return true;
}

void MonotoneBooleanFunction::updateMinCuts() {
    for (int i=0; i< (1 << dimension); i++) {
      if (checkMinCut(i)) {
        min_cuts.insert(i);
      } else {
        min_cuts.remove(i);
      }
    }
}

void MonotoneBooleanFunction::updateMinCutsFast(int index) {
    for (int k=0; k < dimension; k++) {
      int idx2 = index ^ (1 << k);
      if (checkMinCut(idx2)) {
        min_cuts.insert(idx2);
      } else {
        min_cuts.remove(idx2);
      }
    }
}

int MonotoneBooleanFunction::getRandomMinCut() const {
    return min_cuts.getRandomElement();
}

void MonotoneBooleanFunction::printMinCuts() const {
    min_cuts.print();
}

int MonotoneBooleanFunction::getWeight() const {
    return weight;
}

int MonotoneBooleanFunction::minCutSize() const {
    return min_cuts.getSize();
}

void MonotoneBooleanFunction::toRecord(Record& r) {
    for (int j = 0; j < rsize; j++) r.data[j] = 0;
    for (int j = 0; j < size; j++) {
        if (getFunctionValue(j)) {
            int p = (size - j - 1) / 64;
            int k = (size - j - 1) % 64;
            r.data[p] ^= (1ULL << k);
        }
    }
}