Class PrunedLandmarkLabeling¶

Nested Relationships¶

Inheritance Relationships¶

Class Documentation¶

class PrunedLandmarkLabeling : public NetworKit::Algorithm¶

Subclassed by NetworKit::DynPrunedLandmarkLabeling

Public Functions

PrunedLandmarkLabeling(const Graph &G)¶

Pruned Landmark Labeling algorithm based on the paper “Fast exact shortest-path distance

queries on large networks by pruned landmark labeling” from Akiba et al., ACM SIGMOD 2013. The algorithm computes distance labels by performing pruned breadth-first searches from each vertex. Labels are used to quickly retrieve shortest-path distances between node pairs.

Note

this algorithm only works for unweighted graphs.

Parameters:

G – The input graph.

virtual void run() override¶

Computes distance labels. Run this function before calling ‘query’.

count query(node u, node v) const¶

Returns the shortest-path distance between the two nodes.

Parameters:

• u – Source node.

• v – Target node.

Returns:

The shortest-path distance from u to v.

Protected Functions

count queryImpl(node u, node v, node upperBound = none) const¶

template<bool Reverse = false>
void prunedBFS(node root, node rankOfRootNode)¶

inline auto getSourceLabelsIterators(node u, bool reverse = false) const¶

inline auto getTargetLabelsIterators(node u) const¶

Protected Attributes

const Graph *G¶

std::vector<node> nodesSortedByDegreeDesc¶

std::vector<bool> visited¶

std::vector<std::vector<Label>> labelsOut¶

std::vector<std::vector<Label>> labelsIn¶

std::vector<Label> labelsUCopy¶

std::vector<Label> labelsVCopy¶

Protected Static Attributes

static constexpr count infDist = std::numeric_limits<count>::max()¶

struct Label¶

Public Functions

inline Label()¶

inline Label(node node_, count distance_)¶

Public Members

node node_¶

count distance_¶