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
|
#include "prpack_preprocessed_schur_graph.h"
#include <algorithm>
#include <cstring>
using namespace prpack;
using namespace std;
void prpack_preprocessed_schur_graph::initialize() {
heads = NULL;
tails = NULL;
vals = NULL;
ii = NULL;
d = NULL;
num_outlinks = NULL;
encoding = NULL;
decoding = NULL;
}
void prpack_preprocessed_schur_graph::initialize_weighted(const prpack_base_graph* bg) {
// permute d
ii = d;
d = new double[num_vs];
for (int i = 0; i < num_vs; ++i)
d[encoding[i]] = ii[i];
// convert bg to head/tail format
for (int tails_i = 0, heads_i = 0; tails_i < num_vs; ++tails_i) {
ii[tails_i] = 0;
tails[tails_i] = heads_i;
const int decoded = decoding[tails_i];
const int start_i = bg->tails[decoded];
const int end_i = (decoded + 1 != num_vs) ? bg->tails[decoded + 1] : bg->num_es;
for (int i = start_i; i < end_i; ++i) {
if (decoded == bg->heads[i])
ii[tails_i] += bg->vals[i];
else {
heads[heads_i] = encoding[bg->heads[i]];
vals[heads_i] = bg->vals[i];
++heads_i;
}
}
}
}
void prpack_preprocessed_schur_graph::initialize_unweighted(const prpack_base_graph* bg) {
// permute num_outlinks
ii = num_outlinks;
num_outlinks = new double[num_vs];
for (int i = 0; i < num_vs; ++i)
num_outlinks[encoding[i]] = (ii[i] == 0) ? -1 : ii[i];
// convert bg to head/tail format
for (int tails_i = 0, heads_i = 0; tails_i < num_vs; ++tails_i) {
ii[tails_i] = 0;
tails[tails_i] = heads_i;
const int decoded = decoding[tails_i];
const int start_i = bg->tails[decoded];
const int end_i = (decoded + 1 != num_vs) ? bg->tails[decoded + 1] : bg->num_es;
for (int i = start_i; i < end_i; ++i) {
if (decoded == bg->heads[i])
++ii[tails_i];
else
heads[heads_i++] = encoding[bg->heads[i]];
}
if (ii[tails_i] > 0)
ii[tails_i] /= num_outlinks[tails_i];
}
}
prpack_preprocessed_schur_graph::prpack_preprocessed_schur_graph(const prpack_base_graph* bg) {
initialize();
// initialize instance variables
num_vs = bg->num_vs;
num_es = bg->num_es - bg->num_self_es;
tails = new int[num_vs];
heads = new int[num_es];
const bool weighted = bg->vals != NULL;
if (weighted) {
vals = new double[num_vs];
d = new double[num_vs];
fill(d, d + num_vs, 1);
for (int i = 0; i < bg->num_es; ++i)
d[bg->heads[i]] -= bg->vals[i];
} else {
num_outlinks = new double[num_vs];
fill(num_outlinks, num_outlinks + num_vs, 0);
for (int i = 0; i < bg->num_es; ++i)
++num_outlinks[bg->heads[i]];
}
// permute no-inlink vertices to the beginning, and no-outlink vertices to the end
encoding = new int[num_vs];
decoding = new int[num_vs];
num_no_in_vs = num_no_out_vs = 0;
for (int i = 0; i < num_vs; ++i) {
if (bg->tails[i] == ((i + 1 != num_vs) ? bg->tails[i + 1] : bg->num_es)) {
decoding[encoding[i] = num_no_in_vs] = i;
++num_no_in_vs;
} else if ((weighted) ? (d[i] == 1) : (num_outlinks[i] == 0)) {
decoding[encoding[i] = num_vs - 1 - num_no_out_vs] = i;
++num_no_out_vs;
}
}
// permute everything else
for (int i = 0, p = num_no_in_vs; i < num_vs; ++i)
if (bg->tails[i] < ((i + 1 != num_vs) ? bg->tails[i + 1] : bg->num_es) && ((weighted) ? (d[i] < 1) : (num_outlinks[i] > 0)))
decoding[encoding[i] = p++] = i;
// continue initialization based off of weightedness
if (weighted)
initialize_weighted(bg);
else
initialize_unweighted(bg);
}
prpack_preprocessed_schur_graph::~prpack_preprocessed_schur_graph() {
delete[] heads;
delete[] tails;
delete[] vals;
delete[] ii;
delete[] d;
delete[] num_outlinks;
delete[] encoding;
delete[] decoding;
}
|