Program Listing for File BSuitorMatcher.hpp¶

/*
 * BSuitorMatcher.hpp
 *
 *  Created on: 07.08.2023
 *      Author: Fabian Brandt-Tumescheit
 *              Frieda Gerharz
 */

#ifndef NETWORKIT_MATCHING_B_SUITOR_MATCHER_HPP_
#define NETWORKIT_MATCHING_B_SUITOR_MATCHER_HPP_

#include <algorithm>
#include <string_view>

#include <networkit/graph/Graph.hpp>
#include <networkit/matching/BMatcher.hpp>

namespace NetworKit {

class BSuitorMatcher : public BMatcher {
protected:
    struct MatchingNode {
        node id;
        edgeweight weight;

        MatchingNode() : id(none), weight(0) {}
        MatchingNode(node n, edgeweight w) : id(n), weight(w) {}

        // If the edgeweight is the same for two MatchingNodes
        // then we compare the node id, where a smaller id is
        // ranked higher.
        std::partial_ordering operator<=>(const MatchingNode &other) const {
            if (auto cmp = weight <=> other.weight; cmp != 0)
                return cmp;

            return -static_cast<int64_t>(id) <=> -static_cast<int64_t>(other.id);
        }

        bool operator==(const MatchingNode &other) const = default;
    };

    struct MatchingNodeInfo {
        std::vector<MatchingNode> partners;
        MatchingNode min; // (none, 0) if partners still has free capacity
        count max_size;

        MatchingNodeInfo() = default;

        MatchingNodeInfo(count b) {
            partners.reserve(b);
            max_size = b;
        }

        bool hasPartner(node u) const {
            return std::find_if(partners.begin(), partners.end(),
                                [u](const MatchingNode &v) { return v.id == u; })
                   != partners.end();
        }

        MatchingNode popMinIfFull() {
            if (partners.size() < max_size) {
                return {none, 0};
            } else {
                MatchingNode min_copy = min;
                remove(min.id);
                return min_copy;
            }
        }

        void insert(const MatchingNode &u) {
            assert(partners.size() < max_size);
            partners.emplace_back(u);
            if (partners.size() == max_size && !partners.empty()) {
                min = *std::min_element(partners.begin(), partners.end());
            }
        }

        void remove(node u) {
            partners.erase(std::remove_if(partners.begin(), partners.end(),
                                          [u](const MatchingNode &v) { return v.id == u; }),
                           partners.end());
            min = MatchingNode();
        }
    };

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

    BSuitorMatcher(const Graph &G, count b = 1);

    BSuitorMatcher(const Graph &G, std::string_view &path);

    ~BSuitorMatcher() override = default;

    void run() override;

protected:
    std::vector<MatchingNodeInfo> suitors;
    std::vector<MatchingNodeInfo> proposed;
    const std::vector<count> b;

    std::vector<count> readBValuesFromFile(count size, std::string_view &path) const;

    void findSuitors(node u);

    MatchingNode findPreferred(node u);

    void makeSuitor(node u, edgeweight w, node v);

    bool isSymmetrical() const;

private:
    void buildBMatching();
};
} // namespace NetworKit

#endif // NETWORKIT_MATCHING_B_SUITOR_MATCHER_HPP_