jlongs calculateRetainedSizesViaDominatorTree()

in src/sizes/dominator_tree.cpp [48:124]

• 68 lines of code
• 15 McCabe index (conditional complexity)

jlongs calculateRetainedSizesViaDominatorTree(const graph_t &graph, const jlongs &sizes) {
    auto n = static_cast<jlong>(graph.size());
    jlongs semi(n);
    jlongs parent(n);
    jlongs vertex(n);
    jlongs ancestor(n);
    jlongs label(n);
    jlongs dom(n);
    jlongs retainedSizes(n);
    graph_t pred(n);
    graph_t bucket(n);

    for (jlong i = 0; i < n; i++) {
        retainedSizes[i] = sizes[i];
        label[i] = i;
        ancestor[i] = -1;
    }

    n = 0;
    dfs(0, n, graph, semi, parent, vertex, pred);

    for (jlong i = n - 1; i > 0; i--) {
        jlong w = vertex[i];
        for (jlong v : pred[w]) {
            jlong u = eval(v, ancestor, label, semi);
            if (semi[u] < semi[w]) {
                semi[w] = semi[u];
            }
        }
        bucket[vertex[semi[w]]].push_back(w);
        link(parent[w], w, ancestor);

        for (jlong v : bucket[parent[w]]) {
            jlong u = eval(v, ancestor, label, semi);
            if (semi[u] < semi[v]) {
                dom[v] = u;
            } else {
                dom[v] = parent[w];
            }
        }
        bucket[parent[w]].clear();
    }

    dom[0] = -1;
    jlongs childCount(n);
    for (jlong i = 1; i < n; i++) {
        jlong w = vertex[i];
        if (dom[w] != vertex[semi[w]]) {
            dom[w] = dom[dom[w]];
        }

        if (dom[w] >= 0) {
            childCount[dom[w]]++;
        }
    }

    std::queue<jlong> leaves;
    for (jlong i = 1; i < n; i++) {
        if (childCount[i] == 0) {
            leaves.push(i);
        }
    }

    while (!leaves.empty()) {
        jlong leaf = leaves.front();
        leaves.pop();
        jlong d = dom[leaf];
        if (d >= 0) {
            retainedSizes[d] += retainedSizes[leaf];
            if (--childCount[d] == 0) {
                leaves.push(d);
            }
        }
    }

    return retainedSizes;
}