tree_augmentation.hpp File Reference

#include "paal/iterative_rounding/ir_components.hpp"
#include "paal/iterative_rounding/iterative_rounding.hpp"
#include "paal/utils/hash.hpp"
#include <boost/bimap.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/connected_components.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/stoer_wagner_min_cut.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/range/as_array.hpp>
#include <boost/range/distance.hpp>
#include <algorithm>
#include <utility>

Go to the source code of this file.

Classes
struct	paal::ir::detail::bool_map_to_tree_filter< EdgeBoolMap >
struct	paal::ir::detail::bool_map_to_non_tree_filter< EdgeBoolMap >
class	paal::ir::detail::const_int_map< KeyType, num >
	A boost graph map that returns a constant integer value. More...
struct	paal::ir::ta_round_condition
struct	paal::ir::ta_set_solution
class	paal::ir::ta_init
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. More...

Namespaces
	paal
	global namespace of project.
	paal::ir
	Iterative Rounding namespace.
	paal::ir::detail
	Detail of Iterative Rounding namespace.

Typedefs
template<typename Init = ta_init, typename RoundCondition = ta_round_condition, typename RelaxContition = utils::always_false, typename SetSolution = ta_set_solution>
using	paal::ir::tree_augmentation_ir_components = IRcomponents< Init, RoundCondition, RelaxContition, SetSolution >

Functions
template<class EdgeListGraph >
int	paal::ir::detail::filtered_num_edges (const EdgeListGraph &g)
template<typename Graph , typename TreeMap , typename CostMap , typename VertexIndex , typename EdgeSetOutputIterator >
tree_aug< Graph, TreeMap, CostMap, VertexIndex, EdgeSetOutputIterator >	paal::ir::detail::make_tree_aug (const Graph &g, TreeMap tree_map, CostMap cost_map, VertexIndex vertex_index, EdgeSetOutputIterator solution)
	Creates a tree_aug object. Non-named parameters. More...
template<typename Graph , typename TreeMap , typename CostMap , typename VertexIndex , typename EdgeSetOutputIterator , typename IRcomponents = tree_augmentation_ir_components<>, typename Visitor = trivial_visitor>
IRResult	paal::ir::detail::tree_augmentation_iterative_rounding (const Graph &g, TreeMap tree_map, CostMap cost_map, VertexIndex vertex_index, EdgeSetOutputIterator solution, IRcomponents components=IRcomponents(), Visitor visitor=Visitor())
	Solves the Tree Augmentation problem using Iterative Rounding. Non-named parameters. More...
template<typename Graph , typename EdgeSetOutputIterator , typename P , typename T , typename R >
auto	paal::ir::make_tree_aug (const Graph &g, const boost::bgl_named_params< P, T, R > &params, EdgeSetOutputIterator solution) -> tree_aug< Graph, decltype(choose_const_pmap(get_param(params, boost::edge_color), g, boost::edge_color)), decltype(choose_const_pmap(get_param(params, boost::edge_weight), g, boost::edge_weight)), decltype(choose_const_pmap(get_param(params, boost::vertex_index), g, boost::vertex_index)), EdgeSetOutputIterator >
template<typename Graph , typename EdgeSetOutputIterator >
auto	paal::ir::make_tree_aug (const Graph &g, EdgeSetOutputIterator solution) -> decltype(make_tree_aug(g, boost::no_named_parameters(), solution))
template<typename Graph , typename EdgeSetOutputIterator , typename IRcomponents = tree_augmentation_ir_components<>, typename Visitor = trivial_visitor, typename P , typename T , typename R >
IRResult	paal::ir::tree_augmentation_iterative_rounding (const Graph &g, const boost::bgl_named_params< P, T, R > &params, EdgeSetOutputIterator solution, IRcomponents components=IRcomponents(), Visitor visitor=Visitor())
	Solves the Tree Augmentation problem using Iterative Rounding. Named parameters. More...
template<typename Graph , typename EdgeSetOutputIterator , typename IRcomponents = tree_augmentation_ir_components<>, typename Visitor = trivial_visitor>
IRResult	paal::ir::tree_augmentation_iterative_rounding (const Graph &g, EdgeSetOutputIterator solution, IRcomponents components=IRcomponents(), Visitor visitor=Visitor())
	Solves the Tree Augmentation problem using Iterative Rounding. All default parameters. More...

Detailed Description

Author

Attila Bernath, Piotr Smulewicz, Piotr Wygocki, Piotr Godlewski

Version

1.0

Date

2013-06-20

Definition in file tree_augmentation.hpp.