Class DynamicBSuitorMatcher¶

Inheritance Relationships¶

Class Documentation¶

class DynamicBSuitorMatcher : public NetworKit::BSuitorMatcher, public NetworKit::DynAlgorithm¶

Public Functions

inline DynamicBSuitorMatcher(const Graph &G, const std::vector<count> &b)¶

Implementation from the algorithm from “A Fully-dynamic Approximation Algorithm for Maximum

Weight b-Matchings in Graphs” from Proceedings of The Thirteenth International Conference on Complex Networks and their Applications 2024 by Fabian Brandt-Tumescheit, Frieda Gerharz and Henning Meyerhenke. The algorithm dynamically updates the b-matching based on the b-Suitor algorithm by Khan et al. The solution is the same as a complete recomputation of the b-Suitor b-matching.

Parameters:

• G – The graph,

• b – List of b-values for each node in the graph.

inline DynamicBSuitorMatcher(const Graph &G, count b = 1)¶

Parameters:

• G – The graph,

• b – Set the same b-value for all nodes. Optional and defaults to 1.

virtual void update(GraphEvent e) override¶

Updates the b-matching after an edge insertion or deletion on the graph. Notice: Supported events include edge insertion and deletion.

Parameters:

e – The update event.

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

Updates the b-matching after a batch of edge insertions or deletions on the graph. Notice: Supported events include edge insertion and deletion.

Parameters:

e – The batch of update events.