Structural Bioinformatics Library
Template C++ / Python API for developping structural bioinformatics applications.
T_Earth_mover_distance_with_connectivity_constraints< VerticesAccessor, DistanceFunctor > Class Template Reference

Earth mover distance algorithm with connectivity constraints on the input data. More...

#include <Earth_mover_distance_with_connectivity_constraints.hpp>

Public Types

typedef T_Earth_mover_distance_with_connectivity_constraints< VerticesAccessor, DistanceFunctor > Self
 
typedef VerticesAccessor::Vertices_container Vertices_container
 
typedef DistanceFunctor Distance
 
typedef Distance::FT FT_flow_cost
 
typedef VerticesAccessor::Vertex_rep Vertex_rep
 
typedef T_Earth_mover_distance_transportation_plan< Vertex_rep, FT_flow_costTransportation_plan
 

Public Member Functions

 T_Earth_mover_distance_with_connectivity_constraints (const Distance &dist=Distance())
 
void set_max_cost (const FT_flow_cost &max_cost)
 
Transportation_plan operator() (Vertices_container &source, Vertices_container &demand)
 

Static Public Member Functions

static EMD_algorithm_typeget_algorithm_type (void)
 
static void set_algorithm_type (EMD_algorithm_type algo_type)
 
static EMD_edge_selection_strategyget_edge_selection_strategy (void)
 
static void set_edge_selection_strategy (EMD_edge_selection_strategy edge_selection_strategy)
 
static EMD_recursion_modeget_recursion_mode (void)
 
static void set_recursion_mode (EMD_recursion_mode recursion_mode)
 
static void set_verbose_mode (unsigned verbose)
 
static void set_log (std::ostream &out)
 

Detailed Description

template<class VerticesAccessor, class DistanceFunctor = T_EMD_distance_default<VerticesAccessor>>
class SBL::CADS::T_Earth_mover_distance_with_connectivity_constraints< VerticesAccessor, DistanceFunctor >

Earth mover distance algorithm with connectivity constraints on the input data.

This algorithm uses a recursive strategy for solving the EMD problem while the input is defined with connectivity constraints. In particular, the algorithm is parametrized by three parameters:

  • algorithm type : regular (when updating the candidate edges during the algorithm, all possible candidates are updated) or star (only candidates in the star of the selected source vertex are updated).
  • edge selection strategy : minimal cost (when a candidate edge is selected for driving the flow, the one with the smallest cost is selected) or first found (the first edge that satisfies the constraints for driving the flow is selected)
  • recursion mode : coarse (the algorithm looks straight for the solution with the lowest cost, with possibly an approximated answer) or refined (the algorithm finds the best solution out of all possible solutions, with a much more expansive computation time).

It is designed as a generic functor implementing the earth mover distance algorithm between two data structures. It is able to handle any type of data structure through the parameter VerticesAccessor that provides the base methods for traversing the set of points of the source and the demand. The distance between points of the source and the demand is also editable and is provided as a template parameter.

Template Parameters
VerticesAccessorBase data structure defining the types and accessors related to the input data structures that are required by this algorithm. See classes SBL::CADS::T_Earth_mover_distance_vertices_accessor_vector and SBL::CADS::T_Earth_mover_distance_vertices_accessor_graph for two examples of use, one where the input data structures are simple containers of weighted points, and the other one where the input data structures are graphs connecting those weighted points.
DistanceFunctorFunctor defining the number type used for representing the distance and returning a distance between two input points. By default, the algorithm is instantiated with the class T_EMD_distance_default which returns a null distance for any pair of points.

Member Typedef Documentation

◆ Distance

typedef DistanceFunctor Distance

◆ FT_flow_cost

typedef Distance::FT FT_flow_cost

◆ Self

typedef T_Earth_mover_distance_with_connectivity_constraints<VerticesAccessor, DistanceFunctor> Self

◆ Transportation_plan

◆ Vertex_rep

typedef VerticesAccessor::Vertex_rep Vertex_rep

◆ Vertices_container

typedef VerticesAccessor::Vertices_container Vertices_container

Constructor & Destructor Documentation

◆ T_Earth_mover_distance_with_connectivity_constraints()

Member Function Documentation

◆ get_algorithm_type()

EMD_algorithm_type & get_algorithm_type ( void  )
inlinestatic

◆ get_edge_selection_strategy()

EMD_edge_selection_strategy & get_edge_selection_strategy ( void  )
inlinestatic

◆ get_recursion_mode()

EMD_recursion_mode & get_recursion_mode ( void  )
inlinestatic

◆ operator()()

T_Earth_mover_distance_with_connectivity_constraints< VerticesAccessor, DistanceFunctor >::Transportation_plan operator() ( Vertices_container source,
Vertices_container demand 
)
inline

◆ set_algorithm_type()

void set_algorithm_type ( EMD_algorithm_type  algo_type)
inlinestatic

◆ set_edge_selection_strategy()

void set_edge_selection_strategy ( EMD_edge_selection_strategy  edge_selection_strategy)
inlinestatic

◆ set_log()

void set_log ( std::ostream &  out)
inlinestatic

◆ set_max_cost()

void set_max_cost ( const FT_flow_cost max_cost)
inline

◆ set_recursion_mode()

void set_recursion_mode ( EMD_recursion_mode  recursion_mode)
inlinestatic

◆ set_verbose_mode()

void set_verbose_mode ( unsigned  verbose)
inlinestatic