Structural Bioinformatics Library
Template C++ / Python API for developping structural bioinformatics applications.
List of all members
T_Earth_mover_distance_with_connectivity_constraints< VerticesAccessor, DistanceFunctor > Class Template Reference
Reference Manuals » Earth_mover_distance

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

#include <Earth_mover_distance_with_connectivity_constraints.hpp>

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.