All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
Public Types | Public Member Functions | List of all members
paal::ir::tree_aug< Graph, TreeMap, CostMap, VertexIndex, EdgeSetOutputIterator > Class Template Reference

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
Graphthe graph type used
TreeMapit 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.
CostMaptype for the costs of the links.
VertexIndextype for the vertex index map.
EdgeSetOutputIteratortype 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
gthe graph to work with
tree_mapdesignate a spanning tree in g
cost_mapcosts of the links (=non-tree edges). The costs assigned to tree edges are not used.
vertex_indexvertex index map
solutionresult 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: