This is Jain's iterative rounding 2-approximation algorithm for the Generalised Steiner Network Problem, specialized for the Tree Augmentation Problem. More...

#include <tree_augmentation.hpp>

Public Types
using	Edge = typename boost::graph_traits< Graph >::edge_descriptor

using	Vertex = typename boost::graph_traits< Graph >::vertex_descriptor

using	CostValue = double

using	TreeGraph = boost::filtered_graph< Graph, detail::bool_map_to_tree_filter< TreeMap >>

using	NonTreeGraph = boost::filtered_graph< Graph, detail::bool_map_to_non_tree_filter< TreeMap >>

using	EdgeList = std::vector< Edge >

using	CoverMap = std::unordered_map< Edge, EdgeList, edge_hash< Graph >>

using	EdgeToColId = boost::bimap< Edge, lp::col_id >

using	RowIdToEdge = std::unordered_map< lp::row_id, Edge >

using	ErrorMessage = boost::optional< std::string >

Public Member Functions
	tree_aug (const Graph &g, TreeMap tree_map, CostMap cost_map, VertexIndex vertex_index, EdgeSetOutputIterator solution)

ErrorMessage	check_input_validity ()
	Checks validity of the input.

const NonTreeGraph &	get_links_graph () const

const TreeGraph &	get_tree_graph () const

auto	get_cost (Edge e) -> decltype(get(std::declval< CostMap >(), e))

void	add_to_solution (lp::col_id col)

void	bind_edge_to_col (Edge e, lp::col_id col)

void	bind_edge_to_row (Edge e, lp::row_id row)

void	init ()

Edge	row_to_edge (lp::row_id row) const

lp::col_id	edge_to_col (Edge e) const

EdgeList &	get_covered_by (Edge e)

bool	is_in_solution (Edge e) const

CostValue	get_solution_cost () const

Detailed Description

template<typename Graph, typename TreeMap, typename CostMap, typename VertexIndex, typename EdgeSetOutputIterator>
class paal::ir::tree_aug< Graph, TreeMap, CostMap, VertexIndex, EdgeSetOutputIterator >

This is Jain's iterative rounding 2-approximation algorithm for the Generalised Steiner Network Problem, specialized for the Tree Augmentation Problem.

The Tree Augmentation Problem is the following. Given a 2-edge connected graph, in which a spanning tree is designated. The non-tree edges are also called links. The links have non-negative costs. The problem is to find a minimum cost subset of links which, together with the tree-edges give a 2-edge-connected graph.

Template Parameters

Graph	the graph type used
TreeMap	it is assumed to be a bool map on the edges of a graph of type Graph. It is used for designating a spanning tree in the graph.
CostMap	type for the costs of the links.
VertexIndex	type for the vertex index map.
EdgeSetOutputIterator	type for the result edge set.

Definition at line 242 of file tree_augmentation.hpp.

Constructor & Destructor Documentation

template<typename Graph , typename TreeMap , typename CostMap , typename VertexIndex , typename EdgeSetOutputIterator >

paal::ir::tree_aug< Graph, TreeMap, CostMap, VertexIndex, EdgeSetOutputIterator >::tree_aug	(	const Graph &	g,
		TreeMap	tree_map,
		CostMap	cost_map,
		VertexIndex	vertex_index,
		EdgeSetOutputIterator	solution
	)

inline

Constructor.

Parameters

g	the graph to work with
tree_map	designate a spanning tree in `g`
cost_map	costs of the links (=non-tree edges). The costs assigned to tree edges are not used.
vertex_index	vertex index map
solution	result set of edges output iterator

Definition at line 271 of file tree_augmentation.hpp.

Member Function Documentation

template<typename Graph , typename TreeMap , typename CostMap , typename VertexIndex , typename EdgeSetOutputIterator >

void paal::ir::tree_aug< Graph, TreeMap, CostMap, VertexIndex, EdgeSetOutputIterator >::add_to_solution ( lp::col_id col )

inline

Adds an edge corresponding to the given LP column to the result set.

Definition at line 330 of file tree_augmentation.hpp.

template<typename Graph , typename TreeMap , typename CostMap , typename VertexIndex , typename EdgeSetOutputIterator >

void paal::ir::tree_aug< Graph, TreeMap, CostMap, VertexIndex, EdgeSetOutputIterator >::bind_edge_to_col	(	Edge	e,
		lp::col_id	col
	)

inline

Binds a graph edge to a LP column.

Definition at line 340 of file tree_augmentation.hpp.

template<typename Graph , typename TreeMap , typename CostMap , typename VertexIndex , typename EdgeSetOutputIterator >

