The class for solving the Bounded Degree MST problem using Iterative Rounding. More...

#include <bounded_degree_mst.hpp>

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

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

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

using	VertexMap = std::unordered_map< lp::row_id, Vertex >

using	EdgeMapOriginal = std::vector< std::pair< lp::col_id, Edge >>

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

Public Member Functions
	bounded_degree_mst (const Graph &g, const DegreeBounds &deg_bounds, CostMap cost_map, VertexIndex index, SpanningTreeOutputIterator result_spanning_tree, Oracle oracle=Oracle{})

ErrorMessage	check_input_validity ()

template<typename LP >
auto	get_find_violation (LP &lp)

const Graph &	get_graph () const

const VertexIndex &	get_index () const

void	remove_column (lp::col_id col_id)

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

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

decltype(std::declval < DegreeBounds >()(get(std::declval < VertexIndex > (), std::declval< Vertex >())))	get_degree_bound (Vertex v)

boost::optional< lp::col_id >	edge_to_col (Edge e) const

const EdgeMap &	get_edge_map () const

const EdgeMapOriginal &	get_original_edges_map () const

void	add_to_result_spanning_tree (Edge e)

utils::compare< double >	get_compare () const

void	bind_vertex_to_row (Vertex v, lp::row_id row)

void	remove_row (lp::row_id row_id)

boost::optional< Vertex >	row_to_vertex (lp::row_id row)

Detailed Description

template<typename Graph, typename DegreeBounds, typename CostMap, typename VertexIndex, typename SpanningTreeOutputIterator, typename Oracle = paal::lp::random_violated_separation_oracle>
class paal::ir::bounded_degree_mst< Graph, DegreeBounds, CostMap, VertexIndex, SpanningTreeOutputIterator, Oracle >

The class for solving the Bounded Degree MST problem using Iterative Rounding.

Template Parameters

Graph	input graph
DegreeBounds	map from Graph vertices to degree bounds
CostMap	map from Graph edges to costs
VertexIndex	map from Graph vertices to indices
SpanningTreeOutputIterator
Oracle	separation oracle

Definition at line 54 of file bounded_degree_mst.hpp.

Constructor & Destructor Documentation

template<typename Graph , typename DegreeBounds , typename CostMap , typename VertexIndex , typename SpanningTreeOutputIterator , typename Oracle = paal::lp::random_violated_separation_oracle>

paal::ir::bounded_degree_mst< Graph, DegreeBounds, CostMap, VertexIndex, SpanningTreeOutputIterator, Oracle >::bounded_degree_mst	(	const Graph &	g,
		const DegreeBounds &	deg_bounds,
		CostMap	cost_map,
		VertexIndex	index,
		SpanningTreeOutputIterator	result_spanning_tree,
		Oracle	oracle = `Oracle{}`
	)

inline

Constructor.

Definition at line 59 of file bounded_degree_mst.hpp.

Member Function Documentation

template<typename Graph , typename DegreeBounds , typename CostMap , typename VertexIndex , typename SpanningTreeOutputIterator , typename Oracle = paal::lp::random_violated_separation_oracle>

void paal::ir::bounded_degree_mst< Graph, DegreeBounds, CostMap, VertexIndex, SpanningTreeOutputIterator, Oracle >::add_to_result_spanning_tree ( Edge e )

inline

Adds an edge to the result spanning tree.

Definition at line 181 of file bounded_degree_mst.hpp.

template<typename Graph , typename DegreeBounds , typename CostMap , typename VertexIndex , typename SpanningTreeOutputIterator , typename Oracle = paal::lp::random_violated_separation_oracle>

void paal::ir::bounded_degree_mst< Graph, DegreeBounds, CostMap, VertexIndex, SpanningTreeOutputIterator, Oracle >::bind_edge_to_col	(	Edge	e,
		lp::col_id	col
	)

inline

Binds a graph edge to a LP column.

Definition at line 130 of file bounded_degree_mst.hpp.

template<typename Graph , typename DegreeBounds , typename CostMap , typename VertexIndex , typename SpanningTreeOutputIterator , typename Oracle = paal::lp::random_violated_separation_oracle>

void paal::ir::bounded_degree_mst< Graph, DegreeBounds, CostMap, VertexIndex, SpanningTreeOutputIterator, Oracle >::bind_vertex_to_row	(	Vertex	v,
		lp::row_id	row
	)

inline

Binds a graph vertex to an LP row.

Definition at line 196 of file bounded_degree_mst.hpp.

template<typename Graph , typename DegreeBounds , typename CostMap , typename VertexIndex , typename SpanningTreeOutputIterator , typename Oracle = paal::lp::random_violated_separation_oracle>

ErrorMessage paal::ir::bounded_degree_mst< Graph, DegreeBounds, CostMap, VertexIndex, SpanningTreeOutputIterator, Oracle >::check_input_validity ( )

inline

Checks if the input graph is connected.

Definition at line 81 of file bounded_degree_mst.hpp.

template<typename Graph , typename DegreeBounds , typename CostMap , typename VertexIndex , typename SpanningTreeOutputIterator , typename Oracle = paal::lp::random_violated_separation_oracle>

boost::optional<lp::col_id> paal::ir::bounded_degree_mst< Graph, DegreeBounds, CostMap, VertexIndex, SpanningTreeOutputIterator, Oracle >::edge_to_col ( Edge e ) const

inline

Returns the LP column corresponding to an edge, if it wasn't deleted from the LP.

Definition at line 157 of file bounded_degree_mst.hpp.

template<typename Graph , typename DegreeBounds , typename CostMap , typename VertexIndex , typename SpanningTreeOutputIterator , typename Oracle = paal::lp::random_violated_separation_oracle>

