COIN-OR::LEMON - Graph Library

Changeset 493:bbd1db03f0fe in lemon-0.x for src/work/klao/path.h


Ignore:
Timestamp:
04/30/04 03:59:15 (17 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@651
Message:

DirPath? fejlodes.
Kiserleti struktura a forditasi idoben kapcsolhato konzisztencia es range
ellenorzesekre.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/klao/path.h

    r450 r493  
    11// -*- c++ -*- //
    22
    3 ///ingroup datas
     3///\ingroup datas
    44///\file
    5 ///\brief Class for representing paths in graphs.
     5///\brief Classes for representing paths in graphs.
    66
    77#ifndef HUGO_PATH_H
     
    1313
    1414#include <invalid.h>
     15#include <error.h>
     16#include <debug.h>
    1517
    1618namespace hugo {
     
    1921  /// @{
    2022
    21   ///A container for directed paths
    22 
    23   ///\param Graph The graph type in which the path is.
    24   ///
    25   ///In a sense, the path can be treated as a graph, for is has \c NodeIt
    26   ///and \c EdgeIt with the same usage. These types converts to the \c Node
    27   ///and \c Edge of the original graph.
    28   ///\todo How to clear a path?
    29   ///\todo Clarify the consistency checks to do.
    30   template<typename Graph>
     23
     24  //! \brief A structure for representing directed path in a graph.
     25  //!
     26  //! \param Graph The graph type in which the path is.
     27  //! \param DM DebugMode, defaults to DefaultDebugMode.
     28  //!
     29  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
     30  //! and \c EdgeIt with the same usage. These types converts to the \c Node
     31  //! and \c Edge of the original graph.
     32  //!
     33  //! \todo Thoroughfully check all the range and consistency tests.
     34  template<typename Graph, typename DM = DefaultDebugMode>
    3135  class DirPath {
    3236  public:
     
    4347  public:
    4448
    45     /// Constructor
    46    
    4749    /// \param _G The graph in which the path is.
    4850    ///
    4951    DirPath(const Graph &_G) : gr(&_G) {}
    5052
     53    /// \brief Subpath constructor.
     54    ///
    5155    /// Subpath defined by two nodes.
    5256    /// \warning It is an error if the two edges are not in order!
     57    /// \todo Implement!
    5358    DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b);
     59    /// \brief Subpath constructor.
     60    ///
    5461    /// Subpath defined by two edges. Contains edges in [a,b)
    5562    /// \warning It is an error if the two edges are not in order!
     63    /// \todo Implement!
    5664    DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b);
    5765
     66    /// Length of the path.
    5867    size_t length() const { return edges.size(); }
     68    /// Returns whether the path is empty.
    5969    bool empty() const { return edges.empty(); }
     70
     71    /// Resets the path to an empty path.
     72    void clear() { edges.clear(); }
     73
     74    /// \brief Starting point of the path.
     75    ///
     76    /// Starting point of the path.
     77    /// Returns INVALID if the path is empty.
    6078    GraphNode from() const {
    6179      return empty() ? INVALID : gr->tail(edges[0]);
    6280    }
     81    /// \brief End point of the path.
     82    ///
     83    /// End point of the path.
     84    /// Returns INVALID if the path is empty.
    6385    GraphNode to() const {
    6486      return empty() ? INVALID : gr->head(edges[length()-1]);
    6587    }
    6688
     89    /// \brief Initializes node or edge iterator to point to the first
     90    /// node or edge.
     91    ///
     92    /// \sa nth
    6793    template<typename It>
    6894    It& first(It &i) const { return i=It(*this); }
    6995
     96    /// \brief Initializes node or edge iterator to point to the node or edge
     97    /// of a given index.
    7098    template<typename It>
    71     It& nth(It &i, int n) const { return i=It(*this, n); }
    72 
     99    It& nth(It &i, int n) const {
     100      // FIXME: this test should be different for NodeIt and EdgeIt:
     101      if( DM::range_check && (n<0 || n>int(length())) )
     102        fault("DirPath::nth: index out of range");
     103      return i=It(*this, n);
     104    }
     105
     106    /// Checks validity of a node or edge iterator.
    73107    template<typename It>
    74108    bool valid(const It &i) const { return i.valid(); }
    75109
     110    /// Steps the given node or edge iterator.
    76111    template<typename It>
    77     It& next(It &e) const { return ++e; }
    78 
    79     /// \todo !
    80     NodeIt head(const EdgeIt& e) const;
    81     NodeIt tail(const EdgeIt& e) const;
     112    It& next(It &e) const {
     113      if( DM::range_check && !e.valid() )
     114        fault("DirPath::next() on invalid iterator");
     115      return ++e;
     116    }
     117
     118    /// \brief Returns node iterator pointing to the head node of the
     119    /// given edge iterator.
     120    NodeIt head(const EdgeIt& e) const {
     121      return NodeIt(*this, e.idx+1);
     122    }
     123
     124    /// \brief Returns node iterator pointing to the tail node of the
     125    /// given edge iterator.
     126    NodeIt tail(const EdgeIt& e) const {
     127      return NodeIt(*this, e.idx);
     128    }
    82129
    83130
     
    144191    friend class Builder;   
    145192
    146     ///Class to build paths
    147 
    148     ///\ingroup datas
    149     ///This class is used to build new paths.
    150     ///You can push new edges to the front and to the back of the path in
    151     ///arbitrary order the you can commit these changes to the graph.
    152     ///\todo We must clarify when the path will be in "transitional" state.
     193    /**
     194     * \brief Class to build paths
     195     *
     196     * \ingroup datas
     197     * This class is used to fill a path with edges.
     198     *
     199     * You can push new edges to the front and to the back of the path in
     200     * arbitrary order the you can commit these changes to the graph.
     201     *
     202     * Fundamentally, for most "Paths" (classes fulfilling the
     203     * PathConcept) while the builder is active (after the first modifying
     204     * operation and until the commit()) the original Path is in a
     205     * "transitional" state (operations ot it have undefined result). But
     206     * in the case of DirPath the original path is unchanged until the
     207     * commit. However we don't recomend that you use this feature.
     208     */
    153209    class Builder {
    154210      DirPath &P;
    155       Container d;
     211      Container front, back;
    156212
    157213    public:
    158       ///Constructor
    159 
    160       ///\param _P the path you want to build.
     214      ///\param _P the path you want to fill in.
    161215      ///
    162216      Builder(DirPath &_P) : P(_P) {}
    163217
    164       ///Set the first node of the path.
     218      ///Sets the first node of the path.
    165219     
    166       ///Set the first node of the path.
    167       ///If the path is empty, this must be call before any call of
    168       ///\ref pushFront() or \ref pushBack()
    169       void setFirst(const GraphNode &) { }
     220      ///Sets the first node of the path. If the path is empty, this
     221      ///function or setTo() have to be called before any call to \ref
     222      ///pushFront() or \ref pushBack()
     223      void setFrom(const GraphNode &) {}
     224     
     225      ///Sets the last node of the path.
     226     
     227      ///Sets the last node of the path. If the path is empty, this
     228      ///function or setFrom() have to be called before any call of \ref
     229      ///pushFront() or \ref pushBack()
     230      void setTo(const GraphNode &) {}
    170231     
    171232      ///Push a new edge to the front of the path
    172233
    173234      ///Push a new edge to the front of the path.
    174       ///\sa setFirst()
    175       bool pushFront(const GraphEdge& e) {
    176         if( empty() || P.gr->head(e)==from() ) {
    177           d.push_back(e);
    178           return true;
     235      ///\sa setTo
     236      void pushFront(const GraphEdge& e) {
     237        if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
     238          fault("DirPath::Builder::pushFront: nonincident edge");
    179239        }
    180         return false;
    181       }
     240        front.push_back(e);
     241      }
     242
    182243      ///Push a new edge to the back of the path
    183244
    184245      ///Push a new edge to the back of the path.
    185       ///\sa setFirst()
    186       bool pushBack(const GraphEdge& e) {
    187         if( empty() || P.gr->tail(e)==to() ) {
    188           P.edges.push_back(e);
    189           return true;
     246      ///\sa setFrom
     247      void pushBack(const GraphEdge& e) {
     248        if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
     249          fault("DirPath::Builder::pushBack: nonincident edge");
    190250        }
    191         return false;
     251        back.push_back(e);
    192252      }
    193253
    194254      ///Commit the changes to the path.
    195255      void commit() {
    196         if( !d.empty() ) {
    197           P.edges.insert(P.edges.begin(), d.rbegin(), d.rend());
    198           d.clear();
     256        if( !(front.empty() && back.empty()) ) {
     257          Container tmp;
     258          tmp.reserve(front.size()+back.size()+P.length());
     259          tmp.insert(tmp.end(), front.rbegin(), front.rend());
     260          tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
     261          tmp.insert(tmp.end(), back.begin(), back.end());
     262          P.edges.swap(tmp);
     263          front.clear();
     264          back.clear();
    199265        }
    200266      }
    201267
    202       ///Desctuctor
    203 
    204       ///The desctuctor.
    205       ///It commit also commit the changes.
    206       ///\todo Is this what we want?
    207       ~Builder() { commit(); }
     268//       ///Desctuctor
     269
     270//       ///The desctuctor.
     271//       ///It commit also commit the changes.
     272//       ///\todo Is this what we want?
     273//  Nope. Let's use commit() explicitly.
     274//       ~Builder() { commit(); }
    208275
    209276      // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
    210277      // Hogy kenyelmes egy ilyet hasznalni?
    211278      void reserve(size_t r) {
    212         d.reserve(r);
    213         P.edges.reserve(P.length()+r);
     279        front.reserve(r);
     280        back.reserve(r);
    214281      }
    215282
    216283    private:
    217       bool empty() { return d.empty() && P.empty(); }
     284      bool empty() {
     285        return front.empty() && back.empty() && P.empty();
     286      }
    218287
    219288      GraphNode from() const {
    220         if( ! d.empty() )
    221           return P.gr->tail(d[d.size()-1]);
     289        if( ! front.empty() )
     290          return P.gr->tail(front[front.size()-1]);
    222291        else if( ! P.empty() )
    223292          return P.gr->tail(P.edges[0]);
     293        else if( ! back.empty() )
     294          return P.gr->tail(back[0]);
    224295        else
    225296          return INVALID;
    226297      }
    227298      GraphNode to() const {
    228         if( ! P.empty() )
     299        if( ! back.empty() )
     300          return P.gr->head(back[back.size()-1]);
     301        else if( ! P.empty() )
    229302          return P.gr->head(P.edges[P.length()-1]);
    230         else if( ! d.empty() )
    231           return P.gr->head(d[0]);
     303        else if( ! front.empty() )
     304          return P.gr->head(front[0]);
    232305        else
    233306          return INVALID;
Note: See TracChangeset for help on using the changeset viewer.