void paal::ir::tree_aug< Graph, TreeMap, CostMap, VertexIndex, EdgeSetOutputIterator >::bind_edge_to_row	(	Edge	e,
		lp::row_id	row
	)

inline

Binds a graph edge to a LP row.

Definition at line 349 of file tree_augmentation.hpp.

template<typename Graph , typename TreeMap , typename CostMap , typename VertexIndex , typename EdgeSetOutputIterator >

lp::col_id paal::ir::tree_aug< Graph, TreeMap, CostMap, VertexIndex, EdgeSetOutputIterator >::edge_to_col ( Edge e ) const

inline

Returns the LP columnn corresponding to a graph edge.

Definition at line 396 of file tree_augmentation.hpp.

template<typename Graph , typename TreeMap , typename CostMap , typename VertexIndex , typename EdgeSetOutputIterator >

auto paal::ir::tree_aug< Graph, TreeMap, CostMap, VertexIndex, EdgeSetOutputIterator >::get_cost ( Edge e ) -> decltype(get(std::declval<CostMap>(), e))

inline

Returns the cost of an edge.

Definition at line 323 of file tree_augmentation.hpp.

template<typename Graph , typename TreeMap , typename CostMap , typename VertexIndex , typename EdgeSetOutputIterator >

EdgeList& paal::ir::tree_aug< Graph, TreeMap, CostMap, VertexIndex, EdgeSetOutputIterator >::get_covered_by ( Edge e )

inline

Returns the list of links covering a given edge.

Definition at line 401 of file tree_augmentation.hpp.

template<typename Graph , typename TreeMap , typename CostMap , typename VertexIndex , typename EdgeSetOutputIterator >

const NonTreeGraph& paal::ir::tree_aug< Graph, TreeMap, CostMap, VertexIndex, EdgeSetOutputIterator >::get_links_graph ( ) const

inline

Returns the non-tree graph (set of links).

Definition at line 313 of file tree_augmentation.hpp.

template<typename Graph , typename TreeMap , typename CostMap , typename VertexIndex , typename EdgeSetOutputIterator >

CostValue paal::ir::tree_aug< Graph, TreeMap, CostMap, VertexIndex, EdgeSetOutputIterator >::get_solution_cost ( ) const

inline

Returns cost of the found solution.

Definition at line 413 of file tree_augmentation.hpp.

template<typename Graph , typename TreeMap , typename CostMap , typename VertexIndex , typename EdgeSetOutputIterator >

const TreeGraph& paal::ir::tree_aug< Graph, TreeMap, CostMap, VertexIndex, EdgeSetOutputIterator >::get_tree_graph ( ) const

inline

Returns the spanning tree.

Definition at line 318 of file tree_augmentation.hpp.

template<typename Graph , typename TreeMap , typename CostMap , typename VertexIndex , typename EdgeSetOutputIterator >

void paal::ir::tree_aug< Graph, TreeMap, CostMap, VertexIndex, EdgeSetOutputIterator >::init ( )

inline

Initializes the necessary data structures.

Definition at line 358 of file tree_augmentation.hpp.

template<typename Graph , typename TreeMap , typename CostMap , typename VertexIndex , typename EdgeSetOutputIterator >

bool paal::ir::tree_aug< Graph, TreeMap, CostMap, VertexIndex, EdgeSetOutputIterator >::is_in_solution ( Edge e ) const

inline

Checks if an edge belongs to the solution.

Definition at line 406 of file tree_augmentation.hpp.

template<typename Graph , typename TreeMap , typename CostMap , typename VertexIndex , typename EdgeSetOutputIterator >

Edge paal::ir::tree_aug< Graph, TreeMap, CostMap, VertexIndex, EdgeSetOutputIterator >::row_to_edge ( lp::row_id row ) const

inline

Returns the edge corresponding to an LP row.

Definition at line 391 of file tree_augmentation.hpp.

The documentation for this class was generated from the following file:

include/paal/iterative_rounding/treeaug/tree_augmentation.hpp

Public Types

Public Member Functions

Detailed Description

template<typename Graph, typename TreeMap, typename CostMap, typename VertexIndex, typename EdgeSetOutputIterator> class paal::ir::tree_aug< Graph, TreeMap, CostMap, VertexIndex, EdgeSetOutputIterator >

Constructor & Destructor Documentation

Member Function Documentation

template<typename Graph, typename TreeMap, typename CostMap, typename VertexIndex, typename EdgeSetOutputIterator>
class paal::ir::tree_aug< Graph, TreeMap, CostMap, VertexIndex, EdgeSetOutputIterator >