Java Graph Algorithms Visualizer

Ray Jasson
26/07/2020

📓 Background

This is a dynamic and interactive graph algorithm visualizer written in Java that demonstrates the solution of the following problems:

• Strong Connectivity
• Cycle Detection
• Shortest Path

This visualizer is developed using JavaFX SmartGraph library written by Bruno Silva.

🔓 The visualizer was implemented in Java 8 which includes JavaFX as bundle.

💬 Graph Representation in Java

The data structure for graph is represented using an adjacency map. The adjacency map has a primary and a secondary structure. In the primary structure represented by the hash-based map, the names or IDs of vertices serve as keys and the associated vertices as values. The secondary structure maintains the incidence collection of the edges using two different map references: an Outgoing Edges hash-based map and an Incoming Edges hash-based map. In both hash-based maps, the opposite end vertices serve as the keys and the edges serve as the values.

Schematic Representation of an Adjacency Map

Refer to AdjacencyMapDigraph.java for more details.

💻 Program Execution

The visualizer has 5 functions:

• Strong Connectivity
• Cycle Detection
• Shortest Path
• Add Vertex
• Reset Graph

User Interface of the Graph Algorithms Visualizer

🔽 Strong Connectivity

Tarjan's algorithm is used to determine whether the directed graph is strongly connected by finding the strongly connected components (SCCs) of the graph. The implementation of Tarjan's algorithm is as follows:

• If the graph is strongly connected
  Print the resulting strongly-connected graph
• Else
  Generate random edges between vertices until the graph is strongly connected

Random edges are generated until the graph is strongly connected

Refer to StrongConnectivity.java for more details.

🔽 Cycle Detection

Depth-First Search (DFS) is used to detect the presence of a cycle in the graph. The implementation of DFS cycle detection algorithm is as follows:

• If the graph has a cycle
  Print the resulting cycle and its length
• Else
  Generate random edges between vertices until the graph has a cycle

Random edges are generated until the graph has a cycle

Refer to CycleDetection.java for more details.

🔽 Shortest Path

Dijkstra's algorithm is used to determine the shortest path between two end vertices in the graph. You can select a start vertex and an end vertex of the shortest path by double-clicking the vertices. The selected end vertices are shown in yellow. The implementation of Dijkstra's algorithm is as follows:

• If there is a path between the start vertex and the end vertex
  Print the shortest path between the end vertices and the path cost
• Else
  Generate random edges between vertices until a path is formed between the end vertices

Random edges are generated until the graph has a path between two end vertices

Refer to ShortestPath.java for more details.

🔽 Add Vertex and Reset Graph

• You can add up to maximum 5 additional vertices to the graph for testing and viewing the solution of the algorithms.

An example of adding 2 additional vertices to the graph, and performing strong connectivity algorithm

• You can reset the graph to its default state.

Refer to Main.java for more details.

✒️ References

• Cormen, T. H., Leiserson, C., Rivest, R., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). Cambridge, Massachusetts, United States of America: MIT Press.
• Goodrich, M. T., & Tamassia, R. (2014). Data Structures and Algorithms in Java (6th ed.). New Jersey: John Wiley.
• A generic (Java FX) graph visualization library