utils::compare<double> paal::ir::bounded_degree_mst< Graph, DegreeBounds, CostMap, VertexIndex, SpanningTreeOutputIterator, Oracle >::get_compare ( ) const

inline

Returns the double comparison object.

Definition at line 189 of file bounded_degree_mst.hpp.

template<typename Graph , typename DegreeBounds , typename CostMap , typename VertexIndex , typename SpanningTreeOutputIterator , typename Oracle = paal::lp::random_violated_separation_oracle>

decltype(get(std::declval<CostMap>(), std::declval<Edge>())) paal::ir::bounded_degree_mst< Graph, DegreeBounds, CostMap, VertexIndex, SpanningTreeOutputIterator, Oracle >::get_cost ( Edge e )

inline

Returns the cost of a given edge.

Definition at line 140 of file bounded_degree_mst.hpp.

template<typename Graph , typename DegreeBounds , typename CostMap , typename VertexIndex , typename SpanningTreeOutputIterator , typename Oracle = paal::lp::random_violated_separation_oracle>

decltype(std::declval<DegreeBounds>()(get(std::declval<VertexIndex>(), std::declval<Vertex>()))) paal::ir::bounded_degree_mst< Graph, DegreeBounds, CostMap, VertexIndex, SpanningTreeOutputIterator, Oracle >::get_degree_bound ( Vertex v )

inline

Returns the degree bound of a vertex.

Definition at line 149 of file bounded_degree_mst.hpp.

template<typename Graph , typename DegreeBounds , typename CostMap , typename VertexIndex , typename SpanningTreeOutputIterator , typename Oracle = paal::lp::random_violated_separation_oracle>

const EdgeMap& paal::ir::bounded_degree_mst< Graph, DegreeBounds, CostMap, VertexIndex, SpanningTreeOutputIterator, Oracle >::get_edge_map ( ) const

inline

Returns a bimap between edges and LP column IDs.

Definition at line 169 of file bounded_degree_mst.hpp.

template<typename Graph , typename DegreeBounds , typename CostMap , typename VertexIndex , typename SpanningTreeOutputIterator , typename Oracle = paal::lp::random_violated_separation_oracle>

template<typename LP >

auto paal::ir::bounded_degree_mst< Graph, DegreeBounds, CostMap, VertexIndex, SpanningTreeOutputIterator, Oracle >::get_find_violation ( LP & lp )

inline

Template Parameters

LP

Parameters

lp

Returns

Definition at line 102 of file bounded_degree_mst.hpp.

template<typename Graph , typename DegreeBounds , typename CostMap , typename VertexIndex , typename SpanningTreeOutputIterator , typename Oracle = paal::lp::random_violated_separation_oracle>

const Graph& paal::ir::bounded_degree_mst< Graph, DegreeBounds, CostMap, VertexIndex, SpanningTreeOutputIterator, Oracle >::get_graph ( ) const

inline

Returns the input graph.

Definition at line 112 of file bounded_degree_mst.hpp.

template<typename Graph , typename DegreeBounds , typename CostMap , typename VertexIndex , typename SpanningTreeOutputIterator , typename Oracle = paal::lp::random_violated_separation_oracle>

const VertexIndex& paal::ir::bounded_degree_mst< Graph, DegreeBounds, CostMap, VertexIndex, SpanningTreeOutputIterator, Oracle >::get_index ( ) const

inline

Returns the vertex index.

Definition at line 117 of file bounded_degree_mst.hpp.

template<typename Graph , typename DegreeBounds , typename CostMap , typename VertexIndex , typename SpanningTreeOutputIterator , typename Oracle = paal::lp::random_violated_separation_oracle>

const EdgeMapOriginal& paal::ir::bounded_degree_mst< Graph, DegreeBounds, CostMap, VertexIndex, SpanningTreeOutputIterator, Oracle >::get_original_edges_map ( ) const

inline

Returns a mapping between LP column IDs and edges in the original graph.

Definition at line 174 of file bounded_degree_mst.hpp.

template<typename Graph , typename DegreeBounds , typename CostMap , typename VertexIndex , typename SpanningTreeOutputIterator , typename Oracle = paal::lp::random_violated_separation_oracle>

void paal::ir::bounded_degree_mst< Graph, DegreeBounds, CostMap, VertexIndex, SpanningTreeOutputIterator, Oracle >::remove_column ( lp::col_id col_id )

inline

Removes an LP column and the graph edge corresponding to it.

Definition at line 122 of file bounded_degree_mst.hpp.

template<typename Graph , typename DegreeBounds , typename CostMap , typename VertexIndex , typename SpanningTreeOutputIterator , typename Oracle = paal::lp::random_violated_separation_oracle>

void paal::ir::bounded_degree_mst< Graph, DegreeBounds, CostMap, VertexIndex, SpanningTreeOutputIterator, Oracle >::remove_row ( lp::row_id row_id )

inline

Unbinds the graph vertex from its corresponding (deleted) LP row.

Definition at line 203 of file bounded_degree_mst.hpp.

template<typename Graph , typename DegreeBounds , typename CostMap , typename VertexIndex , typename SpanningTreeOutputIterator , typename Oracle = paal::lp::random_violated_separation_oracle>

boost::optional<Vertex> paal::ir::bounded_degree_mst< Graph, DegreeBounds, CostMap, VertexIndex, SpanningTreeOutputIterator, Oracle >::row_to_vertex ( lp::row_id row )

inline

Returns the graph vertex corresponding to a given LP row, unless the row doen't correspond to any vertex.

Definition at line 212 of file bounded_degree_mst.hpp.

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

include/paal/iterative_rounding/bounded_degree_min_spanning_tree/bounded_degree_mst.hpp

Public Types

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation