Program Listing for File AlgebraicTriangleCounting.hpp¶

/*
 * AlgebraicTriangleCounting.hpp
 *
 *  Created on: Jul 12, 2016
 *      Author: Michael Wegner (michael.wegner@student.kit.edu)
 */

#ifndef NETWORKIT_ALGEBRAIC_ALGORITHMS_ALGEBRAIC_TRIANGLE_COUNTING_HPP_
#define NETWORKIT_ALGEBRAIC_ALGORITHMS_ALGEBRAIC_TRIANGLE_COUNTING_HPP_

#include <networkit/base/Algorithm.hpp>

namespace NetworKit {

template <class Matrix>
class AlgebraicTriangleCounting : public Algorithm {
public:
    AlgebraicTriangleCounting(const Graph &graph)
        : A(Matrix::adjacencyMatrix(graph)), directed(graph.isDirected()) {}

    void run() override;

    count score(node u) const {
        assureFinished();
        assert(u < A.numberOfRows());
        return nodeScores[u];
    }

    const std::vector<count> &getScores() const {
        assureFinished();
        return nodeScores;
    }

private:
    Matrix A;
    bool directed;
    std::vector<count> nodeScores;
};

template <class Matrix>
void AlgebraicTriangleCounting<Matrix>::run() {
    Matrix powA = A * A * A;

    nodeScores.clear();
    nodeScores.resize(A.numberOfRows(), 0);

#pragma omp parallel for
    for (omp_index i = 0; i < static_cast<omp_index>(powA.numberOfRows()); ++i) {
        nodeScores[i] = directed ? powA(i, i) : powA(i, i) / 2.0;
    }

    hasRun = true;
}

} /* namespace NetworKit */

#endif // NETWORKIT_ALGEBRAIC_ALGORITHMS_ALGEBRAIC_TRIANGLE_COUNTING_HPP_