T_Spanning_tree_solver< IntersectionGraph, StopCondition, SpanningTreeGenerator, Algorithm > Class Template Reference

A heuristic algorithm to solve the D-Family-matching problem by using spanning trees. More...

#include <Spanning_tree_solver.hpp>

Classes
class	Meta_clusters_iterator

Public Types
typedef IntersectionGraph	Intersection_graph
typedef SpanningTreeGenerator	ST_computer
typedef StopCondition	SC_computer
typedef T_Spanning_tree_solver< Intersection_graph, SC_computer, ST_computer, Algorithm >	Self
typedef boost::graph_traits< Intersection_graph >::vertex_descriptor	Intersection_graph_vertex
typedef boost::graph_traits< Intersection_graph >::edge_descriptor	Intersection_graph_edge
typedef boost::property_map< Intersection_graph, boost::edge_weight_t >::type	Intersection_graph_edge_weight_map
typedef Algorithm::Sub_graph	Sub_graph
typedef Algorithm::Tree	Tree
typedef SC_computer::Solution_space	Solution_type
typedef std::vector< Sub_graph >	Results
typedef std::map< unsigned, std::vector< Intersection_graph_vertex > >	Meta_cluster_map
typedef Meta_cluster_map::iterator	Map_iterator
typedef std::vector< Intersection_graph_vertex >::iterator	Clusters_iterator

Constructors
	T_Spanning_tree_solver ()
	The best score is always initialized at 0. More...
	T_Spanning_tree_solver (Intersection_graph *g)
	T_Spanning_tree_solver (const Self &other)

Functor
unsigned	operator() (unsigned D, Solution_type &solutions)
	A functor to solve the D-Family-matching problem using the heuristic algorithm on the given intersection graph m_graph. Updates the graph if required. More...

Iterators
Meta_clusters_iterator	meta_clusters_begin ()
	Iterate over meta clusters. More...
Meta_clusters_iterator	meta_clusters_end ()
Clusters_iterator	clusters_in_meta_cluster_begin (unsigned meta_index)
	Iterate over clusters contained in a meta cluster. More...
Clusters_iterator	clusters_in_meta_cluster_end (unsigned meta_index)

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 IntersectionGraph, class StopCondition, class SpanningTreeGenerator, class Algorithm>
class SBL::CADS::T_Spanning_tree_solver< IntersectionGraph, StopCondition, SpanningTreeGenerator, Algorithm >

A heuristic algorithm to solve the D-Family-matching problem by using spanning trees.

The graph must be weighted.

Template Parameters

Graph	Representation of the intersection graph.
StopCondition	A functor to compute if the stop condition is met. Also provides the definitions of the Solution space (which is inherent to a particular stop condition).
SpanningTreeGenerator	A method to generate a spanning tree over a connected component of the intersection graph
Algorithm	The algorithm to solve the D-Family-matching problem over a tree.

Member Typedef Documentation

Clusters_iterator

typedef std::vector<Intersection_graph_vertex>::iterator Clusters_iterator

Intersection_graph

typedef IntersectionGraph Intersection_graph

Intersection_graph_edge

typedef boost::graph_traits<Intersection_graph>::edge_descriptor Intersection_graph_edge

Intersection_graph_edge_weight_map

typedef boost::property_map<Intersection_graph, boost::edge_weight_t>::type Intersection_graph_edge_weight_map

Intersection_graph_vertex

typedef boost::graph_traits<Intersection_graph>::vertex_descriptor Intersection_graph_vertex

Map_iterator

typedef Meta_cluster_map::iterator Map_iterator

Meta_cluster_map

typedef std::map<unsigned, std::vector<Intersection_graph_vertex> > Meta_cluster_map

Results

typedef std::vector<Sub_graph> Results

SC_computer

typedef StopCondition SC_computer

Self

typedef T_Spanning_tree_solver<Intersection_graph, SC_computer, ST_computer, Algorithm> Self

Solution_type

typedef SC_computer::Solution_space Solution_type

ST_computer

typedef SpanningTreeGenerator ST_computer

Sub_graph

typedef Algorithm::Sub_graph Sub_graph

Tree

typedef Algorithm::Tree Tree

Constructor & Destructor Documentation

T_Spanning_tree_solver() [1/3]

T_Spanning_tree_solver ( )

inline

The best score is always initialized at 0.

T_Spanning_tree_solver() [2/3]

T_Spanning_tree_solver ( Intersection_graph *  g )

inline

T_Spanning_tree_solver() [3/3]

T_Spanning_tree_solver ( const Self &  other )

inline

Member Function Documentation

add_options()

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

inline

Just to add options on the command line.

clusters_in_meta_cluster_begin()

T_Spanning_tree_solver< IntersectionGraph, StopCondition, SpanningTreeGenerator, Algorithm >::Clusters_iterator clusters_in_meta_cluster_begin ( unsigned  meta_index )

inline

Iterate over clusters contained in a meta cluster.

clusters_in_meta_cluster_end()

T_Spanning_tree_solver< IntersectionGraph, StopCondition, SpanningTreeGenerator, Algorithm >::Clusters_iterator clusters_in_meta_cluster_end ( unsigned  meta_index )

inline

meta_clusters_begin()

T_Spanning_tree_solver< IntersectionGraph, StopCondition, SpanningTreeGenerator, Algorithm >::Meta_clusters_iterator meta_clusters_begin

inline

Iterate over meta clusters.

meta_clusters_end()

T_Spanning_tree_solver< IntersectionGraph, StopCondition, SpanningTreeGenerator, Algorithm >::Meta_clusters_iterator meta_clusters_end

inline

operator()()

unsigned operator() ( unsigned  D, Solution_type &  solutions  )

inline

A functor to solve the D-Family-matching problem using the heuristic algorithm on the given intersection graph m_graph. Updates the graph if required.