Class STSP¶

Defined in File STSP.hpp

Inheritance Relationships¶

Base Type¶

public NetworKit::Algorithm (Class Algorithm)

Derived Types¶

public NetworKit::AStar (Class AStar)
public NetworKit::AStarGeneral< Heuristic > (Template Class AStarGeneral)
public NetworKit::BidirectionalBFS (Class BidirectionalBFS)
public NetworKit::BidirectionalDijkstra (Class BidirectionalDijkstra)
public NetworKit::MultiTargetBFS (Class MultiTargetBFS)
public NetworKit::MultiTargetDijkstra (Class MultiTargetDijkstra)

Class Documentation¶

class STSP : public NetworKit::Algorithm ¶

Abstract base class for source-target shortest path algorithms.

Subclassed by NetworKit::AStar, NetworKit::AStarGeneral< Heuristic >, NetworKit::BidirectionalBFS, NetworKit::BidirectionalDijkstra, NetworKit::MultiTargetBFS, NetworKit::MultiTargetDijkstra

Public Functions

inline STSP(const Graph &G, node source, node target, bool storePred = true)¶

Creates the STSP class for a graph G, source node source, and target node target.

Parameters:

G – The graph.
source – The source node.
target – The target node.
storePred – If true, the algorithm will also store the predecessors and reconstruct a shortest path from source and target.

template<class InputIt> inline STSP(const Graph &G, node source, InputIt targetsFirst, InputIt targetsLast)¶

Creates the STSP class for a graph G, source node source, and multiple target nodes.

Parameters:

G – The graph.
source – The source node.
targetsFirst, targetsLast – Range of target nodes.

inline virtual std::vector<node> getPath() const¶

Returns a shortest path from the source node to the target node (without including them). Note: the shortest path can be constructed only if the algorithm is executed with storePred set to true.

Returns:: A shortest path from the source to target.

inline const std::vector<node> &getPredecessors() const¶

Returns the predecessor nodes from the target to the source. Note: predecessors are stored only if the algorithm is executed with storePred set to true.

Returns:: The list of predecessors from target to source.

inline edgeweight getDistance() const¶

If the target is a single node: returns the distance from the source node to the target node.

Returns:: The distance from source to the target node.

inline const std::vector<edgeweight> &getDistances() const¶

In case of multiple target nodes: returns the distance from the source node to the target nodes.

Returns:: Distances from the source to the target nodes.

inline void setSource(node newSource)¶

Sets the source node.

Parameters:: newSource – The new source node.

inline void setTarget(node newTarget)¶

Sets the target node.

Parameters:: newTarget – The new target node.

template<class InputIt> inline void setTargets(InputIt targetsFirst, InputIt targetsLast)¶

Sets the target nodes.

Parameters:: targetsFirst, targetsLast – Range of target nodes.

inline const std::unordered_map<node, index> &getTargetIndexMap() const¶

Returns the <node, index> map from target nodes to their index in the vector returned by STSP::getDistances().

Returns:: Map from target nodes to their index in the vector returned by STSP::getDistances().

Protected Functions

inline void buildPath()¶

inline void checkStorePredecessors() const¶

inline void init()¶

Protected Attributes

const Graph *G¶

node source = none ¶

node target = none ¶

std::vector<node> targets¶

const bool storePred¶

std::vector<node> pred¶

std::vector<node> path¶

edgeweight distance¶

std::vector<edgeweight> distances¶

std::unordered_map<node, index> targetIdx¶