All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
AlgebraicBellmanFord.h
Go to the documentation of this file.
1 /*
2  * AlgebraicBellmanFord.h
3  *
4  * Created on: Jun 6, 2016
5  * Author: Michael Wegner (michael.wegner@student.kit.edu)
6  */
7 
8 #ifndef NETWORKIT_CPP_ALGEBRAIC_ALGORITHMS_ALGEBRAICBELLMANFORD_H_
9 #define NETWORKIT_CPP_ALGEBRAIC_ALGORITHMS_ALGEBRAICBELLMANFORD_H_
10 
11 #include "../../base/Algorithm.h"
12 #include "../../graph/Graph.h"
13 #include "../GraphBLAS.h"
14 
15 #include <iostream>
16 
17 namespace NetworKit {
18 
23 template<class Matrix>
25 public:
31  AlgebraicBellmanFord(const Graph& graph, node source) : At(Matrix::adjacencyMatrix(graph, MinPlusSemiring::zero()).transpose()), source(source), negCycle(false) {}
32 
34  ~AlgebraicBellmanFord() = default;
35 
39  void run();
40 
46  inline edgeweight distance(node t) const {
47  assert(t < At.numberOfRows());
48  if (!hasRun) throw std::runtime_error("BellmanFord: Call run() method first.");
49  return distances[t];
50  }
51 
55  inline bool hasNegativeCycle() const {
56  if (!hasRun) throw std::runtime_error("BellmanFord: Call run() method first.");
57  return negCycle;
58  }
59 
60 private:
61  const Matrix At;
62  node source;
63  Vector distances;
64  bool negCycle;
65 };
66 
67 template<class Matrix>
69  count n = At.numberOfRows();
70  distances = Vector(n, std::numeric_limits<double>::infinity());
71  distances[source] = 0;
72 
73  for (index k = 1; k < n; ++k) {
74  GraphBLAS::MxV<MinPlusSemiring>(At, distances, distances);
75  }
76 
77  Vector oldDist = distances;
78  GraphBLAS::MxV<MinPlusSemiring>(At, distances, distances);
79  negCycle = (oldDist != distances);
80  hasRun = true;
81 }
82 
83 
84 } /* namespace NetworKit */
85 
86 #endif /* NETWORKIT_CPP_ALGEBRAIC_ALGORITHMS_ALGEBRAICBELLMANFORD_H_ */
Implementation of the Bellman-Ford algorithm using the GraphBLAS interface.
Definition: AlgebraicBellmanFord.h:24
add: min mult: arithmetic add zero: +infty one: 0 codomain = (-infty, +infty]
Definition: Semirings.h:51
AlgebraicBellmanFord(const Graph &graph, node source)
Construct an instance of the BellmanFord algorithm for the Graph graph and the given source node...
Definition: AlgebraicBellmanFord.h:31
bool hasNegativeCycle() const
Definition: AlgebraicBellmanFord.h:55
uint64_t index
Typedefs.
Definition: Globals.h:20
bool hasRun
A boolean variable indicating whether an algorithm has finished its computation or not...
Definition: Algorithm.h:14
uint64_t count
Definition: Globals.h:21
std::vector< std::vector< count > > Matrix
Definition: DynamicNMIDistance.h:16
index node
Definition: Globals.h:23
~AlgebraicBellmanFord()=default
Default destructor.
The Vector class represents a basic vector with double coefficients.
Definition: Vector.h:25
Definition: Algorithm.h:9
void run()
Compute the shortest path from the source to all other nodes.
Definition: AlgebraicBellmanFord.h:68
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
edgeweight distance(node t) const
Returns the distance from the source node to t.
Definition: AlgebraicBellmanFord.h:46
double edgeweight
Definition: Globals.h:24