MPMB_code/Model.cpp at main · Spockkk0225/MPMB_code · 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
104
105
106
107
108
109
#include "Model.h"

bool cmp(const pair<Butterfly, double> &e1, const pair<Butterfly, double> &e2) { return e1.second > e2.second; }

void Model::PrintResult(double coe) {
    vector<pair<Butterfly, double>> b;
    for (auto &b_p: result) {
        b.push_back(b_p);
    }
    cout << "S{MB} size = " << result.size() << endl;
    sort(b.begin(), b.end(), cmp);
    int i = 0;
    for (auto &b_p: b) {
        i++;
        if (i > 50) break;
        cout << "Butterfly("
             << b_p.first.u1
             << "," << b_p.first.u2
             << "," << b_p.first.v1
             << "," << b_p.first.v2
             << ")   weight=" << b_p.first.weight
             << "  times=" << b_p.second
             << "  percent=" << b_p.second / coe
             << "  butterfly pr=" << b_p.first.pr
             << "  butterfly combined weight=" << b_p.first.combined_weight << endl;
    }
}


// e1 = (u, v1)
// e2 = (u, v2)
// a  = (v1, u, v2)
Angle Model::EdgeToAngle(Edge e1, Edge e2) {
    Angle a{};
    a.weight = e1.weight + e2.weight;
    a.pr = e1.pr * e2.pr;
    a.combined_weight = (int) (e1.weight * e1.pr + e2.weight * e2.pr);

    if (e1.u == e2.u) {
        //
    } else if (e1.u == e2.v) {
        swap(e2.u, e2.v);

    } else if (e1.v == e2.u) {
        swap(e1.u, e1.v);

    } else if (e1.v == e2.v) {
        swap(e1.u, e1.v);
        swap(e2.u, e2.v);

    } else {
        assert(0);
    }
    if (e1.v > e2.v) swap(e1, e2);
    a.u = e1.v;
    a.v = e1.u;
    a.w = e2.v;
    a.pr_u_v = e1.pr;
    a.pr_v_w = e2.pr;

    return a;
}

// a1 = (u1, v1, u2)
// a2 = (u1, v2, u2)
// b  = (u1, u2, v1, v2)
// u1 < u2
Butterfly Model::AngleToButterfly(const Angle &a1, const Angle &a2) {
//    if (a1.u != a2.u) {
//        cout << a1.u << " " << a1.v << " " << a1.w << endl;
//        cout << a2.u << " " << a2.v << " " << a2.w << endl;
//    }
    assert(a1.u == a2.u);
    assert(a1.w == a2.w);
    Butterfly b{};
    b.weight = a1.weight + a2.weight;
    b.pr = a1.pr * a2.pr;
    b.combined_weight = a1.combined_weight + a2.combined_weight;

    if (a1.v < a2.v) {
        b.u1 = a1.u;
        b.u2 = a1.w;
        b.v1 = a1.v;
        b.v2 = a2.v;
        b.pr_u1_v1 = a1.pr_u_v;
        b.pr_u2_v1 = a1.pr_v_w;
        b.pr_u1_v2 = a2.pr_u_v;
        b.pr_u2_v2 = a2.pr_v_w;
    } else {
        b.u1 = a1.u;
        b.u2 = a1.w;
        b.v1 = a2.v;
        b.v2 = a1.v;
        b.pr_u1_v1 = a2.pr_u_v;
        b.pr_u2_v1 = a2.pr_v_w;
        b.pr_u1_v2 = a1.pr_u_v;
        b.pr_u2_v2 = a1.pr_v_w;
    }

    if (is_left[b.u1] == 0) {
        swap(b.u1, b.v1);
        swap(b.u2, b.v2);
        swap(b.pr_u1_v2, b.pr_u2_v1);
    }

    return b;
}

unordered_map<int, int> Model::is_left{};