Several changes. \n If new map is added to mapstorage it emits signal with the name of the new map. This was important, because from now on not only tha mapwin should be updated. \n Furthermore algobox gets a pointer to mapstorage instead of only the mapnames from it. This is important because without it it would be complicated to pass all of the required maps to algobox.
2 * test/dijkstra_test.cc - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #include "test_tools.h"
18 #include <lemon/smart_graph.h>
19 #include <lemon/dijkstra.h>
20 #include <lemon/path.h>
21 #include <lemon/maps.h>
22 #include <lemon/concept/graph.h>
23 #include <lemon/concept/maps.h>
24 using namespace lemon;
26 const int PET_SIZE =5;
29 void check_Dijkstra_BinHeap_Compile()
32 typedef concept::StaticGraph Graph;
34 typedef Graph::Edge Edge;
35 typedef Graph::Node Node;
36 typedef Graph::EdgeIt EdgeIt;
37 typedef Graph::NodeIt NodeIt;
38 typedef concept::ReadMap<Edge,VType> LengthMap;
40 typedef Dijkstra<Graph, LengthMap> DType;
49 // DType::PredNodeMap pn(G);
52 DType dijkstra_test(G,cap);
56 l = dijkstra_test.dist(n);
57 e = dijkstra_test.predEdge(n);
58 n = dijkstra_test.predNode(n);
59 d = dijkstra_test.distMap();
60 p = dijkstra_test.predMap();
61 // pn = dijkstra_test.predNodeMap();
62 b = dijkstra_test.reached(n);
65 dijkstra_test.getPath(pp,n);
68 void check_Dijkstra_Function_Compile()
71 typedef concept::StaticGraph Graph;
73 typedef Graph::Edge Edge;
74 typedef Graph::Node Node;
75 typedef Graph::EdgeIt EdgeIt;
76 typedef Graph::NodeIt NodeIt;
77 typedef concept::ReadMap<Edge,VType> LengthMap;
79 dijkstra(Graph(),LengthMap(),Node()).run();
80 dijkstra(Graph(),LengthMap()).source(Node()).run();
81 dijkstra(Graph(),LengthMap())
82 .predMap(concept::WriteMap<Node,Edge>())
83 .distMap(concept::WriteMap<Node,VType>())
92 typedef SmartGraph Graph;
94 typedef Graph::Edge Edge;
95 typedef Graph::Node Node;
96 typedef Graph::EdgeIt EdgeIt;
97 typedef Graph::NodeIt NodeIt;
98 typedef Graph::EdgeMap<int> LengthMap;
103 PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
105 for(int i=0;i<PET_SIZE;i++) {
108 cap[ps.chords[i]]=10;
113 Dijkstra<Graph, LengthMap>
114 dijkstra_test(G, cap);
115 dijkstra_test.run(s);
117 check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
121 check(dijkstra_test.getPath(p,t),"getPath() failed to set the path.");
122 check(p.length()==4,"getPath() found a wrong path.");
125 for(EdgeIt e(G); e!=INVALID; ++e) {
128 check( !dijkstra_test.reached(u) ||
129 (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap[e]),
130 "dist(target)-dist(source)- edge_length= "
131 << dijkstra_test.dist(v) - dijkstra_test.dist(u)
135 ///\bug This works only for integer lengths
136 for(NodeIt v(G); v!=INVALID; ++v){
137 check(dijkstra_test.reached(v),"Each node should be reached.");
138 if ( dijkstra_test.predEdge(v)!=INVALID ) {
139 Edge e=dijkstra_test.predEdge(v);
141 check(u==dijkstra_test.predNode(v),"Wrong tree.");
142 check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e],
143 "Wrong distance! Difference: "
144 << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)
151 NullMap<Node,Edge> myPredMap;
152 dijkstra(G,cap).predMap(myPredMap).run(s);