All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
DynAPSP.h
Go to the documentation of this file.
1 /*
2  * DynAPSP.h
3  *
4  * Created on: 12.08.2015
5  * Author: Arie Slobbe, Elisabetta Bergamini
6  */
7 
8 #ifndef DYNAPSP_H_
9 #define DYNAPSP_H_
10 
11 #include "APSP.h"
12 #include "../dynamics/GraphEvent.h"
13 #include "../base/DynAlgorithm.h"
14 
15 namespace NetworKit {
16 
21 class DynAPSP : public APSP, public DynAlgorithm {
22 
23 public:
29  DynAPSP(Graph& G);
30 
32  void run() override;
33 
40  void update(GraphEvent e) override;
41 
48  void updateBatch(const std::vector<GraphEvent>& batch) override;
49 
50 
52  count visPairs();
53 
58  std::vector<node> getPath(node u, node v);
59 
60 private:
61 
62  const edgeweight infDist = std::numeric_limits<edgeweight>::max();
63  const edgeweight epsilon = 0.0000000001; //make sure that no legitimate edge weight is below that.
64  count visitedPairs = 0;
65 };
66 
67 } /* namespace NetworKit */
68 
69 #endif /* DynAPSP_H_ */
std::vector< node > getPath(node u, node v)
Returns a vector containing a shortest path from node u to node v, and an empty path if u and v are n...
Definition: DynAPSP.cpp:45
void updateBatch(const std::vector< GraphEvent > &batch) override
Updates the pairwise distances after a batch of edge insertions on the graph.
Definition: DynAPSP.cpp:180
void update(GraphEvent e) override
Updates the pairwise distances after an edge insertions on the graph.
Definition: DynAPSP.cpp:65
Definition: DynAlgorithm.h:10
Definition: GraphEvent.h:19
count visPairs()
Returns number of visited pairs.
Definition: DynAPSP.cpp:186
uint64_t count
Definition: Globals.h:21
index node
Definition: Globals.h:23
const Graph & G
Definition: APSP.h:63
void run() override
initialize distances and Pred by repeatedly running the Dijkstra2 algorithm
Definition: DynAPSP.cpp:30
Class for all-pair shortest path algorithm.
Definition: APSP.h:20
Dynamic APSP.
Definition: DynAPSP.h:21
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
DynAPSP(Graph &G)
Creates the object for G.
Definition: DynAPSP.cpp:25
double edgeweight
Definition: Globals.h:24