1 #define SKELETON |
|
2 // -*- c++ -*- // |
1 // -*- c++ -*- // |
3 |
2 |
4 ///\ingroup skeletons |
3 ///\ingroup skeletons |
5 ///\file |
4 ///\file |
6 ///\brief Classes for representing paths in graphs. |
5 ///\brief Classes for representing paths in graphs. |
7 |
6 |
8 #ifndef HUGO_PATH_H |
7 #ifndef HUGO_SKELETON_PATH_H |
9 #define HUGO_PATH_H |
8 #define HUGO_SKELETON_PATH_H |
10 |
9 |
11 #include <hugo/invalid.h> |
10 #include <hugo/invalid.h> |
12 |
11 |
13 namespace hugo { |
12 namespace hugo { |
14 namespace skeleton { |
13 namespace skeleton { |
15 /// \addtogroup skeletons |
14 /// \addtogroup skeletons |
16 /// @{ |
15 /// @{ |
17 |
16 |
18 |
17 |
19 //! \brief A skeletom structure for representing directed paths in a graph. |
18 //! \brief A skeletom structure for representing directed paths in a graph. |
20 //! |
19 //! |
21 //! A skeleton structure for representing directed paths in a graph. |
20 //! A skeleton structure for representing directed paths in a graph. |
22 //! \param GR The graph type in which the path is. |
21 //! \param GR The graph type in which the path is. |
23 //! |
22 //! |
24 //! In a sense, the path can be treated as a graph, for is has \c NodeIt |
23 //! 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 |
24 //! and \c EdgeIt with the same usage. These types converts to the \c Node |
26 //! and \c Edge of the original graph. |
25 //! and \c Edge of the original graph. |
27 template<typename GR> |
26 template<typename GR> |
28 class Path { |
27 class Path { |
29 public: |
28 public: |
30 |
29 |
31 /// Type of the underlying graph. |
30 /// Type of the underlying graph. |
32 typedef /*typename*/ GR Graph; |
31 typedef /*typename*/ GR Graph; |
33 /// Edge type of the underlying graph. |
32 /// Edge type of the underlying graph. |
34 typedef typename Graph::Edge GraphEdge; |
33 typedef typename Graph::Edge GraphEdge; |
35 /// Node type of the underlying graph. |
34 /// Node type of the underlying graph. |
36 typedef typename Graph::Node GraphNode; |
35 typedef typename Graph::Node GraphNode; |
37 class NodeIt; |
36 class NodeIt; |
38 class EdgeIt; |
37 class EdgeIt; |
39 |
38 |
40 /// \param _G The graph in which the path is. |
39 /// \param _G The graph in which the path is. |
41 /// |
40 /// |
42 Path(const Graph &_G) {} |
41 Path(const Graph &_G) {} |
43 |
42 |
44 /// Length of the path. |
43 /// Length of the path. |
45 size_t length() const {return 0;} |
44 size_t length() const {return 0;} |
46 /// Returns whether the path is empty. |
45 /// Returns whether the path is empty. |
47 bool empty() const {} |
46 bool empty() const { return true;} |
48 |
47 |
49 /// Resets the path to an empty path. |
48 /// Resets the path to an empty path. |
50 void clear() {} |
49 void clear() {} |
51 |
50 |
52 /// \brief Starting point of the path. |
51 /// \brief Starting point of the path. |
53 /// |
52 /// |
69 |
68 |
70 /// \brief The head of an edge. |
69 /// \brief The head of an edge. |
71 /// |
70 /// |
72 /// Returns node iterator pointing to the head node of the |
71 /// Returns node iterator pointing to the head node of the |
73 /// given edge iterator. |
72 /// given edge iterator. |
74 NodeIt head(const EdgeIt& e) const {} |
73 NodeIt head(const EdgeIt& e) const {return INVALID;} |
75 |
74 |
76 /// \brief The tail of an edge. |
75 /// \brief The tail of an edge. |
77 /// |
76 /// |
78 /// Returns node iterator pointing to the tail node of the |
77 /// Returns node iterator pointing to the tail node of the |
79 /// given edge iterator. |
78 /// given edge iterator. |
80 NodeIt tail(const EdgeIt& e) const {} |
79 NodeIt tail(const EdgeIt& e) const {return INVALID;} |
81 |
80 |
82 |
81 |
83 /* Iterator classes */ |
82 /* Iterator classes */ |
84 |
83 |
85 /** |
84 /** |
86 * \brief Iterator class to iterate on the edges of the paths |
85 * \brief Iterator class to iterate on the edges of the paths |
87 * |
86 * |
88 * \ingroup skeletons |
87 * \ingroup skeletons |
89 * This class is used to iterate on the edges of the paths |
88 * This class is used to iterate on the edges of the paths |
90 * |
89 * |
91 * Of course it converts to Graph::Edge |
90 * Of course it converts to Graph::Edge |
92 * |
91 * |
93 */ |
92 */ |
94 class EdgeIt { |
93 class EdgeIt { |
95 public: |
94 public: |
96 /// Default constructor |
95 /// Default constructor |
97 EdgeIt() {} |
96 EdgeIt() {} |
101 EdgeIt(const Path &_p) {} |
100 EdgeIt(const Path &_p) {} |
102 |
101 |
103 operator GraphEdge () const {} |
102 operator GraphEdge () const {} |
104 |
103 |
105 /// Next edge |
104 /// Next edge |
106 EdgeIt& operator++() {} |
105 EdgeIt& operator++() {return *this;} |
107 |
106 |
108 /// Comparison operator |
107 /// Comparison operator |
109 bool operator==(const EdgeIt& e) const {return true;} |
108 bool operator==(const EdgeIt& e) const {return true;} |
110 /// Comparison operator |
109 /// Comparison operator |
111 bool operator!=(const EdgeIt& e) const {return true;} |
110 bool operator!=(const EdgeIt& e) const {return true;} |
134 NodeIt(const Path &_p) {} |
133 NodeIt(const Path &_p) {} |
135 |
134 |
136 ///Conversion to Graph::Node |
135 ///Conversion to Graph::Node |
137 operator const GraphNode& () const {} |
136 operator const GraphNode& () const {} |
138 /// Next node |
137 /// Next node |
139 NodeIt& operator++() {} |
138 NodeIt& operator++() {return *this;} |
140 |
139 |
141 /// Comparison operator |
140 /// Comparison operator |
142 bool operator==(const NodeIt& e) const {} |
141 bool operator==(const NodeIt& e) const {return true;} |
143 /// Comparison operator |
142 /// Comparison operator |
144 bool operator!=(const NodeIt& e) const {} |
143 bool operator!=(const NodeIt& e) const {return true;} |
145 // /// Comparison operator |
144 // /// Comparison operator |
146 // /// \todo It is not clear what is the "natural" ordering. |
145 // /// \todo It is not clear what is the "natural" ordering. |
147 // bool operator<(const NodeIt& e) const {} |
146 // bool operator<(const NodeIt& e) const {} |
148 |
147 |
149 }; |
148 }; |
150 |
149 |
151 friend class Builder; |
150 friend class Builder; |
152 |
151 |
153 /** |
152 /** |
154 * \brief Class to build paths |
153 * \brief Class to build paths |
155 * |
154 * |
156 * \ingroup skeletons |
155 * \ingroup skeletons |
157 * This class is used to fill a path with edges. |
156 * This class is used to fill a path with edges. |
158 * |
157 * |
159 * You can push new edges to the front and to the back of the path in |
158 * 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. |
159 * arbitrary order then you should commit these changes to the graph. |
172 ///\param _P the path you want to fill in. |
171 ///\param _P the path you want to fill in. |
173 /// |
172 /// |
174 Builder(Path &_P) : P(_P) {} |
173 Builder(Path &_P) : P(_P) {} |
175 |
174 |
176 /// Sets the starting node of the path. |
175 /// Sets the starting node of the path. |
177 |
176 |
178 /// Sets the starting node of the path. Edge added to the path |
177 /// Sets the starting node of the path. Edge added to the path |
179 /// afterwards have to be incident to this node. |
178 /// afterwards have to be incident to this node. |
180 /// You \em must start building an empry path with this functions. |
179 /// You \em must start building an empry path with this functions. |
181 /// (And you \em must \em not use it later). |
180 /// (And you \em must \em not use it later). |
182 /// \sa pushFront() |
181 /// \sa pushFront() |