Graphcx

A collection of graph analysis and drawing algorithms

tree82-galaxy 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:

tree82-square-edgelength
Simulated annealing grid layout of tree82inc, using $\sum\limits_i ||e_i||_2$ as a fitness criterion.
tree82-ssde
SSDE layout of tree82inc.
matrix1-square-edgelength
Grid layout of matrix1inc, using $\sum\limits_i ||e_i||_2$ as a fitness criterion.
original-galaxy
Galaxy layout of originalinc.

By @Oliver Wiedemann in
Tags :