cover.hpp

Go to the documentation of this file.

 
#pragma once
 
#include <algorithm>
#include <cassert>
#include <deque>
#include <optional>
#include <py2cpp/dict.hpp>
#include <py2cpp/set.hpp>
#include <utility>
#include <vector>
 
template <typename MakeViolator, typename WeightMap, typename SolutionSet>
auto pd_cover(MakeViolator make_violator, WeightMap& weight, SolutionSet& soln)
    -> std::pair<SolutionSet, typename WeightMap::mapped_type> {
    using CostType = typename WeightMap::mapped_type;
    using NodeType = typename SolutionSet::value_type;
 
    CostType total_dual_cost = 0;
    auto gap = weight;  // copy weights
    std::vector<NodeType> added_order;
 
    // Phase 1: Primal-Dual Selection
    // Repeatedly call the violator for each violation, updating
    // coverset/gap between calls (lazy evaluation equivalent to the
    // original coroutine-based generator).
    {
        auto next = make_violator();
        while (auto opt = next()) {
            auto& violate_set = *opt;
            if (violate_set.empty()) continue;
 
            auto min_vtx = *std::min_element(
                violate_set.begin(), violate_set.end(),
                [&](const auto& v1, const auto& v2) { return gap[v1] < gap[v2]; });
            auto min_val = gap[min_vtx];
 
            if (!soln.contains(min_vtx)) {
                soln.insert(min_vtx);
                added_order.emplace_back(min_vtx);
            }
 
            total_dual_cost += min_val;
 
            for (const auto& vtx : violate_set) {
                gap[vtx] -= min_val;
            }
        }
    }
 
    // Phase 2: Reverse-Delete Post-Processing
    for (auto it = added_order.rbegin(); it != added_order.rend(); ++it) {
        soln.erase(*it);
        bool is_redundant = true;
        {
            auto check = make_violator();
            while (auto opt = check()) {
                if (!opt->empty()) {
                    is_redundant = false;
                    break;
                }
            }
        }
        if (!is_redundant) {
            soln.insert(*it);
        }
    }
 
    CostType final_prml_cost = 0;
    for (const auto& vtx : soln) {
        final_prml_cost += weight[vtx];
    }
 
    assert(total_dual_cost <= final_prml_cost);
    return std::make_pair(soln, final_prml_cost);
}
 
template <typename Graph, typename WeightMap, typename CoverSet>
auto min_vertex_cover(const Graph& ugraph, WeightMap& weight, CoverSet& coverset)
    -> std::pair<CoverSet, typename WeightMap::mapped_type>;
 
template <typename Graph, typename WeightMap>
auto min_vertex_cover(const Graph& ugraph, WeightMap& weight)
    -> std::pair<py::set<typename Graph::node_t>, typename WeightMap::mapped_type> {
    py::set<typename Graph::node_t> coverset{};
    return min_vertex_cover(ugraph, weight, coverset);
}
 
template <typename Node> struct BFSInfo {
    Node parent;
    int depth;
 
    BFSInfo(Node p, int d) : parent(p), depth(d) {}
    BFSInfo(const BFSInfo&) = default;
    BFSInfo(BFSInfo&&) = default;
    BFSInfo& operator=(const BFSInfo&) = default;
    BFSInfo& operator=(BFSInfo&&) = default;
    ~BFSInfo() = default;
};
 
template <typename Node> auto construct_cycle(const py::dict<Node, BFSInfo<Node>>& info,
                                              Node parent, Node child) -> std::deque<Node>;
 
template <typename Graph, typename CoverSet>
auto generic_bfs_cycle(const Graph& ugraph, const CoverSet& coverset)
    -> std::vector<std::tuple<py::dict<typename Graph::node_t, BFSInfo<typename Graph::node_t>>,
                              typename Graph::node_t, typename Graph::node_t>>;
 
template <typename Graph, typename WeightMap, typename CoverSet>
auto min_cycle_cover(const Graph& ugraph, WeightMap& weight, CoverSet& coverset)
    -> std::pair<CoverSet, typename WeightMap::mapped_type> {
    using node_t = typename Graph::node_t;
 
    // Factory: returns a violator that does a fresh BFS each call
    // and returns the first cycle found (or nullopt if none).
    auto make_violate = [&]() {
        return [&ugraph, &coverset]() -> std::optional<std::vector<node_t>> {
            auto cycles = generic_bfs_cycle<Graph, CoverSet>(ugraph, coverset);
            if (cycles.empty()) return std::nullopt;
            const auto& [info, parent, child] = cycles[0];
            auto cycle_deque = construct_cycle<node_t>(info, parent, child);
            return std::vector<node_t>(cycle_deque.begin(), cycle_deque.end());
        };
    };
 
    return pd_cover(make_violate, weight, coverset);
}
 
template <typename Graph, typename WeightMap>
auto min_cycle_cover(const Graph& ugraph, WeightMap& weight)
    -> std::pair<py::set<typename Graph::node_t>, typename WeightMap::mapped_type> {
    py::set<typename Graph::node_t> coverset{};
    return min_cycle_cover(ugraph, weight, coverset);
}
 
template <typename Graph, typename WeightMap, typename CoverSet>
auto min_odd_cycle_cover(const Graph& ugraph, WeightMap& weight, CoverSet& coverset)
    -> std::pair<CoverSet, typename WeightMap::mapped_type>;
 
template <typename Graph, typename WeightMap>
auto min_odd_cycle_cover(const Graph& ugraph, WeightMap& weight)
    -> std::pair<py::set<typename Graph::node_t>, typename WeightMap::mapped_type> {
    py::set<typename Graph::node_t> coverset{};
    return min_odd_cycle_cover(ugraph, weight, coverset);
}