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

The BFS class is used to do a breadth-first search on a Graph from a given source node. More...

#include <BFS.h>

Public Member Functions

 BFS (const Graph &G, node source, bool storePaths=true, bool storeNodesSortedByDistance=false, node target=none)
 Constructs the BFS class for G and source node source. More...
 
virtual void run ()
 Breadth-first search from source. 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
 

Friends

class DynBFS
 

Additional Inherited Members

- 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

The BFS class is used to do a breadth-first search on a Graph from a given source node.

Constructor & Destructor Documentation

NetworKit::BFS::BFS ( const Graph G,
node  source,
bool  storePaths = true,
bool  storeNodesSortedByDistance = false,
node  target = none 
)

Constructs the BFS class for G and source node source.

Parameters
GThe graph
sourceThe source node of the breadth-first search
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.

Member Function Documentation

void NetworKit::BFS::run ( )
virtual

Breadth-first search from source.

Returns
Vector of unweighted distances from node source, i.e. the length (number of edges) of the shortest path from source to any other node.

Implements NetworKit::SSSP.

Friends And Related Function Documentation

friend class DynBFS
friend

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