Structural Bioinformatics Library
Template C++ / Python API for developping structural bioinformatics applications.
T_Morse_Smale_Witten_chain_complex_from_NNG_builder< GraphType, MorseFunction, DistanceFunction, StableManifoldTraits > Class Template Reference

Builds the Morse Smale Witten chain complex from a NNG. More...

#include <Morse_Smale_Witten_chain_complex_from_NNG_builder.hpp>


void operator() (const Graph &G, Morse_Smale_Witten_chain_complex &complex) const
void operator() (const Graph &G, Morse_Smale_Witten_chain_complex &complex, Morse_function &function) const

Detailed Description

template<class GraphType, class MorseFunction, class DistanceFunction = T_Distance_default_for_graph<GraphType, typename MorseFunction::FT>, class StableManifoldTraits = T_Stable_manifold_as_list_traits<typename MorseFunction::Point>>
class SBL::GT::T_Morse_Smale_Witten_chain_complex_from_NNG_builder< GraphType, MorseFunction, DistanceFunction, StableManifoldTraits >

Builds the Morse Smale Witten chain complex from a NNG.


  • compute the pseudo gradient graph: create a map from vertices to them selves. For each edge e, let u its highest incident vertex, and v the vertex associated to u in the map: if u == v or if (u,v) has a lower absolute gradient than e, replace v by the other incident vertex of e.
  • we sort the vertices by increasing height, and associates to each vertex the minimum it flows to.
  • run tomato algorithm: when processing the lower star of a vertex, each c.c to map each vertex to its associated cc. If more than one cc, we just check all the different ccs, and map each vertex . minima we associate the minimum merging several ccs, check the minimum
Template Parameters
GraphTypeGraph from which the complex is constructed.
MorseFunctionHeight function returning the height of a vertex of a given graph.