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:
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.