COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • test/path_test.cc

    r1212 r1144  
    2222#include <lemon/concepts/path.h>
    2323#include <lemon/concepts/digraph.h>
    24 #include <lemon/concept_check.h>
    2524
    2625#include <lemon/path.h>
    … …  
    3231using namespace lemon;
    3332
    34 template <typename GR>
    35 void checkConcepts() {
    36   checkConcept<concepts::Path<GR>, concepts::Path<GR> >();
    37   checkConcept<concepts::Path<GR>, Path<GR> >();
    38   checkConcept<concepts::Path<GR>, SimplePath<GR> >();
    39   checkConcept<concepts::Path<GR>, StaticPath<GR> >();
    40   checkConcept<concepts::Path<GR>, ListPath<GR> >();
    41 }
    42 
    43 // Conecpt checking for path structures
    44 void checkPathConcepts() {
    45   checkConcepts<concepts::Digraph>();
    46   checkConcepts<ListDigraph>();
     33void check_concepts() {
     34  checkConcept<concepts::Path<ListDigraph>, concepts::Path<ListDigraph> >();
     35  checkConcept<concepts::Path<ListDigraph>, Path<ListDigraph> >();
     36  checkConcept<concepts::Path<ListDigraph>, SimplePath<ListDigraph> >();
     37  checkConcept<concepts::Path<ListDigraph>, StaticPath<ListDigraph> >();
     38  checkConcept<concepts::Path<ListDigraph>, ListPath<ListDigraph> >();
    4739}
    4840
    4941// Check if proper copy consructor is called (use valgrind for testing)
    50 template <typename GR, typename P1, typename P2>
    51 void checkCopy(typename GR::Arc a) {
    52   P1 p;
     42template<class _Path>
     43void checkCopy()
     44{
     45  ListDigraph g;
     46  ListDigraph::Arc a  = g.addArc(g.addNode(), g.addNode());
     47 
     48  _Path p,q;
    5349  p.addBack(a);
    54   P1 q;
    55   q = p;
    56   P1 r(p);
    57   P2 q2;
    58   q2 = p;
    59   P2 r2(p);
     50  q=p;
     51  _Path r(p);
     52  StaticPath<ListDigraph> s(r);
    6053}
     54 
     55int main() {
     56  check_concepts();
    6157
    62 // Tests for copy constructors and assignment operators of paths
    63 void checkPathCopy() {
     58  checkCopy<Path<ListDigraph> >();
     59  checkCopy<SimplePath<ListDigraph> >();
     60  checkCopy<ListPath<ListDigraph> >();
     61
    6462  ListDigraph g;
    65   ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode());
    66 
    67   typedef Path<ListDigraph> Path1;
    68   typedef SimplePath<ListDigraph> Path2;
    69   typedef ListPath<ListDigraph> Path3;
    70   typedef StaticPath<ListDigraph> Path4;
    71   checkCopy<ListDigraph, Path1, Path2>(a);
    72   checkCopy<ListDigraph, Path1, Path3>(a);
    73   checkCopy<ListDigraph, Path1, Path4>(a);
    74   checkCopy<ListDigraph, Path2, Path1>(a);
    75   checkCopy<ListDigraph, Path2, Path3>(a);
    76   checkCopy<ListDigraph, Path2, Path4>(a);
    77   checkCopy<ListDigraph, Path3, Path1>(a);
    78   checkCopy<ListDigraph, Path3, Path2>(a);
    79   checkCopy<ListDigraph, Path3, Path4>(a);
    80 }
    81 
    82 // Class for testing path functions
    83 class CheckPathFunctions {
    84   typedef ListDigraph GR;
    85   DIGRAPH_TYPEDEFS(GR);
    86   GR gr;
    87   const GR& cgr;
    88   Node n1, n2, n3, n4;
    89   Node tmp_n;
    90   Arc a1, a2, a3, a4;
    91   Arc tmp_a;
    92 
    93 public:
    94 
    95   CheckPathFunctions() : cgr(gr) {
    96     n1 = gr.addNode();
    97     n2 = gr.addNode();
    98     n3 = gr.addNode();
    99     n4 = gr.addNode();
    100     a1 = gr.addArc(n1, n2);
    101     a2 = gr.addArc(n2, n3);
    102     a3 = gr.addArc(n3, n4);
    103     a4 = gr.addArc(n4, n1);
    104   }
    105 
    106   void run() {
    107     checkBackAndFrontInsertablePath<Path<GR> >();
    108     checkBackAndFrontInsertablePath<ListPath<GR> >();
    109     checkBackInsertablePath<SimplePath<GR> >();
    110 
    111     checkListPathSplitAndSplice();
    112   }
    113 
    114 private:
    115 
    116   template <typename P>
    117   void checkBackInsertablePath() {
    118 
    119     // Create and check empty path
    120     P p;
    121     const P& cp = p;
    122     check(cp.empty(), "The path is not empty");
    123     check(cp.length() == 0, "The path is not empty");
    124 //    check(cp.front() == INVALID, "Wrong front()");
    125 //    check(cp.back() == INVALID, "Wrong back()");
    126     typename P::ArcIt ai(cp);
    127     check(ai == INVALID, "Wrong ArcIt");
    128     check(pathSource(cgr, cp) == INVALID, "Wrong pathSource()");
    129     check(pathTarget(cgr, cp) == INVALID, "Wrong pathTarget()");
    130     check(checkPath(cgr, cp), "Wrong checkPath()");
    131     PathNodeIt<P> ni(cgr, cp);
    132     check(ni == INVALID, "Wrong PathNodeIt");
    133 
    134     // Check single-arc path
    135     p.addBack(a1);
    136     check(!cp.empty(), "Wrong empty()");
    137     check(cp.length() == 1, "Wrong length");
    138     check(cp.front() == a1, "Wrong front()");
    139     check(cp.back() == a1, "Wrong back()");
    140     check(cp.nth(0) == a1, "Wrong nth()");
    141     ai = cp.nthIt(0);
    142     check((tmp_a = ai) == a1, "Wrong nthIt()");
    143     check(++ai == INVALID, "Wrong nthIt()");
    144     typename P::ArcIt ai2(cp);
    145     check((tmp_a = ai2) == a1, "Wrong ArcIt");
    146     check(++ai2 == INVALID, "Wrong ArcIt");
    147     check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
    148     check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
    149     check(checkPath(cgr, cp), "Wrong checkPath()");
    150     PathNodeIt<P> ni2(cgr, cp);
    151     check((tmp_n = ni2) == n1, "Wrong PathNodeIt");
    152     check((tmp_n = ++ni2) == n2, "Wrong PathNodeIt");
    153     check(++ni2 == INVALID, "Wrong PathNodeIt");
    154 
    155     // Check adding more arcs
    156     p.addBack(a2);
    157     p.addBack(a3);
    158     check(!cp.empty(), "Wrong empty()");
    159     check(cp.length() == 3, "Wrong length");
    160     check(cp.front() == a1, "Wrong front()");
    161     check(cp.back() == a3, "Wrong back()");
    162     check(cp.nth(0) == a1, "Wrong nth()");
    163     check(cp.nth(1) == a2, "Wrong nth()");
    164     check(cp.nth(2) == a3, "Wrong nth()");
    165     typename P::ArcIt ai3(cp);
    166     check((tmp_a = ai3) == a1, "Wrong ArcIt");
    167     check((tmp_a = ++ai3) == a2, "Wrong nthIt()");
    168     check((tmp_a = ++ai3) == a3, "Wrong nthIt()");
    169     check(++ai3 == INVALID, "Wrong nthIt()");
    170     ai = cp.nthIt(0);
    171     check((tmp_a = ai) == a1, "Wrong nthIt()");
    172     check((tmp_a = ++ai) == a2, "Wrong nthIt()");
    173     ai = cp.nthIt(2);
    174     check((tmp_a = ai) == a3, "Wrong nthIt()");
    175     check(++ai == INVALID, "Wrong nthIt()");
    176     check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
    177     check(pathTarget(cgr, cp) == n4, "Wrong pathTarget()");
    178     check(checkPath(cgr, cp), "Wrong checkPath()");
    179     PathNodeIt<P> ni3(cgr, cp);
    180     check((tmp_n = ni3) == n1, "Wrong PathNodeIt");
    181     check((tmp_n = ++ni3) == n2, "Wrong PathNodeIt");
    182     check((tmp_n = ++ni3) == n3, "Wrong PathNodeIt");
    183     check((tmp_n = ++ni3) == n4, "Wrong PathNodeIt");
    184     check(++ni3 == INVALID, "Wrong PathNodeIt");
    185 
    186     // Check arc removal and addition
    187     p.eraseBack();
    188     p.eraseBack();
    189     p.addBack(a2);
    190     check(!cp.empty(), "Wrong empty()");
    191     check(cp.length() == 2, "Wrong length");
    192     check(cp.front() == a1, "Wrong front()");
    193     check(cp.back() == a2, "Wrong back()");
    194     check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
    195     check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()");
    196     check(checkPath(cgr, cp), "Wrong checkPath()");
    197 
    198     // Check clear()
    199     p.clear();
    200     check(cp.empty(), "The path is not empty");
    201     check(cp.length() == 0, "The path is not empty");
    202 
    203     // Check inconsistent path
    204     p.addBack(a4);
    205     p.addBack(a2);
    206     p.addBack(a1);
    207     check(!cp.empty(), "Wrong empty()");
    208     check(cp.length() == 3, "Wrong length");
    209     check(cp.front() == a4, "Wrong front()");
    210     check(cp.back() == a1, "Wrong back()");
    211     check(pathSource(cgr, cp) == n4, "Wrong pathSource()");
    212     check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
    213     check(!checkPath(cgr, cp), "Wrong checkPath()");
    214   }
    215 
    216   template <typename P>
    217   void checkBackAndFrontInsertablePath() {
    218 
    219     // Include back insertable test cases
    220     checkBackInsertablePath<P>();
    221 
    222     // Check front and back insertion
    223     P p;
    224     const P& cp = p;
    225     p.addFront(a4);
    226     p.addBack(a1);
    227     p.addFront(a3);
    228     check(!cp.empty(), "Wrong empty()");
    229     check(cp.length() == 3, "Wrong length");
    230     check(cp.front() == a3, "Wrong front()");
    231     check(cp.back() == a1, "Wrong back()");
    232     check(cp.nth(0) == a3, "Wrong nth()");
    233     check(cp.nth(1) == a4, "Wrong nth()");
    234     check(cp.nth(2) == a1, "Wrong nth()");
    235     typename P::ArcIt ai(cp);
    236     check((tmp_a = ai) == a3, "Wrong ArcIt");
    237     check((tmp_a = ++ai) == a4, "Wrong nthIt()");
    238     check((tmp_a = ++ai) == a1, "Wrong nthIt()");
    239     check(++ai == INVALID, "Wrong nthIt()");
    240     ai = cp.nthIt(0);
    241     check((tmp_a = ai) == a3, "Wrong nthIt()");
    242     check((tmp_a = ++ai) == a4, "Wrong nthIt()");
    243     ai = cp.nthIt(2);
    244     check((tmp_a = ai) == a1, "Wrong nthIt()");
    245     check(++ai == INVALID, "Wrong nthIt()");
    246     check(pathSource(cgr, cp) == n3, "Wrong pathSource()");
    247     check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
    248     check(checkPath(cgr, cp), "Wrong checkPath()");
    249 
    250     // Check eraseFront()
    251     p.eraseFront();
    252     p.addBack(a2);
    253     check(!cp.empty(), "Wrong empty()");
    254     check(cp.length() == 3, "Wrong length");
    255     check(cp.front() == a4, "Wrong front()");
    256     check(cp.back() == a2, "Wrong back()");
    257     check(cp.nth(0) == a4, "Wrong nth()");
    258     check(cp.nth(1) == a1, "Wrong nth()");
    259     check(cp.nth(2) == a2, "Wrong nth()");
    260     typename P::ArcIt ai2(cp);
    261     check((tmp_a = ai2) == a4, "Wrong ArcIt");
    262     check((tmp_a = ++ai2) == a1, "Wrong nthIt()");
    263     check((tmp_a = ++ai2) == a2, "Wrong nthIt()");
    264     check(++ai2 == INVALID, "Wrong nthIt()");
    265     ai = cp.nthIt(0);
    266     check((tmp_a = ai) == a4, "Wrong nthIt()");
    267     check((tmp_a = ++ai) == a1, "Wrong nthIt()");
    268     ai = cp.nthIt(2);
    269     check((tmp_a = ai) == a2, "Wrong nthIt()");
    270     check(++ai == INVALID, "Wrong nthIt()");
    271     check(pathSource(cgr, cp) == n4, "Wrong pathSource()");
    272     check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()");
    273     check(checkPath(cgr, cp), "Wrong checkPath()");
    274   }
    275 
    276   void checkListPathSplitAndSplice() {
    277 
    278     // Build a path with spliceFront() and spliceBack()
    279     ListPath<GR> p1, p2, p3, p4;
    280     p1.addBack(a3);
    281     p1.addFront(a2);
    282     p2.addBack(a1);
    283     p1.spliceFront(p2);
    284     p3.addFront(a4);
    285     p1.spliceBack(p3);
    286     check(p1.length() == 4, "Wrong length");
    287     check(p1.front() == a1, "Wrong front()");
    288     check(p1.back() == a4, "Wrong back()");
    289     ListPath<GR>::ArcIt ai(p1);
    290     check((tmp_a = ai) == a1, "Wrong ArcIt");
    291     check((tmp_a = ++ai) == a2, "Wrong nthIt()");
    292     check((tmp_a = ++ai) == a3, "Wrong nthIt()");
    293     check((tmp_a = ++ai) == a4, "Wrong nthIt()");
    294     check(++ai == INVALID, "Wrong nthIt()");
    295     check(checkPath(cgr, p1), "Wrong checkPath()");
    296 
    297     // Check split()
    298     p1.split(p1.nthIt(2), p2);
    299     check(p1.length() == 2, "Wrong length");
    300     ai = p1.nthIt(0);
    301     check((tmp_a = ai) == a1, "Wrong ArcIt");
    302     check((tmp_a = ++ai) == a2, "Wrong nthIt()");
    303     check(++ai == INVALID, "Wrong nthIt()");
    304     check(checkPath(cgr, p1), "Wrong checkPath()");
    305     check(p2.length() == 2, "Wrong length");
    306     ai = p2.nthIt(0);
    307     check((tmp_a = ai) == a3, "Wrong ArcIt");
    308     check((tmp_a = ++ai) == a4, "Wrong nthIt()");
    309     check(++ai == INVALID, "Wrong nthIt()");
    310     check(checkPath(cgr, p2), "Wrong checkPath()");
    311 
    312     // Check split() and splice()
    313     p1.spliceFront(p2);
    314     p1.split(p1.nthIt(2), p2);
    315     p2.split(p2.nthIt(1), p3);
    316     p2.spliceBack(p1);
    317     p2.splice(p2.nthIt(1), p3);
    318     check(p2.length() == 4, "Wrong length");
    319     check(p2.front() == a1, "Wrong front()");
    320     check(p2.back() == a4, "Wrong back()");
    321     ai = p2.nthIt(0);
    322     check((tmp_a = ai) == a1, "Wrong ArcIt");
    323     check((tmp_a = ++ai) == a2, "Wrong nthIt()");
    324     check((tmp_a = ++ai) == a3, "Wrong nthIt()");
    325     check((tmp_a = ++ai) == a4, "Wrong nthIt()");
    326     check(++ai == INVALID, "Wrong nthIt()");
    327     check(checkPath(cgr, p2), "Wrong checkPath()");
    328   }
    329 
    330 };
    331 
    332 int main() {
    333   checkPathConcepts();
    334   checkPathCopy();
    335   CheckPathFunctions cpf;
    336   cpf.run();
     63  ListDigraph::Arc a  = g.addArc(g.addNode(), g.addNode());
     64 
     65  Path<ListDigraph> p;
     66  StaticPath<ListDigraph> q,r;
     67  p.addBack(a);
     68  q=p;
     69  r=q;
     70  StaticPath<ListDigraph> s(q);
    33771
    33872  return 0;
Note: See TracChangeset for help on using the changeset viewer.