COIN-OR::LEMON - Graph Library

Changeset 228:b6732e0d38c5 in lemon-1.2 for test/dijkstra_test.cc


Ignore:
Timestamp:
07/21/08 16:30:28 (11 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Children:
229:aebc0161f6e5, 230:af4e8ba94294
Phase:
public
Message:

Reworking graph testing

  • The graph tests check more graph functionality.
  • The petersen graph is too regular, therefore special graphs are used.
  • The graph_test.h contains just general tools to test graphs.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/dijkstra_test.cc

    r220 r228  
    2020#include <lemon/smart_graph.h>
    2121#include <lemon/list_graph.h>
     22#include <lemon/lgf_reader.h>
     23
    2224#include <lemon/dijkstra.h>
    2325#include <lemon/path.h>
     
    2729
    2830using namespace lemon;
     31
     32char test_lgf[] =
     33  "@nodes\n"
     34  "label\n"
     35  "0\n"
     36  "1\n"
     37  "2\n"
     38  "3\n"
     39  "4\n"
     40  "@arcs\n"
     41  "     label length\n"
     42  "0 1  0     1\n"
     43  "1 2  1     1\n"
     44  "2 3  2     1\n"
     45  "0 3  4     5\n"
     46  "0 3  5     10\n"
     47  "0 3  6     7\n"
     48  "4 2  7     1\n"
     49  "@attributes\n"
     50  "source 0\n"
     51  "target 3\n";
    2952
    3053void checkDijkstraCompile()
     
    85108  Node s, t;
    86109  LengthMap length(G);
    87   PetStruct<Digraph> ps = addPetersen(G, 5);
    88110
    89   for(int i=0;i<5;i++) {
    90     length[ps.outcir[i]]=4;
    91     length[ps.incir[i]]=1;
    92     length[ps.chords[i]]=10;
    93   }
    94   s=ps.outer[0];
    95   t=ps.inner[1];
     111  std::istringstream input(test_lgf);
     112  digraphReader(input, G).
     113    arcMap("length", length).
     114    node("source", s).
     115    node("target", t).
     116    run();
    96117
    97118  Dijkstra<Digraph, LengthMap>
     
    99120  dijkstra_test.run(s);
    100121
    101   check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
     122  check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path.");
    102123
    103124  Path<Digraph> p = dijkstra_test.path(t);
    104   check(p.length()==4,"getPath() found a wrong path.");
     125  check(p.length()==3,"getPath() found a wrong path.");
    105126  check(checkPath(G, p),"path() found a wrong path.");
    106127  check(pathSource(G, p) == s,"path() found a wrong path.");
     
    116137  }
    117138
    118   for(NodeIt v(G); v!=INVALID; ++v){
    119     check(dijkstra_test.reached(v),"Each node should be reached.");
    120     if ( dijkstra_test.predArc(v)!=INVALID ) {
    121       Arc e=dijkstra_test.predArc(v);
    122       Node u=G.source(e);
    123       check(u==dijkstra_test.predNode(v),"Wrong tree.");
    124       check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
    125             "Wrong distance! Difference: " <<
    126             std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
     139  for(NodeIt v(G); v!=INVALID; ++v) {
     140    if (dijkstra_test.reached(v)) {
     141      check(v==s || dijkstra_test.predArc(v)!=INVALID, "Wrong tree.");
     142      if (dijkstra_test.predArc(v)!=INVALID ) {
     143        Arc e=dijkstra_test.predArc(v);
     144        Node u=G.source(e);
     145        check(u==dijkstra_test.predNode(v),"Wrong tree.");
     146        check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
     147              "Wrong distance! Difference: " <<
     148              std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
     149      }
    127150    }
    128151  }
Note: See TracChangeset for help on using the changeset viewer.