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

     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     /// \brief Returns node iterator pointing to the head node of the

   129     /// given edge iterator.

   130     NodeIt head(const EdgeIt& e) const {

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

   132     }

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

   135     /// given edge iterator.

   136     NodeIt tail(const EdgeIt& e) const {

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

   138     }

   141     /* Iterator classes */

   143     /**

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

   145      *

   146      * \ingroup paths

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

   148      *

   149      * Of course it converts to Graph::Edge

   150      *

   151      */

   152     class EdgeIt {

   153       friend class DirPath;

   155       int idx;

   156       const DirPath *p;

   157     public:

   158       /// Default constructor

   159       EdgeIt() {}

   160       /// Invalid constructor

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

   162       /// Constructor with starting point

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

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

   166       ///Validity check

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

   169       ///Conversion to Graph::Edge

   170       operator GraphEdge () const {

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

   172       }

   174       /// Next edge

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

   177       /// Comparison operator

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

   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; }

   184     private:

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

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

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

   188     };

   190     /**

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

   192      *

   193      * \ingroup paths

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

   195      *

   196      * Of course it converts to Graph::Node

   197      *

   198      */

   199     class NodeIt {

   200       friend class DirPath;

   202       int idx;

   203       const DirPath *p;

   204     public:

   205       /// Default constructor

   206       NodeIt() {}

   207       /// Invalid constructor

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

   209       /// Constructor with starting point

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

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

   213       ///Validity check

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

   216       ///Conversion to Graph::Node

   217       operator const GraphNode& () const {

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

   219 	  return p->head();

   220 	else if(idx >= 0)

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

   222 	else

   223 	  return INVALID;

   224       }

   225       /// Next node

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

   228       /// Comparison operator

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

   230       /// Comparison operator

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

   232       /// Comparison operator

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

   235     private:

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

   237     };

   239     friend class Builder;

   241     /**

   242      * \brief Class to build paths

   243      *

   244      * \ingroup paths

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

   246      *

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

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

   249      *

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

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

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

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

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

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

   256      */

   257     class Builder {

   258       DirPath &P;

   259       Container front, back;

   261     public:

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

   263       ///

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

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

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

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

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

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

   272       void setStartNode(const GraphNode &) {}

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

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

   277       ///\sa setStartNode

   278       void pushFront(const GraphEdge& e) {

   279 	front.push_back(e);

   280       }

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

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

   285       ///\sa setStartNode

   286       void pushBack(const GraphEdge& e) {

   287 	back.push_back(e);

   288       }

   290       ///Commit the changes to the path.

   291       void commit() {

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

   293 	  Container tmp;

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

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

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

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

   298 	  P.edges.swap(tmp);

   299 	  front.clear();

   300 	  back.clear();

   301 	}

   302       }

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

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

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

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

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

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

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

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

   318     private:

   319       bool empty() {

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

   321       }

   323       GraphNode tail() const {

   324 	if( ! front.empty() )

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

   326 	else if( ! P.empty() )

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

   328 	else if( ! back.empty() )

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

   330 	else

   331 	  return INVALID;

   332       }

   333       GraphNode head() const {

   334 	if( ! back.empty() )

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

   336 	else if( ! P.empty() )

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

   338 	else if( ! front.empty() )

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

   340 	else

   341 	  return INVALID;

   342       }

   344     };

   346   };

   357   /**********************************************************************/

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

   361   //!

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

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

   364   //! forward.

   365   //!

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

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

   368   //!

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

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

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

   372   //!

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

   374   template<typename Graph>

   375   class UndirPath {

   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;

   384   protected:

   385     const Graph *gr;

   386     typedef std::vector<GraphEdge> Container;

   387     Container edges;

   389   public:

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

   392     ///

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

   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     UndirPath(const UndirPath &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     }

   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     UndirPath(const UndirPath &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     }

   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(); }

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

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

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

   422     ///

   423     /// Starting point of the path.

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

   425     GraphNode tail() const {

   426       return empty() ? INVALID : gr->tail(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 head() const {

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

   434     }

   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); }

   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     }

   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     }

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

   454     template<typename It>

   455     static

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

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

   459     template<typename It>

   460     static

   461     It& next(It &e) {

   462       return ++e;

   463     }

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

   466     /// given edge iterator.

   467     NodeIt head(const EdgeIt& e) const {

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

   469     }

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

   472     /// given edge iterator.

   473     NodeIt tail(const EdgeIt& e) const {

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

   475     }

   479     /**

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

   481      *

   482      * \ingroup paths

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

   484      *

   485      * Of course it converts to Graph::Edge

   486      *

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

   488      * Yes, it shouldn't.

   489      */

   490     class EdgeIt {

   491       friend class UndirPath;

   493       int idx;

   494       const UndirPath *p;

   495     public:

   496       /// Default constructor

   497       EdgeIt() {}

   498       /// Invalid constructor

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

   500       /// Constructor with starting point

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

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

   504       ///Validity check

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

   507       ///Conversion to Graph::Edge

   508       operator GraphEdge () const {

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

   510       }

   511       /// Next edge

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

   514       /// Comparison operator

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

   516       /// Comparison operator

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

   518       /// Comparison operator

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

   521     private:

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

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

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

   525     };

   527     /**

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

   529      *

   530      * \ingroup paths

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

   532      *

   533      * Of course it converts to Graph::Node

   534      *

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

   536      * Yes, it shouldn't.

   537      */

   538     class NodeIt {

   539       friend class UndirPath;

   541       int idx;

   542       const UndirPath *p;

   543     public:

   544       /// Default constructor

   545       NodeIt() {}

   546       /// Invalid constructor

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

   548       /// Constructor with starting point

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

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

   552       ///Validity check

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

   555       ///Conversion to Graph::Node

   556       operator const GraphNode& () const {

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

   558 	  return p->head();

   559 	else if(idx >= 0)

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

   561 	else

   562 	  return INVALID;

   563       }

   564       /// Next node

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

   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        /// Comparison operator

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

   574     private:

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

   576     };

   578     friend class Builder;

   580     /**

   581      * \brief Class to build paths

   582      *

   583      * \ingroup paths

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

   585      *

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

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

   588      *

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

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

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

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

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

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

   595      */

   596     class Builder {

   597       UndirPath &P;

   598       Container front, back;

   600     public:

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

   602       ///

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

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

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

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

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

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

   611       void setStartNode(const GraphNode &) {}

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

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

   616       ///\sa setStartNode

   617       void pushFront(const GraphEdge& e) {

   618 	front.push_back(e);

   619       }

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

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

   624       ///\sa setStartNode

   625       void pushBack(const GraphEdge& e) {

   626 	back.push_back(e);

   627       }

   629       ///Commit the changes to the path.

   630       void commit() {

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

   632 	  Container tmp;

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

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

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

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

   637 	  P.edges.swap(tmp);

   638 	  front.clear();

   639 	  back.clear();

   640 	}

   641       }

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

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

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

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

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

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

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

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

   658     private:

   659       bool empty() {

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

   661       }

   663       GraphNode tail() const {

   664 	if( ! front.empty() )

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

   666 	else if( ! P.empty() )

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

   668 	else if( ! back.empty() )

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

   670 	else

   671 	  return INVALID;

   672       }

   673       GraphNode head() const {

   674 	if( ! back.empty() )

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

   676 	else if( ! P.empty() )

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

   678 	else if( ! front.empty() )

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

   680 	else

   681 	  return INVALID;

   682       }

   684     };

   686   };

   689   ///@}

   691 } // namespace hugo

   693 #endif // HUGO_PATH_H

author	marci
	Mon, 20 Sep 2004 17:53:33 +0000
changeset 890	3a48bc350e0f
parent 837	2d50d1f045c5
child 900	fc7bc2dacee5
permissions	-rw-r--r--