alpar@906: /* -*- C++ -*-
ladanyi@1435:  * test/dijkstra_test.cc - Part of LEMON, a generic C++ optimization library
alpar@906:  *
alpar@1164:  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@906:  *
alpar@906:  * Permission to use, modify and distribute this software is granted
alpar@906:  * provided that this copyright notice appears in all copies. For
alpar@906:  * precise terms see the accompanying LICENSE file.
alpar@906:  *
alpar@906:  * This software is provided "AS IS" with no warranty of any kind,
alpar@906:  * express or implied, and with no claim as to its suitability for any
alpar@906:  * purpose.
alpar@906:  *
alpar@906:  */
alpar@906: 
alpar@578: #include "test_tools.h"
alpar@921: #include <lemon/smart_graph.h>
alpar@921: #include <lemon/dijkstra.h>
alpar@1283: #include <lemon/path.h>
alpar@1148: #include <lemon/maps.h>
klao@959: #include <lemon/concept/graph.h>
klao@959: #include <lemon/concept/maps.h>
alpar@921: using namespace lemon;
alpar@568: 
alpar@568: const int PET_SIZE =5;
alpar@568: 
alpar@570: 
alpar@793: void check_Dijkstra_BinHeap_Compile() 
alpar@570: {
alpar@570:   typedef int VType;
klao@959:   typedef concept::StaticGraph Graph;
alpar@570: 
alpar@570:   typedef Graph::Edge Edge;
alpar@570:   typedef Graph::Node Node;
alpar@570:   typedef Graph::EdgeIt EdgeIt;
alpar@570:   typedef Graph::NodeIt NodeIt;
klao@959:   typedef concept::ReadMap<Edge,VType> LengthMap;
alpar@570:  
alpar@570:   typedef Dijkstra<Graph, LengthMap> DType;
alpar@570:   
alpar@570:   Graph G;
alpar@570:   Node n;
alpar@570:   Edge e;
alpar@570:   VType l;
alpar@570:   bool b;
alpar@570:   DType::DistMap d(G);
alpar@570:   DType::PredMap p(G);
alpar@1148:   //  DType::PredNodeMap pn(G);
alpar@793:   LengthMap cap;
alpar@570: 
alpar@570:   DType dijkstra_test(G,cap);
alpar@570: 
alpar@570:   dijkstra_test.run(n);
alpar@570: 
alpar@570:   l  = dijkstra_test.dist(n);
deba@1763:   e  = dijkstra_test.predEdge(n);
alpar@570:   n  = dijkstra_test.predNode(n);
alpar@570:   d  = dijkstra_test.distMap();
alpar@570:   p  = dijkstra_test.predMap();
alpar@1148:   //  pn = dijkstra_test.predNodeMap();
alpar@570:   b  = dijkstra_test.reached(n);
alpar@1283: 
alpar@1283:   DirPath<Graph> pp(G);
alpar@1283:   dijkstra_test.getPath(pp,n);
alpar@570: }
alpar@570: 
alpar@1220: void check_Dijkstra_Function_Compile() 
alpar@1220: {
alpar@1220:   typedef int VType;
alpar@1220:   typedef concept::StaticGraph Graph;
alpar@1220: 
alpar@1220:   typedef Graph::Edge Edge;
alpar@1220:   typedef Graph::Node Node;
alpar@1220:   typedef Graph::EdgeIt EdgeIt;
alpar@1220:   typedef Graph::NodeIt NodeIt;
alpar@1220:   typedef concept::ReadMap<Edge,VType> LengthMap;
alpar@1220:    
alpar@1220:   dijkstra(Graph(),LengthMap(),Node()).run();
alpar@1220:   dijkstra(Graph(),LengthMap()).source(Node()).run();
alpar@1220:   dijkstra(Graph(),LengthMap())
alpar@1220:     .predMap(concept::WriteMap<Node,Edge>())
alpar@1220:     .distMap(concept::WriteMap<Node,VType>())
alpar@1220:     .run(Node());
alpar@1220:   
alpar@1220: }
alpar@1220: 
alpar@1220: 
alpar@568: int main()
alpar@568: {
alpar@568:     
alpar@568:   typedef SmartGraph Graph;
alpar@568: 
alpar@568:   typedef Graph::Edge Edge;
alpar@568:   typedef Graph::Node Node;
alpar@568:   typedef Graph::EdgeIt EdgeIt;
alpar@568:   typedef Graph::NodeIt NodeIt;
alpar@568:   typedef Graph::EdgeMap<int> LengthMap;
alpar@568: 
alpar@568:   Graph G;
alpar@568:   Node s, t;
alpar@568:   LengthMap cap(G);
alpar@568:   PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
alpar@578:    
alpar@568:   for(int i=0;i<PET_SIZE;i++) {
alpar@568:     cap[ps.outcir[i]]=4;
alpar@568:     cap[ps.incir[i]]=1;
alpar@568:     cap[ps.chords[i]]=10;
alpar@568:   }
alpar@568:   s=ps.outer[0];
alpar@568:   t=ps.inner[1];
alpar@568:   
alpar@568:   Dijkstra<Graph, LengthMap> 
alpar@568: 	dijkstra_test(G, cap);
alpar@568:   dijkstra_test.run(s);
alpar@568:   
alpar@568:   check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
alpar@585: 
alpar@585: 
alpar@1283:   DirPath<Graph> p(G);
alpar@1283:   check(dijkstra_test.getPath(p,t),"getPath() failed to set the path.");
alpar@1283:   check(p.length()==4,"getPath() found a wrong path.");
alpar@1283:   
alpar@1283: 
hegyi@776:   for(EdgeIt e(G); e!=INVALID; ++e) {
alpar@986:     Node u=G.source(e);
alpar@986:     Node v=G.target(e);
alpar@585:     check( !dijkstra_test.reached(u) ||
alpar@585: 	   (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap[e]),
alpar@986: 	   "dist(target)-dist(source)- edge_length= " 
alpar@585: 	   << dijkstra_test.dist(v) - dijkstra_test.dist(u) 
alpar@585: 	   - cap[e]);
alpar@585:   }
alpar@585: 
alpar@585:   ///\bug This works only for integer lengths
alpar@780:   for(NodeIt v(G); v!=INVALID; ++v){
alpar@780:     check(dijkstra_test.reached(v),"Each node should be reached.");
deba@1763:     if ( dijkstra_test.predEdge(v)!=INVALID ) {
deba@1763:       Edge e=dijkstra_test.predEdge(v);
alpar@986:       Node u=G.source(e);
alpar@780:       check(u==dijkstra_test.predNode(v),"Wrong tree.");
alpar@585:       check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e],
alpar@780: 	    "Wrong distance! Difference: " 
alpar@585: 	    << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u) 
alpar@585: 			    - cap[e]));
alpar@585:     }
alpar@780:   }
alpar@1148: 
alpar@1148:   
alpar@1148:   {
alpar@1218:     NullMap<Node,Edge> myPredMap;
alpar@1218:     dijkstra(G,cap).predMap(myPredMap).run(s);
alpar@1148:   }
alpar@1148:   return 0;
alpar@568: }