COIN-OR::LEMON - Graph Library

Changeset 2247:269a0dcee70b in lemon-0.x for lemon


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

Location:
lemon
Files:
2 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
  • lemon/path.h

    r2084 r2247  
    2222///\brief Classes for representing paths in graphs.
    2323///
    24 ///\todo Iterators have obsolete style
    2524
    2625#ifndef LEMON_PATH_H
    2726#define LEMON_PATH_H
    2827
    29 #include <deque>
    3028#include <vector>
    3129#include <algorithm>
    3230
     31#include <lemon/error.h>
    3332#include <lemon/bits/invalid.h>
    3433
     
    4342  //! A structure for representing directed path in a graph.
    4443  //! \param Graph The graph type in which the path is.
    45   //! \param DM DebugMode, defaults to DefaultDebugMode.
    4644  //!
    4745  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
     
    5149  //! \todo Thoroughfully check all the range and consistency tests.
    5250  template<typename Graph>
    53   class DirPath {
     51  class Path {
    5452  public:
    5553    /// Edge type of the underlying graph.
    56     typedef typename Graph::Edge GraphEdge;
     54    typedef typename Graph::Edge Edge;
    5755    /// Node type of the underlying graph.
    58     typedef typename Graph::Node GraphNode;
     56    typedef typename Graph::Node Node;
     57
    5958    class NodeIt;
    6059    class EdgeIt;
    6160
    62   protected:
    63     const Graph *gr;
    64     typedef std::vector<GraphEdge> Container;
    65     Container edges;
     61    struct PathError : public LogicError {
     62      virtual const char* what() const throw() {
     63        return "lemon::PathError";
     64      }     
     65    };
    6666
    6767  public:
    6868
     69    /// \brief Constructor
     70    ///
     71    /// Constructor
    6972    /// \param _G The graph in which the path is.
    70     ///
    71     DirPath(const Graph &_G) : gr(&_G) {}
    72 
     73    Path(const Graph &_graph) : graph(&_graph), start(INVALID) {}
     74   
    7375    /// \brief Subpath constructor.
    7476    ///
    7577    /// Subpath defined by two nodes.
    7678    /// \warning It is an error if the two edges are not in order!
    77     DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
    78       gr = P.gr;
    79       edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
     79    Path(const Path &other, const NodeIt &a, const NodeIt &b) {
     80      graph = other.graph;
     81      start = a;
     82      edges.insert(edges.end(),
     83                   other.edges.begin() + a.id, other.edges.begin() + b.id);
    8084    }
    8185
     
    8488    /// Subpath defined by two edges. Contains edges in [a,b)
    8589    /// \warning It is an error if the two edges are not in order!
    86     DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
    87       gr = P.gr;
    88       edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
    89     }
    90 
    91     /// Length of the path.
     90    Path(const Path &other, const EdgeIt &a, const EdgeIt &b) {
     91      graph = other.graph;
     92      start = graph->source(a);
     93      edges.insert(edges.end(),
     94                   other.edges.begin() + a.id, other.edges.begin() + b.id);
     95    }
     96
     97    /// \brief Length of the path.
     98    ///
     99    /// The number of the edges in the path. It can be zero if the
     100    /// path has only one node or it is empty.
    92101    int length() const { return edges.size(); }
    93     /// Returns whether the path is empty.
    94     bool empty() const { return edges.empty(); }
    95 
     102
     103    /// \brief Returns whether the path is empty.
     104    ///
     105    /// Returns true when the path does not contain neither edge nor
     106    /// node.
     107    bool empty() const { return start == INVALID; }
     108
     109    /// \brief Resets the path to an empty path.
     110    ///
    96111    /// Resets the path to an empty path.
    97     void clear() { edges.clear(); }
     112    void clear() { edges.clear(); start = INVALID; }
    98113
    99114    /// \brief Starting point of the path.
     
    101116    /// Starting point of the path.
    102117    /// Returns INVALID if the path is empty.
    103     GraphNode source() const {
    104       return empty() ? INVALID : gr->source(edges[0]);
     118    Node source() const {
     119      return start;
    105120    }
    106121    /// \brief End point of the path.
     
    108123    /// End point of the path.
    109124    /// Returns INVALID if the path is empty.
    110     GraphNode target() const {
    111       return empty() ? INVALID : gr->target(edges[length()-1]);
    112     }
    113 
    114     /// \brief Initializes node or edge iterator to point to the first
    115     /// node or edge.
    116     ///
    117     /// \sa nth
    118     template<typename It>
    119     It& first(It &i) const { return i=It(*this); }
    120 
    121     /// \brief Initializes node iterator to point to the node of a given index.
    122     NodeIt& nth(NodeIt &i, int n) const {
    123       return i=NodeIt(*this, n);
    124     }
    125 
    126     /// \brief Initializes edge iterator to point to the edge of a given index.
    127     EdgeIt& nth(EdgeIt &i, int n) const {
    128       return i=EdgeIt(*this, n);
     125    Node target() const {
     126      return length() == 0 ? start : graph->target(edges[length()-1]);
     127    }
     128
     129    /// \brief Gives back a node iterator to point to the node of a
     130    /// given index.
     131    ///
     132    /// Gives back a node iterator to point to the node of a given
     133    /// index.
     134    /// \pre n should less or equal to \c length()
     135    NodeIt nthNode(int n) const {
     136      return NodeIt(*this, n);
     137    }
     138
     139    /// \brief Gives back an edge iterator to point to the edge of a
     140    /// given index.
     141    ///
     142    /// Gives back an edge iterator to point to the node of a given
     143    /// index. 
     144    /// \pre n should less than \c length()
     145    EdgeIt nthEdge(int n) const {
     146      return EdgeIt(*this, n);
     147    }
     148
     149    /// \brief Returns node iterator pointing to the source node of the
     150    /// given edge iterator.
     151    ///
     152    /// Returns node iterator pointing to the source node of the given
     153    /// edge iterator.
     154    NodeIt source(const EdgeIt& e) const {
     155      return NodeIt(*this, e.id);
    129156    }
    130157
    131158    /// \brief Returns node iterator pointing to the target node of the
    132159    /// given edge iterator.
     160    ///
     161    /// Returns node iterator pointing to the target node of the given
     162    /// edge iterator.
    133163    NodeIt target(const EdgeIt& e) const {
    134       return NodeIt(*this, e.idx+1);
    135     }
    136 
    137     /// \brief Returns node iterator pointing to the source node of the
    138     /// given edge iterator.
    139     NodeIt source(const EdgeIt& e) const {
    140       return NodeIt(*this, e.idx);
    141     }
    142 
    143 
    144     /* Iterator classes */
    145 
    146     /**
    147      * \brief Iterator class to iterate on the edges of the paths
    148      *
    149      * This class is used to iterate on the edges of the paths
    150      *
    151      * Of course it converts to Graph::Edge
    152      *
    153      */
     164      return NodeIt(*this, e.id + 1);
     165    }
     166
     167
     168    /// \brief Iterator class to iterate on the nodes of the paths
     169    ///
     170    /// This class is used to iterate on the nodes of the paths
     171    ///
     172    /// Of course it converts to Graph::Node
     173    class NodeIt {
     174      friend class Path;
     175    public:
     176
     177      /// \brief Default constructor
     178      ///
     179      /// Default constructor
     180      NodeIt() {}
     181
     182      /// \brief Invalid constructor
     183      ///
     184      /// Invalid constructor
     185      NodeIt(Invalid) : id(-1), path(0) {}
     186
     187      /// \brief Constructor with starting point
     188      ///
     189      /// Constructor with starting point
     190      NodeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) {
     191        if (id > path->length()) id = -1;
     192      }
     193
     194      /// \brief Conversion to Graph::Node
     195      ///
     196      /// Conversion to Graph::Node
     197      operator Node() const {
     198        if (id > 0) {
     199          return path->graph->target(path->edges[id - 1]);
     200        } else if (id == 0) {
     201          return path->start;
     202        } else {
     203          return INVALID;
     204        }
     205      }
     206
     207      /// \brief Steps to the next node
     208      ///
     209      /// Steps to the next node
     210      NodeIt& operator++() {
     211        ++id;
     212        if (id > path->length()) id = -1;
     213        return *this;
     214      }
     215
     216      /// \brief Comparison operator
     217      ///
     218      /// Comparison operator
     219      bool operator==(const NodeIt& n) const { return id == n.id; }
     220
     221      /// \brief Comparison operator
     222      ///
     223      /// Comparison operator
     224      bool operator!=(const NodeIt& n) const { return id != n.id; }
     225
     226      /// \brief Comparison operator
     227      ///
     228      /// Comparison operator
     229      bool operator<(const NodeIt& n) const { return id < n.id; }
     230
     231    private:
     232      int id;
     233      const Path *path;
     234    };
     235
     236    /// \brief Iterator class to iterate on the edges of the paths
     237    ///
     238    /// This class is used to iterate on the edges of the paths
     239    /// Of course it converts to Graph::Edge
    154240    class EdgeIt {
    155       friend class DirPath;
    156 
    157       int idx;
    158       const DirPath *p;
     241      friend class Path;
    159242    public:
     243
     244      /// \brief Default constructor
     245      ///
    160246      /// Default constructor
    161247      EdgeIt() {}
     248
     249      /// \brief Invalid constructor
     250      ///
    162251      /// Invalid constructor
    163       EdgeIt(Invalid) : idx(-1), p(0) {}
     252      EdgeIt(Invalid) : id(-1), path(0) {}
     253
     254      /// \brief Constructor with starting point
     255      ///
    164256      /// Constructor with starting point
    165       EdgeIt(const DirPath &_p, int _idx = 0) :
    166         idx(_idx), p(&_p) { validate(); }
    167 
    168       ///Validity check
    169       bool valid() const { return idx!=-1; }
    170 
    171       ///Conversion to Graph::Edge
    172       operator GraphEdge () const {
    173         return valid() ? p->edges[idx] : INVALID;
    174       }
    175 
    176       /// Next edge
    177       EdgeIt& operator++() { ++idx; validate(); return *this; }
    178 
    179       /// Comparison operator
    180       bool operator==(const EdgeIt& e) const { return idx==e.idx; }
    181       /// Comparison operator
    182       bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
    183       /// Comparison operator
    184       bool operator<(const EdgeIt& e) const { return idx<e.idx; }
     257      EdgeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) {
     258        if (id >= path->length()) id = -1;
     259      }
     260
     261      /// \brief Conversion to Graph::Edge
     262      ///
     263      /// Conversion to Graph::Edge
     264      operator Edge() const {
     265        return id != -1 ? path->edges[id] : INVALID;
     266      }
     267
     268      /// \brief Steps to the next edge
     269      ///
     270      /// Steps to the next edge
     271      EdgeIt& operator++() {
     272        ++id;
     273        if (id >= path->length()) id = -1;
     274        return *this;
     275      }
     276
     277      /// \brief Comparison operator
     278      ///
     279      /// Comparison operator
     280      bool operator==(const EdgeIt& e) const { return id == e.id; }
     281
     282      /// \brief Comparison operator
     283      ///
     284      /// Comparison operator
     285      bool operator!=(const EdgeIt& e) const { return id != e.id; }
     286
     287      /// \brief Comparison operator
     288      ///
     289      /// Comparison operator
     290      bool operator<(const EdgeIt& e) const { return id < e.id; }
    185291
    186292    private:
    187       void validate() { if(idx >= p->length() ) idx=-1; }
     293
     294      int id;
     295      const Path *path;
    188296    };
    189297
    190     /**
    191      * \brief Iterator class to iterate on the nodes of the paths
    192      *
    193      * This class is used to iterate on the nodes of the paths
    194      *
    195      * Of course it converts to Graph::Node
    196      *
    197      */
    198     class NodeIt {
    199       friend class DirPath;
    200 
    201       int idx;
    202       const DirPath *p;
     298  protected:
     299
     300    const Graph *graph;
     301
     302    typedef std::vector<Edge> Container;
     303    Container edges;
     304    Node start;
     305
     306  public:
     307
     308    friend class Builder;
     309
     310    /// \brief Class to build paths
     311    ///
     312    /// This class is used to fill a path with edges.
     313    ///
     314    /// You can push new edges to the front and to the back of the
     315    /// path in arbitrary order then you should commit these changes
     316    /// to the graph.
     317    ///
     318    /// Fundamentally, for most "Paths" (classes fulfilling the
     319    /// PathConcept) while the builder is active (after the first
     320    /// modifying operation and until the commit()) the original Path
     321    /// is in a "transitional" state (operations on it have undefined
     322    /// result). But in the case of Path the original path remains
     323    /// unchanged until the commit. However we don't recomend that you
     324    /// use this feature.
     325    class Builder {
    203326    public:
    204       /// Default constructor
    205       NodeIt() {}
    206       /// Invalid constructor
    207       NodeIt(Invalid) : idx(-1), p(0) {}
    208       /// Constructor with starting point
    209       NodeIt(const DirPath &_p, int _idx = 0) :
    210         idx(_idx), p(&_p) { validate(); }
    211 
    212       ///Validity check
    213       bool valid() const { return idx!=-1; }
    214 
    215       ///Conversion to Graph::Node
    216       operator GraphNode () const {
    217         if(idx >= p->length())
    218           return p->target();
    219         else if(idx >= 0)
    220           return p->gr->source(p->edges[idx]);
    221         else
    222           return INVALID;
    223       }
    224       /// Next node
    225       NodeIt& operator++() { ++idx; validate(); return *this; }
    226 
    227       /// Comparison operator
    228       bool operator==(const NodeIt& e) const { return idx==e.idx; }
    229       /// Comparison operator
    230       bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
    231       /// Comparison operator
    232       bool operator<(const NodeIt& e) const { return idx<e.idx; }
    233 
    234     private:
    235       void validate() { if(idx > p->length() ) idx=-1; }
    236     };
    237 
    238     friend class Builder;
    239 
    240     /**
    241      * \brief Class to build paths
    242      *
    243      * This class is used to fill a path with edges.
    244      *
    245      * You can push new edges to the front and to the back of the path in
    246      * arbitrary order then you should commit these changes to the graph.
    247      *
    248      * Fundamentally, for most "Paths" (classes fulfilling the
    249      * PathConcept) while the builder is active (after the first modifying
    250      * operation and until the commit()) the original Path is in a
    251      * "transitional" state (operations on it have undefined result). But
    252      * in the case of DirPath the original path remains unchanged until the
    253      * commit. However we don't recomend that you use this feature.
    254      */
    255     class Builder {
    256       DirPath &P;
    257       Container front, back;
    258 
    259     public:
    260       ///\param _p the path you want to fill in.
    261       ///
    262       Builder(DirPath &_p) : P(_p) {}
    263 
    264       /// Sets the starting node of the path.
    265 
     327      /// \brief Constructor
     328      ///
     329      /// Constructor
     330      /// \param _path the path you want to fill in.
     331      Builder(Path &_path) : path(_path), start(INVALID) {}
     332
     333      /// \brief Destructor
     334      ///
     335      /// Destructor
     336      ~Builder() {
     337        LEMON_ASSERT(front.empty() && back.empty() && start == INVALID,
     338                     PathError());
     339      }
     340
     341      /// \brief Sets the starting node of the path.
     342      ///
    266343      /// Sets the starting node of the path. Edge added to the path
    267       /// afterwards have to be incident to this node.
    268       /// It should be called if and only if
    269       /// the path is empty and before any call to
    270       /// \ref pushFront() or \ref pushBack()
    271       void setStartNode(const GraphNode &) {}
    272 
    273       ///Push a new edge to the front of the path
    274 
    275       ///Push a new edge to the front of the path.
    276       ///\sa setStartNode
    277       void pushFront(const GraphEdge& e) {
     344      /// afterwards have to be incident to this node.  It should be
     345      /// called if and only if the path is empty and before any call
     346      /// to \ref pushFront() or \ref pushBack()
     347      void setStartNode(const Node &_start) {
     348        LEMON_ASSERT(path.empty() && start == INVALID, PathError());
     349        start = _start;
     350      }
     351
     352      /// \brief Push a new edge to the front of the path
     353      ///
     354      /// Push a new edge to the front of the path. 
     355      /// \sa setStartNode
     356      void pushFront(const Edge& e) {
     357        LEMON_ASSERT(front.empty() ||
     358                     (path.graph->source(front.back()) ==
     359                      path.graph->target(e)), PathError());
     360        LEMON_ASSERT(path.empty() ||
     361                     (path.source() == path.graph->target(e)), PathError());
     362        LEMON_ASSERT(!path.empty() || !front.empty() ||
     363                     (start == path.graph->target(e)), PathError());
    278364        front.push_back(e);
    279365      }
    280366
    281       ///Push a new edge to the back of the path
    282 
    283       ///Push a new edge to the back of the path.
    284       ///\sa setStartNode
    285       void pushBack(const GraphEdge& e) {
     367      /// \brief Push a new edge to the back of the path
     368      ///
     369      /// Push a new edge to the back of the path.
     370      /// \sa setStartNode
     371      void pushBack(const Edge& e) {
     372        LEMON_ASSERT(back.empty() ||
     373                     (path.graph->target(back.back()) ==
     374                      path.graph->source(e)), PathError());
     375        LEMON_ASSERT(path.empty() ||
     376                     (path.target() == path.graph->source(e)), PathError());
     377        LEMON_ASSERT(!path.empty() || !back.empty() ||
     378                     (start == path.graph->source(e)), PathError());
    286379        back.push_back(e);
    287380      }
    288381
    289       ///Commit the changes to the path.
     382      /// \brief Commit the changes to the path.
     383      ///
     384      /// Commit the changes to the path.
    290385      void commit() {
    291         if( !front.empty() || !back.empty() ) {
     386        if( !front.empty() || !back.empty() || start != INVALID) {
    292387          Container tmp;
    293           tmp.reserve(front.size()+back.size()+P.length());
     388          tmp.reserve(front.size() + back.size() + path.length());
    294389          tmp.insert(tmp.end(), front.rbegin(), front.rend());
    295           tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
     390          tmp.insert(tmp.end(), path.edges.begin(), path.edges.end());
    296391          tmp.insert(tmp.end(), back.begin(), back.end());
    297           P.edges.swap(tmp);
     392          path.edges.swap(tmp);
     393          if (!front.empty()) {
     394            path.start = path.graph->source(front.back());
     395          } else {
     396            path.start = start;
     397          }
     398          start = INVALID;
    298399          front.clear();
    299400          back.clear();
     
    301402      }
    302403
    303       ///Reserve storage for the builder in advance.
    304 
    305       ///If you know a reasonable upper bound of the number of the edges
    306       ///to add to the front, using this function you can speed up the building.
    307 
     404      /// \brief Reserve storage for the builder in advance.
     405      ///
     406      /// If you know a reasonable upper bound of the number of the
     407      /// edges to add to the front, using this function you can speed
     408      /// up the building.
    308409      void reserveFront(size_t r) {front.reserve(r);}
    309410
    310       ///Reserve storage for the builder in advance.
    311 
    312       ///If you know a reasonable upper bound of the number of the edges
    313       ///to add to the back, using this function you can speed up the building.
    314 
     411      /// \brief Reserve storage for the builder in advance.
     412      ///
     413      /// If you know a reasonable upper bound of the number of the
     414      /// edges to add to the back, using this function you can speed
     415      /// up the building.
    315416      void reserveBack(size_t r) {back.reserve(r);}
    316417
    317418    private:
    318       bool empty() {
    319         return front.empty() && back.empty() && P.empty();
    320       }
    321 
    322       GraphNode source() const {
    323         if( ! front.empty() )
    324           return P.gr->source(front[front.size()-1]);
    325         else if( ! P.empty() )
    326           return P.gr->source(P.edges[0]);
    327         else if( ! back.empty() )
    328           return P.gr->source(back[0]);
    329         else
    330           return INVALID;
    331       }
    332       GraphNode target() const {
    333         if( ! back.empty() )
    334           return P.gr->target(back[back.size()-1]);
    335         else if( ! P.empty() )
    336           return P.gr->target(P.edges[P.length()-1]);
    337         else if( ! front.empty() )
    338           return P.gr->target(front[0]);
    339         else
    340           return INVALID;
    341       }
     419
     420      Path &path;
     421      Container front, back;
     422      Node start;
    342423
    343424    };
     
    345426  };
    346427
    347 
    348 
    349 
    350 
    351 
    352 
    353 
    354 
    355 
    356   /**********************************************************************/
    357 
    358 
    359   //! \brief A structure for representing undirected path in a graph.
    360   //!
    361   //! A structure for representing undirected path in a graph. Ie. this is
    362   //! a path in a \e directed graph but the edges should not be directed
    363   //! forward.
    364   //!
    365   //! \param Graph The graph type in which the path is.
    366   //! \param DM DebugMode, defaults to DefaultDebugMode.
    367   //!
    368   //! In a sense, the path can be treated as a graph, for is has \c NodeIt
    369   //! and \c EdgeIt with the same usage. These types converts to the \c Node
    370   //! and \c Edge of the original graph.
    371   //!
    372   //! \todo Thoroughfully check all the range and consistency tests.
    373   /// \todo May we need just path for undirected graph instead of this.
    374   template<typename Graph>
    375   class UPath {
    376   public:
    377     /// Edge type of the underlying graph.
    378     typedef typename Graph::Edge GraphEdge;
    379      /// Node type of the underlying graph.
    380    typedef typename Graph::Node GraphNode;
    381     class NodeIt;
    382     class EdgeIt;
    383 
    384   protected:
    385     const Graph *gr;
    386     typedef std::vector<GraphEdge> Container;
    387     Container edges;
    388 
    389   public:
    390 
    391     /// \param _G The graph in which the path is.
    392     ///
    393     UPath(const Graph &_G) : gr(&_G) {}
    394 
    395     /// \brief Subpath constructor.
    396     ///
    397     /// Subpath defined by two nodes.
    398     /// \warning It is an error if the two edges are not in order!
    399     UPath(const UPath &P, const NodeIt &a, const NodeIt &b) {
    400       gr = P.gr;
    401       edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
    402     }
    403 
    404     /// \brief Subpath constructor.
    405     ///
    406     /// Subpath defined by two edges. Contains edges in [a,b)
    407     /// \warning It is an error if the two edges are not in order!
    408     UPath(const UPath &P, const EdgeIt &a, const EdgeIt &b) {
    409       gr = P.gr;
    410       edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
    411     }
    412 
    413     /// Length of the path.
    414     size_t length() const { return edges.size(); }
    415     /// Returns whether the path is empty.
    416     bool empty() const { return edges.empty(); }
    417 
    418     /// Resets the path to an empty path.
    419     void clear() { edges.clear(); }
    420 
    421     /// \brief Starting point of the path.
    422     ///
    423     /// Starting point of the path.
    424     /// Returns INVALID if the path is empty.
    425     GraphNode source() const {
    426       return empty() ? INVALID : gr->source(edges[0]);
    427     }
    428     /// \brief End point of the path.
    429     ///
    430     /// End point of the path.
    431     /// Returns INVALID if the path is empty.
    432     GraphNode target() const {
    433       return empty() ? INVALID : gr->target(edges[length()-1]);
    434     }
    435 
    436     /// \brief Initializes node or edge iterator to point to the first
    437     /// node or edge.
    438     ///
    439     /// \sa nth
    440     template<typename It>
    441     It& first(It &i) const { return i=It(*this); }
    442 
    443     /// \brief Initializes node iterator to point to the node of a given index.
    444     NodeIt& nth(NodeIt &i, int n) const {
    445       return i=NodeIt(*this, n);
    446     }
    447 
    448     /// \brief Initializes edge iterator to point to the edge of a given index.
    449     EdgeIt& nth(EdgeIt &i, int n) const {
    450       return i=EdgeIt(*this, n);
    451     }
    452 
    453     /// Checks validity of a node or edge iterator.
    454     template<typename It>
    455     static
    456     bool valid(const It &i) { return i.valid(); }
    457 
    458     /// Steps the given node or edge iterator.
    459     template<typename It>
    460     static
    461     It& next(It &e) {
    462       return ++e;
    463     }
    464 
    465     /// \brief Returns node iterator pointing to the target node of the
    466     /// given edge iterator.
    467     NodeIt target(const EdgeIt& e) const {
    468       return NodeIt(*this, e.idx+1);
    469     }
    470 
    471     /// \brief Returns node iterator pointing to the source node of the
    472     /// given edge iterator.
    473     NodeIt source(const EdgeIt& e) const {
    474       return NodeIt(*this, e.idx);
    475     }
    476 
    477 
    478 
    479     /**
    480      * \brief Iterator class to iterate on the edges of the paths
    481      *
    482      * This class is used to iterate on the edges of the paths
    483      *
    484      * Of course it converts to Graph::Edge
    485      *
    486      * \todo Its interface differs from the standard edge iterator.
    487      * Yes, it shouldn't.
    488      */
    489     class EdgeIt {
    490       friend class UPath;
    491 
    492       int idx;
    493       const UPath *p;
    494     public:
    495       /// Default constructor
    496       EdgeIt() {}
    497       /// Invalid constructor
    498       EdgeIt(Invalid) : idx(-1), p(0) {}
    499       /// Constructor with starting point
    500       EdgeIt(const UPath &_p, int _idx = 0) :
    501         idx(_idx), p(&_p) { validate(); }
    502 
    503       ///Validity check
    504       bool valid() const { return idx!=-1; }
    505 
    506       ///Conversion to Graph::Edge
    507       operator GraphEdge () const {
    508         return valid() ? p->edges[idx] : INVALID;
    509       }
    510       /// Next edge
    511      EdgeIt& operator++() { ++idx; validate(); return *this; }
    512 
    513       /// Comparison operator
    514       bool operator==(const EdgeIt& e) const { return idx==e.idx; }
    515       /// Comparison operator
    516       bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
    517       /// Comparison operator
    518       bool operator<(const EdgeIt& e) const { return idx<e.idx; }
    519 
    520     private:
    521       // FIXME: comparison between signed and unsigned...
    522       // Jo ez igy? Vagy esetleg legyen a length() int?
    523       void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
    524     };
    525 
    526     /**
    527      * \brief Iterator class to iterate on the nodes of the paths
    528      *
    529      * This class is used to iterate on the nodes of the paths
    530      *
    531      * Of course it converts to Graph::Node
    532      *
    533      * \todo Its interface differs from the standard node iterator.
    534      * Yes, it shouldn't.
    535      */
    536     class NodeIt {
    537       friend class UPath;
    538 
    539       int idx;
    540       const UPath *p;
    541     public:
    542       /// Default constructor
    543       NodeIt() {}
    544       /// Invalid constructor
    545       NodeIt(Invalid) : idx(-1), p(0) {}
    546       /// Constructor with starting point
    547       NodeIt(const UPath &_p, int _idx = 0) :
    548         idx(_idx), p(&_p) { validate(); }
    549 
    550       ///Validity check
    551       bool valid() const { return idx!=-1; }
    552 
    553       ///Conversion to Graph::Node
    554       operator const GraphNode& () const {
    555         if(idx >= p->length())
    556           return p->target();
    557         else if(idx >= 0)
    558           return p->gr->source(p->edges[idx]);
    559         else
    560           return INVALID;
    561       }
    562       /// Next node
    563       NodeIt& operator++() { ++idx; validate(); return *this; }
    564 
    565       /// Comparison operator
    566       bool operator==(const NodeIt& e) const { return idx==e.idx; }
    567       /// Comparison operator
    568       bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
    569        /// Comparison operator
    570      bool operator<(const NodeIt& e) const { return idx<e.idx; }
    571 
    572     private:
    573       void validate() { if( size_t(idx) > p->length() ) idx=-1; }
    574     };
    575 
    576     friend class Builder;
    577 
    578     /**
    579      * \brief Class to build paths
    580      *
    581      * This class is used to fill a path with edges.
    582      *
    583      * You can push new edges to the front and to the back of the path in
    584      * arbitrary order then you should commit these changes to the graph.
    585      *
    586      * Fundamentally, for most "Paths" (classes fulfilling the
    587      * PathConcept) while the builder is active (after the first modifying
    588      * operation and until the commit()) the original Path is in a
    589      * "transitional" state (operations ot it have undefined result). But
    590      * in the case of UPath the original path is unchanged until the
    591      * commit. However we don't recomend that you use this feature.
    592      */
    593     class Builder {
    594       UPath &P;
    595       Container front, back;
    596 
    597     public:
    598       ///\param _p the path you want to fill in.
    599       ///
    600       Builder(UPath &_p) : P(_p) {}
    601 
    602       /// Sets the starting node of the path.
    603 
    604       /// Sets the starting node of the path. Edge added to the path
    605       /// afterwards have to be incident to this node.
    606       /// It should be called if and only if
    607       /// the path is empty and before any call to
    608       /// \ref pushFront() or \ref pushBack()
    609       void setStartNode(const GraphNode &) {}
    610 
    611       ///Push a new edge to the front of the path
    612 
    613       ///Push a new edge to the front of the path.
    614       ///\sa setStartNode
    615       void pushFront(const GraphEdge& e) {
    616         front.push_back(e);
    617       }
    618 
    619       ///Push a new edge to the back of the path
    620 
    621       ///Push a new edge to the back of the path.
    622       ///\sa setStartNode
    623       void pushBack(const GraphEdge& e) {
    624         back.push_back(e);
    625       }
    626 
    627       ///Commit the changes to the path.
    628       void commit() {
    629         if( !(front.empty() && back.empty()) ) {
    630           Container tmp;
    631           tmp.reserve(front.size()+back.size()+P.length());
    632           tmp.insert(tmp.end(), front.rbegin(), front.rend());
    633           tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
    634           tmp.insert(tmp.end(), back.begin(), back.end());
    635           P.edges.swap(tmp);
    636           front.clear();
    637           back.clear();
    638         }
    639       }
    640 
    641 
    642       ///Reserve storage for the builder in advance.
    643 
    644       ///If you know a reasonable upper bound of the number of the edges
    645       ///to add to the front, using this function you can speed up the building.
    646 
    647       void reserveFront(size_t r) {front.reserve(r);}
    648 
    649       ///Reserve storage for the builder in advance.
    650 
    651       ///If you know a reasonable upper bound of the number of the edges
    652       ///to add to the back, using this function you can speed up the building.
    653 
    654       void reserveBack(size_t r) {back.reserve(r);}
    655 
    656     private:
    657       bool empty() {
    658         return front.empty() && back.empty() && P.empty();
    659       }
    660 
    661       GraphNode source() const {
    662         if( ! front.empty() )
    663           return P.gr->source(front[front.size()-1]);
    664         else if( ! P.empty() )
    665           return P.gr->source(P.edges[0]);
    666         else if( ! back.empty() )
    667           return P.gr->source(back[0]);
    668         else
    669           return INVALID;
    670       }
    671       GraphNode target() const {
    672         if( ! back.empty() )
    673           return P.gr->target(back[back.size()-1]);
    674         else if( ! P.empty() )
    675           return P.gr->target(P.edges[P.length()-1]);
    676         else if( ! front.empty() )
    677           return P.gr->target(front[0]);
    678         else
    679           return INVALID;
    680       }
    681 
    682     };
    683 
    684   };
    685 
    686 
    687428  ///@}
    688429
Note: See TracChangeset for help on using the changeset viewer.