test/dijkstra_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Mon, 14 Jul 2008 09:37:51 +0100
changeset 213 56579d12575b
parent 209 765619b7cbb2
child 220 a5d8c039f218
permissions -rw-r--r--
Merge
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     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) ||
   114            (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]),
   115            "dist(target)-dist(source)-arc_length= " <<
   116            dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
   117   }
   118 
   119   for(NodeIt v(G); v!=INVALID; ++v){
   120     check(dijkstra_test.reached(v),"Each node should be reached.");
   121     if ( dijkstra_test.predArc(v)!=INVALID ) {
   122       Arc e=dijkstra_test.predArc(v);
   123       Node u=G.source(e);
   124       check(u==dijkstra_test.predNode(v),"Wrong tree.");
   125       check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
   126             "Wrong distance! Difference: " <<
   127             std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
   128     }
   129   }
   130 
   131   {
   132     NullMap<Node,Arc> myPredMap;
   133     dijkstra(G,length).predMap(myPredMap).run(s);
   134   }
   135 }
   136 
   137 int main() {
   138   checkDijkstra<ListDigraph>();
   139   checkDijkstra<SmartDigraph>();
   140   return 0;
   141 }