All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
DynBFS.h
Go to the documentation of this file.
1 /*
2  * DynBFS.h
3  *
4  * Created on: 17.07.2014
5  * Author: cls, ebergamini
6  */
7 
8 #ifndef DYNBFS_H_
9 #define DYNBFS_H_
10 
11 #include "DynSSSP.h"
12 
13 
14 namespace NetworKit {
15 
20 class DynBFS : public DynSSSP {
21 
22 public:
23 
31  DynBFS(const Graph& G, node s, bool storePredecessors = true);
32 
33  void run() override;
34 
36  void update(GraphEvent e) override;
37 
39  void updateBatch(const std::vector<GraphEvent>& batch) override;
40 
41  /* Returns the number of shortest paths to node t.*/
43 
44 protected:
45  enum Color {WHITE, BLACK, GRAY};
46  std::vector<Color> color;
48 
49 };
50 
52  return npaths[t];
53 }
54 
55 } /* namespace NetworKit */
56 
57 #endif /* DYNSSSP_H_ */
count maxDistance
Definition: DynBFS.h:47
Definition: DynBFS.h:45
const Graph & G
Definition: SSSP.h:127
std::vector< bigfloat > npaths
Definition: SSSP.h:132
void updateBatch(const std::vector< GraphEvent > &batch) override
Updates the distances after a batch of edge insertions.
Definition: DynBFS.cpp:41
void update(GraphEvent e) override
Updates the distances after an edge insertion.
Definition: DynBFS.cpp:35
Definition: DynBFS.h:45
void run() override
Computes the shortest paths from the source to all other nodes.
Definition: DynBFS.cpp:20
Definition: GraphEvent.h:19
Definition: DynBFS.h:45
uint64_t count
Definition: Globals.h:21
index node
Definition: Globals.h:23
Color
Definition: DynBFS.h:45
DynBFS(const Graph &G, node s, bool storePredecessors=true)
Creates the object for G and source s.
Definition: DynBFS.cpp:16
Interface for dynamic single-source shortest path algorithms.
Definition: DynSSSP.h:24
bigfloat getNumberOfPaths(node t) const
Definition: DynBFS.h:51
Dynamic breadth-first search.
Definition: DynBFS.h:20
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
Big implements the floating point numbers.
Definition: ttmathbig.h:63
std::vector< Color > color
Definition: DynBFS.h:46