coauthorGraph/Analyser.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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include "Analyser.h"

Analyser::Analyser(const std::string &edges_filename) {
    std::cout << "creating the adjacency list...\n";
    json input;
    std::ifstream file(edges_filename, std::ifstream::binary);
    file >> input;
    std::vector<std::pair<std::string, std::string>> edges = input.get<std::vector<std::pair<std::string, std::string>>>();
    std::unordered_map<std::string, int> idsToIndices;
    for (const auto &edge: edges) {
        int index1, index2;
        if (idsToIndices.find(edge.first) == idsToIndices.end()) {
            index1 = adjList.size();
            idsToIndices[edge.first] = index1;
            if (edge.first == ErdosId)
                ErdosIndex = index1;
            adjList.push_back(std::vector<int>(0));
        } else
            index1 = idsToIndices[edge.first];
        if (idsToIndices.find(edge.second) == idsToIndices.end()) {
            index2 = adjList.size();
            idsToIndices[edge.second] = index2;
            if (edge.second == ErdosId)
                ErdosIndex = index2;
            adjList.push_back(std::vector<int>(0));
        } else
            index2 = idsToIndices[edge.second];
        if (find(adjList[index1].begin(), adjList[index1].end(), index2) ==
            adjList[index1].end()) //to avoid duplicate edges
            adjList[index1].push_back(index2);
        if (find(adjList[index2].begin(), adjList[index2].end(), index1) == adjList[index2].end())
            adjList[index2].push_back(index1);
    }
    size = adjList.size();

    maxdeg = 0;
    volume = 0;
    for (const auto &l: adjList) {
        if (l.size() > maxdeg)
            maxdeg = l.size();
        volume += l.size();
    }
}

int Analyser::findMaxErdosNumber() {
    std::cout << "finding tha largest Erdos number...\n";
    int visited = 0;
    std::queue<int> q;
    q.push(ErdosIndex);
    std::vector<int> dist(size, INT32_MAX);
    dist[ErdosIndex] = 0;
    while (!q.empty()) {
        visited++;
        int cur = q.front();
        q.pop();
        for (auto v: adjList[cur]) {
            if (dist[v] != INT32_MAX)
                continue;
            dist[v] = dist[cur] + 1;
            q.push(v);
        }
    }
    return *std::max_element(dist.begin(), dist.end());
}

float Analyser::computeConductanceManually(std::vector<bool> partitition) {
    int cutEdges = 0;
    int partVolume = 0;
    for (int i = 0; i < size; i++) {
        if (partitition[i])
            partVolume += adjList[i].size();
        for (int v: adjList[i]) {
            if (partitition[v] != partitition[i])
                cutEdges++;
        }
    }
    return float(cutEdges) / 2 / std::min(partVolume, volume - partVolume);
}

void Analyser::saveAdjList(const std::string &filename) {
    std::ofstream output;
    output.open(filename);
    for (int i = 0; i < size; i++) {
        for (int to: adjList[i])
            output << to << " ";
        output << '\n';
    }
    output.close();
}

void Analyser::saveErdosIndex(const std::string &filename) const {
    std::ofstream output;
    output.open(filename);
    output << ErdosIndex;
    output.close();
}

Analyser::Analyser(const std::string &adjList_filename, const std::string &ErdosIndex_filename) {
    std::ifstream input1;
    input1.open(ErdosIndex_filename);
    input1 >> ErdosIndex;
    maxdeg = 0;
    volume = 0;

    std::ifstream input2;
    input2.open(adjList_filename);
    std::string line;
    while (getline(input2, line)) {
        adjList.push_back(std::vector<int>(0));
        std::stringstream iss(line);
        int to;
        while (iss >> to)
            adjList.back().push_back(to);
        if (adjList.back().size() > maxdeg)
            maxdeg = adjList.back().size();
        volume += adjList.back().size();
    }
    size = adjList.size();
}

void Analyser::saveGuess(const std::string &filename, std::vector<bool> _guess) {
    std::ofstream output;
    output.open(filename);
    for (int i = 0; i < size; i++)
        output << _guess[i] << "\n";
    output.close();
}