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

Implementation of IncompleteSSSP using a normal Dijkstra with binary heaps. More...

#include <IncompleteDijkstra.h>

Public Member Functions

 IncompleteDijkstra (const Graph *G, const std::vector< node > &sources, const std::unordered_set< node > *explored=nullptr)
 Creates a IncompleteDijkstra instance from the sources in sources (act like a super source) in the graph G. More...
 
virtual bool hasNext () override
 Returns whether there is a next-nearest node or all of the nodes reachable from the source have already been processed. More...
 
virtual std::pair< node,
edgeweight
next () override
 Returns the next-nearest node from the source and its distance to the source. More...
 

Detailed Description

Implementation of IncompleteSSSP using a normal Dijkstra with binary heaps.

Constructor & Destructor Documentation

NetworKit::IncompleteDijkstra::IncompleteDijkstra ( const Graph G,
const std::vector< node > &  sources,
const std::unordered_set< node > *  explored = nullptr 
)

Creates a IncompleteDijkstra instance from the sources in sources (act like a super source) in the graph G.

The edges in G must have nonnegative weight and G should not be null.

We also consider the nodes in explored to not exist if explored is not null.

Warning
We do not copy G or explored, but store a non-owning pointer to them. Otherwise IncompleteDijkstra would not be more efficient than normal Dijkstra. Thus, G and explored must exist at least as long as this IncompleteDijkstra instance.
Todo:
This is somewhat ugly, but we do not want introduce a std::shared_ptr<> since G and explored could well be stack allocated.

Member Function Documentation

bool NetworKit::IncompleteDijkstra::hasNext ( )
overridevirtual

Returns whether there is a next-nearest node or all of the nodes reachable from the source have already been processed.

Implements NetworKit::IncompleteSSSP.

std::pair< node, edgeweight > NetworKit::IncompleteDijkstra::next ( )
overridevirtual

Returns the next-nearest node from the source and its distance to the source.

Should only be called if hasNext() returns true.

Implements NetworKit::IncompleteSSSP.


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