Port dijkstra_test.cc from SVN -r3499
authorPeter Kovacs <kpeter@inf.elte.hu>
Sun, 15 Jun 2008 22:03:33 +0200
changeset 17091fb4372688f
parent 169 5b507a86ad72
child 171 02f4d5d9bfd7
Port dijkstra_test.cc from SVN -r3499
test/CMakeLists.txt
test/Makefile.am
test/dijkstra_test.cc
     1.1 --- a/test/CMakeLists.txt	Sun Jun 15 09:19:53 2008 +0200
     1.2 +++ b/test/CMakeLists.txt	Sun Jun 15 22:03:33 2008 +0200
     1.3 @@ -7,6 +7,7 @@
     1.4    counter_test
     1.5    dfs_test
     1.6    digraph_test
     1.7 +  dijkstra_test
     1.8    dim_test
     1.9    error_test
    1.10    graph_test
     2.1 --- a/test/Makefile.am	Sun Jun 15 09:19:53 2008 +0200
     2.2 +++ b/test/Makefile.am	Sun Jun 15 22:03:33 2008 +0200
     2.3 @@ -13,6 +13,7 @@
     2.4          test/counter_test \
     2.5  	test/dfs_test \
     2.6  	test/digraph_test \
     2.7 +	test/dijkstra_test \
     2.8          test/dim_test \
     2.9  	test/error_test \
    2.10  	test/graph_test \
    2.11 @@ -33,6 +34,7 @@
    2.12  test_counter_test_SOURCES = test/counter_test.cc
    2.13  test_dfs_test_SOURCES = test/dfs_test.cc
    2.14  test_digraph_test_SOURCES = test/digraph_test.cc
    2.15 +test_dijkstra_test_SOURCES = test/dijkstra_test.cc
    2.16  test_dim_test_SOURCES = test/dim_test.cc
    2.17  test_error_test_SOURCES = test/error_test.cc
    2.18  test_graph_test_SOURCES = test/graph_test.cc
     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/test/dijkstra_test.cc	Sun Jun 15 22:03:33 2008 +0200
     3.3 @@ -0,0 +1,140 @@
     3.4 +/* -*- C++ -*-
     3.5 + *
     3.6 + * This file is a part of LEMON, a generic C++ optimization library
     3.7 + *
     3.8 + * Copyright (C) 2003-2008
     3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    3.11 + *
    3.12 + * Permission to use, modify and distribute this software is granted
    3.13 + * provided that this copyright notice appears in all copies. For
    3.14 + * precise terms see the accompanying LICENSE file.
    3.15 + *
    3.16 + * This software is provided "AS IS" with no warranty of any kind,
    3.17 + * express or implied, and with no claim as to its suitability for any
    3.18 + * purpose.
    3.19 + *
    3.20 + */
    3.21 +
    3.22 +///\file
    3.23 +///\brief Test cases for Dijkstra algorithm.
    3.24 +
    3.25 +#include <lemon/concepts/digraph.h>
    3.26 +#include <lemon/smart_graph.h>
    3.27 +#include <lemon/list_graph.h>
    3.28 +#include <lemon/graph_utils.h>
    3.29 +#include <lemon/dijkstra.h>
    3.30 +#include <lemon/path.h>
    3.31 +
    3.32 +#include "test_tools.h"
    3.33 +
    3.34 +using namespace lemon;
    3.35 +
    3.36 +void checkDijkstraCompile() 
    3.37 +{
    3.38 +  typedef int VType;
    3.39 +  typedef concepts::Digraph Digraph;
    3.40 +  typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
    3.41 +  typedef Dijkstra<Digraph, LengthMap> DType;
    3.42 +  
    3.43 +  Digraph G;
    3.44 +  Digraph::Node n;
    3.45 +  Digraph::Arc e;
    3.46 +  VType l;
    3.47 +  bool b;
    3.48 +  DType::DistMap d(G);
    3.49 +  DType::PredMap p(G);
    3.50 +  //  DType::PredNodeMap pn(G);
    3.51 +  LengthMap length;
    3.52 +
    3.53 +  DType dijkstra_test(G,length);
    3.54 +
    3.55 +  dijkstra_test.run(n);
    3.56 +
    3.57 +  l  = dijkstra_test.dist(n);
    3.58 +  e  = dijkstra_test.predArc(n);
    3.59 +  n  = dijkstra_test.predNode(n);
    3.60 +  d  = dijkstra_test.distMap();
    3.61 +  p  = dijkstra_test.predMap();
    3.62 +  //  pn = dijkstra_test.predNodeMap();
    3.63 +  b  = dijkstra_test.reached(n);
    3.64 +
    3.65 +  Path<Digraph> pp = dijkstra_test.path(n);
    3.66 +}
    3.67 +
    3.68 +void checkDijkstraFunctionCompile() 
    3.69 +{
    3.70 +  typedef int VType;
    3.71 +  typedef concepts::Digraph Digraph;
    3.72 +  typedef Digraph::Arc Arc;
    3.73 +  typedef Digraph::Node Node;
    3.74 +  typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
    3.75 +   
    3.76 +  Digraph g;
    3.77 +  dijkstra(g,LengthMap(),Node()).run();
    3.78 +  dijkstra(g,LengthMap()).source(Node()).run();
    3.79 +  dijkstra(g,LengthMap())
    3.80 +    .predMap(concepts::WriteMap<Node,Arc>())
    3.81 +    .distMap(concepts::WriteMap<Node,VType>())
    3.82 +    .run(Node());
    3.83 +}
    3.84 +
    3.85 +template <class Digraph>
    3.86 +void checkDijkstra() {    
    3.87 +  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    3.88 +  typedef typename Digraph::template ArcMap<int> LengthMap;
    3.89 +
    3.90 +  Digraph G;
    3.91 +  Node s, t;
    3.92 +  LengthMap length(G);
    3.93 +  PetStruct<Digraph> ps = addPetersen(G, 5);
    3.94 +   
    3.95 +  for(int i=0;i<5;i++) {
    3.96 +    length[ps.outcir[i]]=4;
    3.97 +    length[ps.incir[i]]=1;
    3.98 +    length[ps.chords[i]]=10;
    3.99 +  }
   3.100 +  s=ps.outer[0];
   3.101 +  t=ps.inner[1];
   3.102 +  
   3.103 +  Dijkstra<Digraph, LengthMap> 
   3.104 +	dijkstra_test(G, length);
   3.105 +  dijkstra_test.run(s);
   3.106 +  
   3.107 +  check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
   3.108 +
   3.109 +  Path<Digraph> p = dijkstra_test.path(t);
   3.110 +  check(p.length()==4,"getPath() found a wrong path.");
   3.111 +  check(checkPath(G, p),"path() found a wrong path.");
   3.112 +  check(pathSource(G, p) == s,"path() found a wrong path.");
   3.113 +  check(pathTarget(G, p) == t,"path() found a wrong path.");
   3.114 +  
   3.115 +  for(ArcIt e(G); e!=INVALID; ++e) {
   3.116 +    Node u=G.source(e);
   3.117 +    Node v=G.target(e);
   3.118 +    check( !dijkstra_test.reached(u) || (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]),
   3.119 +	   "dist(target)-dist(source)-arc_length= " << dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
   3.120 +  }
   3.121 +
   3.122 +  for(NodeIt v(G); v!=INVALID; ++v){
   3.123 +    check(dijkstra_test.reached(v),"Each node should be reached.");
   3.124 +    if ( dijkstra_test.predArc(v)!=INVALID ) {
   3.125 +      Arc e=dijkstra_test.predArc(v);
   3.126 +      Node u=G.source(e);
   3.127 +      check(u==dijkstra_test.predNode(v),"Wrong tree.");
   3.128 +      check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
   3.129 +	    "Wrong distance! Difference: " << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]));
   3.130 +    }
   3.131 +  }
   3.132 +  
   3.133 +  {
   3.134 +    NullMap<Node,Arc> myPredMap;
   3.135 +    dijkstra(G,length).predMap(myPredMap).run(s);
   3.136 +  }
   3.137 +}
   3.138 +
   3.139 +int main() {
   3.140 +  checkDijkstra<ListDigraph>();
   3.141 +  checkDijkstra<SmartDigraph>();
   3.142 +  return 0;
   3.143 +}