Structural Bioinformatics Library
Template C++ / Python API for developping structural bioinformatics applications.

Authors: F. Cazals and T. Dreyfus and C. Roth
This package provides operations to build a nearest neighbors graph (NN graph for short), basically a Boost Graph from the BGL library, with weights on the edges representing distances.
The NN graph may be defined by linking all vertices to a subset of its neighbors, k closest or in a given range r. All proimity queries rely on an underlying spatial search engine, as explained in the package Spatial_search .
Consider a Boost Graph G from the BGL library such that each vertex is associated to a point. To be precise, it is assumed that the bundle property of the vertex is a point. The package provides a concept of NearestNeighborsGraphBuilder for building such a graph from a range of points [begin,end) and a spatial search engine (search_engine).
In the following, we assume that one is given a search engine either returning the neighbors of a sample within a distance range, or returning the k nearest neighbors of a sample. Three operations are defined:
NearestNeighborsGraphBuilder(begin, end, G);
NearestNeighborsGraphBuilder(u, search_engine, G);
NearestNeighborsGraphBuilder(search_engine, G);
The package provides two models of builders :
This package provides the module SBL::Modules::T_Nearest_neighbors_graph_builder_module< ModuleTraits > to build a NNG from an input set of points. The template parameter ModuleTraits must define three types :
The main options of the module T_Nearest_neighbors_graph_builder_module are:
–numneighbors
int: Target number of neighbors for each vertex.
–distancerange
int: Distance range specification.
–nngsym
bool: Symmetric NNG ie connects two vertices iff they are mutual nearest neighbors.
–nngconnected
int: Attempt connecting the NNG by iteratively increasing the number of neighbors; halt if NNG is connected, or if the prescribed num of neighbors is reached.
–nngfile
int: Skip calculations by loading the NNG from a file.
This example shows how to build the NNG of 2D points built on 100x100 grid, setting four neighbors per point.
This example performs the same task as previous but with a NNG able to store the distances between pairs of points linked bya nedge in he NNG.