src/test/dijkstra_test.cc
author alpar
Sat, 13 Nov 2004 12:53:28 +0000
changeset 986 e997802b855c
parent 959 c80ef5912903
child 1148 1eea022c7a16
permissions -rw-r--r--
Naming changes:
- head -> target
- tail -> source
     1 /* -*- C++ -*-
     2  * src/test/dijkstra_test.cc - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Combinatorial Optimization Research Group, EGRES).
     6  *
     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.
    10  *
    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
    13  * purpose.
    14  *
    15  */
    16 
    17 #include "test_tools.h"
    18 #include <lemon/smart_graph.h>
    19 #include <lemon/dijkstra.h>
    20 #include <lemon/concept/graph.h>
    21 #include <lemon/concept/maps.h>
    22 using namespace lemon;
    23 
    24 const int PET_SIZE =5;
    25 
    26 
    27 void check_Dijkstra_BinHeap_Compile() 
    28 {
    29   typedef int VType;
    30   typedef concept::StaticGraph Graph;
    31 
    32   typedef Graph::Edge Edge;
    33   typedef Graph::Node Node;
    34   typedef Graph::EdgeIt EdgeIt;
    35   typedef Graph::NodeIt NodeIt;
    36   typedef concept::ReadMap<Edge,VType> LengthMap;
    37  
    38   typedef Dijkstra<Graph, LengthMap> DType;
    39   
    40   Graph G;
    41   Node n;
    42   Edge e;
    43   VType l;
    44   bool b;
    45   DType::DistMap d(G);
    46   DType::PredMap p(G);
    47   DType::PredNodeMap pn(G);
    48   LengthMap cap;
    49 
    50   DType dijkstra_test(G,cap);
    51 
    52   dijkstra_test.run(n);
    53 
    54   l  = dijkstra_test.dist(n);
    55   e  = dijkstra_test.pred(n);
    56   n  = dijkstra_test.predNode(n);
    57   d  = dijkstra_test.distMap();
    58   p  = dijkstra_test.predMap();
    59   pn = dijkstra_test.predNodeMap();
    60   b  = dijkstra_test.reached(n);
    61 
    62 }
    63 
    64 int main()
    65 {
    66     
    67   typedef SmartGraph Graph;
    68 
    69   typedef Graph::Edge Edge;
    70   typedef Graph::Node Node;
    71   typedef Graph::EdgeIt EdgeIt;
    72   typedef Graph::NodeIt NodeIt;
    73   typedef Graph::EdgeMap<int> LengthMap;
    74 
    75   Graph G;
    76   Node s, t;
    77   LengthMap cap(G);
    78   PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
    79    
    80   for(int i=0;i<PET_SIZE;i++) {
    81     cap[ps.outcir[i]]=4;
    82     cap[ps.incir[i]]=1;
    83     cap[ps.chords[i]]=10;
    84   }
    85   s=ps.outer[0];
    86   t=ps.inner[1];
    87   
    88   Dijkstra<Graph, LengthMap> 
    89 	dijkstra_test(G, cap);
    90   dijkstra_test.run(s);
    91   
    92   check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
    93 
    94 
    95   for(EdgeIt e(G); e!=INVALID; ++e) {
    96     Node u=G.source(e);
    97     Node v=G.target(e);
    98     check( !dijkstra_test.reached(u) ||
    99 	   (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap[e]),
   100 	   "dist(target)-dist(source)- edge_length= " 
   101 	   << dijkstra_test.dist(v) - dijkstra_test.dist(u) 
   102 	   - cap[e]);
   103   }
   104 
   105   ///\bug This works only for integer lengths
   106   for(NodeIt v(G); v!=INVALID; ++v){
   107     check(dijkstra_test.reached(v),"Each node should be reached.");
   108     if ( dijkstra_test.pred(v)!=INVALID ) {
   109       Edge e=dijkstra_test.pred(v);
   110       Node u=G.source(e);
   111       check(u==dijkstra_test.predNode(v),"Wrong tree.");
   112       check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e],
   113 	    "Wrong distance! Difference: " 
   114 	    << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u) 
   115 			    - cap[e]));
   116     }
   117   }
   118 }
   119