lemon/path.h
author ladanyi
Wed, 02 Aug 2006 20:15:22 +0000
changeset 2167 7e109b222053
parent 2045 012cd0ca3254
child 2247 269a0dcee70b
permissions -rw-r--r--
Fixed the mailinglist link and removed the gui section.
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2006
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 
    20 ///\ingroup paths
    21 ///\file
    22 ///\brief Classes for representing paths in graphs.
    23 ///
    24 ///\todo Iterators have obsolete style
    25 
    26 #ifndef LEMON_PATH_H
    27 #define LEMON_PATH_H
    28 
    29 #include <deque>
    30 #include <vector>
    31 #include <algorithm>
    32 
    33 #include <lemon/bits/invalid.h>
    34 
    35 namespace lemon {
    36 
    37   /// \addtogroup paths
    38   /// @{
    39 
    40 
    41   //! \brief A structure for representing directed paths in a graph.
    42   //!
    43   //! A structure for representing directed path in a graph.
    44   //! \param Graph The graph type in which the path is.
    45   //! \param DM DebugMode, defaults to DefaultDebugMode.
    46   //!
    47   //! In a sense, the path can be treated as a graph, for is has \c NodeIt
    48   //! and \c EdgeIt with the same usage. These types converts to the \c Node
    49   //! and \c Edge of the original graph.
    50   //!
    51   //! \todo Thoroughfully check all the range and consistency tests.
    52   template<typename Graph>
    53   class DirPath {
    54   public:
    55     /// Edge type of the underlying graph.
    56     typedef typename Graph::Edge GraphEdge;
    57     /// Node type of the underlying graph.
    58     typedef typename Graph::Node GraphNode;
    59     class NodeIt;
    60     class EdgeIt;
    61 
    62   protected:
    63     const Graph *gr;
    64     typedef std::vector<GraphEdge> Container;
    65     Container edges;
    66 
    67   public:
    68 
    69     /// \param _G The graph in which the path is.
    70     ///
    71     DirPath(const Graph &_G) : gr(&_G) {}
    72 
    73     /// \brief Subpath constructor.
    74     ///
    75     /// Subpath defined by two nodes.
    76     /// \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);
    80     }
    81 
    82     /// \brief Subpath constructor.
    83     ///
    84     /// Subpath defined by two edges. Contains edges in [a,b)
    85     /// \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.
    92     int length() const { return edges.size(); }
    93     /// Returns whether the path is empty.
    94     bool empty() const { return edges.empty(); }
    95 
    96     /// Resets the path to an empty path.
    97     void clear() { edges.clear(); }
    98 
    99     /// \brief Starting point of the path.
   100     ///
   101     /// Starting point of the path.
   102     /// Returns INVALID if the path is empty.
   103     GraphNode source() const {
   104       return empty() ? INVALID : gr->source(edges[0]);
   105     }
   106     /// \brief End point of the path.
   107     ///
   108     /// End point of the path.
   109     /// 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);
   129     }
   130 
   131     /// \brief Returns node iterator pointing to the target node of the
   132     /// given edge iterator.
   133     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      */
   154     class EdgeIt {
   155       friend class DirPath;
   156 
   157       int idx;
   158       const DirPath *p;
   159     public:
   160       /// Default constructor
   161       EdgeIt() {}
   162       /// Invalid constructor
   163       EdgeIt(Invalid) : idx(-1), p(0) {}
   164       /// 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; }
   185 
   186     private:
   187       void validate() { if(idx >= p->length() ) idx=-1; }
   188     };
   189 
   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;
   203     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 
   266       /// 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) {
   278 	front.push_back(e);
   279       }
   280 
   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) {
   286 	back.push_back(e);
   287       }
   288 
   289       ///Commit the changes to the path.
   290       void commit() {
   291 	if( !front.empty() || !back.empty() ) {
   292 	  Container tmp;
   293 	  tmp.reserve(front.size()+back.size()+P.length());
   294 	  tmp.insert(tmp.end(), front.rbegin(), front.rend());
   295 	  tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
   296 	  tmp.insert(tmp.end(), back.begin(), back.end());
   297 	  P.edges.swap(tmp);
   298 	  front.clear();
   299 	  back.clear();
   300 	}
   301       }
   302 
   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 
   308       void reserveFront(size_t r) {front.reserve(r);}
   309 
   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 
   315       void reserveBack(size_t r) {back.reserve(r);}
   316 
   317     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       }
   342 
   343     };
   344 
   345   };
   346 
   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 
   687   ///@}
   688 
   689 } // namespace lemon
   690 
   691 #endif // LEMON_PATH_H