All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
Classes | Namespaces | Typedefs | Functions
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.