rand_cover.hpp

Go to the documentation of this file.

#pragma once
 
#include <cassert>
#include <optional>
#include <py2cpp/set.hpp>
#include <random>
#include <utility>
#include <vector>
#include <xnetwork/thread_pool.hpp>
 
namespace detail {
 
    template <typename Node, typename Validator>
    void reverse_delete_cover(py::set<Node>& soln, const std::vector<Node>& added_order,
                              Validator&& is_valid) {
        for (auto it = added_order.rbegin(); it != added_order.rend(); ++it) {
            soln.erase(*it);
            if (!std::forward<Validator>(is_valid)()) {
                soln.insert(*it);
            }
        }
    }
 
}  // namespace detail
 
template <typename Graph, typename WeightMap, typename RNG>
auto rand_vertex_cover_trial(const Graph& ugraph, const WeightMap& weight,
                             const py::set<typename Graph::node_t>& coverset, RNG& rng)
    -> std::pair<py::set<typename Graph::node_t>, typename WeightMap::mapped_type>;
 
// -----------------------------------------------------------------------
// Convenience overload - single trial with seed
// -----------------------------------------------------------------------
 
template <typename Graph, typename WeightMap>
auto rand_vertex_cover(const Graph& ugraph, const WeightMap& weight,
                       std::optional<unsigned int> seed = std::optional<unsigned int>{0},
                       const py::set<typename Graph::node_t>& coverset = {})
    -> std::pair<py::set<typename Graph::node_t>, typename WeightMap::mapped_type> {
    // using node_t = typename Graph::node_t;
 
    if (seed.has_value()) {
        std::mt19937 rng{seed.value()};
        return rand_vertex_cover_trial(ugraph, weight, coverset, rng);
    }
    std::random_device rd;
    std::mt19937 rng{rd()};
    return rand_vertex_cover_trial(ugraph, weight, coverset, rng);
}
 
// -----------------------------------------------------------------------
// Multi-threaded: run num_trials independent trials, return best cover
// -----------------------------------------------------------------------
 
template <typename Graph, typename WeightMap>
auto rand_vertex_cover_mt(const Graph& ugraph, const WeightMap& weight,
                          unsigned int num_trials = 64, unsigned int seed = 0,
                          const py::set<typename Graph::node_t>& coverset = {})
    -> std::pair<py::set<typename Graph::node_t>, typename WeightMap::mapped_type>;