Structural Bioinformatics Library
Template C++ / Python API for developping structural bioinformatics applications.
T_Greedy_selection< Arrangement, GetWeightOfArrangement, GetOverlappingArrangements > Class Template Reference

Generic greedy selection algorithm of arrangements of cells. More...

#include <Greedy_selection.hpp>

Detailed Description

template<class Arrangement, class GetWeightOfArrangement, class GetOverlappingArrangements>
class SBL::CADS::T_Greedy_selection< Arrangement, GetWeightOfArrangement, GetOverlappingArrangements >

Generic greedy selection algorithm of arrangements of cells.

Note that the algorithm uses arrangments of cells instead of cells: this is because we do not know for sure what is a cell, but we have to deal in any cases with arrangements.

The algorithm first compute a graph of intersection of the arrangements of cells, allowing to find quickly the changes of weight of the arrangements during the algorithm.

Second it creates a priority queue of the arrangements with respect to their weight, computed from GetWeightOfArrangment. When selecting an arrangement, only the top of the priority queue is inspected: its weight is updated related to the previously selected neighbors, and compared to the next top of the priority queue. If it remains the top, it is the selection and it is added as selected neighbor to its neighbors, otherwise it is reinserted in the priority queue and the next top is inspected.