What is NGL

NGL (Neighborhood Graph Library) is a lightweight library written in C++ that supports a variety of geometric neighborhood graphs in arbitrary dimensions. Neighborhood graphs include:

Relative neighbor graph
Gabriel graph
beta-Skeleton

News

(20 October 2012) NGL released

Getting NGL

The latest version of NGL can be downloaded from here:

Version 0.1
ngl-beta.tar.gz

Check out also the google project page for code updates and latest versions:
http://code.google.com/p/ngl/

Documentation

More information on experimental results in using neighborhood graphs for analysis and clustering of multi-dimensional data can be found in the following papers:

Carlos D. Correa and Peter Lindstorm, "Locally-Scaled Spectral Clustering using Empty Region Graphs". ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2012 [ PDF ]

Carlos D. Correa and Peter Lindstorm, "Towards Robust Topology of Sparsely Sampled Data". EEE Transactions on Visualization and Computer Graphics (Proceedings Visualization / Information Visualization 2011), vol. 17, no. 12, Dec. 2011. [ PDF ]

Example

The following is an example on how to use NGL. For the full code, refer to the example in binsrc/getNeighborGraph.cpp

    #include "ngl.h"

    int dims = 3; 
    Geometry::init(dims);   // Initialize NGL for 3-dimensional points

    float *pts;
    int n;
    //
    // Allocate memory and populate pts with n 3-dimensional points
    //

    ANNPointSet P(pts, n);  // Initialize Point set using ANN (computes a kd-tree)

    NGLParams params;
    params.iparam0 = KMAX;      // Initialize parameters 
                                // Only computes Gabriel graph from the KMAX nearest
                                // neighbor graph, computed using ANN
    IndexType *indices;
    int numEdges;
    ngl::getGabrielGraph(P, &indices, numEdges, params);   // Get graph

    // Iterate over indices to output neighbor pairs
    for(int i=0;i<numEdges;i++) 
    {
        fprintf(stdout, "%d %d\n", indices[2*i], indices[2*i+1]);
    }

Conditions of use

NGL is distributed under the terms of the BSD License.

If you use this library in scientific work, we kindly ask you that you cite the following reference:

Citation

        Carlos D. Correa and Peter Lindstorm,
        "Towards Robust Topology of Sparsely Sampled Data".
        IEEE Transactions on Visualization and Computer Graphics 17, 12 (December 2011), 1852-1861.

Bibtex

      @article{Correa:2011,
         author = {Correa, Carlos and Lindstrom, Peter},
         title = {Towards Robust Topology of Sparsely Sampled Data},
         journal = {IEEE Transactions on Visualization and Computer Graphics},
         issue_date = {December 2011},
         volume = {17},
         number = {12},
         month = dec,
         year = {2011},
         issn = {1077-2626},
         pages = {1852--1861},
         numpages = {10},
         doi = {10.1109/TVCG.2011.245},
      }

Questions

email :

neighborhood graph library