Class DynPrunedLandmarkLabeling¶

Inheritance Relationships¶

Class Documentation¶

class DynPrunedLandmarkLabeling : public NetworKit::PrunedLandmarkLabeling, public NetworKit::DynAlgorithm¶

Dynamic pruned landmark labeling.

Public Functions

inline DynPrunedLandmarkLabeling(const Graph &G)¶

Dynamic Pruned Landmark Labeling algorithm based on the paper “Fully Dynamic 2-Hop Cover

Labeling “ from D’Angelo et al., ACM JEA 2019. The algorithm computes distance labels by performing pruned breadth-first searches from each vertex. Distance labels can be updated efficiently after edge insertions.

Note

this algorithm ignores edge weights and only supports edge insertions.

Parameters:

G – The input graph.

~DynPrunedLandmarkLabeling() override = default¶

virtual void update(GraphEvent e) override¶

Updates the distance labels after an edge insertion on the graph.

Note

supports only edge insertions.

Parameters:

e – The edge insertion.

inline virtual void updateBatch(const std::vector<GraphEvent>&) override¶

Not implemented. The algorithm does not support batch updates.

Note

This function is not implemented.