FGNG - Fast Growing Neural Gas

--------------------------------------------

Authors:
- Carlos Augusto Teixeira Mendes (cmendes@k2sistemas.com.br)
- Marcelo Gattass (mgattass@inf.puc-rio.br)
- Helio Lopes (lopes@inf.puc-rio.br)

The present files consists in the implementation of the FGNG algorithm 
described in detail in the paper "FGNG: a Fast multi-dimensional
Growing Neural Gas implementation"

This software is distributed under the terms of the MIT license,
reproduced on the LICENSE.txt file.


--------------------------------------------
File structure
--------------------------------------------

- bin  : Binary files for testing the algorithms on windows platform.
- gng  : Source files for the simple GNG implementation
- fgng : Source files for the FGNG implementation
- fgngFib : Source files for the FGNG implementation using a Fibonacci heap 
            instead of a simple heap
- samples : Some images that can be used as probability maps for 2D test cases

--------------------------------------------
Running the test cases
--------------------------------------------

The bin directory contains executable files for 2D test cases for the simple 
GNG implementation (gng_test.exe), the FGNG implementation (fgng_test.exe)
and for the FGNG implementation using a Fibonacci heap (fgngFib_test.exe).

For running the programs, open a command prompt and type:

c:> bin\fgng_test samples\test.png 1000

where 

- bin\fgng_test is the implementation to be tested. Change it for gng_test
  to run the original GNG reference implementation or to fgngFib_test to 
  test the FGNG implementation with a Fibonacci heap.

- samples\test.png is the image file used as a base for the probability 
  distribution function.  Every non white pixel in the image will be 
  uniformally sampled by the function.  The tests in the paper where done 
  with the uniform image samples\big.png file

- 1000 is the number of nodes that will be generated by the algorithm.

If you run the program without parameters, a help text will be displayed
with all the available command line options.
  
While running, the program will display the time taken to add each 1000 nodes
to the graph, followed by the complete execution time of the GNG/FGNG
algorithm and will create two additional files to display an image and a
text file representation of the GNG graph. If your input file is called
test.png the two created files will be called test_graph.png and 
test_result.txt

To run k-dimensional test cases or to change other GNG/FGNG parameters,
it will be necessary to make simple changes in the source code and recompile
the programs. See below.

--------------------------------------------
Compiling the code
--------------------------------------------

To compile the code, an installation of the Qt library will be necessary.
The code was tested with versions 4.5.3 and 4.8.1, but any newer version 
shouldn't present a problem.  You can download the GPL version of the 
library from http://qt-project.org/.

The Qt library is used for support routines to read and write image files,
draw graphs and other similar tasks.  The Gng/FGng implementation classes
use Qt only for creating vectors and lists. If necessary, its replacement 
by STL containers should be an easy task.

Once the Qt library is installed, compiling the GNG/FGNG implementations
should be straightforward.  Just open a Qt command line console and run
the vc_build bat file to create suitable Visual studio projects. Then
open the provided test.sln file and compile the project.

Each of the three implementations has independent codes.  To change 
GNG/FGNG parameters, change the defines on top of the gng.cpp, fgng.cpp
or fgngFib.cpp files.  To change the number of dimensions, change the 
FGNG_DIMENSION definition on the top of the gng.h, fgng.h or fgngFib.h 
header files.