Structural Bioinformatics Library
Template C++ / Python API for developping structural bioinformatics applications.
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_graphResults
 
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
GraphRepresentation of the intersection graph.
StopConditionA 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).
SpanningTreeGeneratorA method to generate a spanning tree over a connected component of the intersection graph
AlgorithmThe 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

◆ 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]

The best score is always initialized at 0.

◆ T_Spanning_tree_solver() [2/3]

◆ 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.