- Increased max. number of iteration
- Better tests.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
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 "test_tools.h"
20 #include <lemon/smart_graph.h>
21 #include <lemon/dijkstra.h>
22 #include <lemon/path.h>
23 #include <lemon/maps.h>
24 #include <lemon/concept/graph.h>
25 #include <lemon/concept/maps.h>
26 using namespace lemon;
28 const int PET_SIZE =5;
31 void check_Dijkstra_BinHeap_Compile()
34 typedef concept::StaticGraph Graph;
36 typedef Graph::Edge Edge;
37 typedef Graph::Node Node;
38 typedef Graph::EdgeIt EdgeIt;
39 typedef Graph::NodeIt NodeIt;
40 typedef concept::ReadMap<Edge,VType> LengthMap;
42 typedef Dijkstra<Graph, LengthMap> DType;
51 // DType::PredNodeMap pn(G);
54 DType dijkstra_test(G,cap);
58 l = dijkstra_test.dist(n);
59 e = dijkstra_test.predEdge(n);
60 n = dijkstra_test.predNode(n);
61 d = dijkstra_test.distMap();
62 p = dijkstra_test.predMap();
63 // pn = dijkstra_test.predNodeMap();
64 b = dijkstra_test.reached(n);
67 dijkstra_test.getPath(pp,n);
70 void check_Dijkstra_Function_Compile()
73 typedef concept::StaticGraph Graph;
75 typedef Graph::Edge Edge;
76 typedef Graph::Node Node;
77 typedef Graph::EdgeIt EdgeIt;
78 typedef Graph::NodeIt NodeIt;
79 typedef concept::ReadMap<Edge,VType> LengthMap;
81 dijkstra(Graph(),LengthMap(),Node()).run();
82 dijkstra(Graph(),LengthMap()).source(Node()).run();
83 dijkstra(Graph(),LengthMap())
84 .predMap(concept::WriteMap<Node,Edge>())
85 .distMap(concept::WriteMap<Node,VType>())
94 typedef SmartGraph Graph;
96 typedef Graph::Edge Edge;
97 typedef Graph::Node Node;
98 typedef Graph::EdgeIt EdgeIt;
99 typedef Graph::NodeIt NodeIt;
100 typedef Graph::EdgeMap<int> LengthMap;
105 PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
107 for(int i=0;i<PET_SIZE;i++) {
110 cap[ps.chords[i]]=10;
115 Dijkstra<Graph, LengthMap>
116 dijkstra_test(G, cap);
117 dijkstra_test.run(s);
119 check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
123 check(dijkstra_test.getPath(p,t),"getPath() failed to set the path.");
124 check(p.length()==4,"getPath() found a wrong path.");
127 for(EdgeIt e(G); e!=INVALID; ++e) {
130 check( !dijkstra_test.reached(u) ||
131 (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap[e]),
132 "dist(target)-dist(source)- edge_length= "
133 << dijkstra_test.dist(v) - dijkstra_test.dist(u)
137 ///\bug This works only for integer lengths
138 for(NodeIt v(G); v!=INVALID; ++v){
139 check(dijkstra_test.reached(v),"Each node should be reached.");
140 if ( dijkstra_test.predEdge(v)!=INVALID ) {
141 Edge e=dijkstra_test.predEdge(v);
143 check(u==dijkstra_test.predNode(v),"Wrong tree.");
144 check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e],
145 "Wrong distance! Difference: "
146 << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)
153 NullMap<Node,Edge> myPredMap;
154 dijkstra(G,cap).predMap(myPredMap).run(s);