Report for lv.id.jc.algorithm.graph.SearchAlgorithmsSpec

Summary:

Created on Sun Oct 16 12:33:47 EEST 2022 by jegors

Executed features	Passed	Failures	Errors	Skipped	Success rate	Time
1	1	0	0	0	100.0%	0.005 seconds

Comparison of two algorithms

Issues:

Issue #30

See:

Features:

should find a route for a complex graph

should find a route for a complex graph Return

(0)

Given:

a complex graph with eight nodes

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]
])

When:

we use Breadth First Search algorithm for the first route

def routeOne = bfsAlgorithm.findPath(graph, source, target)

And:

we use Dijkstra's algorithm for the second route

def routeTwo = dijkstras.findPath(graph, source, target)

Then:

the first route is the shortest

routeOne == shortest

And:

the second route is the fastest

routeTwo == fastest

And:

the distance calculated correctly

graph.getDistance(routeOne) == t1 as double
graph.getDistance(routeTwo) == t2 as double

Examples:

source	target	t1	shortest	t2	fastest
A	A	0	[A]	0	[A]	OK (0)
B	B	0	[B]	0	[B]	OK (0)
A	B	5	[A, B]	5	[A, B]	OK (0)
B	A	5	[B, A]	5	[B, A]	OK (0)
A	C	12	[A, B, C]	9	[A, H, G, C]	OK (0)
C	A	12	[C, B, A]	12	[C, B, A]	OK (0)
A	G	5	[A, H, G]	5	[A, H, G]	OK (0)
C	D	3	[C, D]	3	[C, D]	OK (0)
D	C	20	[D, C]	19	[D, E, F, G, C]	OK (0)
B	D	10	[B, C, D]	10	[B, C, D]	OK (0)
D	B	27	[D, C, B]	26	[D, E, F, G, C, B]	OK (0)
D	H	34	[D, C, B, A, H]	33	[D, E, F, G, C, B, A, H]	OK (0)

12/12 passed