All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
AlgebraicBFS.h
Go to the documentation of this file.
1 /*
2  * AlgebraicBFS.h
3  *
4  * Created on: Jun 7, 2016
5  * Author: Michael Wegner (michael.wegner@student.kit.edu)
6  */
7 
8 #ifndef NETWORKIT_CPP_ALGEBRAIC_ALGORITHMS_ALGEBRAICBFS_H_
9 #define NETWORKIT_CPP_ALGEBRAIC_ALGORITHMS_ALGEBRAICBFS_H_
10 
11 #include "../../base/Algorithm.h"
12 #include "../../graph/Graph.h"
13 #include "../Vector.h"
14 #include "../GraphBLAS.h"
15 
16 namespace NetworKit {
17 
22 template<class Matrix>
23 class AlgebraicBFS : public Algorithm {
24 public:
30  AlgebraicBFS(const Graph& graph, node source) : At(Matrix::adjacencyMatrix(graph, MinPlusSemiring::zero()).transpose()), source(source) {}
31 
35  void run();
36 
41  double distance(node v) const {
42  if (!hasRun) throw std::runtime_error("BFS: Call run() method first");
43  assert(v <= At.numberOfRows());
44  return distances[v];
45  }
46 
47 private:
48  Matrix At;
49  node source;
50  Vector distances;
51 };
52 
53 template<class Matrix>
55  count n = At.numberOfRows();
56  distances = Vector(n, std::numeric_limits<double>::infinity());
57  distances[source] = 0;
58 
59  Vector oldDist;
60  do {
61  oldDist = distances;
62  GraphBLAS::MxV<MinPlusSemiring>(At, distances, distances);
63  } while (oldDist != distances);
64 
65  hasRun = true;
66 }
67 
68 } /* namespace NetworKit */
69 
70 
71 
72 #endif /* NETWORKIT_CPP_ALGEBRAIC_ALGORITHMS_ALGEBRAICBFS_H_ */
add: min mult: arithmetic add zero: +infty one: 0 codomain = (-infty, +infty]
Definition: Semirings.h:51
double distance(node v) const
Returns the distance from the source to node v.
Definition: AlgebraicBFS.h:41
Implementation of Breadth-First-Search using the GraphBLAS interface.
Definition: AlgebraicBFS.h:23
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
void run()
Runs a bfs using the GraphBLAS interface from the source node.
Definition: AlgebraicBFS.h:54
The Vector class represents a basic vector with double coefficients.
Definition: Vector.h:25
Definition: Algorithm.h:9
AlgebraicBFS(const Graph &graph, node source)
Constructs an instance of the AlgebraicBFS algorithm for the given Graph graph and the given source n...
Definition: AlgebraicBFS.h:30
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79