**A collection of graph analysis and drawing algorithms**

*Galaxy layout of tree82inc.*

## History

I began working on graphcx as a project on genetic algorithms at the University of Limerick in 2016. The mandatory implementation was largely extended with a flexible OpenGL based visualization module and bunch of interesting algorithms.

The propably most interesting part is an implementation of the *Sampled Spectral
Distance Embedding* algorithm, which was presented by Ã‡ivril, Magdon-Ismail
and Bocek-Rivele at the 14th International Symposium on Graph Drawing, Karlsruhe, 2006.
http://dx.doi.org/10.1007/978-3-540-70904-6_5

The euclidean distances between vertices in a SSDE layout approximate the underlying graph-theoretical distances. An obvious application is to combine SSDE on a global scale with a further local optimizer (e.g. a force-directed algorithm) to speed up the drawing process and circumvent bad local energy minima.

## About the Project

- Written in Java, depends on la4j and jogl.
- Build system / dependency management: gradle.
- Source: GitHub

## Functionality & Algorithms

- Genetic optimization by simulated annealing:
- Grid or circular layout
- \(\sum\limits_i ||e_i||_2\) or #EdgeIntersections as fitness criteria.

- Galaxy: A straight-forward
*force directed*implementation. The name is due to the typical shape this algorithm produces. - Fruchterman-Reingold algorithm.
- Dijkstra shortest-path.
- General graph handling, representation and conversion.
- OpenGL based visualization which nicely depicts optimization progress.

## Todo

- Add rudimentary interface to avoid recompiling b/c of parameter changes.
- Port OpenGL to Vulcan just for fun and out of interest.
- Add more algorithms.

## Sample Layouts:

*Simulated annealing grid layout of tree82inc, using $\sum\limits_i ||e_i||_2$ as a fitness criterion.*

*SSDE layout of tree82inc.*

*Grid layout of matrix1inc, using $\sum\limits_i ||e_i||_2$ as a fitness criterion.*

*Galaxy layout of originalinc.*