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

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

Executed features	Passed	Failures	Errors	Skipped	Success rate	Time
4	4	0	0	0	100.0%	0.037 seconds

Breadth First Search Algorithm

Breadth First Search algorithm for finding the shortest paths between nodes in a graph

See:

should find a route for simple graph Return

(0.006 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)

Then:

path == shortest

And:

graph.getDistance(path) == time as double

Examples:

source	target	time	shortest
A	A	0	[A]	OK (0.006 seconds)
A	B	7	[A, B]	OK (0)
B	C	5	[B, C]	OK (0)
C	B	3	[C, B]	OK (0)

4/4 passed

should find a route for complex graph Return

(0)

Given:

def graph = Graph.of([
A: [B: 1],
B: [A: 1, D: 1],
C: [A: 1],
D: [C: 1, E: 1],
E: [F: 1],
F: [D: 1, E: 1]])

When:

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

Then:

path == shortest

And:

graph.getDistance(path) == time as double

And:

time = shortest.size() - 1

Examples:

source	target	shortest	time
A	A	[A]	0	OK (0)
B	B	[B]	0	OK (0)
A	B	[A, B]	1	OK (0)
B	A	[B, A]	1	OK (0)
A	C	[A, B, D, C]	3	OK (0)
C	A	[C, A]	1	OK (0)
E	B	[E, F, D, C, A, B]	5	OK (0)

7/7 passed

should thrown an exception for an empty graph Return

(0)

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

(0)

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 == []