Repository files navigation

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. Youcan also see thespecifications generated with the spock-reports.

To demonstrate the work of search algorithms, I made a small console program 'Graph Shell'. The programallows you to selectone of three build-in graph samples and search for a path using two algorithms. The sourcecode of the program is located ingraph-shell module.

These algorithms used in theHypermetro project, where they areutilized to find the optimal route in the metro schema.

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

In the following Java code we create a graph structure with eight nodes. WeuseCharacter class for vertexidentification andInteger for thedistance. You can see the graphic representation of the schemehere.

vargraph =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.

varfastest =newDijkstrasAlgorithm<Character>();varshortest =newBreadthFirstSearch<Character>();

Now we can search for the route.

varsource ='D';vartarget ='C';varrouteOne =shortest.findPath(graph,source,target);varrouteTwo =fastest.findPath(graph,source,target);

As result, you get a list with the path.

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

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

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

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

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