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

Interface for dynamic single-source shortest path algorithms. More...

#include <DynSSSP.h>

Public Member Functions

 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 void run ()=0
 Computes the shortest paths from the source to all other nodes. More...
 
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...
 
virtual void update (GraphEvent e)=0
 The generic update method for updating data structure after an update. More...
 
virtual void updateBatch (const std::vector< GraphEvent > &batch)=0
 The generic update method for updating data structure after a batch of updates. More...
 

Protected Attributes

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...
 

Friends

class DynApproxBetweenness
 

Detailed Description

Interface for dynamic single-source shortest path algorithms.

Constructor & Destructor Documentation

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.

Parameters
graphinput graph.
sourcesource vertex.
storePredecessorskeep track of the lists of predecessors?
virtual NetworKit::DynSSSP::~DynSSSP ( )
virtualdefault

Member Function Documentation

std::vector< node > NetworKit::DynSSSP::getPredecessors ( node  t) const
inline

Returns the predecessor nodes of t on all shortest paths from source to t.

Parameters
tTarget node.
Returns
The predecessors of t on all shortest paths from source to t.
bool NetworKit::DynSSSP::modified ( )
inline

Returns true or false depending on whether the node previoulsy specified with setTargetNode has been modified by the udate or not.

Parameters
batchThe batch of edge insertions.
void NetworKit::DynSSSP::setTargetNode ( const node  t = 0)
inline

Set a target node to be observed during the update.

If a node t is set as target before the update, the function modified() will return true or false depending on whether node t has been modified by the update.

Parameters
tNode to be observed.

Friends And Related Function Documentation

friend class DynApproxBetweenness
friend

Member Data Documentation

bool NetworKit::DynSSSP::mod = false
protected
bool NetworKit::DynSSSP::storePreds = true
protected
node NetworKit::DynSSSP::target
protected

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