rand_cover.hpp File Reference

Randomized Approximation Algorithm for Minimum Weighted Vertex Cover. More...

#include <cassert>
#include <optional>
#include <py2cpp/set.hpp>
#include <random>
#include <utility>
#include <vector>
#include <xnetwork/thread_pool.hpp>

Include dependency graph for rand_cover.hpp:

Go to the source code of this file.

Namespaces
namespace	detail

Functions
template<typename Node , typename Validator >
void	detail::reverse_delete_cover (py::set< Node > &soln, const std::vector< Node > &added_order, Validator &&is_valid)
	Reverse-delete post-processing step.
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 >
	Single trial of Pitt's randomized vertex cover algorithm.
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 >
	Single-trial randomized vertex cover (seeded convenience wrapper).
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 >
	Multi-threaded randomized vertex cover.

Detailed Description

Randomized Approximation Algorithm for Minimum Weighted Vertex Cover.

Implements Pitt's randomized algorithm (1985) for solving the minimum weighted vertex cover problem on graphs. The algorithm achieves an expected approximation ratio of 2.

For each uncovered edge (u, v), selects one endpoint with probability inversely proportional to its weight: P(pick u) = w(v) / (w(u) + w(v))

Multi-threaded overloads run independent trials in parallel and return the best (lowest-weight) cover.

Reference: L. Pitt, "A Simple Probabilistic Approximation Algorithm for Vertex Cover," Technical Report, Yale University, 1985.

Function Documentation

rand_vertex_cover()

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>

Single-trial randomized vertex cover (seeded convenience wrapper).

Parameters

ugraph	Input graph
weight	Vertex weights
seed	Random seed (default: 0). Use std::nullopt for non-deterministic.
coverset	Optional initial cover set

Returns

A pair of (cover set, total weight)

rand_vertex_cover_mt()

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 >

Multi-threaded randomized vertex cover.

Runs num_trials independent Pitt trials in parallel using std::async, then returns the cover with the lowest total weight.

Template Parameters

Graph	Graph type
WeightMap	Weight map type

Parameters

ugraph	Input undirected graph
weight	Vertex weight mapping (read-concurrently from threads)
num_trials	Number of independent Monte Carlo trials (default: 64)
seed	Master random seed (default: 0). Trials use seed + index.
coverset	Optional initial cover set (shared by all trials)

Returns

std::pair<py::set<typename Graph::node_t>, typename WeightMap::mapped_type>

rand_vertex_cover_trial()

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 >

Single trial of Pitt's randomized vertex cover algorithm.

Template Parameters

Graph	Graph type (requires node_t, edges())
WeightMap	Weight map type (requires mapped_type, operator[])
RNG	Random number generator type

Parameters

ugraph	Input undirected graph
weight	Vertex weight mapping
coverset	Initial vertex cover (preserved in the result)
rng	Random number generator (seeded externally)

Returns

std::pair<py::set<typename Graph::node_t>, typename WeightMap::mapped_type>