src/work/peter/path/path_skeleton.h
author alpar
Fri, 01 Apr 2005 14:13:32 +0000
changeset 1292 585674087522
parent 959 c80ef5912903
permissions -rw-r--r--
Options for debugging.
     1 #define SKELETON
     2 // -*- c++ -*- //
     3 
     4 ///\ingroup concept
     5 ///\file
     6 ///\brief Classes for representing paths in graphs.
     7 
     8 #ifndef LEMON_PATH_H
     9 #define LEMON_PATH_H
    10 
    11 #include <lemon/invalid.h>
    12 
    13 namespace lemon {
    14   namespace concept {
    15     /// \addtogroup concept
    16     /// @{
    17     
    18     
    19     //! \brief A skeleton structure for representing directed paths in a graph.
    20     //!
    21     //! A skeleton structure for representing directed paths in a graph.
    22     //! \param GR The graph type in which the path is.
    23     //! 
    24     //! In a sense, the path can be treated as a graph, for is has \c NodeIt
    25     //! and \c EdgeIt with the same usage. These types converts to the \c Node
    26     //! and \c Edge of the original graph.
    27     template<typename GR>
    28     class Path {
    29     public:
    30       
    31       /// Type of the underlying graph.
    32       typedef /*typename*/ GR Graph;
    33       /// Edge type of the underlying graph.
    34       typedef typename Graph::Edge GraphEdge; 
    35       /// Node type of the underlying graph.
    36      typedef typename Graph::Node GraphNode;
    37       class NodeIt;
    38       class EdgeIt;
    39       
    40       /// \param _G The graph in which the path is.
    41       ///
    42       Path(const Graph &_G) {}
    43       
    44       /// Length of the path.
    45       size_t length() const {}
    46       /// Returns whether the path is empty.
    47       bool empty() const {}
    48       
    49       /// Resets the path to an empty path.
    50       void clear() {}
    51 
    52       /// \brief Starting point of the path.
    53       ///
    54       /// Starting point of the path.
    55       /// Returns INVALID if the path is empty.
    56       GraphNode target() const {}
    57       /// \brief End point of the path.
    58       ///
    59       /// End point of the path.
    60       /// Returns INVALID if the path is empty.
    61       GraphNode source() const {}
    62 
    63       /// \brief First NodeIt/EdgeIt.
    64       ///
    65       /// Initializes node or edge iterator to point to the first
    66       /// node or edge.
    67       template<typename It>
    68       It& first(It &i) const { return i=It(*this); }
    69 
    70       /// \brief The target of an edge.
    71       ///
    72       /// Returns node iterator pointing to the target node of the
    73       /// given edge iterator.
    74       NodeIt target(const EdgeIt& e) const {}
    75 
    76       /// \brief The source of an edge.
    77       ///
    78       /// Returns node iterator pointing to the source node of the
    79       /// given edge iterator.
    80       NodeIt source(const EdgeIt& e) const {}
    81 
    82 
    83       /* Iterator classes */
    84 
    85       /**
    86        * \brief Iterator class to iterate on the edges of the paths
    87        * 
    88        * \ingroup concept
    89        * This class is used to iterate on the edges of the paths
    90        *
    91        * Of course it converts to Graph::Edge
    92        * 
    93        */
    94       class EdgeIt {
    95       public:
    96 	/// Default constructor
    97 	EdgeIt() {}
    98 	/// Invalid constructor
    99 	EdgeIt(Invalid) {}
   100 	/// Constructor with starting point
   101 	EdgeIt(const Path &_p) {}
   102 
   103 	operator GraphEdge () const {}
   104 
   105 	/// Next edge
   106 	EdgeIt& operator++() {}
   107 
   108 	/// Comparison operator
   109 	bool operator==(const EdgeIt& e) const {}
   110 	/// Comparison operator
   111 	bool operator!=(const EdgeIt& e) const {}
   112 // 	/// Comparison operator
   113 //      /// \todo It is not clear what is the "natural" ordering.
   114 // 	bool operator<(const EdgeIt& e) const {}
   115 
   116       };
   117 
   118       /**
   119        * \brief Iterator class to iterate on the nodes of the paths
   120        * 
   121        * \ingroup concept
   122        * This class is used to iterate on the nodes of the paths
   123        *
   124        * Of course it converts to Graph::Node.
   125        * 
   126        */
   127       class NodeIt {
   128       public:
   129 	/// Default constructor
   130 	NodeIt() {}
   131 	/// Invalid constructor
   132 	NodeIt(Invalid) {}
   133 	/// Constructor with starting point
   134 	NodeIt(const Path &_p) {}
   135 
   136 	///Conversion to Graph::Node
   137 	operator const GraphNode& () const {}
   138 	/// Next node
   139 	NodeIt& operator++() {}
   140 
   141 	/// Comparison operator
   142 	bool operator==(const NodeIt& e) const {}
   143 	/// Comparison operator
   144 	bool operator!=(const NodeIt& e) const {}
   145 // 	/// Comparison operator
   146 //      /// \todo It is not clear what is the "natural" ordering.
   147 // 	bool operator<(const NodeIt& e) const {}
   148 
   149       };
   150 
   151       friend class Builder;    
   152 
   153       /**
   154        * \brief Class to build paths
   155        * 
   156        * \ingroup concept
   157        * This class is used to fill a path with edges.
   158        *
   159        * You can push new edges to the front and to the back of the path in
   160        * arbitrary order then you should commit these changes to the graph.
   161        *
   162        * While the builder is active (after the first modifying
   163        * operation and until the call of \ref commit())
   164        * the underlining Path is in a
   165        * "transitional" state (operations on it have undefined result).
   166        */
   167       class Builder {
   168       public:
   169 
   170         Path &P;
   171 
   172 	///\param _P the path you want to fill in.
   173 	///
   174 	Builder(Path &_P) : P(_P) {}
   175 
   176 	/// Sets the starting node of the path.
   177       
   178 	/// Sets the starting node of the path. Edge added to the path
   179 	/// afterwards have to be incident to this node.
   180 	/// You \em must start building an empry path with this functions.
   181 	/// (And you \em must \em not use it later).
   182 	/// \sa pushFront()
   183 	/// \sa pushBack()
   184 	void setStartNode(const GraphNode &) {}
   185 
   186 	///Push a new edge to the front of the path
   187 
   188 	///Push a new edge to the front of the path.
   189 	///If the path is empty, you \em must call \ref setStartNode() before
   190 	///the first use of \ref pushFront().
   191 	void pushFront(const GraphEdge& e) {}
   192 
   193 	///Push a new edge to the back of the path
   194 
   195 	///Push a new edge to the back of the path.
   196 	///If the path is empty, you \em must call \ref setStartNode() before
   197 	///the first use of \ref pushBack().
   198 	void pushBack(const GraphEdge& e) {}
   199 
   200 	///Commit the changes to the path.
   201 	void commit() {}
   202 
   203 	///Reserve (front) storage for the builder in advance.
   204 
   205 	///If you know an reasonable upper bound of the number of the edges
   206 	///to add to the front of the path,
   207 	///using this function you may speed up the building.
   208 	void reserveFront(size_t r) {}
   209 	///Reserve (back) storage for the builder in advance.
   210 
   211 	///If you know an reasonable upper bound of the number of the edges
   212 	///to add to the back of the path,
   213 	///using this function you may speed up the building.
   214 	void reserveBack(size_t r) {}
   215       };
   216     };
   217 
   218   ///@}
   219   }
   220   
   221 } // namespace lemon
   222 
   223 #endif // LEMON_PATH_H