lemon/concept/path.h
author hegyi
Thu, 17 Nov 2005 15:34:18 +0000
changeset 1814 0f02ced2e2ba
parent 1624 61cc647dac99
child 1875 98698b69a902
permissions -rw-r--r--
As initial value of a new map expression with ()+-/* operators can be given. These operators work on numbers, or on maps. If maps are given, then the new value for a given graph element will be calculated using the value from the given maps that belong to that graph element.
     1 /* -*- C++ -*-
     2  * lemon/concept/path.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 ///\ingroup concept
    18 ///\file
    19 ///\brief Classes for representing paths in graphs.
    20 ///
    21 ///\todo Iterators have obsolete style
    22 
    23 #ifndef LEMON_CONCEPT_PATH_H
    24 #define LEMON_CONCEPT_PATH_H
    25 
    26 #include <lemon/invalid.h>
    27 #include <lemon/concept_check.h>
    28 
    29 namespace lemon {
    30   namespace concept {
    31     /// \addtogroup concept
    32     /// @{
    33 
    34 
    35     //! \brief A skeleton structure for representing directed paths in a graph.
    36     //!
    37     //! A skeleton structure for representing directed paths in a graph.
    38     //! \param GR The graph type in which the path is.
    39     //!
    40     //! In a sense, the path can be treated as a graph, for it has \c NodeIt
    41     //! and \c EdgeIt with the same usage. These types converts to the \c Node
    42     //! and \c Edge of the original graph.
    43     template<typename GR>
    44     class Path {
    45     public:
    46 
    47       /// Type of the underlying graph.
    48       typedef /*typename*/ GR Graph;
    49       /// Edge type of the underlying graph.
    50       typedef typename Graph::Edge GraphEdge;
    51       /// Node type of the underlying graph.
    52      typedef typename Graph::Node GraphNode;
    53       class NodeIt;
    54       class EdgeIt;
    55 
    56       /// \param _g The graph in which the path is.
    57       ///
    58       Path(const Graph &_g) {
    59 	ignore_unused_variable_warning(_g);
    60       }
    61 
    62       /// Length of the path.
    63       int length() const {return 0;}
    64       /// Returns whether the path is empty.
    65       bool empty() const { return true;}
    66 
    67       /// Resets the path to an empty path.
    68       void clear() {}
    69 
    70       /// \brief Starting point of the path.
    71       ///
    72       /// Starting point of the path.
    73       /// Returns INVALID if the path is empty.
    74       GraphNode/*It*/ target() const {return INVALID;}
    75       /// \brief End point of the path.
    76       ///
    77       /// End point of the path.
    78       /// Returns INVALID if the path is empty.
    79       GraphNode/*It*/ source() const {return INVALID;}
    80 
    81       /// \brief First NodeIt/EdgeIt.
    82       ///
    83       /// Initializes node or edge iterator to point to the first
    84       /// node or edge.
    85       template<typename It>
    86       It& first(It &i) const { return i=It(*this); }
    87 
    88       /// \brief The target of an edge.
    89       ///
    90       /// Returns node iterator pointing to the target node of the
    91       /// given edge iterator.
    92       NodeIt target(const EdgeIt&) const {return INVALID;}
    93 
    94       /// \brief The source of an edge.
    95       ///
    96       /// Returns node iterator pointing to the source node of the
    97       /// given edge iterator.
    98       NodeIt source(const EdgeIt&) const {return INVALID;}
    99 
   100 
   101       /* Iterator classes */
   102 
   103       /**
   104        * \brief Iterator class to iterate on the edges of the paths
   105        *
   106        * This class is used to iterate on the edges of the paths
   107        *
   108        * Of course it converts to Graph::Edge
   109        *
   110        */
   111       class EdgeIt {
   112       public:
   113 	/// Default constructor
   114 	EdgeIt() {}
   115 	/// Invalid constructor
   116 	EdgeIt(Invalid) {}
   117 	/// Constructor with starting point
   118 	EdgeIt(const Path &) {}
   119 
   120 	operator GraphEdge () const {}
   121 
   122 	/// Next edge
   123 	EdgeIt& operator++() {return *this;}
   124 
   125 	/// Comparison operator
   126 	bool operator==(const EdgeIt&) const {return true;}
   127 	/// Comparison operator
   128 	bool operator!=(const EdgeIt&) const {return true;}
   129 // 	/// Comparison operator
   130 //      /// \todo It is not clear what is the "natural" ordering.
   131 // 	bool operator<(const EdgeIt& e) const {}
   132 
   133       };
   134 
   135       /**
   136        * \brief Iterator class to iterate on the nodes of the paths
   137        *
   138        * This class is used to iterate on the nodes of the paths
   139        *
   140        * Of course it converts to Graph::Node.
   141        *
   142        */
   143       class NodeIt {
   144       public:
   145 	/// Default constructor
   146 	NodeIt() {}
   147 	/// Invalid constructor
   148 	NodeIt(Invalid) {}
   149 	/// Constructor with starting point
   150 	NodeIt(const Path &) {}
   151 
   152 	///Conversion to Graph::Node
   153 	operator const GraphNode& () const {}
   154 	/// Next node
   155 	NodeIt& operator++() {return *this;}
   156 
   157 	/// Comparison operator
   158 	bool operator==(const NodeIt&) const {return true;}
   159 	/// Comparison operator
   160 	bool operator!=(const NodeIt&) const {return true;}
   161 // 	/// Comparison operator
   162 //      /// \todo It is not clear what is the "natural" ordering.
   163 // 	bool operator<(const NodeIt& e) const {}
   164 
   165       };
   166 
   167       friend class Builder;
   168 
   169       /**
   170        * \brief Class to build paths
   171        *
   172        * This class is used to fill a path with edges.
   173        *
   174        * You can push new edges to the front and to the back of the path in
   175        * arbitrary order then you should commit these changes to the graph.
   176        *
   177        * While the builder is active (after the first modifying
   178        * operation and until the call of \ref commit()) the
   179        * underlining Path is in a "transitional" state (operations on
   180        * it have undefined result).
   181        */
   182       class Builder {
   183       public:
   184 
   185         Path &P;
   186 
   187 	///\param _p the path you want to fill in.
   188 	///
   189 
   190 	Builder(Path &_p) : P(_p) {}
   191 
   192 	/// Sets the starting node of the path.
   193 
   194 	/// Sets the starting node of the path. Edge added to the path
   195 	/// afterwards have to be incident to this node.
   196 	/// You \em must start building an empty path with these functions.
   197 	/// (And you \em must \em not use it later).
   198 	/// \sa pushFront()
   199 	/// \sa pushBack()
   200 	void setStartNode(const GraphNode &) {}
   201 
   202 	///Push a new edge to the front of the path
   203 
   204 	///Push a new edge to the front of the path.
   205 	///If the path is empty, you \em must call \ref setStartNode() before
   206 	///the first use of \ref pushFront().
   207 	void pushFront(const GraphEdge&) {}
   208 
   209 	///Push a new edge to the back of the path
   210 
   211 	///Push a new edge to the back of the path.
   212 	///If the path is empty, you \em must call \ref setStartNode() before
   213 	///the first use of \ref pushBack().
   214 	void pushBack(const GraphEdge&) {}
   215 
   216 	///Commit the changes to the path.
   217 	void commit() {}
   218 
   219 	///Reserve (front) storage for the builder in advance.
   220 
   221 	///If you know a reasonable upper bound on the number of the edges
   222 	///to add to the front of the path,
   223 	///using this function you may speed up the building.
   224 	void reserveFront(size_t) {}
   225 	///Reserve (back) storage for the builder in advance.
   226 
   227 	///If you know a reasonable upper bound on the number of the edges
   228 	///to add to the back of the path,
   229 	///using this function you may speed up the building.
   230 	void reserveBack(size_t) {}
   231       };
   232     };
   233 
   234   ///@}
   235   }
   236 
   237 } // namespace lemon
   238 
   239 #endif // LEMON_CONCEPT_PATH_H