COIN-OR::LEMON - Graph Library

Changeset 619:e09818232531 in lemon-0.x


Ignore:
Timestamp:
05/12/04 00:50:09 (17 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@804
Message:

path improvements

Location:
src/work/klao
Files:
2 edited

Legend:

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

    r493 r619  
    1919    //! corresponding map to NULL...
    2020    static const bool ensure_safe_state = true;
     21
     22    static const int verbose = 5;
    2123  };
    2224
     
    2527    static const bool range_check = false;
    2628    static const bool ensure_safe_state = false;
     29    static const int verbose = 0;
    2730  };
    2831
  • src/work/klao/path.h

    r607 r619  
    2424  //! \brief A structure for representing directed path in a graph.
    2525  //!
     26  //! A structure for representing directed path in a graph.
    2627  //! \param Graph The graph type in which the path is.
    2728  //! \param DM DebugMode, defaults to DefaultDebugMode.
     
    5556    /// Subpath defined by two nodes.
    5657    /// \warning It is an error if the two edges are not in order!
    57     /// \todo Implement!
    58     DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b);
     58    DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
     59      if( DM::range_check && (!a.valid() || !b.valid) ) {
     60        // FIXME: this check should be more elaborate...
     61        fault("DirPath, subpath ctor: invalid bounding nodes");
     62      }
     63      gr = P.gr;
     64      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
     65    }
     66
    5967    /// \brief Subpath constructor.
    6068    ///
    6169    /// Subpath defined by two edges. Contains edges in [a,b)
    6270    /// \warning It is an error if the two edges are not in order!
    63     /// \todo Implement!
    64     DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b);
     71    DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
     72      if( DM::range_check && (!a.valid() || !b.valid) ) {
     73        // FIXME: this check should be more elaborate...
     74        fault("DirPath, subpath ctor: invalid bounding nodes");
     75      }
     76      gr = P.gr;
     77      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
     78    }
    6579
    6680    /// Length of the path.
     
    94108    It& first(It &i) const { return i=It(*this); }
    95109
    96     /// \brief Initializes node or edge iterator to point to the node or edge
    97     /// of a given index.
    98     template<typename It>
    99     It& nth(It &i, int n) const {
    100       // FIXME: this test should be different for NodeIt and EdgeIt:
     110    /// \brief Initializes node iterator to point to the node of a given index.
     111    NodeIt& nth(NodeIt &i, int n) const {
    101112      if( DM::range_check && (n<0 || n>int(length())) )
    102113        fault("DirPath::nth: index out of range");
    103       return i=It(*this, n);
     114      return i=NodeIt(*this, n);
     115    }
     116
     117    /// \brief Initializes edge iterator to point to the edge of a given index.
     118    EdgeIt& nth(EdgeIt &i, int n) const {
     119      if( DM::range_check && (n<0 || n>=int(length())) )
     120        fault("DirPath::nth: index out of range");
     121      return i=EdgeIt(*this, n);
    104122    }
    105123
    106124    /// Checks validity of a node or edge iterator.
    107125    template<typename It>
    108     bool valid(const It &i) const { return i.valid(); }
     126    static
     127    bool valid(const It &i) { return i.valid(); }
    109128
    110129    /// Steps the given node or edge iterator.
    111130    template<typename It>
    112     It& next(It &e) const {
     131    static
     132    It& next(It &e) {
    113133      if( DM::range_check && !e.valid() )
    114134        fault("DirPath::next() on invalid iterator");
     
    119139    /// given edge iterator.
    120140    NodeIt head(const EdgeIt& e) const {
     141      if( DM::range_check && !e.valid() )
     142        fault("DirPath::head() on invalid iterator");
    121143      return NodeIt(*this, e.idx+1);
    122144    }
     
    125147    /// given edge iterator.
    126148    NodeIt tail(const EdgeIt& e) const {
     149      if( DM::range_check && !e.valid() )
     150        fault("DirPath::tail() on invalid iterator");
    127151      return NodeIt(*this, e.idx);
    128152    }
     
    171195      bool valid() const { return idx!=-1; }
    172196
    173       operator const GraphEdge& () const {
     197      operator const GraphNode& () const {
    174198        if(idx >= p->length())
    175199          return p->to();
     
    198222     *
    199223     * 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.
     224     * arbitrary order then you should commit these changes to the graph.
    201225     *
    202226     * Fundamentally, for most "Paths" (classes fulfilling the
     
    216240      Builder(DirPath &_P) : P(_P) {}
    217241
    218       ///Sets the first node of the path.
     242      /// Sets the starting node of the path.
    219243     
    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 &) {}
    231      
     244      /// Sets the starting node of the path. Edge added to the path
     245      /// afterwards have to be incident to this node.
     246      /// It should be called iff the path is empty and before any call to
     247      /// \ref pushFront() or \ref pushBack()
     248      void setStart(const GraphNode &) {}
     249
    232250      ///Push a new edge to the front of the path
    233251
    234252      ///Push a new edge to the front of the path.
    235       ///\sa setTo
     253      ///\sa setStart
    236254      void pushFront(const GraphEdge& e) {
    237255        if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
     
    244262
    245263      ///Push a new edge to the back of the path.
    246       ///\sa setFrom
     264      ///\sa setStart
    247265      void pushBack(const GraphEdge& e) {
    248266        if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
     
    266284      }
    267285
    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(); }
     286      // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
     287      // Hogy kenyelmes egy ilyet hasznalni?
     288      void reserve(size_t r) {
     289        front.reserve(r);
     290        back.reserve(r);
     291      }
     292
     293    private:
     294      bool empty() {
     295        return front.empty() && back.empty() && P.empty();
     296      }
     297
     298      GraphNode from() const {
     299        if( ! front.empty() )
     300          return P.gr->tail(front[front.size()-1]);
     301        else if( ! P.empty() )
     302          return P.gr->tail(P.edges[0]);
     303        else if( ! back.empty() )
     304          return P.gr->tail(back[0]);
     305        else
     306          return INVALID;
     307      }
     308      GraphNode to() const {
     309        if( ! back.empty() )
     310          return P.gr->head(back[back.size()-1]);
     311        else if( ! P.empty() )
     312          return P.gr->head(P.edges[P.length()-1]);
     313        else if( ! front.empty() )
     314          return P.gr->head(front[0]);
     315        else
     316          return INVALID;
     317      }
     318
     319    };
     320
     321  };
     322
     323
     324
     325
     326
     327
     328
     329
     330
     331
     332  /**********************************************************************/
     333
     334
     335  //! \brief A structure for representing undirected path in a graph.
     336  //!
     337  //! A structure for representing undirected path in a graph. Ie. this is
     338  //! a path in a \e directed graph but the edges should not be directed
     339  //! forward.
     340  //!
     341  //! \param Graph The graph type in which the path is.
     342  //! \param DM DebugMode, defaults to DefaultDebugMode.
     343  //!
     344  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
     345  //! and \c EdgeIt with the same usage. These types converts to the \c Node
     346  //! and \c Edge of the original graph.
     347  //!
     348  //! \todo Thoroughfully check all the range and consistency tests.
     349  template<typename Graph, typename DM = DefaultDebugMode>
     350  class UndirPath {
     351  public:
     352    typedef typename Graph::Edge GraphEdge;
     353    typedef typename Graph::Node GraphNode;
     354    class NodeIt;
     355    class EdgeIt;
     356
     357  protected:
     358    const Graph *gr;
     359    typedef std::vector<GraphEdge> Container;
     360    Container edges;
     361
     362  public:
     363
     364    /// \param _G The graph in which the path is.
     365    ///
     366    UndirPath(const Graph &_G) : gr(&_G) {}
     367
     368    /// \brief Subpath constructor.
     369    ///
     370    /// Subpath defined by two nodes.
     371    /// \warning It is an error if the two edges are not in order!
     372    UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
     373      if( DM::range_check && (!a.valid() || !b.valid) ) {
     374        // FIXME: this check should be more elaborate...
     375        fault("UndirPath, subpath ctor: invalid bounding nodes");
     376      }
     377      gr = P.gr;
     378      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
     379    }
     380
     381    /// \brief Subpath constructor.
     382    ///
     383    /// Subpath defined by two edges. Contains edges in [a,b)
     384    /// \warning It is an error if the two edges are not in order!
     385    UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
     386      if( DM::range_check && (!a.valid() || !b.valid) ) {
     387        // FIXME: this check should be more elaborate...
     388        fault("UndirPath, subpath ctor: invalid bounding nodes");
     389      }
     390      gr = P.gr;
     391      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
     392    }
     393
     394    /// Length of the path.
     395    size_t length() const { return edges.size(); }
     396    /// Returns whether the path is empty.
     397    bool empty() const { return edges.empty(); }
     398
     399    /// Resets the path to an empty path.
     400    void clear() { edges.clear(); }
     401
     402    /// \brief Starting point of the path.
     403    ///
     404    /// Starting point of the path.
     405    /// Returns INVALID if the path is empty.
     406    GraphNode from() const {
     407      return empty() ? INVALID : gr->tail(edges[0]);
     408    }
     409    /// \brief End point of the path.
     410    ///
     411    /// End point of the path.
     412    /// Returns INVALID if the path is empty.
     413    GraphNode to() const {
     414      return empty() ? INVALID : gr->head(edges[length()-1]);
     415    }
     416
     417    /// \brief Initializes node or edge iterator to point to the first
     418    /// node or edge.
     419    ///
     420    /// \sa nth
     421    template<typename It>
     422    It& first(It &i) const { return i=It(*this); }
     423
     424    /// \brief Initializes node iterator to point to the node of a given index.
     425    NodeIt& nth(NodeIt &i, int n) const {
     426      if( DM::range_check && (n<0 || n>int(length())) )
     427        fault("UndirPath::nth: index out of range");
     428      return i=NodeIt(*this, n);
     429    }
     430
     431    /// \brief Initializes edge iterator to point to the edge of a given index.
     432    EdgeIt& nth(EdgeIt &i, int n) const {
     433      if( DM::range_check && (n<0 || n>=int(length())) )
     434        fault("UndirPath::nth: index out of range");
     435      return i=EdgeIt(*this, n);
     436    }
     437
     438    /// Checks validity of a node or edge iterator.
     439    template<typename It>
     440    static
     441    bool valid(const It &i) { return i.valid(); }
     442
     443    /// Steps the given node or edge iterator.
     444    template<typename It>
     445    static
     446    It& next(It &e) {
     447      if( DM::range_check && !e.valid() )
     448        fault("UndirPath::next() on invalid iterator");
     449      return ++e;
     450    }
     451
     452    /// \brief Returns node iterator pointing to the head node of the
     453    /// given edge iterator.
     454    NodeIt head(const EdgeIt& e) const {
     455      if( DM::range_check && !e.valid() )
     456        fault("UndirPath::head() on invalid iterator");
     457      return NodeIt(*this, e.idx+1);
     458    }
     459
     460    /// \brief Returns node iterator pointing to the tail node of the
     461    /// given edge iterator.
     462    NodeIt tail(const EdgeIt& e) const {
     463      if( DM::range_check && !e.valid() )
     464        fault("UndirPath::tail() on invalid iterator");
     465      return NodeIt(*this, e.idx);
     466    }
     467
     468
     469    /*** Iterator classes ***/
     470    class EdgeIt {
     471      friend class UndirPath;
     472
     473      int idx;
     474      const UndirPath *p;
     475    public:
     476      EdgeIt() {}
     477      EdgeIt(Invalid) : idx(-1), p(0) {}
     478      EdgeIt(const UndirPath &_p, int _idx = 0) :
     479        idx(_idx), p(&_p) { validate(); }
     480
     481      bool valid() const { return idx!=-1; }
     482
     483      operator GraphEdge () const {
     484        return valid() ? p->edges[idx] : INVALID;
     485      }
     486      EdgeIt& operator++() { ++idx; validate(); return *this; }
     487
     488      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
     489      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
     490      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
     491
     492    private:
     493      // FIXME: comparison between signed and unsigned...
     494      // Jo ez igy? Vagy esetleg legyen a length() int?
     495      void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
     496    };
     497
     498    class NodeIt {
     499      friend class UndirPath;
     500
     501      int idx;
     502      const UndirPath *p;
     503    public:
     504      NodeIt() {}
     505      NodeIt(Invalid) : idx(-1), p(0) {}
     506      NodeIt(const UndirPath &_p, int _idx = 0) :
     507        idx(_idx), p(&_p) { validate(); }
     508
     509      bool valid() const { return idx!=-1; }
     510
     511      operator const GraphNode& () const {
     512        if(idx >= p->length())
     513          return p->to();
     514        else if(idx >= 0)
     515          return p->gr->tail(p->edges[idx]);
     516        else
     517          return INVALID;
     518      }
     519      NodeIt& operator++() { ++idx; validate(); return *this; }
     520
     521      bool operator==(const NodeIt& e) const { return idx==e.idx; }
     522      bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
     523      bool operator<(const NodeIt& e) const { return idx<e.idx; }
     524
     525    private:
     526      void validate() { if( size_t(idx) > p->length() ) idx=-1; }
     527    };
     528
     529    friend class Builder;   
     530
     531    /**
     532     * \brief Class to build paths
     533     *
     534     * \ingroup datas
     535     * This class is used to fill a path with edges.
     536     *
     537     * You can push new edges to the front and to the back of the path in
     538     * arbitrary order then you should commit these changes to the graph.
     539     *
     540     * Fundamentally, for most "Paths" (classes fulfilling the
     541     * PathConcept) while the builder is active (after the first modifying
     542     * operation and until the commit()) the original Path is in a
     543     * "transitional" state (operations ot it have undefined result). But
     544     * in the case of UndirPath the original path is unchanged until the
     545     * commit. However we don't recomend that you use this feature.
     546     */
     547    class Builder {
     548      UndirPath &P;
     549      Container front, back;
     550
     551    public:
     552      ///\param _P the path you want to fill in.
     553      ///
     554      Builder(UndirPath &_P) : P(_P) {}
     555
     556      /// Sets the starting node of the path.
     557     
     558      /// Sets the starting node of the path. Edge added to the path
     559      /// afterwards have to be incident to this node.
     560      /// It should be called iff the path is empty and before any call to
     561      /// \ref pushFront() or \ref pushBack()
     562      void setStart(const GraphNode &) {}
     563
     564      ///Push a new edge to the front of the path
     565
     566      ///Push a new edge to the front of the path.
     567      ///\sa setStart
     568      void pushFront(const GraphEdge& e) {
     569        if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
     570          fault("UndirPath::Builder::pushFront: nonincident edge");
     571        }
     572        front.push_back(e);
     573      }
     574
     575      ///Push a new edge to the back of the path
     576
     577      ///Push a new edge to the back of the path.
     578      ///\sa setStart
     579      void pushBack(const GraphEdge& e) {
     580        if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
     581          fault("UndirPath::Builder::pushBack: nonincident edge");
     582        }
     583        back.push_back(e);
     584      }
     585
     586      ///Commit the changes to the path.
     587      void commit() {
     588        if( !(front.empty() && back.empty()) ) {
     589          Container tmp;
     590          tmp.reserve(front.size()+back.size()+P.length());
     591          tmp.insert(tmp.end(), front.rbegin(), front.rend());
     592          tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
     593          tmp.insert(tmp.end(), back.begin(), back.end());
     594          P.edges.swap(tmp);
     595          front.clear();
     596          back.clear();
     597        }
     598      }
    275599
    276600      // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
Note: See TracChangeset for help on using the changeset viewer.