cover.hpp File Reference

Primal-dual approximation algorithms for covering problems. More...

#include <algorithm>
#include <cassert>
#include <deque>
#include <optional>
#include <py2cpp/dict.hpp>
#include <py2cpp/set.hpp>
#include <utility>
#include <vector>

Include dependency graph for cover.hpp:

Go to the source code of this file.

Classes
struct	BFSInfo< Node >
	Information structure for BFS traversal. More...

Functions
template<typename MakeViolator , typename WeightMap , typename SolutionSet >
auto	pd_cover (MakeViolator make_violator, WeightMap &weight, SolutionSet &soln) -> std::pair< SolutionSet, typename WeightMap::mapped_type >
	Implements a primal-dual approximation algorithm for covering problems.
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 >
	Performs minimum weighted vertex cover using primal-dual approximation.
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 >
	Overload without pre-existing coverset.
template<typename Node >
auto	construct_cycle (const py::dict< Node, BFSInfo< Node > > &info, Node parent, Node child) -> std::deque< Node >
	Constructs a cycle from BFS information.
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 > >
	Generic BFS cycle detection.
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 >
	Performs minimum cycle cover using primal-dual approximation.
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 >
	Overload without pre-existing 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 >
	Performs minimum odd cycle cover using primal-dual approximation.
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 >
	Overload without pre-existing coverset.

Detailed Description

Primal-dual approximation algorithms for covering problems.

Implements a generic primal-dual cover algorithm (pd_cover) and specialized functions for minimum vertex cover, minimum cycle cover, and minimum odd cycle cover.

Function Documentation

construct_cycle()

template<typename Node >

auto construct_cycle	(	const py::dict< Node, BFSInfo< Node > > &	info,
		Node	parent,
		Node	child
	)		-> std::deque< Node >

Constructs a cycle from BFS information.

Template Parameters

Node

Node type

Parameters

info	BFS information mapping
parent	First node in cycle
child	Second node in cycle

Returns

std::deque<Node> The constructed cycle

generic_bfs_cycle()

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 > >

Generic BFS cycle detection.

Template Parameters

Graph	Graph type
CoverSet	Cover set type

Parameters

ugraph	Input graph
coverset	Set of covered vertices (excluded from search)

Returns

std::vector<std::tuple<py::dict<typename Graph::node_t, BFSInfo<typename Graph::node_t>>, typename Graph::node_t, typename Graph::node_t>> Vector of (BFS info, parent, child) tuples for each cycle found

min_cycle_cover() [1/2]

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>

Overload without pre-existing coverset.

min_cycle_cover() [2/2]

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>

Performs minimum cycle cover using primal-dual approximation.

Template Parameters

Graph	Graph type
WeightMap	Weight map type
CoverSet	Cover set type

Parameters

ugraph	Input graph
weight	Weight function
coverset	Cover set (will be modified)

Returns

std::pair<CoverSet, typename WeightMap::mapped_type> Cover set and total weight

min_odd_cycle_cover() [1/2]

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>

Overload without pre-existing coverset.

min_odd_cycle_cover() [2/2]

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 >

Performs minimum odd cycle cover using primal-dual approximation.

Template Parameters

Graph	Graph type
WeightMap	Weight map type
CoverSet	Cover set type

Parameters

ugraph	Input graph
weight	Weight function
coverset	Cover set (will be modified)

Returns

std::pair<CoverSet, typename WeightMap::mapped_type> Cover set and total weight

min_vertex_cover() [1/2]

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>

Overload without pre-existing coverset.

min_vertex_cover() [2/2]

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 >

Performs minimum weighted vertex cover using primal-dual approximation.

Template Parameters

Graph	Graph type
WeightMap	Weight map type
CoverSet	Cover set type

Parameters

ugraph	Input graph
weight	Weight function
coverset	Cover set (will be modified)

Returns

std::pair<CoverSet, typename WeightMap::mapped_type> Cover set and total weight

pd_cover()

template<typename MakeViolator , typename WeightMap , typename SolutionSet >

auto pd_cover	(	MakeViolator	make_violator,
		WeightMap &	weight,
		SolutionSet &	soln
	)		-> std::pair<SolutionSet, typename WeightMap::mapped_type>

Implements a primal-dual approximation algorithm for covering problems.

Template Parameters

MakeViolator	Factory callable: make_violator() returns a "violator". The violator is called repeatedly; each call returns std::optional<std::vector<NodeType>> - the next violation, or std::nullopt when exhausted.
WeightMap	Weight mapping (mutable)
SolutionSet	Set-like container for the solution

Parameters

make_violator	Factory that creates fresh violators
weight	Weight function for vertices
soln	Solution set (will be modified)

Returns

std::pair<SolutionSet, typename WeightMap::mapped_type> Solution and total primal cost