Removed references to the gui.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
21 ///\brief Classes for representing paths in graphs.
23 ///\todo Iterators have obsolete style
25 #ifndef LEMON_CONCEPT_PATH_H
26 #define LEMON_CONCEPT_PATH_H
28 #include <lemon/bits/invalid.h>
29 #include <lemon/concept_check.h>
33 /// \addtogroup concept
37 //! \brief A skeleton structure for representing directed paths in a graph.
39 //! A skeleton structure for representing directed paths in a graph.
40 //! \param GR The graph type in which the path is.
42 //! In a sense, the path can be treated as a graph, for it has \c NodeIt
43 //! and \c EdgeIt with the same usage. These types converts to the \c Node
44 //! and \c Edge of the original graph.
49 /// Type of the underlying graph.
50 typedef /*typename*/ GR Graph;
51 /// Edge type of the underlying graph.
52 typedef typename Graph::Edge GraphEdge;
53 /// Node type of the underlying graph.
54 typedef typename Graph::Node GraphNode;
58 /// \param _g The graph in which the path is.
60 Path(const Graph &_g) {
61 ignore_unused_variable_warning(_g);
64 /// Length of the path.
65 int length() const {return 0;}
66 /// Returns whether the path is empty.
67 bool empty() const { return true;}
69 /// Resets the path to an empty path.
72 /// \brief Starting point of the path.
74 /// Starting point of the path.
75 /// Returns INVALID if the path is empty.
76 GraphNode/*It*/ target() const {return INVALID;}
77 /// \brief End point of the path.
79 /// End point of the path.
80 /// Returns INVALID if the path is empty.
81 GraphNode/*It*/ source() const {return INVALID;}
83 /// \brief First NodeIt/EdgeIt.
85 /// Initializes node or edge iterator to point to the first
88 It& first(It &i) const { return i=It(*this); }
90 /// \brief The target of an edge.
92 /// Returns node iterator pointing to the target node of the
93 /// given edge iterator.
94 NodeIt target(const EdgeIt&) const {return INVALID;}
96 /// \brief The source of an edge.
98 /// Returns node iterator pointing to the source node of the
99 /// given edge iterator.
100 NodeIt source(const EdgeIt&) const {return INVALID;}
103 /* Iterator classes */
106 * \brief Iterator class to iterate on the edges of the paths
108 * This class is used to iterate on the edges of the paths
110 * Of course it converts to Graph::Edge
115 /// Default constructor
117 /// Invalid constructor
119 /// Constructor with starting point
120 EdgeIt(const Path &) {}
122 operator GraphEdge () const {}
125 EdgeIt& operator++() {return *this;}
127 /// Comparison operator
128 bool operator==(const EdgeIt&) const {return true;}
129 /// Comparison operator
130 bool operator!=(const EdgeIt&) const {return true;}
131 // /// Comparison operator
132 // /// \todo It is not clear what is the "natural" ordering.
133 // bool operator<(const EdgeIt& e) const {}
138 * \brief Iterator class to iterate on the nodes of the paths
140 * This class is used to iterate on the nodes of the paths
142 * Of course it converts to Graph::Node.
147 /// Default constructor
149 /// Invalid constructor
151 /// Constructor with starting point
152 NodeIt(const Path &) {}
154 ///Conversion to Graph::Node
155 operator const GraphNode& () const {}
157 NodeIt& operator++() {return *this;}
159 /// Comparison operator
160 bool operator==(const NodeIt&) const {return true;}
161 /// Comparison operator
162 bool operator!=(const NodeIt&) const {return true;}
163 // /// Comparison operator
164 // /// \todo It is not clear what is the "natural" ordering.
165 // bool operator<(const NodeIt& e) const {}
169 friend class Builder;
172 * \brief Class to build paths
174 * This class is used to fill a path with edges.
176 * You can push new edges to the front and to the back of the path in
177 * arbitrary order then you should commit these changes to the graph.
179 * While the builder is active (after the first modifying
180 * operation and until the call of \ref commit()) the
181 * underlining Path is in a "transitional" state (operations on
182 * it have undefined result).
189 ///\param _p the path you want to fill in.
192 Builder(Path &_p) : P(_p) {}
194 /// Sets the starting node of the path.
196 /// Sets the starting node of the path. Edge added to the path
197 /// afterwards have to be incident to this node.
198 /// You \em must start building an empty path with these functions.
199 /// (And you \em must \em not use it later).
202 void setStartNode(const GraphNode &) {}
204 ///Push a new edge to the front of the path
206 ///Push a new edge to the front of the path.
207 ///If the path is empty, you \em must call \ref setStartNode() before
208 ///the first use of \ref pushFront().
209 void pushFront(const GraphEdge&) {}
211 ///Push a new edge to the back of the path
213 ///Push a new edge to the back of the path.
214 ///If the path is empty, you \em must call \ref setStartNode() before
215 ///the first use of \ref pushBack().
216 void pushBack(const GraphEdge&) {}
218 ///Commit the changes to the path.
221 ///Reserve (front) storage for the builder in advance.
223 ///If you know a reasonable upper bound on the number of the edges
224 ///to add to the front of the path,
225 ///using this function you may speed up the building.
226 void reserveFront(size_t) {}
227 ///Reserve (back) storage for the builder in advance.
229 ///If you know a reasonable upper bound on the number of the edges
230 ///to add to the back of the path,
231 ///using this function you may speed up the building.
232 void reserveBack(size_t) {}
241 #endif // LEMON_CONCEPT_PATH_H