Class SPSP¶

Inheritance Relationships¶

Class Documentation¶

class SPSP : public NetworKit::Algorithm¶

Class for some-pairs shortest path algorithm.

Public Functions

template<class InputIt>
inline explicit SPSP(const Graph &G, InputIt sourcesFirst, InputIt sourcesLast)¶

Creates the SPSP class for G.

Parameters:

• G – The graph.

• sourcesFirst, sourcesLast – Range of the source nodes.

template<class SourcesInputIt, class TargetsInputIt>
inline explicit SPSP(const Graph &G, SourcesInputIt sourcesFirst, SourcesInputIt sourcesLast, TargetsInputIt targetsFirst, TargetsInputIt targetsLast)¶

Creates the SPSP class for G.

Parameters:

• G – The graph.

• sourcesFirst, sourcesLast – Range of the source nodes.

• targetsFirst, targetLast – Range of the target nodes.

template<class InputIt>
inline void setSources(InputIt sourcesFirst, InputIt sourcesLast)¶

Sets the source nodes.

Parameters:

sourcesFirst, sourcesLast – Range of the new source nodes.

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

Sets the target nodes.

Parameters:

sourcesFirst, sourcesLast – Range of the new source nodes.

~SPSP() override = default¶

virtual void run() override¶

Computes the shortest paths from the source nodes to the target nodes using bidirectional graph explorations. If no targets nodes are provided, the algorithm computes the shortest paths from each source node to all the other nodes. The algorithm is parallel.

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

Returns a vector of weighted distances between all the source nodes to all the other nodes.

Returns:

The shortest-path distances from the source nodes to any other node in the graph.

inline edgeweight getDistance(node u, node v) const¶

Returns the distance from the source u to node v or infinity if u cannot reach v.

Parameters:

• u – A source node.

• v – A node.

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

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

Returns:

Map from source nodes to their index in the vector returned by SPSP::getDistances().

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

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

Returns:

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