1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2010
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #include <lemon/concepts/digraph.h>
20 #include <lemon/smart_graph.h>
21 #include <lemon/list_graph.h>
22 #include <lemon/lgf_reader.h>
23 #include <lemon/dijkstra.h>
24 #include <lemon/path.h>
25 #include <lemon/bin_heap.h>
27 #include "graph_test.h"
28 #include "test_tools.h"
30 using namespace lemon;
53 void checkDijkstraCompile()
56 typedef concepts::Digraph Digraph;
57 typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
58 typedef Dijkstra<Digraph, LengthMap> DType;
59 typedef Digraph::Node Node;
60 typedef Digraph::Arc Arc;
72 concepts::ReadMap<Node,bool> nm;
75 DType dijkstra_test(G,length);
76 const DType& const_dijkstra_test = dijkstra_test;
79 dijkstra_test.run(s,t);
82 dijkstra_test.addSource(s);
83 dijkstra_test.addSource(s, 1);
84 n = dijkstra_test.processNextNode();
85 n = const_dijkstra_test.nextNode();
86 b = const_dijkstra_test.emptyQueue();
87 i = const_dijkstra_test.queueSize();
89 dijkstra_test.start();
90 dijkstra_test.start(t);
91 dijkstra_test.start(nm);
93 l = const_dijkstra_test.dist(t);
94 e = const_dijkstra_test.predArc(t);
95 s = const_dijkstra_test.predNode(t);
96 b = const_dijkstra_test.reached(t);
97 b = const_dijkstra_test.processed(t);
98 d = const_dijkstra_test.distMap();
99 p = const_dijkstra_test.predMap();
100 pp = const_dijkstra_test.path(t);
101 l = const_dijkstra_test.currentDist(t);
105 ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
106 ::SetDistMap<concepts::ReadWriteMap<Node,VType> >
107 ::SetStandardProcessedMap
108 ::SetProcessedMap<concepts::WriteMap<Node,bool> >
109 ::SetOperationTraits<DijkstraDefaultOperationTraits<VType> >
110 ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
111 ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
112 ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> >,
113 concepts::ReadWriteMap<Node,int> >
114 ::Create dijkstra_test(G,length);
116 LengthMap length_map;
117 concepts::ReadWriteMap<Node,Arc> pred_map;
118 concepts::ReadWriteMap<Node,VType> dist_map;
119 concepts::WriteMap<Node,bool> processed_map;
120 concepts::ReadWriteMap<Node,int> heap_cross_ref;
121 BinHeap<VType, concepts::ReadWriteMap<Node,int> > heap(heap_cross_ref);
124 .lengthMap(length_map)
127 .processedMap(processed_map)
128 .heap(heap, heap_cross_ref);
130 dijkstra_test.run(s);
131 dijkstra_test.run(s,t);
133 dijkstra_test.addSource(s);
134 dijkstra_test.addSource(s, 1);
135 n = dijkstra_test.processNextNode();
136 n = dijkstra_test.nextNode();
137 b = dijkstra_test.emptyQueue();
138 i = dijkstra_test.queueSize();
140 dijkstra_test.start();
141 dijkstra_test.start(t);
142 dijkstra_test.start(nm);
144 l = dijkstra_test.dist(t);
145 e = dijkstra_test.predArc(t);
146 s = dijkstra_test.predNode(t);
147 b = dijkstra_test.reached(t);
148 b = dijkstra_test.processed(t);
149 pp = dijkstra_test.path(t);
150 l = dijkstra_test.currentDist(t);
155 void checkDijkstraFunctionCompile()
158 typedef concepts::Digraph Digraph;
159 typedef Digraph::Arc Arc;
160 typedef Digraph::Node Node;
161 typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
165 dijkstra(g,LengthMap()).run(Node());
166 b=dijkstra(g,LengthMap()).run(Node(),Node());
167 dijkstra(g,LengthMap())
168 .predMap(concepts::ReadWriteMap<Node,Arc>())
169 .distMap(concepts::ReadWriteMap<Node,VType>())
170 .processedMap(concepts::WriteMap<Node,bool>())
172 b=dijkstra(g,LengthMap())
173 .predMap(concepts::ReadWriteMap<Node,Arc>())
174 .distMap(concepts::ReadWriteMap<Node,VType>())
175 .processedMap(concepts::WriteMap<Node,bool>())
176 .path(concepts::Path<Digraph>())
181 template <class Digraph>
182 void checkDijkstra() {
183 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
184 typedef typename Digraph::template ArcMap<int> LengthMap;
190 std::istringstream input(test_lgf);
191 digraphReader(G, input).
192 arcMap("length", length).
197 Dijkstra<Digraph, LengthMap>
198 dijkstra_test(G, length);
199 dijkstra_test.run(s);
201 check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path.");
203 Path<Digraph> p = dijkstra_test.path(t);
204 check(p.length()==3,"path() found a wrong path.");
205 check(checkPath(G, p),"path() found a wrong path.");
206 check(pathSource(G, p) == s,"path() found a wrong path.");
207 check(pathTarget(G, p) == t,"path() found a wrong path.");
209 for(ArcIt e(G); e!=INVALID; ++e) {
212 check( !dijkstra_test.reached(u) ||
213 (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]),
214 "Wrong output. dist(target)-dist(source)-arc_length=" <<
215 dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
218 for(NodeIt v(G); v!=INVALID; ++v) {
219 if (dijkstra_test.reached(v)) {
220 check(v==s || dijkstra_test.predArc(v)!=INVALID, "Wrong tree.");
221 if (dijkstra_test.predArc(v)!=INVALID ) {
222 Arc e=dijkstra_test.predArc(v);
224 check(u==dijkstra_test.predNode(v),"Wrong tree.");
225 check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
226 "Wrong distance! Difference: " <<
227 std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
233 NullMap<Node,Arc> myPredMap;
234 dijkstra(G,length).predMap(myPredMap).run(s);
239 checkDijkstra<ListDigraph>();
240 checkDijkstra<SmartDigraph>();