Program Listing for File AlgebraicBFS.hpp¶

/*
 * AlgebraicBFS.hpp
 *
 *  Created on: Jun 7, 2016
 *      Author: Michael Wegner (michael.wegner@student.kit.edu)
 */

#ifndef NETWORKIT_ALGEBRAIC_ALGORITHMS_ALGEBRAIC_BFS_HPP_
#define NETWORKIT_ALGEBRAIC_ALGORITHMS_ALGEBRAIC_BFS_HPP_

#include <networkit/algebraic/GraphBLAS.hpp>
#include <networkit/algebraic/Vector.hpp>
#include <networkit/base/Algorithm.hpp>
#include <networkit/graph/Graph.hpp>

namespace NetworKit {

template <class Matrix>
class AlgebraicBFS : public Algorithm {
public:
    AlgebraicBFS(const Graph &graph, node source)
        : At(Matrix::adjacencyMatrix(graph, MinPlusSemiring::zero()).transpose()), source(source) {}

    void run();

    double distance(node v) const {
        assureFinished();
        assert(v <= At.numberOfRows());
        return distances[v];
    }

private:
    Matrix At;
    node source;
    Vector distances;
};

template <class Matrix>
void AlgebraicBFS<Matrix>::run() {
    count n = At.numberOfRows();
    distances = Vector(n, std::numeric_limits<double>::infinity());
    distances[source] = 0;

    Vector oldDist;
    do {
        oldDist = distances;
        GraphBLAS::MxV<MinPlusSemiring>(At, distances, distances);
    } while (oldDist != distances);

    hasRun = true;
}

} /* namespace NetworKit */

#endif // NETWORKIT_ALGEBRAIC_ALGORITHMS_ALGEBRAIC_BFS_HPP_