graph_algo.hpp File Reference

Graph algorithm implementations for vertex cover and independent set. More...

#include <cassert>
#include <py2cpp/dict.hpp>
#include <py2cpp/set.hpp>
#include <utility>

Include dependency graph for graph_algo.hpp:

Go to the source code of this file.

Functions
template<typename Graph , typename WeightMap , typename CoverSet >
auto	min_vertex_cover_fast (const Graph &ugraph, WeightMap &weight, CoverSet &coverset) -> std::pair< CoverSet, typename WeightMap::mapped_type >
	Performs minimum weighted vertex cover using a primal-dual approximation algorithm.
template<typename Graph , typename WeightMap >
auto	min_vertex_cover_fast (const Graph &ugraph, WeightMap &weight) -> std::pair< py::set< typename Graph::node_t >, typename WeightMap::mapped_type >
	Overload that creates an empty coverset.
template<typename Graph , typename WeightMap , typename IndSet , typename DepSet >
auto	min_maximal_independant_set (const Graph &ugraph, WeightMap &weight, IndSet &indset, DepSet &dep) -> std::pair< IndSet, typename WeightMap::mapped_type >
	Performs minimum weighted maximal independent set using primal-dual algorithm.
template<typename Graph , typename WeightMap >
auto	min_maximal_independant_set (const Graph &ugraph, WeightMap &weight) -> std::pair< py::set< typename Graph::node_t >, typename WeightMap::mapped_type >
	Overload that creates empty indset and dep sets.

Detailed Description

Graph algorithm implementations for vertex cover and independent set.

Provides primal-dual approximation algorithms for minimum weighted vertex cover and minimum maximal independent set.

Function Documentation

min_maximal_independant_set() [1/2]

template<typename Graph , typename WeightMap >

auto min_maximal_independant_set	(	const Graph &	ugraph,
		WeightMap &	weight
	)		-> std::pair<py::set<typename Graph::node_t>, typename WeightMap::mapped_type>

Overload that creates empty indset and dep sets.

min_maximal_independant_set() [2/2]

template<typename Graph , typename WeightMap , typename IndSet , typename DepSet >

auto min_maximal_independant_set	(	const Graph &	ugraph,
		WeightMap &	weight,
		IndSet &	indset,
		DepSet &	dep
	)		-> std::pair< IndSet, typename WeightMap::mapped_type >

Performs minimum weighted maximal independent set using primal-dual algorithm.

This function implements a primal-dual algorithm for minimum weighted maximal independent set.

Template Parameters

Graph	The graph type
WeightMap	The weight map type
IndSet	The independent set type
DepSet	The dependent set type

Parameters

ugraph	The input graph
weight	The weight function for vertices
indset	The independent set (will be modified)
dep	The dependent set (will be modified)

Returns

std::pair<IndSet, typename WeightMap::mapped_type> The independent set and total weight

min_vertex_cover_fast() [1/2]

template<typename Graph , typename WeightMap >

auto min_vertex_cover_fast	(	const Graph &	ugraph,
		WeightMap &	weight
	)		-> std::pair<py::set<typename Graph::node_t>, typename WeightMap::mapped_type>

Overload that creates an empty coverset.

min_vertex_cover_fast() [2/2]

template<typename Graph , typename WeightMap , typename CoverSet >

auto min_vertex_cover_fast	(	const Graph &	ugraph,
		WeightMap &	weight,
		CoverSet &	coverset
	)		-> std::pair< CoverSet, typename WeightMap::mapped_type >

Performs minimum weighted vertex cover using a primal-dual approximation algorithm.

This function implements a primal-dual algorithm for minimum weighted vertex cover on a graph.

Template Parameters

Graph	The graph type
WeightMap	The weight map type (mutable mapping from node to weight)
CoverSet	The cover set type

Parameters

ugraph	The input graph
weight	The weight function for vertices
coverset	The vertex cover set (will be modified)

Returns

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