COIN-OR::LEMON - Graph Library

Changeset 2247:269a0dcee70b in lemon-0.x for test/path_test.cc


Ignore:
Timestamp:
10/17/06 12:50:57 (15 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2997
Message:

Update the Path concept
Concept check for paths

DirPath? renamed to Path
The interface updated to the new lemon interface
Make difference between the empty path and the path from one node
Builder interface have not been changed

I wanted but there was not accordance about it

UPath is removed
It was a buggy implementation, it could not iterate on the
nodes in the right order
Right way to use undirected paths => path of edges in undirected graphs

The tests have been modified to the current implementation

File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/path_test.cc

    r1956 r2247  
    1919#include <string>
    2020#include <iostream>
     21
    2122#include <lemon/concept/path.h>
     23#include <lemon/concept/graph.h>
     24
    2225#include <lemon/path.h>
    2326#include <lemon/list_graph.h>
    2427
     28#include "test_tools.h"
     29
    2530using namespace std;
    2631using namespace lemon;
    27 using namespace lemon::concept;
    2832
    29 template<class Path> void checkCompilePath(Path &P)
    30 {
    31   typedef typename Path::EdgeIt EdgeIt;
    32   typedef typename Path::NodeIt NodeIt;
    33   typedef typename Path::GraphNode GraphNode;
    34   typedef typename Path::GraphEdge GraphEdge;
    35   //typedef typename Path::Builder Builder;
    36   //??? ha csinalok ilyet es siman Builderrel peldanyositok, akkor warningol. Talan friend miatt? De ki az?
    37 
    38   EdgeIt ei;
    39   NodeIt ni;
    40   GraphNode gn;
    41   GraphEdge ge;
    42 
    43   size_t st;
    44   bool b;
    45 
    46   //Path(const Graph &_G) {}      //the constructor has been already called
    47 
    48   st=P.length();                  //size_t length() const {return 0;}
    49   b=P.empty();                    //bool empty() const {}
    50   P.clear();                      //void clear() {}
    51 
    52   gn=P.target();                    //GraphNode/*It*/ target() const {return INVALID;}
    53   gn=P.source();                    //GraphNode/*It*/ source() const {return INVALID;}
    54 
    55   ei=P.first(ei);                 //It& first(It &i) const { return i=It(*this); }
    56 
    57   ni=P.target(ei);                  //NodeIt target(const EdgeIt& e) const {}
    58   ni=P.source(ei);                  //NodeIt source(const EdgeIt& e) const {}
    59 
    60 
    61   ListGraph lg;
    62   Path p(lg);
    63 
    64   EdgeIt i;                       //EdgeIt() {}
    65   EdgeIt j(INVALID);              //EdgeIt(Invalid) {}
    66   EdgeIt k(p);                    //EdgeIt(const Path &_p) {}
    67 
    68   i=++j;                          //EdgeIt& operator++() {}
    69   ++k;
    70   b=(i==j);                       //bool operator==(const EdgeIt& e) const {return true;}
    71   b=(i!=j);                       //bool operator!=(const EdgeIt& e) const {return true;}
    72 
    73 
    74   NodeIt l;                       //NodeIt() {}
    75   NodeIt m(INVALID);              //NodeIt(Invalid) {}
    76   NodeIt n(p);                    //NodeIt(const Path &_p) {}
    77 
    78   l=++m;                          //NodeIt& operator++() {}
    79   b=(m==n);                       //bool operator==(const NodeIt& e) const {}
    80   b=(m!=n);                       //bool operator!=(const NodeIt& e) const {}
    81 
    82   typename Path::Builder builder(p);     //Builder(Path &_P) : P(_P) {}
    83   builder.setStartNode(gn);              //void setStartNode(const GraphNode &) {}
    84   builder.pushFront(ge);                 //void pushFront(const GraphEdge& e) {}
    85   builder.pushBack(ge);                  //void pushBack(const GraphEdge& e) {}
    86   builder.commit();                      //void commit() {}
    87   builder.reserveFront(st);              //void reserveFront(size_t r) {}
    88   builder.reserveBack(st);               //void reserveBack(size_t r) {}
    89 
     33void check_concepts() {
     34  checkConcept<concept::Path<concept::Graph>,
     35    concept::Path<concept::Graph> >();
     36  checkConcept<concept::Path<concept::Graph>,
     37    Path<concept::Graph> >();
     38  checkConcept<concept::Path<ListGraph>, Path<ListGraph> >();
    9039}
    9140
    92 template void checkCompilePath< concept::Path<ListGraph> >(concept::Path<ListGraph> &);
    93 template void checkCompilePath< DirPath<ListGraph> >(DirPath<ListGraph> &);
    94 template void checkCompilePath< UPath<ListGraph> >(UPath<ListGraph> &);
     41int main() {
     42  check_concepts();
     43 
     44  ListGraph g;
     45 
     46  ListGraph::Node n1 = g.addNode();
     47  ListGraph::Node n2 = g.addNode();
     48  ListGraph::Node n3 = g.addNode();
     49  ListGraph::Node n4 = g.addNode();
     50  ListGraph::Node n5 = g.addNode();
     51 
     52  ListGraph::Edge e1 = g.addEdge(n1, n2);
     53  ListGraph::Edge e2 = g.addEdge(n2, n3);
     54  ListGraph::Edge e3 = g.addEdge(n3, n4);
     55  ListGraph::Edge e4 = g.addEdge(n4, n5);
     56  ListGraph::Edge e5 = g.addEdge(n5, n1);
    9557
    96 int main()
    97 {
     58  {
     59    Path<ListGraph> p(g);
     60
     61    check(p.empty(), "Wrong Path");
     62    check(p.length() == 0, "Wrong Path");
     63   
     64    {
     65      Path<ListGraph>::Builder b(p);
     66      b.setStartNode(n3);
     67      b.commit();
     68    }
     69
     70    check(!p.empty(), "Wrong Path");
     71    check(p.length() == 0, "Wrong Path");
     72    check(p.source() == n3, "Wrong Path");
     73    check(p.target() == n3, "Wrong Path");
     74
     75    {
     76      Path<ListGraph>::Builder b(p);
     77      b.pushBack(e3);
     78      b.pushBack(e4);
     79      b.pushFront(e2);
     80      b.commit();
     81    }
     82
     83    check(!p.empty(), "Wrong Path");
     84    check(p.length() == 3, "Wrong Path");
     85    check(p.source() == n2, "Wrong Path");
     86    check(p.target() == n5, "Wrong Path");
     87   
     88    {
     89      Path<ListGraph>::NodeIt it(p);
     90      check((ListGraph::Node)it == n2, "Wrong Path"); ++it;
     91      check((ListGraph::Node)it == n3, "Wrong Path"); ++it;
     92      check((ListGraph::Node)it == n4, "Wrong Path"); ++it;
     93      check((ListGraph::Node)it == n5, "Wrong Path"); ++it;
     94      check((ListGraph::Node)it == INVALID, "Wrong Path");
     95    }
     96
     97    {
     98      Path<ListGraph>::EdgeIt it(p);
     99      check((ListGraph::Edge)it == e2, "Wrong Path"); ++it;
     100      check((ListGraph::Edge)it == e3, "Wrong Path"); ++it;
     101      check((ListGraph::Edge)it == e4, "Wrong Path"); ++it;
     102      check((ListGraph::Edge)it == INVALID, "Wrong Path");
     103    }
     104   
     105  }
     106 
     107  return 0;
    98108}
Note: See TracChangeset for help on using the changeset viewer.