All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | Protected Types | Protected Attributes | List of all members
NetworKit::DynDijkstra Class Reference

Dynamic Dijkstra. More...

#include <DynDijkstra.h>

Public Member Functions

 DynDijkstra (const Graph &G, node s, bool storePredecessors=true)
 Creates the object for G and source s. More...
 
void run () override
 Computes the shortest paths from the source to all other nodes. More...
 
void update (GraphEvent e) override
 Updates the distances after an edge insertion. More...
 
void updateBatch (const std::vector< GraphEvent > &batch) override
 Updates the distances after a batch of edge insertions. More...
 
- Public Member Functions inherited from NetworKit::DynSSSP
 DynSSSP (const Graph &G, node source, bool storePredecessors=true, node target=none)
 The algorithm computes a dynamic SSSP starting from the specified source vertex. More...
 
virtual ~DynSSSP ()=default
 
bool modified ()
 Returns true or false depending on whether the node previoulsy specified with setTargetNode has been modified by the udate or not. More...
 
void setTargetNode (const node t=0)
 Set a target node to be observed during the update. More...
 
std::vector< nodegetPredecessors (node t) const
 Returns the predecessor nodes of t on all shortest paths from source to t. More...
 
- Public Member Functions inherited from NetworKit::SSSP
 SSSP (const Graph &G, node source, bool storePaths=true, bool storeNodesSortedByDistance=false, node target=none)
 Creates the SSSP class for G and source s. More...
 
virtual ~SSSP ()=default
 
virtual std::vector< edgeweightgetDistances (bool moveOut=true)
 Returns a vector of weighted distances from the source node, i.e. More...
 
edgeweight distance (node t) const
 Returns the distance from the source node to t. More...
 
bigfloat numberOfPaths (node t) const
 Returns the number of shortest paths between the source node and t. More...
 
double _numberOfPaths (node t) const
 Returns the number of shortest paths between the source node and t as a double value. More...
 
std::vector< nodegetPredecessors (node t) const
 Returns the predecessor nodes of t on all shortest paths from source to t. More...
 
virtual std::vector< nodegetPath (node t, bool forward=true) const
 Returns a shortest path from source to t and an empty path if source and t are not connected. More...
 
virtual std::set< std::vector
< node > > 
getPaths (node t, bool forward=true) const
 Returns all shortest paths from source to t and an empty set if source and t are not connected. More...
 
bigfloat getNumberOfPaths (node t) const
 
virtual std::vector< nodegetStack (bool moveOut=true)
 Returns a vector of nodes ordered in increasing distance from the source. More...
 
virtual std::vector< nodegetNodesSortedByDistance (bool moveOut=true)
 Returns a vector of nodes ordered in increasing distance from the source. More...
 
- Public Member Functions inherited from NetworKit::Algorithm
 Algorithm ()
 Constructor to the algorithm base class. More...
 
virtual ~Algorithm ()=default
 Virtual default destructor. More...
 
bool hasFinished () const
 Indicates whether an algorithm has completed computation or not. More...
 
void assureFinished () const
 Assure that the algorithm has been run, throws a std::runtime_error otherwise. More...
 
virtual std::string toString () const
 Returns a string with the algorithm's name and its parameters, if there are any. More...
 
virtual bool isParallel () const
 
- Public Member Functions inherited from NetworKit::DynAlgorithm
virtual ~DynAlgorithm ()=default
 Virtual default destructor. More...
 

Protected Types

enum  Color { WHITE, BLACK }
 

Protected Attributes

std::vector< Colorcolor
 
- Protected Attributes inherited from NetworKit::DynSSSP
bool storePreds = true
 
bool mod = false
 
node target
 
- Protected Attributes inherited from NetworKit::SSSP
const GraphG
 
const node source
 
node target
 
std::vector< edgeweightdistances
 
std::vector< std::vector< node > > previous
 
std::vector< bigfloatnpaths
 
std::vector< nodenodesSortedByDistance
 
bool storePaths
 if true, paths are reconstructable and the number of paths is stored More...
 
bool storeNodesSortedByDistance
 if true, store a vector of nodes ordered in increasing distance from the source More...
 
- Protected Attributes inherited from NetworKit::Algorithm
bool hasRun
 A boolean variable indicating whether an algorithm has finished its computation or not. More...
 

Detailed Description

Dynamic Dijkstra.

Member Enumeration Documentation

Enumerator
WHITE 
BLACK 

Constructor & Destructor Documentation

NetworKit::DynDijkstra::DynDijkstra ( const Graph G,
node  s,
bool  storePredecessors = true 
)

Creates the object for G and source s.

Parameters
GThe graph.
sThe source node.
storePredecessorskeep track of the lists of predecessors?

Member Function Documentation

void NetworKit::DynDijkstra::run ( )
overridevirtual

Computes the shortest paths from the source to all other nodes.

Implements NetworKit::SSSP.

void NetworKit::DynDijkstra::update ( GraphEvent  e)
overridevirtual

Updates the distances after an edge insertion.

Implements NetworKit::DynAlgorithm.

void NetworKit::DynDijkstra::updateBatch ( const std::vector< GraphEvent > &  batch)
overridevirtual

Updates the distances after a batch of edge insertions.

Implements NetworKit::DynAlgorithm.

Member Data Documentation

std::vector<Color> NetworKit::DynDijkstra::color
protected

The documentation for this class was generated from the following files: