COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 831:b6ae3446098a in lemon-0.x


Ignore:
Timestamp:
09/12/04 23:46:26 (19 years ago)
Author:
Hegyi Péter
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1129
Message:

The first version of new path test program. The old became old_path_test.

Location:
src
Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed

  • src/hugo/path.h

    r819 r831  
    3030#include <hugo/invalid.h>
    3131#include <hugo/error.h>
    32 #include <hugo/debug.h>
     32//#include <hugo/debug.h>
    3333
    3434namespace hugo {
    … …  
    4949  //!
    5050  //! \todo Thoroughfully check all the range and consistency tests.
    51   template<typename Graph, typename DM = DefaultDebugMode>
     51  template<typename Graph>
    5252  class DirPath {
    5353  public:
    … …  
    7575    /// \warning It is an error if the two edges are not in order!
    7676    DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
    77       if( DM::range_check && (!a.valid() || !b.valid) ) {
     77      if(!a.valid() || !b.valid) {
    7878        // FIXME: this check should be more elaborate...
    7979        fault("DirPath, subpath ctor: invalid bounding nodes");
    … …  
    8888    /// \warning It is an error if the two edges are not in order!
    8989    DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
    90       if( DM::range_check && (!a.valid() || !b.valid) ) {
     90      if (!a.valid() || !b.valid) {
    9191        // FIXME: this check should be more elaborate...
    9292        fault("DirPath, subpath ctor: invalid bounding nodes");
    … …  
    108108    /// Starting point of the path.
    109109    /// Returns INVALID if the path is empty.
    110     GraphNode from() const {
     110    GraphNode tail() const {
    111111      return empty() ? INVALID : gr->tail(edges[0]);
    112112    }
    … …  
    115115    /// End point of the path.
    116116    /// Returns INVALID if the path is empty.
    117     GraphNode to() const {
     117    GraphNode head() const {
    118118      return empty() ? INVALID : gr->head(edges[length()-1]);
    119119    }
    … …  
    128128    /// \brief Initializes node iterator to point to the node of a given index.
    129129    NodeIt& nth(NodeIt &i, int n) const {
    130       if( DM::range_check && (n<0 || n>int(length())) )
     130      if(n<0 || n>int(length()))
    131131        fault("DirPath::nth: index out of range");
    132132      return i=NodeIt(*this, n);
    … …  
    135135    /// \brief Initializes edge iterator to point to the edge of a given index.
    136136    EdgeIt& nth(EdgeIt &i, int n) const {
    137       if( DM::range_check && (n<0 || n>=int(length())) )
     137      if(n<0 || n>=int(length()))
    138138        fault("DirPath::nth: index out of range");
    139139      return i=EdgeIt(*this, n);
    … …  
    149149    static
    150150    It& next(It &e) {
    151       if( DM::range_check && !e.valid() )
     151      if( !e.valid() )
    152152        fault("DirPath::next() on invalid iterator");
    153153      return ++e;
    … …  
    157157    /// given edge iterator.
    158158    NodeIt head(const EdgeIt& e) const {
    159       if( DM::range_check && !e.valid() )
     159      if( !e.valid() )
    160160        fault("DirPath::head() on invalid iterator");
    161161      return NodeIt(*this, e.idx+1);
    … …  
    165165    /// given edge iterator.
    166166    NodeIt tail(const EdgeIt& e) const {
    167       if( DM::range_check && !e.valid() )
     167      if( !e.valid() )
    168168        fault("DirPath::tail() on invalid iterator");
    169169      return NodeIt(*this, e.idx);
    … …  
    253253      operator const GraphNode& () const {
    254254        if(idx >= p->length())
    255           return p->to();
     255          return p->head();
    256256        else if(idx >= 0)
    257257          return p->gr->tail(p->edges[idx]);
    … …  
    313313      ///\sa setStartNode
    314314      void pushFront(const GraphEdge& e) {
    315         if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
     315        if( !empty() && P.gr->head(e)!=tail() ) {
    316316          fault("DirPath::Builder::pushFront: nonincident edge");
    317317        }
    … …  
    324324      ///\sa setStartNode
    325325      void pushBack(const GraphEdge& e) {
    326         if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
     326        if( !empty() && P.gr->tail(e)!=head() ) {
    327327          fault("DirPath::Builder::pushBack: nonincident edge");
    328328        }
    … …  
    356356      }
    357357
     358      void reserveFront(size_t r) {}
     359      void reserveBack(size_t r) {}
     360
    358361    private:
    359362      bool empty() {
    … …  
    361364      }
    362365
    363       GraphNode from() const {
     366      GraphNode tail() const {
    364367        if( ! front.empty() )
    365368          return P.gr->tail(front[front.size()-1]);
    … …  
    371374          return INVALID;
    372375      }
    373       GraphNode to() const {
     376      GraphNode head() const {
    374377        if( ! back.empty() )
    375378          return P.gr->head(back[back.size()-1]);
    … …  
    412415  //!
    413416  //! \todo Thoroughfully check all the range and consistency tests.
    414   template<typename Graph, typename DM = DefaultDebugMode>
     417  template<typename Graph>
    415418  class UndirPath {
    416419  public:
    … …  
    438441    /// \warning It is an error if the two edges are not in order!
    439442    UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
    440       if( DM::range_check && (!a.valid() || !b.valid) ) {
     443      if(!a.valid() || !b.valid) {
    441444        // FIXME: this check should be more elaborate...
    442445        fault("UndirPath, subpath ctor: invalid bounding nodes");
    … …  
    451454    /// \warning It is an error if the two edges are not in order!
    452455    UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
    453       if( DM::range_check && (!a.valid() || !b.valid) ) {
     456      if(!a.valid() || !b.valid) {
    454457        // FIXME: this check should be more elaborate...
    455458        fault("UndirPath, subpath ctor: invalid bounding nodes");
    … …  
    471474    /// Starting point of the path.
    472475    /// Returns INVALID if the path is empty.
    473     GraphNode from() const {
     476    GraphNode tail() const {
    474477      return empty() ? INVALID : gr->tail(edges[0]);
    475478    }
    … …  
    478481    /// End point of the path.
    479482    /// Returns INVALID if the path is empty.
    480     GraphNode to() const {
     483    GraphNode head() const {
    481484      return empty() ? INVALID : gr->head(edges[length()-1]);
    482485    }
    … …  
    491494    /// \brief Initializes node iterator to point to the node of a given index.
    492495    NodeIt& nth(NodeIt &i, int n) const {
    493       if( DM::range_check && (n<0 || n>int(length())) )
     496      if(n<0 || n>int(length()))
    494497        fault("UndirPath::nth: index out of range");
    495498      return i=NodeIt(*this, n);
    … …  
    498501    /// \brief Initializes edge iterator to point to the edge of a given index.
    499502    EdgeIt& nth(EdgeIt &i, int n) const {
    500       if( DM::range_check && (n<0 || n>=int(length())) )
     503      if(n<0 || n>=int(length()))
    501504        fault("UndirPath::nth: index out of range");
    502505      return i=EdgeIt(*this, n);
    … …  
    512515    static
    513516    It& next(It &e) {
    514       if( DM::range_check && !e.valid() )
     517      if( !e.valid() )
    515518        fault("UndirPath::next() on invalid iterator");
    516519      return ++e;
    … …  
    520523    /// given edge iterator.
    521524    NodeIt head(const EdgeIt& e) const {
    522       if( DM::range_check && !e.valid() )
     525      if( !e.valid() )
    523526        fault("UndirPath::head() on invalid iterator");
    524527      return NodeIt(*this, e.idx+1);
    … …  
    528531    /// given edge iterator.
    529532    NodeIt tail(const EdgeIt& e) const {
    530       if( DM::range_check && !e.valid() )
     533      if( !e.valid() )
    531534        fault("UndirPath::tail() on invalid iterator");
    532535      return NodeIt(*this, e.idx);
    … …  
    614617      operator const GraphNode& () const {
    615618        if(idx >= p->length())
    616           return p->to();
     619          return p->head();
    617620        else if(idx >= 0)
    618621          return p->gr->tail(p->edges[idx]);
    … …  
    674677      ///\sa setStartNode
    675678      void pushFront(const GraphEdge& e) {
    676         if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
     679        if( !empty() && P.gr->head(e)!=tail() ) {
    677680          fault("UndirPath::Builder::pushFront: nonincident edge");
    678681        }
    … …  
    685688      ///\sa setStartNode
    686689      void pushBack(const GraphEdge& e) {
    687         if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
     690        if( !empty() && P.gr->tail(e)!=head() ) {
    688691          fault("UndirPath::Builder::pushBack: nonincident edge");
    689692        }
    … …  
    717720      }
    718721
     722      void reserveFront(size_t r) {}
     723      void reserveBack(size_t r) {}
     724
    719725    private:
    720726      bool empty() {
    … …  
    722728      }
    723729
    724       GraphNode from() const {
     730      GraphNode tail() const {
    725731        if( ! front.empty() )
    726732          return P.gr->tail(front[front.size()-1]);
    … …  
    732738          return INVALID;
    733739      }
    734       GraphNode to() const {
     740      GraphNode head() const {
    735741        if( ! back.empty() )
    736742          return P.gr->head(back[back.size()-1]);
    … …  
    792798   
    793799    size_t length() const { return edges.size(); }
    794     GraphNode from() const { return _first; }
    795     GraphNode to() const { return _last; }
     800    GraphNode tail() const { return _first; }
     801    GraphNode head() const { return _last; }
    796802
    797803    NodeIt& first(NodeIt &n) const { return nth(n, 0); }

  • src/hugo/skeletons/path.h

    r823 r831  
    1 #define SKELETON
    21// -*- c++ -*- //
    32
    … …  
    65///\brief Classes for representing paths in graphs.
    76
    8 #ifndef HUGO_PATH_H
    9 #define HUGO_PATH_H
     7#ifndef HUGO_SKELETON_PATH_H
     8#define HUGO_SKELETON_PATH_H
    109
    1110#include <hugo/invalid.h>
    … …  
    1514    /// \addtogroup skeletons
    1615    /// @{
    17    
    18    
     16
     17
    1918    //! \brief A skeletom structure for representing directed paths in a graph.
    2019    //!
    2120    //! A skeleton structure for representing directed paths in a graph.
    2221    //! \param GR The graph type in which the path is.
    23     //! 
     22    //!
    2423    //! In a sense, the path can be treated as a graph, for is has \c NodeIt
    2524    //! and \c EdgeIt with the same usage. These types converts to the \c Node
    … …  
    2827    class Path {
    2928    public:
    30      
     29
    3130      /// Type of the underlying graph.
    3231      typedef /*typename*/ GR Graph;
    3332      /// Edge type of the underlying graph.
    34       typedef typename Graph::Edge GraphEdge; 
     33      typedef typename Graph::Edge GraphEdge;
    3534      /// Node type of the underlying graph.
    3635     typedef typename Graph::Node GraphNode;
    3736      class NodeIt;
    3837      class EdgeIt;
    39      
     38
    4039      /// \param _G The graph in which the path is.
    4140      ///
    4241      Path(const Graph &_G) {}
    43      
     42
    4443      /// Length of the path.
    4544      size_t length() const {return 0;}
    4645      /// Returns whether the path is empty.
    47       bool empty() const {}
    48      
     46      bool empty() const { return true;}
     47
    4948      /// Resets the path to an empty path.
    5049      void clear() {}
    … …  
    7271      /// Returns node iterator pointing to the head node of the
    7372      /// given edge iterator.
    74       NodeIt head(const EdgeIt& e) const {}
     73      NodeIt head(const EdgeIt& e) const {return INVALID;}
    7574
    7675      /// \brief The tail of an edge.
    … …  
    7877      /// Returns node iterator pointing to the tail node of the
    7978      /// given edge iterator.
    80       NodeIt tail(const EdgeIt& e) const {}
     79      NodeIt tail(const EdgeIt& e) const {return INVALID;}
    8180
    8281
    … …  
    8584      /**
    8685       * \brief Iterator class to iterate on the edges of the paths
    87        * 
     86       *
    8887       * \ingroup skeletons
    8988       * This class is used to iterate on the edges of the paths
    9089       *
    9190       * Of course it converts to Graph::Edge
    92        * 
     91       *
    9392       */
    9493      class EdgeIt {
    … …  
    104103
    105104        /// Next edge
    106         EdgeIt& operator++() {}
     105        EdgeIt& operator++() {return *this;}
    107106
    108107        /// Comparison operator
    … …  
    118117      /**
    119118       * \brief Iterator class to iterate on the nodes of the paths
    120        * 
     119       *
    121120       * \ingroup skeletons
    122121       * This class is used to iterate on the nodes of the paths
    123122       *
    124123       * Of course it converts to Graph::Node.
    125        * 
     124       *
    126125       */
    127126      class NodeIt {
    … …  
    137136        operator const GraphNode& () const {}
    138137        /// Next node
    139         NodeIt& operator++() {}
    140 
    141         /// Comparison operator
    142         bool operator==(const NodeIt& e) const {}
    143         /// Comparison operator
    144         bool operator!=(const NodeIt& e) const {}
     138        NodeIt& operator++() {return *this;}
     139
     140        /// Comparison operator
     141        bool operator==(const NodeIt& e) const {return true;}
     142        /// Comparison operator
     143        bool operator!=(const NodeIt& e) const {return true;}
    145144//      /// Comparison operator
    146145//      /// \todo It is not clear what is the "natural" ordering.
    … …  
    149148      };
    150149
    151       friend class Builder;   
     150      friend class Builder;
    152151
    153152      /**
    154153       * \brief Class to build paths
    155        * 
     154       *
    156155       * \ingroup skeletons
    157156       * This class is used to fill a path with edges.
    … …  
    175174
    176175        /// Sets the starting node of the path.
    177      
     176
    178177        /// Sets the starting node of the path. Edge added to the path
    179178        /// afterwards have to be incident to this node.
    … …  
    218217  ///@}
    219218  }
    220  
     219
    221220} // namespace hugo
    222221
    223 #endif // HUGO_PATH_H
     222#endif // HUGO_SKELETON_PATH_H

  • src/test/path_test.cc

    r823 r831  
    11#include <string>
    22#include <iostream>
    3 //#include <hugo/path.h>
    43#include <hugo/skeletons/path.h>
     4#include <hugo/path.h>
    55#include <hugo/list_graph.h>
    66
    77using namespace std;
    88using namespace hugo;
    9 #ifdef SKELETON
    109using namespace skeleton;
    11 #endif
    1210
    13 bool passed = true;
     11template<class Path> void checkCompilePath(Path &P)
     12{
     13  typedef typename Path::EdgeIt EdgeIt;
     14  typedef typename Path::NodeIt NodeIt;
     15  typedef typename Path::GraphNode GraphNode;
     16  typedef typename Path::GraphEdge GraphEdge;
     17  //typedef typename Path::Builder Builder;
     18  //??? ha csinalok ilyet es siman Builderrel peldanyositok, akkor warningol. Talan friend miatt? De ki az?
    1419
    15 void check(bool rc) {
    16   passed = passed && rc;
    17   if(!rc) {
    18     cout << "Test failed!" << endl;
    19   }
     20  EdgeIt ei;
     21  NodeIt ni;
     22  GraphNode gn;
     23  GraphEdge ge;
     24
     25  size_t st;
     26  bool b;
     27
     28  //Path(const Graph &_G) {}      //the constructor has been already called
     29
     30  st=P.length();                  //size_t length() const {return 0;}
     31  b=P.empty();                    //bool empty() const {}
     32  P.clear();                      //void clear() {}
     33
     34  gn=P.head();                    //GraphNode/*It*/ head() const {return INVALID;}
     35  gn=P.tail();                    //GraphNode/*It*/ tail() const {return INVALID;}
     36
     37  ei=P.first(ei);                 //It& first(It &i) const { return i=It(*this); }
     38
     39  ni=P.head(ei);                  //NodeIt head(const EdgeIt& e) const {}
     40  ni=P.tail(ei);                  //NodeIt tail(const EdgeIt& e) const {}
     41
     42
     43  ListGraph lg;
     44  Path p(lg);
     45
     46  EdgeIt i;                       //EdgeIt() {}
     47  EdgeIt j(INVALID);              //EdgeIt(Invalid) {}
     48  EdgeIt k(p);                    //EdgeIt(const Path &_p) {}
     49
     50  //??? operator GraphEdge () const {}
     51
     52  //INVALIDra megy a ++????
     53  i=++j;                          //EdgeIt& operator++() {}
     54  b=(i==j);                       //bool operator==(const EdgeIt& e) const {return true;}
     55  b=(i!=j);                       //bool operator!=(const EdgeIt& e) const {return true;}
     56
     57
     58  NodeIt l;                       //NodeIt() {}
     59  NodeIt m(INVALID);              //NodeIt(Invalid) {}
     60  NodeIt n(p);                    //NodeIt(const Path &_p) {}
     61
     62  //operator const GraphNode& () const {}
     63
     64  l=++m;                          //NodeIt& operator++() {}
     65  b=(m==n);                       //bool operator==(const NodeIt& e) const {}
     66  b=(m!=n);                       //bool operator!=(const NodeIt& e) const {}
     67
     68  typename Path::Builder builder(p);     //Builder(Path &_P) : P(_P) {}
     69  builder.setStartNode(gn);              //void setStartNode(const GraphNode &) {}
     70  builder.pushFront(ge);                 //void pushFront(const GraphEdge& e) {}
     71  builder.pushBack(ge);                  //void pushBack(const GraphEdge& e) {}
     72  builder.commit();                      //void commit() {}
     73  builder.reserveFront(st);              //void reserveFront(size_t r) {}
     74  builder.reserveBack(st);               //void reserveBack(size_t r) {}
     75
    2076}
    2177
    22 #ifdef DEBUG
    23 const bool debug = true;
    24 #else
    25 const bool debug = false;
    26 #endif
     78template void checkCompilePath< skeleton::Path<ListGraph> >(skeleton::Path<ListGraph> &);
     79template void checkCompilePath< DirPath<ListGraph> >(DirPath<ListGraph> &);
     80template void checkCompilePath< UndirPath<ListGraph> >(UndirPath<ListGraph> &);
    2781
    28 
    29 int main() {
    30 
    31   try {
    32 
    33     typedef ListGraph::Node Node;
    34     typedef ListGraph::Edge Edge;
    35 
    36     ListGraph G;
    37 
    38     Node s=G.addNode();
    39     Node v1=G.addNode();
    40     Node v2=G.addNode();
    41     Node v3=G.addNode();
    42     Node v4=G.addNode();
    43     Node t=G.addNode();
    44  
    45     Edge e1 = G.addEdge(s, v1);
    46     Edge e2 = G.addEdge(s, v2);
    47     Edge e3 = G.addEdge(v1, v2);
    48     Edge e4 = G.addEdge(v2, v1);
    49     Edge e5 = G.addEdge(v1, v3);
    50     Edge e6 = G.addEdge(v3, v2);
    51     Edge e7 = G.addEdge(v2, v4);
    52     Edge e8 = G.addEdge(v4, v3);
    53     Edge e9 = G.addEdge(v3, t);
    54     Edge e10 = G.addEdge(v4, t);
    55 
    56 #ifdef DEBUG
    57     bool rc;
    58 #endif
    59 
    60     {
    61       cout << "\n\n\nDirPath tesztelese...\n";
    62 
    63 
    64       cout << "Ures path letrehozasa" << endl;
    65 #ifdef SKELETON
    66       typedef Path <ListGraph> DPath;
    67 #else
    68       typedef DirPath<ListGraph> DPath;
    69 #endif
    70       DPath P(G);
    71 
    72       cout << "P.length() == " << P.length() << endl;
    73       check(P.length() == 0);
    74 
    75 #ifdef SKELETON
    76       cout << "P.tail() valid? " << (P.tail()!=INVALID) << endl;
    77       check(! (P.tail()!=INVALID));
    78 #else
    79       cout << "P.tail() valid? " << (P.from()!=INVALID) << endl;
    80       check(! (P.to()!=INVALID));
    81 #endif
    82       {
    83         cout << "Builder objektum letrehozasa" << endl;
    84         DPath::Builder B(P);
    85 
    86         cout << "Hozzaadunk az elejehez ket elet..." << endl;
    87         B.pushFront(e6);
    88         B.pushFront(e5);
    89         cout << "P.length() == " << P.length() << endl;
    90         check(P.length() == 0);
    91      
    92         cout << "Commitolunk..." << endl;
    93         B.commit();
    94 
    95         cout << "P.length() == " << P.length() << endl;
    96         check(P.length() == 2);
    97 
    98 #ifdef SKELETON
    99         cout << "P.tail() valid? " << (P.tail()!=INVALID) << endl;
    100         check(P.tail()!=INVALID);
    101         cout << "P.tail()==v1 ? " << (P.tail()==v1) << endl;
    102         check(P.tail() == v1);
    103 #else
    104         cout << "P.tail() valid? " << (P.from()!=INVALID) << endl;
    105         check(P.from()!=INVALID);
    106         cout << "P.tail()==v1 ? " << (P.from()==v1) << endl;
    107         check(P.from() == v1);
    108 #endif
    109 
    110         // Na ja, ez igy nem igazi, mindket esetet le kene tesztelni,
    111         // de legalabb valami:
    112 #ifdef DEBUG
    113         cout << "Hozzaadunk az elejehez egy nem illeszkedo elet..." << endl;
    114         rc = false;
    115         try {
    116           B.pushFront(e3);
    117         }
    118         catch(const Exception &e) {
    119           cout << "E: " << e.what() << endl;
    120           rc = true;
    121         }
    122         check(rc);
    123 #endif
    124 
    125         cout << "Hozzaadunk a vegehez ket elet..." << endl;
    126         B.pushBack(e7);
    127         B.pushBack(e8);
    128         cout << "P.length() == " << P.length() << endl;
    129         check(P.length() == 2);
    130      
    131         cout << "Es commitolunk...\n";
    132         B.commit();
    133       }
    134       cout << "P.length() == " << P.length() << endl;
    135       check(P.length() == 4);
    136 
    137 #ifdef SKELETON
    138       cout << "P.head()==v3 ? " << (P.head()==v3) << endl;
    139       check(P.head() == v3);
    140 #else
    141       cout << "P.head()==v3 ? " << (P.to()==v3) << endl;
    142       check(P.to() == v3);
    143 #endif
    144 
    145 #ifndef SKELETON
    146       cout << "Vegigiteralunk az eleken." << endl;
    147       typedef DPath::NodeIt NodeIt;
    148       typedef DPath::EdgeIt EdgeIt;
    149       EdgeIt e;
    150       int i=1;
    151       for(P.first(e); e!=INVALID; ++e, ++i) {
    152         cout << i << ". el: " <</* e << */endl;
    153       }
    154 #endif
    155 
    156       // Na ja, ez igy nem igazi, mindket esetet le kene tesztelni,
    157       // de legalabb valami:
    158 
    159 #ifdef DEBUG
    160       rc = false;
    161       try {
    162         cout << "Setting an edgeiter to a nonexistant edge." << endl;
    163         //P.nth(e,134);
    164         rc = !debug;
    165       }
    166       catch(const Exception &e) {
    167         cout << "E: " << e.what() << endl;
    168         rc = debug;
    169       }
    170       check(rc);
    171 #endif
    172     }
    173 
    174   }
    175   catch(const std::exception &e) {
    176     cout << "Uncaught exception: " << e.what() << endl;
    177     return 1;
    178   }
    179   catch(...) {
    180     cout << "Something horrible happened: an exception which isn't "
    181          << "std::exception" << endl;
    182     return 2;
    183   }
    184 
    185 
    186   cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
    187        << endl;
    188 
    189   return passed ? 0 : 1;
     82int main()
     83{
    19084}
Note: See TracChangeset for help on using the changeset viewer.