Correct the english name of EGRES.
2 * src/lemon/concept/path.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 ///\brief Classes for representing paths in graphs.
21 ///\todo Iterators have obsolete style
23 #ifndef LEMON_CONCEPT_PATH_H
24 #define LEMON_CONCEPT_PATH_H
26 #include <lemon/invalid.h>
30 /// \addtogroup concept
34 //! \brief A skeleton structure for representing directed paths in a graph.
36 //! A skeleton structure for representing directed paths in a graph.
37 //! \param GR The graph type in which the path is.
39 //! In a sense, the path can be treated as a graph, for it has \c NodeIt
40 //! and \c EdgeIt with the same usage. These types converts to the \c Node
41 //! and \c Edge of the original graph.
46 /// Type of the underlying graph.
47 typedef /*typename*/ GR Graph;
48 /// Edge type of the underlying graph.
49 typedef typename Graph::Edge GraphEdge;
50 /// Node type of the underlying graph.
51 typedef typename Graph::Node GraphNode;
55 /// \param _G The graph in which the path is.
57 Path(const Graph &_G) {}
59 /// Length of the path.
60 int length() const {return 0;}
61 /// Returns whether the path is empty.
62 bool empty() const { return true;}
64 /// Resets the path to an empty path.
67 /// \brief Starting point of the path.
69 /// Starting point of the path.
70 /// Returns INVALID if the path is empty.
71 GraphNode/*It*/ target() const {return INVALID;}
72 /// \brief End point of the path.
74 /// End point of the path.
75 /// Returns INVALID if the path is empty.
76 GraphNode/*It*/ source() const {return INVALID;}
78 /// \brief First NodeIt/EdgeIt.
80 /// Initializes node or edge iterator to point to the first
83 It& first(It &i) const { return i=It(*this); }
85 /// \brief The target of an edge.
87 /// Returns node iterator pointing to the target node of the
88 /// given edge iterator.
89 NodeIt target(const EdgeIt& e) const {return INVALID;}
91 /// \brief The source of an edge.
93 /// Returns node iterator pointing to the source node of the
94 /// given edge iterator.
95 NodeIt source(const EdgeIt& e) const {return INVALID;}
98 /* Iterator classes */
101 * \brief Iterator class to iterate on the edges of the paths
103 * This class is used to iterate on the edges of the paths
105 * Of course it converts to Graph::Edge
110 /// Default constructor
112 /// Invalid constructor
114 /// Constructor with starting point
115 EdgeIt(const Path &_p) {}
117 operator GraphEdge () const {}
120 EdgeIt& operator++() {return *this;}
122 /// Comparison operator
123 bool operator==(const EdgeIt& e) const {return true;}
124 /// Comparison operator
125 bool operator!=(const EdgeIt& e) const {return true;}
126 // /// Comparison operator
127 // /// \todo It is not clear what is the "natural" ordering.
128 // bool operator<(const EdgeIt& e) const {}
133 * \brief Iterator class to iterate on the nodes of the paths
135 * This class is used to iterate on the nodes of the paths
137 * Of course it converts to Graph::Node.
142 /// Default constructor
144 /// Invalid constructor
146 /// Constructor with starting point
147 NodeIt(const Path &_p) {}
149 ///Conversion to Graph::Node
150 operator const GraphNode& () const {}
152 NodeIt& operator++() {return *this;}
154 /// Comparison operator
155 bool operator==(const NodeIt& e) const {return true;}
156 /// Comparison operator
157 bool operator!=(const NodeIt& e) const {return true;}
158 // /// Comparison operator
159 // /// \todo It is not clear what is the "natural" ordering.
160 // bool operator<(const NodeIt& e) const {}
164 friend class Builder;
167 * \brief Class to build paths
169 * This class is used to fill a path with edges.
171 * You can push new edges to the front and to the back of the path in
172 * arbitrary order then you should commit these changes to the graph.
174 * While the builder is active (after the first modifying
175 * operation and until the call of \ref commit()) the
176 * underlining Path is in a "transitional" state (operations on
177 * it have undefined result).
184 ///\param _P the path you want to fill in.
187 Builder(Path &_p) : P(_p) {}
189 /// Sets the starting node of the path.
191 /// Sets the starting node of the path. Edge added to the path
192 /// afterwards have to be incident to this node.
193 /// You \em must start building an empty path with these functions.
194 /// (And you \em must \em not use it later).
197 void setStartNode(const GraphNode &) {}
199 ///Push a new edge to the front of the path
201 ///Push a new edge to the front of the path.
202 ///If the path is empty, you \em must call \ref setStartNode() before
203 ///the first use of \ref pushFront().
204 void pushFront(const GraphEdge& e) {}
206 ///Push a new edge to the back of the path
208 ///Push a new edge to the back of the path.
209 ///If the path is empty, you \em must call \ref setStartNode() before
210 ///the first use of \ref pushBack().
211 void pushBack(const GraphEdge& e) {}
213 ///Commit the changes to the path.
216 ///Reserve (front) storage for the builder in advance.
218 ///If you know a reasonable upper bound on the number of the edges
219 ///to add to the front of the path,
220 ///using this function you may speed up the building.
221 void reserveFront(size_t r) {}
222 ///Reserve (back) storage for the builder in advance.
224 ///If you know a reasonable upper bound on the number of the edges
225 ///to add to the back of the path,
226 ///using this function you may speed up the building.
227 void reserveBack(size_t r) {}
236 #endif // LEMON_CONCEPT_PATH_H