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

Summary:

Created on Sun Oct 16 16:27:44 EEST 2022 by jegors

Executed features	Passed	Failures	Errors	Skipped	Success rate	Time
1	0	1	0	0	0.0%	0.037 seconds

Dijkstra's Algorithm

Dijkstra's algorithm is an algorithm for finding 
the fastest paths between nodes in a graph

See:

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Features:

should find a route for a simple graph
should find a route for a medium graph
should find a route for a complex graph
should thrown NPE for an empty graph
should return an empty path if can't find a route

should find a route for a simple graph Return

(0.016 seconds)

Given:

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

When:

def path = algorithm.findPath(graph, source, target)
def time = graph.getDistance(path)

Then:

path == fastestPath // line 29

time == fastestTime

Examples:

source	target	fastestPath	fastestTime
A	A	[A]	0	OK (0.005 seconds)
B	A	[B, A]	3	OK (0)
A	B	[A, B]	5	FAIL (0.011 seconds)

2/3 passed

The following problems occurred:

[A, B, [A, B], 5]

Condition not satisfied:

path == fastestPath
|    |  |
|    |  [A, B]
|    false
[A, C, B]

should find a route for a medium graph Return

Given:

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

When:

def path = algorithm.findPath(graph, source, target)

Then:

path == fastest

And:

graph.getDistance(path) == time as double

should find a route for a complex graph Return

Given:

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:

def path = algorithm.findPath(graph, source, target)

Then:

path == fastest

And:

graph.getDistance(path) == time as double

should thrown NPE for an empty graph Return

Given:

def graph = Graph.of([:])

When:

algorithm.findPath(graph, 'A', 'B')

Then:

thrown NullPointerException

should return an empty path if can't find a route Return

Given:

a simple graph with no edge between nodes

def graph = Graph.of([A: [:], B: [:]])

When:

def path = algorithm.findPath(graph, 'A', 'B')

Then:

path == []