OmniGraph

A multiplatform desktop application that lets you build graphs and visualize a collection of algorithms. Build in JavaFX.

Features Overview

• Interactive graph editor
• Classic algorithms step-by-step visualization
• Graph layout algorithms
• Travelling salesman problem solvers
• Random & preset graph generators
• Graph export & import

How To Run

OmniGraph runs on Windows, Linux and macOS - Java 11+ is required.

Download and run the app with jar file from the latest release,

or clone & run with maven:

git clone https://github.com/Todense/OmniGraph.git
cd OmniGraph
mvn clean javafx:run

Features

Basic algorithms

Step-by-step visualizations for basic algorithms, including:

• DFS
• BFS
• Dijkstra's shortest path algorithm
• A* shortest path algorithm
• Prim's minimum spanning tree algorithm
• Kruskal's minimum spanning tree algorithm
• Hamilton cycle search algorithm

Layout algorithms

Layout algorithms aims to create readable graph drawing by arranging node positions.

Currently, OmniGraph has two force-based layout algorithms:

• Adaptive cooling force-directed layout by Yifan Hu [1]
• D3-Force Layout algorithm [2]

Both algorithms are dynamic, meaning graph can be changed by user while algorithm is running.

For larger graphs, it is best to use Barnes-Hut algorithm which speeds up computations. Also, better layout could be achieved by using multilevel variants which include graph prolongation step between layouts step (see section 5 of [1]).

Travelling salesman problem solvers

Current algorithms for solving TSP are several variants of ant colony optimization technique for TSP based on [3]:

• Ant System
• Ant Colony System
• Ranked Ant System
• Max-Min Ant System

Parameters of solvers can be tweaked while algorithms are running. Options for visualization include moving ants and pheromone levels animations.

Generators

Graph generators include both random graph models and pre-defined collections of graphs (e.g. cycles, grids)

Random generators:

• Erdős–Rényi model
• Barabási–Albert model
• Geometric model
• Randomized geometric model
• Maze generator

Saving & importing graphs

Supported file formats:

• .ogr - OmniGraph custom format (save node positions, node labels, edge weights and colors)
• .tsp - TSPLIB format for the travelling salesman problem (only EUC_2D edge weight type)
• .mtx - Matrix Market format (save structure of a graph)
• .graphml - GraphML format (save node positions)
• .svg - export graph as SVG image

Build with

• Java 11
• OpenJFX
• Maven - dependency management
• Scene Builder - visual layout tool for JavaFX Applications
• MvvmFX - an application framework for implementing the Model-View-ViewModel Pattern for JavaFX
• ControlsFX - custom JavaFX controls
• JFoenix - JavaFX material design library
• Ikonli - icon packs for Java applications
• JUnit 5 - Java testing framework
• CSS

References

[1] Hu, Yifan. (2005). Efficient and High Quality Force-Directed Graph Drawing. Mathematica Journal. 10. 37-71.

[2] M. Bostock. (2011) Force-directed Graph Layout Using Velocity Verlet Integration. https://github.com/d3/d3-force

[3] St, Thomas & Dorigo, Marco. (1999). ACO Algorithms for the Traveling Salesman Problem.