Mercuriallemon-1.1 / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/dijkstra_test.cc
changeset 209 765619b7cbb2
parent 171 02f4d5d9bfd7
child 210 81cfc04531e8
equal deleted inserted replaced
1:621661e24325 2:ed3507799490 
     1 /* -*- C++ -*-
 
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
 
     2  *
 
     2  *
 
     3  * This file is a part of LEMON, a generic C++ optimization library
 
     3  * This file is a part of LEMON, a generic C++ optimization library.
 
     4  *
 
     4  *
 
     5  * Copyright (C) 2003-2008
 
     5  * Copyright (C) 2003-2008
 
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 
     8  *
 
     8  *
 
    26 #include "graph_test.h"
 
    26 #include "graph_test.h"
 
    27 #include "test_tools.h"
 
    27 #include "test_tools.h"
 
    28 
    28 
    29 using namespace lemon;
 
    29 using namespace lemon;
 
    30 
    30 
    31 void checkDijkstraCompile() 
    31 void checkDijkstraCompile()
 
    32 {
 
    32 {
 
    33   typedef int VType;
 
    33   typedef int VType;
 
    34   typedef concepts::Digraph Digraph;
 
    34   typedef concepts::Digraph Digraph;
 
    35   typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
 
    35   typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
 
    36   typedef Dijkstra<Digraph, LengthMap> DType;
 
    36   typedef Dijkstra<Digraph, LengthMap> DType;
 
    37   
    37 
    38   Digraph G;
 
    38   Digraph G;
 
    39   Digraph::Node n;
 
    39   Digraph::Node n;
 
    40   Digraph::Arc e;
 
    40   Digraph::Arc e;
 
    41   VType l;
 
    41   VType l;
 
    42   bool b;
 
    42   bool b;
 
    58   b  = dijkstra_test.reached(n);
 
    58   b  = dijkstra_test.reached(n);
 
    59 
    59 
    60   Path<Digraph> pp = dijkstra_test.path(n);
 
    60   Path<Digraph> pp = dijkstra_test.path(n);
 
    61 }
 
    61 }
 
    62 
    62 
    63 void checkDijkstraFunctionCompile() 
    63 void checkDijkstraFunctionCompile()
 
    64 {
 
    64 {
 
    65   typedef int VType;
 
    65   typedef int VType;
 
    66   typedef concepts::Digraph Digraph;
 
    66   typedef concepts::Digraph Digraph;
 
    67   typedef Digraph::Arc Arc;
 
    67   typedef Digraph::Arc Arc;
 
    68   typedef Digraph::Node Node;
 
    68   typedef Digraph::Node Node;
 
    69   typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
 
    69   typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
 
    70    
    70 
    71   Digraph g;
 
    71   Digraph g;
 
    72   dijkstra(g,LengthMap(),Node()).run();
 
    72   dijkstra(g,LengthMap(),Node()).run();
 
    73   dijkstra(g,LengthMap()).source(Node()).run();
 
    73   dijkstra(g,LengthMap()).source(Node()).run();
 
    74   dijkstra(g,LengthMap())
 
    74   dijkstra(g,LengthMap())
 
    75     .predMap(concepts::WriteMap<Node,Arc>())
 
    75     .predMap(concepts::WriteMap<Node,Arc>())
 
    76     .distMap(concepts::WriteMap<Node,VType>())
 
    76     .distMap(concepts::WriteMap<Node,VType>())
 
    77     .run(Node());
 
    77     .run(Node());
 
    78 }
 
    78 }
 
    79 
    79 
    80 template <class Digraph>
 
    80 template <class Digraph>
 
    81 void checkDijkstra() {    
    81 void checkDijkstra() {
 
    82   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 
    82   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 
    83   typedef typename Digraph::template ArcMap<int> LengthMap;
 
    83   typedef typename Digraph::template ArcMap<int> LengthMap;
 
    84 
    84 
    85   Digraph G;
 
    85   Digraph G;
 
    86   Node s, t;
 
    86   Node s, t;
 
    87   LengthMap length(G);
 
    87   LengthMap length(G);
 
    88   PetStruct<Digraph> ps = addPetersen(G, 5);
 
    88   PetStruct<Digraph> ps = addPetersen(G, 5);
 
    89    
    89 
    90   for(int i=0;i<5;i++) {
 
    90   for(int i=0;i<5;i++) {
 
    91     length[ps.outcir[i]]=4;
 
    91     length[ps.outcir[i]]=4;
 
    92     length[ps.incir[i]]=1;
 
    92     length[ps.incir[i]]=1;
 
    93     length[ps.chords[i]]=10;
 
    93     length[ps.chords[i]]=10;
 
    94   }
 
    94   }
 
    95   s=ps.outer[0];
 
    95   s=ps.outer[0];
 
    96   t=ps.inner[1];
 
    96   t=ps.inner[1];
 
    97   
    97 
    98   Dijkstra<Digraph, LengthMap> 
    98   Dijkstra<Digraph, LengthMap>
 
    99 	dijkstra_test(G, length);
 
    99         dijkstra_test(G, length);
 
   100   dijkstra_test.run(s);
 
   100   dijkstra_test.run(s);
 
   101   
   101 
   102   check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
 
   102   check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
 
   103 
   103 
   104   Path<Digraph> p = dijkstra_test.path(t);
 
   104   Path<Digraph> p = dijkstra_test.path(t);
 
   105   check(p.length()==4,"getPath() found a wrong path.");
 
   105   check(p.length()==4,"getPath() found a wrong path.");
 
   106   check(checkPath(G, p),"path() 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.");
 
   107   check(pathSource(G, p) == s,"path() found a wrong path.");
 
   108   check(pathTarget(G, p) == t,"path() found a wrong path.");
 
   108   check(pathTarget(G, p) == t,"path() found a wrong path.");
 
   109   
   109 
   110   for(ArcIt e(G); e!=INVALID; ++e) {
 
   110   for(ArcIt e(G); e!=INVALID; ++e) {
 
   111     Node u=G.source(e);
 
   111     Node u=G.source(e);
 
   112     Node v=G.target(e);
 
   112     Node v=G.target(e);
 
   113     check( !dijkstra_test.reached(u) || (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[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]);
 
   114            "dist(target)-dist(source)-arc_length= " << dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
 
   115   }
 
   115   }
 
   116 
   116 
   117   for(NodeIt v(G); v!=INVALID; ++v){
 
   117   for(NodeIt v(G); v!=INVALID; ++v){
 
   118     check(dijkstra_test.reached(v),"Each node should be reached.");
 
   118     check(dijkstra_test.reached(v),"Each node should be reached.");
 
   119     if ( dijkstra_test.predArc(v)!=INVALID ) {
 
   119     if ( dijkstra_test.predArc(v)!=INVALID ) {
 
   120       Arc e=dijkstra_test.predArc(v);
 
   120       Arc e=dijkstra_test.predArc(v);
 
   121       Node u=G.source(e);
 
   121       Node u=G.source(e);
 
   122       check(u==dijkstra_test.predNode(v),"Wrong tree.");
 
   122       check(u==dijkstra_test.predNode(v),"Wrong tree.");
 
   123       check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
 
   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]));
 
   124             "Wrong distance! Difference: " << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]));
 
   125     }
 
   125     }
 
   126   }
 
   126   }
 
   127   
   127 
   128   {
 
   128   {
 
   129     NullMap<Node,Arc> myPredMap;
 
   129     NullMap<Node,Arc> myPredMap;
 
   130     dijkstra(G,length).predMap(myPredMap).run(s);
 
   130     dijkstra(G,length).predMap(myPredMap).run(s);
 
   131   }
 
   131   }
 
   132 }
 
   132 }
lemon-1.1