1.1 --- a/src/test/dijkstra_test.cc Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,155 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/test/dijkstra_test.cc - Part of LEMON, a generic C++ optimization library
1.6 - *
1.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 - *
1.10 - * Permission to use, modify and distribute this software is granted
1.11 - * provided that this copyright notice appears in all copies. For
1.12 - * precise terms see the accompanying LICENSE file.
1.13 - *
1.14 - * This software is provided "AS IS" with no warranty of any kind,
1.15 - * express or implied, and with no claim as to its suitability for any
1.16 - * purpose.
1.17 - *
1.18 - */
1.19 -
1.20 -#include "test_tools.h"
1.21 -#include <lemon/smart_graph.h>
1.22 -#include <lemon/dijkstra.h>
1.23 -#include <lemon/path.h>
1.24 -#include <lemon/maps.h>
1.25 -#include <lemon/concept/graph.h>
1.26 -#include <lemon/concept/maps.h>
1.27 -using namespace lemon;
1.28 -
1.29 -const int PET_SIZE =5;
1.30 -
1.31 -
1.32 -void check_Dijkstra_BinHeap_Compile()
1.33 -{
1.34 - typedef int VType;
1.35 - typedef concept::StaticGraph Graph;
1.36 -
1.37 - typedef Graph::Edge Edge;
1.38 - typedef Graph::Node Node;
1.39 - typedef Graph::EdgeIt EdgeIt;
1.40 - typedef Graph::NodeIt NodeIt;
1.41 - typedef concept::ReadMap<Edge,VType> LengthMap;
1.42 -
1.43 - typedef Dijkstra<Graph, LengthMap> DType;
1.44 -
1.45 - Graph G;
1.46 - Node n;
1.47 - Edge e;
1.48 - VType l;
1.49 - bool b;
1.50 - DType::DistMap d(G);
1.51 - DType::PredMap p(G);
1.52 - // DType::PredNodeMap pn(G);
1.53 - LengthMap cap;
1.54 -
1.55 - DType dijkstra_test(G,cap);
1.56 -
1.57 - dijkstra_test.run(n);
1.58 -
1.59 - l = dijkstra_test.dist(n);
1.60 - e = dijkstra_test.pred(n);
1.61 - n = dijkstra_test.predNode(n);
1.62 - d = dijkstra_test.distMap();
1.63 - p = dijkstra_test.predMap();
1.64 - // pn = dijkstra_test.predNodeMap();
1.65 - b = dijkstra_test.reached(n);
1.66 -
1.67 - DirPath<Graph> pp(G);
1.68 - dijkstra_test.getPath(pp,n);
1.69 -}
1.70 -
1.71 -void check_Dijkstra_Function_Compile()
1.72 -{
1.73 - typedef int VType;
1.74 - typedef concept::StaticGraph Graph;
1.75 -
1.76 - typedef Graph::Edge Edge;
1.77 - typedef Graph::Node Node;
1.78 - typedef Graph::EdgeIt EdgeIt;
1.79 - typedef Graph::NodeIt NodeIt;
1.80 - typedef concept::ReadMap<Edge,VType> LengthMap;
1.81 -
1.82 - dijkstra(Graph(),LengthMap(),Node()).run();
1.83 - dijkstra(Graph(),LengthMap()).source(Node()).run();
1.84 - dijkstra(Graph(),LengthMap())
1.85 - .predMap(concept::WriteMap<Node,Edge>())
1.86 - .distMap(concept::WriteMap<Node,VType>())
1.87 - .run(Node());
1.88 -
1.89 -}
1.90 -
1.91 -
1.92 -int main()
1.93 -{
1.94 -
1.95 - typedef SmartGraph Graph;
1.96 -
1.97 - typedef Graph::Edge Edge;
1.98 - typedef Graph::Node Node;
1.99 - typedef Graph::EdgeIt EdgeIt;
1.100 - typedef Graph::NodeIt NodeIt;
1.101 - typedef Graph::EdgeMap<int> LengthMap;
1.102 -
1.103 - Graph G;
1.104 - Node s, t;
1.105 - LengthMap cap(G);
1.106 - PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
1.107 -
1.108 - for(int i=0;i<PET_SIZE;i++) {
1.109 - cap[ps.outcir[i]]=4;
1.110 - cap[ps.incir[i]]=1;
1.111 - cap[ps.chords[i]]=10;
1.112 - }
1.113 - s=ps.outer[0];
1.114 - t=ps.inner[1];
1.115 -
1.116 - Dijkstra<Graph, LengthMap>
1.117 - dijkstra_test(G, cap);
1.118 - dijkstra_test.run(s);
1.119 -
1.120 - check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
1.121 -
1.122 -
1.123 - DirPath<Graph> p(G);
1.124 - check(dijkstra_test.getPath(p,t),"getPath() failed to set the path.");
1.125 - check(p.length()==4,"getPath() found a wrong path.");
1.126 -
1.127 -
1.128 - for(EdgeIt e(G); e!=INVALID; ++e) {
1.129 - Node u=G.source(e);
1.130 - Node v=G.target(e);
1.131 - check( !dijkstra_test.reached(u) ||
1.132 - (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap[e]),
1.133 - "dist(target)-dist(source)- edge_length= "
1.134 - << dijkstra_test.dist(v) - dijkstra_test.dist(u)
1.135 - - cap[e]);
1.136 - }
1.137 -
1.138 - ///\bug This works only for integer lengths
1.139 - for(NodeIt v(G); v!=INVALID; ++v){
1.140 - check(dijkstra_test.reached(v),"Each node should be reached.");
1.141 - if ( dijkstra_test.pred(v)!=INVALID ) {
1.142 - Edge e=dijkstra_test.pred(v);
1.143 - Node u=G.source(e);
1.144 - check(u==dijkstra_test.predNode(v),"Wrong tree.");
1.145 - check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e],
1.146 - "Wrong distance! Difference: "
1.147 - << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)
1.148 - - cap[e]));
1.149 - }
1.150 - }
1.151 -
1.152 -
1.153 - {
1.154 - NullMap<Node,Edge> myPredMap;
1.155 - dijkstra(G,cap).predMap(myPredMap).run(s);
1.156 - }
1.157 - return 0;
1.158 -}