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

Abstract base class for single-source shortest path algorithms. More...

#include <SSSP.h>

Public Member Functions

 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
 

Protected Attributes

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

Abstract base class for single-source shortest path algorithms.

Constructor & Destructor Documentation

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.

Parameters
GThe graph.
sourceThe source node.
storePathsPaths are reconstructable and the number of paths is stored.
storeNodesSortedByDistanceStore a vector of nodes ordered in increasing distance from the source.
targetThe target node.
virtual NetworKit::SSSP::~SSSP ( )
virtualdefault

Member Function Documentation

double NetworKit::SSSP::_numberOfPaths ( node  t) const
inline

Returns the number of shortest paths between the source node and t as a double value.

Workaround for Cython

Parameters
tTarget node.
Returns
The number of shortest paths between source and t.
edgeweight NetworKit::SSSP::distance ( node  t) const
inline

Returns the distance from the source node to t.

Parameters
tTarget node.
Returns
The distance from source to target node t.
std::vector< edgeweight > NetworKit::SSSP::getDistances ( bool  moveOut = true)
virtual

Returns a vector of weighted distances from the source node, i.e.

the length of the shortest path from the source node to any other node.

Parameters
moveOutIf set to true, the container will be moved out of the class instead of copying it; default=true.
Returns
The weighted distances from the source node to any other node in the graph.
std::vector< node > NetworKit::SSSP::getNodesSortedByDistance ( bool  moveOut = true)
virtual

Returns a vector of nodes ordered in increasing distance from the source.

For this functionality to be available, storeNodesSortedByDistance has to be set to true in the constructor. There are no guarantees regarding the ordering of two nodes with the same distance to the source.

Parameters
moveOutIf set to true, the container will be moved out of the class instead of copying it; default=true.
Returns
vector of nodes ordered in increasing distance from the source
bigfloat NetworKit::SSSP::getNumberOfPaths ( node  t) const
inline
std::vector< node > NetworKit::SSSP::getPath ( node  t,
bool  forward = true 
) const
virtual

Returns a shortest path from source to t and an empty path if source and t are not connected.

Parameters
tTarget node.
forwardIf true (default) the path is directed from source to t, otherwise the path is reversed.
Returns
A shortest path from source to t or an empty path.
std::set< std::vector< node > > NetworKit::SSSP::getPaths ( node  t,
bool  forward = true 
) const
virtual

Returns all shortest paths from source to t and an empty set if source and t are not connected.

Parameters
tTarget node.
forwardIf true (default) the path is directed from source to t, otherwise the path is reversed.
Returns
All shortest paths from source node to target node t.
std::vector< node > NetworKit::SSSP::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.
std::vector< node > NetworKit::SSSP::getStack ( bool  moveOut = true)
virtual

Returns a vector of nodes ordered in increasing distance from the source.

For this functionality to be available, storeNodesSortedByDistance has to be set to true in the constructor. There are no guarantees regarding the relative ordering of two nodes with the same distance to the source.

Parameters
moveOutIf set to true, the container will be moved out of the class instead of copying it; default=true.
Returns
vector of nodes ordered in increasing distance from the source
bigfloat NetworKit::SSSP::numberOfPaths ( node  t) const
inline

Returns the number of shortest paths between the source node and t.

Parameters
tTarget node.
Returns
The number of shortest paths between source and t.
virtual void NetworKit::SSSP::run ( )
pure virtual

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

Implements NetworKit::Algorithm.

Implemented in NetworKit::Dijkstra, NetworKit::BFS, NetworKit::DynBFS, and NetworKit::DynDijkstra.

Member Data Documentation

std::vector<edgeweight> NetworKit::SSSP::distances
protected
const Graph& NetworKit::SSSP::G
protected
std::vector<node> NetworKit::SSSP::nodesSortedByDistance
protected
std::vector<bigfloat> NetworKit::SSSP::npaths
protected
std::vector<std::vector<node> > NetworKit::SSSP::previous
protected
const node NetworKit::SSSP::source
protected
bool NetworKit::SSSP::storeNodesSortedByDistance
protected

if true, store a vector of nodes ordered in increasing distance from the source

bool NetworKit::SSSP::storePaths
protected

if true, paths are reconstructable and the number of paths is stored

node NetworKit::SSSP::target
protected

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