lemon-0.x: src/hugo/path.h@d56fad02dc55

     1 // -*- c++ -*- //

     3 /**

     4 @defgroup paths Path Structures

     5 @ingroup datas

     6 \brief Path structures implemented in Hugo.

     8 Hugolib provides flexible data structures

     9 to work with paths.

    11 All of them have the same interface, especially they can be built or extended

    12 using a standard Builder subclass. This make is easy to have e.g. the Dijkstra

    13 algorithm to store its result in any kind of path structure.

    15 \sa hugo::skeleton::Path

    17 */

    19 ///\ingroup paths

    20 ///\file

    21 ///\brief Classes for representing paths in graphs.

    23 #ifndef HUGO_PATH_H

    24 #define HUGO_PATH_H

    26 #include <deque>

    27 #include <vector>

    28 #include <algorithm>

    30 #include <hugo/invalid.h>

    32 namespace hugo {

    34   /// \addtogroup paths

    35   /// @{

    38   //! \brief A structure for representing directed paths in a graph.

    39   //!

    40   //! A structure for representing directed path in a graph.

    41   //! \param Graph The graph type in which the path is.

    42   //! \param DM DebugMode, defaults to DefaultDebugMode.

    43   //!

    44   //! In a sense, the path can be treated as a graph, for is has \c NodeIt

    45   //! and \c EdgeIt with the same usage. These types converts to the \c Node

    46   //! and \c Edge of the original graph.

    47   //!

    48   //! \todo Thoroughfully check all the range and consistency tests.

    49   template<typename Graph>

    50   class DirPath {

    51   public:

    52     /// Edge type of the underlying graph.

    53     typedef typename Graph::Edge GraphEdge;

    54     /// Node type of the underlying graph.

    55     typedef typename Graph::Node GraphNode;

    56     class NodeIt;

    57     class EdgeIt;

    59   protected:

    60     const Graph *gr;

    61     typedef std::vector<GraphEdge> Container;

    62     Container edges;

    64   public:

    66     /// \param _G The graph in which the path is.

    67     ///

    68     DirPath(const Graph &_G) : gr(&_G) {}

    70     /// \brief Subpath constructor.

    71     ///

    72     /// Subpath defined by two nodes.

    73     /// \warning It is an error if the two edges are not in order!

    74     DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {

    75       gr = P.gr;

    76       edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);

    77     }

    79     /// \brief Subpath constructor.

    80     ///

    81     /// Subpath defined by two edges. Contains edges in [a,b)

    82     /// \warning It is an error if the two edges are not in order!

    83     DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {

    84       gr = P.gr;

    85       edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);

    86     }

    88     /// Length of the path.

    89     size_t length() const { return edges.size(); }

    90     /// Returns whether the path is empty.

    91     bool empty() const { return edges.empty(); }

    93     /// Resets the path to an empty path.

    94     void clear() { edges.clear(); }

    96     /// \brief Starting point of the path.

    97     ///

    98     /// Starting point of the path.

    99     /// Returns INVALID if the path is empty.

   100     GraphNode tail() const {

   101       return empty() ? INVALID : gr->tail(edges[0]);

   102     }

   103     /// \brief End point of the path.

   104     ///

   105     /// End point of the path.

   106     /// Returns INVALID if the path is empty.

   107     GraphNode head() const {

   108       return empty() ? INVALID : gr->head(edges[length()-1]);

   109     }

   111     /// \brief Initializes node or edge iterator to point to the first

   112     /// node or edge.

   113     ///

   114     /// \sa nth

   115     template<typename It>

   116     It& first(It &i) const { return i=It(*this); }

   118     /// \brief Initializes node iterator to point to the node of a given index.

   119     NodeIt& nth(NodeIt &i, int n) const {

   120       return i=NodeIt(*this, n);

   121     }

   123     /// \brief Initializes edge iterator to point to the edge of a given index.

   124     EdgeIt& nth(EdgeIt &i, int n) const {

   125       return i=EdgeIt(*this, n);

   126     }

   128     /// Checks validity of a node or edge iterator.

   129     template<typename It>

   130     static

   131     bool valid(const It &i) { return i.valid(); }

   133     /// Steps the given node or edge iterator.

   134     template<typename It>

   135     static

   136     It& next(It &e) {

   137       return ++e;

   138     }

   140     /// \brief Returns node iterator pointing to the head node of the

   141     /// given edge iterator.

   142     NodeIt head(const EdgeIt& e) const {

   143       return NodeIt(*this, e.idx+1);

   144     }

   146     /// \brief Returns node iterator pointing to the tail node of the

   147     /// given edge iterator.

   148     NodeIt tail(const EdgeIt& e) const {

   149       return NodeIt(*this, e.idx);

   150     }

   153     /* Iterator classes */

   155     /**

   156      * \brief Iterator class to iterate on the edges of the paths

   157      *

   158      * \ingroup paths

   159      * This class is used to iterate on the edges of the paths

   160      *

   161      * Of course it converts to Graph::Edge

   162      *

   163      * \todo Its interface differs from the standard edge iterator.

   164      * Yes, it shouldn't.

   165      */

   166     class EdgeIt {

   167       friend class DirPath;

   169       int idx;

   170       const DirPath *p;

   171     public:

   172       /// Default constructor

   173       EdgeIt() {}

   174       /// Invalid constructor

   175       EdgeIt(Invalid) : idx(-1), p(0) {}

   176       /// Constructor with starting point

   177       EdgeIt(const DirPath &_p, int _idx = 0) :

   178 	idx(_idx), p(&_p) { validate(); }

   180       ///Validity check

   181       bool valid() const { return idx!=-1; }

   183       ///Conversion to Graph::Edge

   184       operator GraphEdge () const {

   185 	return valid() ? p->edges[idx] : INVALID;

   186       }

   188       /// Next edge

   189       EdgeIt& operator++() { ++idx; validate(); return *this; }

   191       /// Comparison operator

   192       bool operator==(const EdgeIt& e) const { return idx==e.idx; }

   193       /// Comparison operator

   194       bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }

   195       /// Comparison operator

   196       bool operator<(const EdgeIt& e) const { return idx<e.idx; }

   198     private:

   199       // FIXME: comparison between signed and unsigned...

   200       // Jo ez igy? Vagy esetleg legyen a length() int?

   201       void validate() { if( size_t(idx) >= p->length() ) idx=-1; }

   202     };

   204     /**

   205      * \brief Iterator class to iterate on the nodes of the paths

   206      *

   207      * \ingroup paths

   208      * This class is used to iterate on the nodes of the paths

   209      *

   210      * Of course it converts to Graph::Node

   211      *

   212      * \todo Its interface differs from the standard node iterator.

   213      * Yes, it shouldn't.

   214      */

   215     class NodeIt {

   216       friend class DirPath;

   218       int idx;

   219       const DirPath *p;

   220     public:

   221       /// Default constructor

   222       NodeIt() {}

   223       /// Invalid constructor

   224       NodeIt(Invalid) : idx(-1), p(0) {}

   225       /// Constructor with starting point

   226       NodeIt(const DirPath &_p, int _idx = 0) :

   227 	idx(_idx), p(&_p) { validate(); }

   229       ///Validity check

   230       bool valid() const { return idx!=-1; }

   232       ///Conversion to Graph::Node

   233       operator const GraphNode& () const {

   234 	if(idx >= p->length())

   235 	  return p->head();

   236 	else if(idx >= 0)

   237 	  return p->gr->tail(p->edges[idx]);

   238 	else

   239 	  return INVALID;

   240       }

   241       /// Next node

   242       NodeIt& operator++() { ++idx; validate(); return *this; }

   244       /// Comparison operator

   245       bool operator==(const NodeIt& e) const { return idx==e.idx; }

   246       /// Comparison operator

   247       bool operator!=(const NodeIt& e) const { return idx!=e.idx; }

   248       /// Comparison operator

   249       bool operator<(const NodeIt& e) const { return idx<e.idx; }

   251     private:

   252       void validate() { if( size_t(idx) > p->length() ) idx=-1; }

   253     };

   255     friend class Builder;

   257     /**

   258      * \brief Class to build paths

   259      *

   260      * \ingroup paths

   261      * This class is used to fill a path with edges.

   262      *

   263      * You can push new edges to the front and to the back of the path in

   264      * arbitrary order then you should commit these changes to the graph.

   265      *

   266      * Fundamentally, for most "Paths" (classes fulfilling the

   267      * PathConcept) while the builder is active (after the first modifying

   268      * operation and until the commit()) the original Path is in a

   269      * "transitional" state (operations on it have undefined result). But

   270      * in the case of DirPath the original path remains unchanged until the

   271      * commit. However we don't recomend that you use this feature.

   272      */

   273     class Builder {

   274       DirPath &P;

   275       Container front, back;

   277     public:

   278       ///\param _P the path you want to fill in.

   279       ///

   280       Builder(DirPath &_P) : P(_P) {}

   282       /// Sets the starting node of the path.

   284       /// Sets the starting node of the path. Edge added to the path

   285       /// afterwards have to be incident to this node.

   286       /// It should be called iff the path is empty and before any call to

   287       /// \ref pushFront() or \ref pushBack()

   288       void setStartNode(const GraphNode &) {}

   290       ///Push a new edge to the front of the path

   292       ///Push a new edge to the front of the path.

   293       ///\sa setStartNode

   294       void pushFront(const GraphEdge& e) {

   295 	front.push_back(e);

   296       }

   298       ///Push a new edge to the back of the path

   300       ///Push a new edge to the back of the path.

   301       ///\sa setStartNode

   302       void pushBack(const GraphEdge& e) {

   303 	back.push_back(e);

   304       }

   306       ///Commit the changes to the path.

   307       void commit() {

   308 	if( !front.empty() || !back.empty() ) {

   309 	  Container tmp;

   310 	  tmp.reserve(front.size()+back.size()+P.length());

   311 	  tmp.insert(tmp.end(), front.rbegin(), front.rend());

   312 	  tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());

   313 	  tmp.insert(tmp.end(), back.begin(), back.end());

   314 	  P.edges.swap(tmp);

   315 	  front.clear();

   316 	  back.clear();

   317 	}

   318       }

   320       ///Reserve storage for the builder in advance.

   322       ///If you know a reasonable upper bound of the number of the edges

   323       ///to add to the front, using this function you can speed up the building.

   325       void reserveFront(size_t r) {front.reserve(r);}

   327       ///Reserve storage for the builder in advance.

   329       ///If you know a reasonable upper bound of the number of the edges

   330       ///to add to the back, using this function you can speed up the building.

   332       void reserveBack(size_t r) {back.reserve(r);}

   334     private:

   335       bool empty() {

   336 	return front.empty() && back.empty() && P.empty();

   337       }

   339       GraphNode tail() const {

   340 	if( ! front.empty() )

   341 	  return P.gr->tail(front[front.size()-1]);

   342 	else if( ! P.empty() )

   343 	  return P.gr->tail(P.edges[0]);

   344 	else if( ! back.empty() )

   345 	  return P.gr->tail(back[0]);

   346 	else

   347 	  return INVALID;

   348       }

   349       GraphNode head() const {

   350 	if( ! back.empty() )

   351 	  return P.gr->head(back[back.size()-1]);

   352 	else if( ! P.empty() )

   353 	  return P.gr->head(P.edges[P.length()-1]);

   354 	else if( ! front.empty() )

   355 	  return P.gr->head(front[0]);

   356 	else

   357 	  return INVALID;

   358       }

   360     };

   362   };

   373   /**********************************************************************/

   376   //! \brief A structure for representing undirected path in a graph.

   377   //!

   378   //! A structure for representing undirected path in a graph. Ie. this is

   379   //! a path in a \e directed graph but the edges should not be directed

   380   //! forward.

   381   //!

   382   //! \param Graph The graph type in which the path is.

   383   //! \param DM DebugMode, defaults to DefaultDebugMode.

   384   //!

   385   //! In a sense, the path can be treated as a graph, for is has \c NodeIt

   386   //! and \c EdgeIt with the same usage. These types converts to the \c Node

   387   //! and \c Edge of the original graph.

   388   //!

   389   //! \todo Thoroughfully check all the range and consistency tests.

   390   template<typename Graph>

   391   class UndirPath {

   392   public:

   393     /// Edge type of the underlying graph.

   394     typedef typename Graph::Edge GraphEdge;

   395      /// Node type of the underlying graph.

   396    typedef typename Graph::Node GraphNode;

   397     class NodeIt;

   398     class EdgeIt;

   400   protected:

   401     const Graph *gr;

   402     typedef std::vector<GraphEdge> Container;

   403     Container edges;

   405   public:

   407     /// \param _G The graph in which the path is.

   408     ///

   409     UndirPath(const Graph &_G) : gr(&_G) {}

   411     /// \brief Subpath constructor.

   412     ///

   413     /// Subpath defined by two nodes.

   414     /// \warning It is an error if the two edges are not in order!

   415     UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {

   416       gr = P.gr;

   417       edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);

   418     }

   420     /// \brief Subpath constructor.

   421     ///

   422     /// Subpath defined by two edges. Contains edges in [a,b)

   423     /// \warning It is an error if the two edges are not in order!

   424     UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {

   425       gr = P.gr;

   426       edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);

   427     }

   429     /// Length of the path.

   430     size_t length() const { return edges.size(); }

   431     /// Returns whether the path is empty.

   432     bool empty() const { return edges.empty(); }

   434     /// Resets the path to an empty path.

   435     void clear() { edges.clear(); }

   437     /// \brief Starting point of the path.

   438     ///

   439     /// Starting point of the path.

   440     /// Returns INVALID if the path is empty.

   441     GraphNode tail() const {

   442       return empty() ? INVALID : gr->tail(edges[0]);

   443     }

   444     /// \brief End point of the path.

   445     ///

   446     /// End point of the path.

   447     /// Returns INVALID if the path is empty.

   448     GraphNode head() const {

   449       return empty() ? INVALID : gr->head(edges[length()-1]);

   450     }

   452     /// \brief Initializes node or edge iterator to point to the first

   453     /// node or edge.

   454     ///

   455     /// \sa nth

   456     template<typename It>

   457     It& first(It &i) const { return i=It(*this); }

   459     /// \brief Initializes node iterator to point to the node of a given index.

   460     NodeIt& nth(NodeIt &i, int n) const {

   461       return i=NodeIt(*this, n);

   462     }

   464     /// \brief Initializes edge iterator to point to the edge of a given index.

   465     EdgeIt& nth(EdgeIt &i, int n) const {

   466       return i=EdgeIt(*this, n);

   467     }

   469     /// Checks validity of a node or edge iterator.

   470     template<typename It>

   471     static

   472     bool valid(const It &i) { return i.valid(); }

   474     /// Steps the given node or edge iterator.

   475     template<typename It>

   476     static

   477     It& next(It &e) {

   478       return ++e;

   479     }

   481     /// \brief Returns node iterator pointing to the head node of the

   482     /// given edge iterator.

   483     NodeIt head(const EdgeIt& e) const {

   484       return NodeIt(*this, e.idx+1);

   485     }

   487     /// \brief Returns node iterator pointing to the tail node of the

   488     /// given edge iterator.

   489     NodeIt tail(const EdgeIt& e) const {

   490       return NodeIt(*this, e.idx);

   491     }

   495     /**

   496      * \brief Iterator class to iterate on the edges of the paths

   497      *

   498      * \ingroup paths

   499      * This class is used to iterate on the edges of the paths

   500      *

   501      * Of course it converts to Graph::Edge

   502      *

   503      * \todo Its interface differs from the standard edge iterator.

   504      * Yes, it shouldn't.

   505      */

   506     class EdgeIt {

   507       friend class UndirPath;

   509       int idx;

   510       const UndirPath *p;

   511     public:

   512       /// Default constructor

   513       EdgeIt() {}

   514       /// Invalid constructor

   515       EdgeIt(Invalid) : idx(-1), p(0) {}

   516       /// Constructor with starting point

   517       EdgeIt(const UndirPath &_p, int _idx = 0) :

   518 	idx(_idx), p(&_p) { validate(); }

   520       ///Validity check

   521       bool valid() const { return idx!=-1; }

   523       ///Conversion to Graph::Edge

   524       operator GraphEdge () const {

   525 	return valid() ? p->edges[idx] : INVALID;

   526       }

   527       /// Next edge

   528      EdgeIt& operator++() { ++idx; validate(); return *this; }

   530       /// Comparison operator

   531       bool operator==(const EdgeIt& e) const { return idx==e.idx; }

   532       /// Comparison operator

   533       bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }

   534       /// Comparison operator

   535       bool operator<(const EdgeIt& e) const { return idx<e.idx; }

   537     private:

   538       // FIXME: comparison between signed and unsigned...

   539       // Jo ez igy? Vagy esetleg legyen a length() int?

   540       void validate() { if( size_t(idx) >= p->length() ) idx=-1; }

   541     };

   543     /**

   544      * \brief Iterator class to iterate on the nodes of the paths

   545      *

   546      * \ingroup paths

   547      * This class is used to iterate on the nodes of the paths

   548      *

   549      * Of course it converts to Graph::Node

   550      *

   551      * \todo Its interface differs from the standard node iterator.

   552      * Yes, it shouldn't.

   553      */

   554     class NodeIt {

   555       friend class UndirPath;

   557       int idx;

   558       const UndirPath *p;

   559     public:

   560       /// Default constructor

   561       NodeIt() {}

   562       /// Invalid constructor

   563       NodeIt(Invalid) : idx(-1), p(0) {}

   564       /// Constructor with starting point

   565       NodeIt(const UndirPath &_p, int _idx = 0) :

   566 	idx(_idx), p(&_p) { validate(); }

   568       ///Validity check

   569       bool valid() const { return idx!=-1; }

   571       ///Conversion to Graph::Node

   572       operator const GraphNode& () const {

   573 	if(idx >= p->length())

   574 	  return p->head();

   575 	else if(idx >= 0)

   576 	  return p->gr->tail(p->edges[idx]);

   577 	else

   578 	  return INVALID;

   579       }

   580       /// Next node

   581       NodeIt& operator++() { ++idx; validate(); return *this; }

   583       /// Comparison operator

   584       bool operator==(const NodeIt& e) const { return idx==e.idx; }

   585       /// Comparison operator

   586       bool operator!=(const NodeIt& e) const { return idx!=e.idx; }

   587        /// Comparison operator

   588      bool operator<(const NodeIt& e) const { return idx<e.idx; }

   590     private:

   591       void validate() { if( size_t(idx) > p->length() ) idx=-1; }

   592     };

   594     friend class Builder;

   596     /**

   597      * \brief Class to build paths

   598      *

   599      * \ingroup paths

   600      * This class is used to fill a path with edges.

   601      *

   602      * You can push new edges to the front and to the back of the path in

   603      * arbitrary order then you should commit these changes to the graph.

   604      *

   605      * Fundamentally, for most "Paths" (classes fulfilling the

   606      * PathConcept) while the builder is active (after the first modifying

   607      * operation and until the commit()) the original Path is in a

   608      * "transitional" state (operations ot it have undefined result). But

   609      * in the case of UndirPath the original path is unchanged until the

   610      * commit. However we don't recomend that you use this feature.

   611      */

   612     class Builder {

   613       UndirPath &P;

   614       Container front, back;

   616     public:

   617       ///\param _P the path you want to fill in.

   618       ///

   619       Builder(UndirPath &_P) : P(_P) {}

   621       /// Sets the starting node of the path.

   623       /// Sets the starting node of the path. Edge added to the path

   624       /// afterwards have to be incident to this node.

   625       /// It should be called iff the path is empty and before any call to

   626       /// \ref pushFront() or \ref pushBack()

   627       void setStartNode(const GraphNode &) {}

   629       ///Push a new edge to the front of the path

   631       ///Push a new edge to the front of the path.

   632       ///\sa setStartNode

   633       void pushFront(const GraphEdge& e) {

   634 	front.push_back(e);

   635       }

   637       ///Push a new edge to the back of the path

   639       ///Push a new edge to the back of the path.

   640       ///\sa setStartNode

   641       void pushBack(const GraphEdge& e) {

   642 	back.push_back(e);

   643       }

   645       ///Commit the changes to the path.

   646       void commit() {

   647 	if( !(front.empty() && back.empty()) ) {

   648 	  Container tmp;

   649 	  tmp.reserve(front.size()+back.size()+P.length());

   650 	  tmp.insert(tmp.end(), front.rbegin(), front.rend());

   651 	  tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());

   652 	  tmp.insert(tmp.end(), back.begin(), back.end());

   653 	  P.edges.swap(tmp);

   654 	  front.clear();

   655 	  back.clear();

   656 	}

   657       }

   660       ///Reserve storage for the builder in advance.

   662       ///If you know a reasonable upper bound of the number of the edges

   663       ///to add to the front, using this function you can speed up the building.

   665       void reserveFront(size_t r) {front.reserve(r);}

   667       ///Reserve storage for the builder in advance.

   669       ///If you know a reasonable upper bound of the number of the edges

   670       ///to add to the back, using this function you can speed up the building.

   672       void reserveBack(size_t r) {back.reserve(r);}

   674     private:

   675       bool empty() {

   676 	return front.empty() && back.empty() && P.empty();

   677       }

   679       GraphNode tail() const {

   680 	if( ! front.empty() )

   681 	  return P.gr->tail(front[front.size()-1]);

   682 	else if( ! P.empty() )

   683 	  return P.gr->tail(P.edges[0]);

   684 	else if( ! back.empty() )

   685 	  return P.gr->tail(back[0]);

   686 	else

   687 	  return INVALID;

   688       }

   689       GraphNode head() const {

   690 	if( ! back.empty() )

   691 	  return P.gr->head(back[back.size()-1]);

   692 	else if( ! P.empty() )

   693 	  return P.gr->head(P.edges[P.length()-1]);

   694 	else if( ! front.empty() )

   695 	  return P.gr->head(front[0]);

   696 	else

   697 	  return INVALID;

   698       }

   700     };

   702   };

   705   ///@}

   707 } // namespace hugo

   709 #endif // HUGO_PATH_H

author	alpar
	Mon, 13 Sep 2004 18:00:26 +0000
changeset 843	d56fad02dc55
parent 835	eb9587f09b42
child 852	d50d89b86870
permissions	-rw-r--r--