Program Listing for File DynamicBSuitorMatcher.hpp¶

/*
 * DynamicBSuitorMatcher.hpp
 *
 *  Created on: 06.01.2025
 *      Author: Fabian Brandt-Tumescheit
 *              Frieda Gerharz
 */

#ifndef NETWORKIT_MATCHING_DYNAMIC_B_SUITOR_MATCHER_HPP_
#define NETWORKIT_MATCHING_DYNAMIC_B_SUITOR_MATCHER_HPP_

#include <set>
#include <unordered_map>
#include <networkit/auxiliary/Log.hpp>
#include <networkit/base/DynAlgorithm.hpp>
#include <networkit/matching/BSuitorMatcher.hpp>

namespace NetworKit {
class DynamicBSuitorMatcher final : public BSuitorMatcher, public DynAlgorithm {
    enum class Operation { Insert, Remove };

public:
    DynamicBSuitorMatcher(const Graph &G, const std::vector<count> &b) : BSuitorMatcher(G, b) {}

    DynamicBSuitorMatcher(const Graph &G, count b = 1) : BSuitorMatcher(G, b) {}

    void update(GraphEvent e) override;

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

private:
    // helper function
    bool isBetterMatch(node u, node v, edgeweight ew) const noexcept {
        const MatchingNode currentMatch = suitors[u].min;
        return currentMatch.id == none || currentMatch.weight < ew
               || (currentMatch.weight == ew && v < currentMatch.id);
    }

    void addEdge(const GraphEvent &event);

    void processEdgeInsertion(const GraphEvent &event);

    void removeEdge(const GraphEvent &event);

    void processEdgeRemoval(const GraphEvent &event);

    void trackUpdatePath(node start);
};

} // namespace NetworKit
#endif // NETWORKIT_MATCHING_DYNAMIC_B_SUITOR_MATCHER_HPP_