Program Listing for File AlgebraicBellmanFord.hpp¶

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

#ifndef NETWORKIT_ALGEBRAIC_ALGORITHMS_ALGEBRAIC_BELLMAN_FORD_HPP_
#define NETWORKIT_ALGEBRAIC_ALGORITHMS_ALGEBRAIC_BELLMAN_FORD_HPP_

#include <cassert>

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

namespace NetworKit {

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

    ~AlgebraicBellmanFord() = default;

    void run();

    inline edgeweight distance(node t) const {
        assert(t < At.numberOfRows());
        assureFinished();
        return distances[t];
    }

    inline bool hasNegativeCycle() const {
        assureFinished();
        return negCycle;
    }

private:
    const Matrix At;
    node source;
    Vector distances;
    bool negCycle;
};

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

    for (index k = 1; k < n; ++k) {
        GraphBLAS::MxV<MinPlusSemiring>(At, distances, distances);
    }

    Vector oldDist = distances;
    GraphBLAS::MxV<MinPlusSemiring>(At, distances, distances);
    negCycle = (oldDist != distances);
    hasRun = true;
}

} /* namespace NetworKit */

#endif // NETWORKIT_ALGEBRAIC_ALGORITHMS_ALGEBRAIC_BELLMAN_FORD_HPP_