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 for src/hugo


Ignore:
Timestamp:
09/12/04 23:46:26 (20 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/hugo
Files:
2 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
Note: See TracChangeset for help on using the changeset viewer.