test/dijkstra_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Sat, 12 Jul 2008 09:45:11 +0100
changeset 205 436fe75092b7
parent 170 91fb4372688f
child 209 765619b7cbb2
permissions -rw-r--r--
Merge
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     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.
    12  *
    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
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <lemon/concepts/digraph.h>
    20 #include <lemon/smart_graph.h>
    21 #include <lemon/list_graph.h>
    22 #include <lemon/graph_utils.h>
    23 #include <lemon/dijkstra.h>
    24 #include <lemon/path.h>
    25 
    26 #include "graph_test.h"
    27 #include "test_tools.h"
    28 
    29 using namespace lemon;
    30 
    31 void checkDijkstraCompile() 
    32 {
    33   typedef int VType;
    34   typedef concepts::Digraph Digraph;
    35   typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
    36   typedef Dijkstra<Digraph, LengthMap> DType;
    37   
    38   Digraph G;
    39   Digraph::Node n;
    40   Digraph::Arc e;
    41   VType l;
    42   bool b;
    43   DType::DistMap d(G);
    44   DType::PredMap p(G);
    45   //  DType::PredNodeMap pn(G);
    46   LengthMap length;
    47 
    48   DType dijkstra_test(G,length);
    49 
    50   dijkstra_test.run(n);
    51 
    52   l  = dijkstra_test.dist(n);
    53   e  = dijkstra_test.predArc(n);
    54   n  = dijkstra_test.predNode(n);
    55   d  = dijkstra_test.distMap();
    56   p  = dijkstra_test.predMap();
    57   //  pn = dijkstra_test.predNodeMap();
    58   b  = dijkstra_test.reached(n);
    59 
    60   Path<Digraph> pp = dijkstra_test.path(n);
    61 }
    62 
    63 void checkDijkstraFunctionCompile() 
    64 {
    65   typedef int VType;
    66   typedef concepts::Digraph Digraph;
    67   typedef Digraph::Arc Arc;
    68   typedef Digraph::Node Node;
    69   typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
    70    
    71   Digraph g;
    72   dijkstra(g,LengthMap(),Node()).run();
    73   dijkstra(g,LengthMap()).source(Node()).run();
    74   dijkstra(g,LengthMap())
    75     .predMap(concepts::WriteMap<Node,Arc>())
    76     .distMap(concepts::WriteMap<Node,VType>())
    77     .run(Node());
    78 }
    79 
    80 template <class Digraph>
    81 void checkDijkstra() {    
    82   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    83   typedef typename Digraph::template ArcMap<int> LengthMap;
    84 
    85   Digraph G;
    86   Node s, t;
    87   LengthMap length(G);
    88   PetStruct<Digraph> ps = addPetersen(G, 5);
    89    
    90   for(int i=0;i<5;i++) {
    91     length[ps.outcir[i]]=4;
    92     length[ps.incir[i]]=1;
    93     length[ps.chords[i]]=10;
    94   }
    95   s=ps.outer[0];
    96   t=ps.inner[1];
    97   
    98   Dijkstra<Digraph, LengthMap> 
    99 	dijkstra_test(G, length);
   100   dijkstra_test.run(s);
   101   
   102   check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
   103 
   104   Path<Digraph> p = dijkstra_test.path(t);
   105   check(p.length()==4,"getPath() found a wrong path.");
   106   check(checkPath(G, p),"path() found a wrong path.");
   107   check(pathSource(G, p) == s,"path() found a wrong path.");
   108   check(pathTarget(G, p) == t,"path() found a wrong path.");
   109   
   110   for(ArcIt e(G); e!=INVALID; ++e) {
   111     Node u=G.source(e);
   112     Node v=G.target(e);
   113     check( !dijkstra_test.reached(u) || (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]),
   114 	   "dist(target)-dist(source)-arc_length= " << dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
   115   }
   116 
   117   for(NodeIt v(G); v!=INVALID; ++v){
   118     check(dijkstra_test.reached(v),"Each node should be reached.");
   119     if ( dijkstra_test.predArc(v)!=INVALID ) {
   120       Arc e=dijkstra_test.predArc(v);
   121       Node u=G.source(e);
   122       check(u==dijkstra_test.predNode(v),"Wrong tree.");
   123       check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
   124 	    "Wrong distance! Difference: " << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]));
   125     }
   126   }
   127   
   128   {
   129     NullMap<Node,Arc> myPredMap;
   130     dijkstra(G,length).predMap(myPredMap).run(s);
   131   }
   132 }
   133 
   134 int main() {
   135   checkDijkstra<ListDigraph>();
   136   checkDijkstra<SmartDigraph>();
   137   return 0;
   138 }