T_Tree_solver< Graph > Class Template Reference

A dynamic programming algorithm which solves the D family matching problem for trees. More...

#include <Algorithms.hpp>

Public Types
typedef T_Tree_solver< Graph >	Self
typedef T_Sub_graph< Graph >	Sub_graph
typedef T_Tree< Graph >	Tree
typedef boost::graph_traits< Graph >::vertex_descriptor	Graph_vertex
typedef boost::graph_traits< Graph >::edge_descriptor	Edge
typedef boost::property_map< Graph, boost::edge_weight_t >::type	Edge_weight_map
typedef std::pair< int, Sub_graph >	Result_map_element
typedef std::vector< Result_map_element >	Result_map

Constructors
	T_Tree_solver (Graph *g)
	Initialize the pointer to the graph. More...

Functor
Sub_graph	operator() (Tree &t, unsigned D)

Command line options
boost::program_options::options_description	add_options (void) const
	Just to add options on the command line. More...

Detailed Description

template<class Graph>
class SBL::CADS::T_Tree_solver< Graph >

A dynamic programming algorithm which solves the D family matching problem for trees.

The graph must be weighted.

Template Parameters

Graph

Representation of a graph.

Member Typedef Documentation

Edge

typedef boost::graph_traits<Graph>::edge_descriptor Edge

Edge_weight_map

typedef boost::property_map<Graph, boost::edge_weight_t>::type Edge_weight_map

Graph_vertex

typedef boost::graph_traits<Graph>::vertex_descriptor Graph_vertex

Result_map

typedef std::vector<Result_map_element> Result_map

Result_map_element

typedef std::pair<int, Sub_graph> Result_map_element

Self

typedef T_Tree_solver<Graph> Self

Sub_graph

typedef T_Sub_graph<Graph> Sub_graph

Tree

typedef T_Tree<Graph> Tree

Constructor & Destructor Documentation

T_Tree_solver()

T_Tree_solver ( Graph *  g )

inline

Initialize the pointer to the graph.

Member Function Documentation

add_options()

boost::program_options::options_description add_options ( void  ) const

inline

Just to add options on the command line.

operator()()

T_Tree_solver< Graph >::Sub_graph operator() ( Tree &  t, unsigned  D  )

inline

A functor that computes a solution to the D family matching problem for a given Tree t (that is a spanning tree on m_graph) and a parameter D. Returns a Sub_graph (which is the optimal constructed solution over the Tree)