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.

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. You can play around with the algorithms using the Graph Shell program. You can also see the use of these algorithms in the Hypermetro project, where they are utilized to find the optimal route.

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.

Small Graph Sample

        def graph = Graph.of([
                A: [B: 7, C: 2],
                B: [A: 3, C: 5],
                C: [A: 1, B: 3]
        ])

Medium Graph Sample

        def graph = Graph.of([
                A: [B: 5],
                B: [A: 5, C: 10],
                C: [B: 20, D: 5],
                D: [E: 5],
                E: [B: 5]
        ])

Complex Graph Sample

        def graph = Graph.of([
                A: [B: 5, H: 2],
                B: [A: 5, C: 7],
                C: [B: 7, D: 3, G: 4],
                D: [C: 20, E: 4],
                E: [F: 5],
                F: [G: 6],
                G: [C: 4],
                H: [G: 3]
        ])