Graph search algorithms

The project implements an interface for the weighted graph, as well as two algorithms for finding a path in the graph.

There are implementations and tests for two algorithms:

• Breadth-first search
• Dijkstra’s Algorithm

The implementation is written in Java 17. API documentation is available. You can also see the specifications generated with the spock-reports.

Demo. Graph Shell

To demonstrate the work of search algorithms, I made a small console program ‘Graph Shell’. The program allows you to select one of three build-in graph samples and search for a path using two algorithms. The source code of the program is located in graph-shell module.

Usage in other projects

These algorithms used in the Hypermetro project, where they are utilized to find the optimal route in the metro schema.

How to use the algorithms in your program

The first step is to create a graph structure. The Graph interface is generic, so you can use any Java type for vertex and any Number type for distance.

Example

In the following Java code we create a graph structure with eight nodes. We use Character class for vertex identification and Integer for the distance. You can see the graphic representation of the scheme here.

var graph = Graph.of(Map.of(
            'A', Map.of('B', 5, 'H', 2),
            'B', Map.of('A', 5, 'C', 7),
            'C', Map.of('B', 7, 'D', 3, 'G', 4),
            'D', Map.of('C', 20, 'E', 4),
            'E', Map.of('F', 5),
            'F', Map.of('G', 6),
            'G', Map.of('C', 4),
            'H', Map.of('G', 3)
    ));

The second step is creating a search algorithm class. You can choose one of the two algorithms.

Example

var fastest = new DijkstrasAlgorithm<Character>();
var shortest = new BreadthFirstSearch<Character>();

Now we can search for the route.

Example

var source = 'D';
var target = 'C';

var routeOne = shortest.findPath(graph, source, target);
var routeTwo = fastest.findPath(graph, source, target);

As result, you get a list with the path.

routeOne==['D','C']
        routeTwo==['D','E','F','G','C']

Unit Tests

Tests are written in Groove language. For unit testing, the Spock Framework was used. To test the operation of the algorithms, the following sample graphs were created.

Graph Samples

Small Graph Sample

flowchart LR
    A((A))
    B((B))
    C((C))
    A -->|7| B
    A -->|2| C
    B -->|3| A
    B -->|5| C
    C -->|1| A
    C -->|3| B

Medium Graph Sample

flowchart LR
    A --> |5 | B
    B --> |5 | A
    B --> |10| C
    C --> |5 | D
    C --> |20| B
    D --> |5 | E
    E --> |5 | B

Complex Graph Sample

flowchart LR
    A --> |5 | B
    A --> |2 | H
    B --> |5 | A
    B --> |7 | C
    C --> |7 | B
    C --> |3 | D
    C --> |4 | G
    D --> |20| C
    D --> |4 | E
    E --> |5 | F
    G --> |4 | C
    H --> |3 | G