COIN-OR::LEMON - Graph Library

Changeset 2247:269a0dcee70b in lemon-0.x for lemon/concept/path.h


Ignore:
Timestamp:
10/17/06 12:50:57 (13 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
  • lemon/concept/path.h

    r1993 r2247  
    3838    //!
    3939    //! A skeleton structure for representing directed paths in a graph.
    40     //! \param GR The graph type in which the path is.
     40    //! \param _Graph The graph type in which the path is.
    4141    //!
    4242    //! In a sense, the path can be treated as a graph, for it has \c NodeIt
    4343    //! and \c EdgeIt with the same usage. These types converts to the \c Node
    4444    //! and \c Edge of the original graph.
    45     template<typename GR>
     45    template<typename _Graph>
    4646    class Path {
    4747    public:
    4848
    4949      /// Type of the underlying graph.
    50       typedef /*typename*/ GR Graph;
     50      typedef _Graph Graph;
    5151      /// Edge type of the underlying graph.
    52       typedef typename Graph::Edge GraphEdge;
     52      typedef typename Graph::Edge Edge;
    5353      /// Node type of the underlying graph.
    54      typedef typename Graph::Node GraphNode;
     54      typedef typename Graph::Node Node;
     55
    5556      class NodeIt;
    5657      class EdgeIt;
     
    6263      }
    6364
    64       /// Length of the path.
     65      /// Length of the path ie. the number of edges in the path.
    6566      int length() const {return 0;}
     67
    6668      /// Returns whether the path is empty.
    6769      bool empty() const { return true;}
     
    7476      /// Starting point of the path.
    7577      /// Returns INVALID if the path is empty.
    76       GraphNode/*It*/ target() const {return INVALID;}
     78      Node target() const {return INVALID;}
    7779      /// \brief End point of the path.
    7880      ///
    7981      /// End point of the path.
    8082      /// Returns INVALID if the path is empty.
    81       GraphNode/*It*/ source() const {return INVALID;}
    82 
    83       /// \brief First NodeIt/EdgeIt.
    84       ///
    85       /// Initializes node or edge iterator to point to the first
    86       /// node or edge.
    87       template<typename It>
    88       It& first(It &i) const { return i=It(*this); }
     83      Node source() const {return INVALID;}
    8984
    9085      /// \brief The target of an edge.
     
    10095      NodeIt source(const EdgeIt&) const {return INVALID;}
    10196
    102 
    103       /* Iterator classes */
    104 
    105       /**
    106        * \brief Iterator class to iterate on the edges of the paths
    107        *
    108        * This class is used to iterate on the edges of the paths
    109        *
    110        * Of course it converts to Graph::Edge
    111        *
    112        */
     97      /// \brief Iterator class to iterate on the nodes of the paths
     98      ///
     99      /// This class is used to iterate on the nodes of the paths
     100      ///
     101      /// Of course it converts to Graph::Node.
     102      class NodeIt {
     103      public:
     104        /// Default constructor
     105        NodeIt() {}
     106        /// Invalid constructor
     107        NodeIt(Invalid) {}
     108        /// Constructor with starting point
     109        NodeIt(const Path &) {}
     110
     111        ///Conversion to Graph::Node
     112        operator Node() const { return INVALID; }
     113        /// Next node
     114        NodeIt& operator++() {return *this;}
     115
     116        /// Comparison operator
     117        bool operator==(const NodeIt&) const {return true;}
     118        /// Comparison operator
     119        bool operator!=(const NodeIt&) const {return true;}
     120        /// Comparison operator
     121        bool operator<(const NodeIt&) const {return false;}
     122
     123      };
     124
     125      /// \brief Iterator class to iterate on the edges of the paths
     126      ///
     127      /// This class is used to iterate on the edges of the paths
     128      ///
     129      /// Of course it converts to Graph::Edge
    113130      class EdgeIt {
    114131      public:
     
    120137        EdgeIt(const Path &) {}
    121138
    122         operator GraphEdge () const {}
     139        operator Edge() const { return INVALID; }
    123140
    124141        /// Next edge
     
    129146        /// Comparison operator
    130147        bool operator!=(const EdgeIt&) const {return true;}
    131 //      /// Comparison operator
    132 //      /// \todo It is not clear what is the "natural" ordering.
    133 //      bool operator<(const EdgeIt& e) const {}
    134 
    135       };
    136 
    137       /**
    138        * \brief Iterator class to iterate on the nodes of the paths
    139        *
    140        * This class is used to iterate on the nodes of the paths
    141        *
    142        * Of course it converts to Graph::Node.
    143        *
    144        */
    145       class NodeIt {
    146       public:
    147         /// Default constructor
    148         NodeIt() {}
    149         /// Invalid constructor
    150         NodeIt(Invalid) {}
    151         /// Constructor with starting point
    152         NodeIt(const Path &) {}
    153 
    154         ///Conversion to Graph::Node
    155         operator const GraphNode& () const {}
    156         /// Next node
    157         NodeIt& operator++() {return *this;}
    158 
    159         /// Comparison operator
    160         bool operator==(const NodeIt&) const {return true;}
    161         /// Comparison operator
    162         bool operator!=(const NodeIt&) const {return true;}
    163 //      /// Comparison operator
    164 //      /// \todo It is not clear what is the "natural" ordering.
    165 //      bool operator<(const NodeIt& e) const {}
    166 
    167       };
     148        /// Comparison operator
     149        bool operator<(const EdgeIt&) const {return false;}
     150
     151      };
     152
    168153
    169154      friend class Builder;
    170155
    171       /**
    172        * \brief Class to build paths
    173        *
    174        * This class is used to fill a path with edges.
    175        *
    176        * You can push new edges to the front and to the back of the path in
    177        * arbitrary order then you should commit these changes to the graph.
    178        *
    179        * While the builder is active (after the first modifying
    180        * operation and until the call of \ref commit()) the
    181        * underlining Path is in a "transitional" state (operations on
    182        * it have undefined result).
    183        */
     156      /// \brief Class to build paths
     157      ///
     158      /// This class is used to fill a path with edges.
     159      ///
     160      /// You can push new edges to the front and to the back of the path in
     161      /// arbitrary order then you should commit these changes to the graph.
     162      ///
     163      /// While the builder is active (after the first modifying
     164      /// operation and until the call of \ref commit()) the
     165      /// underlining Path is in a "transitional" state (operations on
     166      /// it have undefined result).
    184167      class Builder {
    185168      public:
    186169
    187         Path &P;
    188 
    189         ///\param _p the path you want to fill in.
     170        /// Constructor
     171
     172        /// Constructor
     173        /// \param _path the path you want to fill in.
    190174        ///
    191175
    192         Builder(Path &_p) : P(_p) {}
     176        Builder(Path &_path) { ignore_unused_variable_warning(_path); }
    193177
    194178        /// Sets the starting node of the path.
     
    200184        /// \sa pushFront()
    201185        /// \sa pushBack()
    202         void setStartNode(const GraphNode &) {}
     186        void setStartNode(const Node &) {}
    203187
    204188        ///Push a new edge to the front of the path
     
    207191        ///If the path is empty, you \em must call \ref setStartNode() before
    208192        ///the first use of \ref pushFront().
    209         void pushFront(const GraphEdge&) {}
     193        void pushFront(const Edge&) {}
    210194
    211195        ///Push a new edge to the back of the path
     
    214198        ///If the path is empty, you \em must call \ref setStartNode() before
    215199        ///the first use of \ref pushBack().
    216         void pushBack(const GraphEdge&) {}
     200        void pushBack(const Edge&) {}
    217201
    218202        ///Commit the changes to the path.
     203
     204        ///Commit the changes to the path.
     205        ///
    219206        void commit() {}
    220207
     
    232219        void reserveBack(size_t) {}
    233220      };
     221
     222      template <typename _Path>
     223      struct Constraints {
     224        void constraints() {
     225          typedef typename _Path::Node Node;
     226          typedef typename _Path::NodeIt NodeIt;
     227          typedef typename Graph::Node GraphNode;
     228
     229          typedef typename _Path::Edge Edge;
     230          typedef typename _Path::EdgeIt EdgeIt;
     231          typedef typename Graph::Edge GraphEdge;
     232
     233          typedef typename _Path::Builder Builder;
     234
     235          path = _Path(graph);
     236
     237          bool b = cpath.empty();
     238          int l = cpath.length();
     239
     240          Node gn;
     241          Edge ge;
     242          gn = cpath.source();
     243          gn = cpath.target();
     244
     245          NodeIt nit;
     246          EdgeIt eit(INVALID);
     247          nit = path.source(eit);
     248          nit = path.target(eit);
     249         
     250          nit = NodeIt();
     251          nit = NodeIt(cpath);
     252          nit = INVALID;
     253          gn = nit;
     254          ++nit;
     255          b = nit == nit;
     256          b = nit != nit;
     257          b = nit < nit;
     258
     259          eit = EdgeIt();
     260          eit = EdgeIt(cpath);
     261          eit = INVALID;
     262          ge = eit;
     263          ++eit;
     264          b = eit == eit;
     265          b = eit != eit;
     266          b = eit < eit;
     267
     268          size_t st = 0;
     269
     270          Builder builder(path);
     271          builder.setStartNode(gn);
     272          builder.pushFront(ge);
     273          builder.pushBack(ge);
     274          builder.commit();
     275          builder.reserveFront(st);
     276          builder.reserveBack(st);
     277         
     278          ignore_unused_variable_warning(l);
     279          ignore_unused_variable_warning(b);
     280        }
     281
     282        const Graph& graph;
     283        const _Path& cpath;
     284        _Path& path;
     285      };
     286
    234287    };
    235288
Note: See TracChangeset for help on using the changeset viewer.