1/** \file
2 * \brief Tests for the A* informed search algorithm.
3 *
4 * \author Tilo Wiedera
5 *
6 * \par License:
7 * This file is part of the Open Graph Drawing Framework (OGDF).
8 *
9 * \par
10 * Copyright (C)<br>
11 * See README.md in the OGDF root directory for details.
12 *
13 * \par
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * Version 2 or 3 as published by the Free Software Foundation;
17 * see the file LICENSE.txt included in the packaging of this file
18 * for details.
19 *
20 * \par
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * \par
27 * You should have received a copy of the GNU General Public
28 * License along with this program; if not, see
29 * http://www.gnu.org/copyleft/gpl.html
30 */
31
32#include <iomanip>
33#include <chrono>
34
35#include <ogdf/basic/graph_generators.h>
36#include <ogdf/graphalg/AStarSearch.h>
37#include <ogdf/graphalg/Dijkstra.h>
38
39#include <testing.h>
40
41template<typename T>
42void validatePath(
43 const node source,
44 const node target,
45 const Graph &graph,
46 const EdgeArray<T> &cost,
47 const NodeArray<edge> &pred,
48 const T expectedCost) {
49
50 T actualCost = 0;
51
52 NodeArray<bool> visited(graph, false);
53
54 for(node v = target; v != source; v = pred[v]->opposite(v)) {
55 AssertThat(visited[v], IsFalse());
56 actualCost += cost[pred[v]];
57 visited[v] = true;
58 }
59
60 AssertThat(actualCost, Equals(expectedCost));
61}
62
63template<typename T>
64void performSingleTest(
65 const Graph &graph,
66 const node source,
67 const node target,
68 const EdgeArray<T> cost,
69 const double maxGap,
70 const bool directed,
71 Dijkstra<T> &dijkstra,
72 AStarSearch<T> &astar,
73 long &ticksDijkstra,
74 long &ticksUninformedAStar,
75 long &ticksAStarHeuristic)
76{
77 NodeArray<T> distance(graph, -1);
78 NodeArray<edge> pred(graph);
79
80 auto start = std::chrono::system_clock::now();
81 dijkstra.call(graph, cost, source, pred, distance, directed);
82 ticksDijkstra += (std::chrono::system_clock::now() - start).count();
83 bool foundPath = pred[target] != nullptr;
84 T opt = distance[target];
85
86 if(foundPath) {
87 validatePath(source, target, graph, cost, pred, distance[target]);
88
89 distance.init(graph, -1);
90 pred.init(graph, nullptr);
91
92 start = std::chrono::system_clock::now();
93 T result = astar.call(graph, cost, source, target, pred, [&](node v) {
94 // utilize distances as returned by Dijkstra for a perfect heuristic
95 return distance[v];
96 });
97 ticksAStarHeuristic += (std::chrono::system_clock::now() - start).count();
98
99 validatePath(source, target, graph, cost, pred, result);
100 AssertThat(pred[target] != nullptr, IsTrue());
101 AssertThat(distance[target], IsLessThan(opt * maxGap + 1));
102 }
103
104 start = std::chrono::system_clock::now();
105 T result = astar.call(graph, cost, source, target, pred);
106 ticksUninformedAStar += (std::chrono::system_clock::now() - start).count();
107
108 AssertThat(pred[target] != nullptr, Equals(foundPath));
109 if(foundPath) {
110 validatePath(source, target, graph, cost, pred, result);
111 AssertThat(distance[target], IsLessThan(opt * maxGap + 1));
112 }
113}
114
115template<typename T>
116void performTests(const bool directed, const double maxGap, const bool pathLike) {
117 const int NUMBER_OF_GRAPHS = 10;
118 const int MIN_NODES = 100;
119 const int MAX_NODES = 200;
120
121 AStarSearch<T> astar(directed, maxGap);
122 Dijkstra<T> dijkstra;
123
124 long ticksDijkstra = 0;
125 long ticksUninformedAStar = 0;
126 long ticksAStarHeuristic = 0;
127
128 for(int i = 0; i < NUMBER_OF_GRAPHS; i++) {
129 Graph graph;
130 EdgeArray<T> cost(graph);
131 node source = nullptr;
132 node target = nullptr;
133 int n = randomNumber(MIN_NODES, MAX_NODES);
134
135 if(pathLike) {
136 completeGraph(graph, n);
137 cost.init(graph, n);
138
139 source = graph.chooseNode();
140 node v = source;
141
142 for(int k = 0; k < n/2 || v == source; k++) {
143 adjEntry adj = v->firstAdj();
144
145 for(int j = randomNumber(0, v->degree()-1); j > 0; j--) {
146 adj = adj->succ();
147 }
148
149 edge e = adj->theEdge();
150 cost[e] = randomNumber(1, 10);
151 v = e->opposite(v);
152 }
153
154 target = v;
155 } else {
156 randomBiconnectedGraph(graph, n, randomNumber(n, (n*(n-1) / 2)));
157
158 for(edge e : graph.edges) {
159 cost[e] = randomNumber(1, graph.numberOfEdges());
160 }
161
162 source = graph.chooseNode();
163 target = graph.chooseNode([&](node v) { return v != source; });
164 }
165
166 performSingleTest(graph, source, target, cost, maxGap, directed, dijkstra, astar,
167 ticksDijkstra, ticksUninformedAStar, ticksAStarHeuristic);
168 }
169
170 std::cout << std::endl;
171 std::cout << std::left << " Dijkstra : " << std::right << std::setw(16) << ticksDijkstra << std::endl;
172 std::cout << std::left << " A* uninformed : " << std::right << std::setw(16) << ticksUninformedAStar << std::endl;
173 std::cout << std::left << " A* perfect heuristic : " << std::right << std::setw(16) << ticksAStarHeuristic << std::endl;
174 std::cout << std::left;
175}
176
177template<typename T>
178void registerTests(string typeName) {
179 EpsilonTest et;
180 for(int i = 0; i < 16; i++) {
181 bool pathLike = i % 2;
182 bool directed = (i / 2) % 2;
183 double maxGap = 1 + (i / 4) / (double) 2;
184
185 string title = "yields the same result as Dijkstra";
186 if(!et.equal(maxGap, 1.0)) {
187 title = "approximates the optimal solution with a maxmimum gap of " + to_string(maxGap);
188 }
189
190 title = "[" + typeName + "] " + title;
191
192 title += " on ";
193 title += (directed ? "directed " : "");
194 title += (pathLike ? "path-like" : "biconnected");
195 title += " graphs";
196
197 it(title, [&](){
198 performTests<T>(directed, maxGap, pathLike);
199 });
200 }
201}
202
203go_bandit([](){
204 describe("A* Informed Search Algorithm", [](){
205 registerTests<int>("int");
206 registerTests<double>("double");
207 });
208});
209