10 // @defgroup empty_graph The GraphSkeleton class |
10 // @defgroup empty_graph The GraphSkeleton class |
11 // @{ |
11 // @{ |
12 |
12 |
13 /// An empty graph class. |
13 /// An empty graph class. |
14 |
14 |
15 /// This class provides all the common features of a grapf structure, |
15 /// This class provides all the common features of a graph structure, |
16 /// however completely without implementations or real data structures |
16 /// however completely without implementations and real data structures |
17 /// behind the interface. |
17 /// behind the interface. |
18 /// All graph algorithms should compile with this class, but it will not |
18 /// All graph algorithms should compile with this class, but it will not |
19 /// run properly, of course. |
19 /// run properly, of course. |
20 /// |
20 /// |
21 /// It can be used for checking the interface compatibility, |
21 /// It can be used for checking the interface compatibility, |
29 { |
29 { |
30 public: |
30 public: |
31 |
31 |
32 /// The base type of the node iterators. |
32 /// The base type of the node iterators. |
33 |
33 |
34 /// This \c Node is the base type of each node iterators, |
34 /// This is the base type of each node iterators, |
35 /// thus each kind of node iterator will convert to this. |
35 /// thus each kind of node iterator will convert to this. |
36 class Node { |
36 class Node { |
37 public: |
37 public: |
38 /// @warning The default constructor sets the iterator |
38 /// @warning The default constructor sets the iterator |
39 /// to an undefined value. |
39 /// to an undefined value. |
56 |
56 |
57 bool operator<(Node n) const { return true; } |
57 bool operator<(Node n) const { return true; } |
58 }; |
58 }; |
59 |
59 |
60 /// This iterator goes through each node. |
60 /// This iterator goes through each node. |
|
61 |
|
62 /// This iterator goes through each node. |
|
63 /// Its usage is quite simple, for example you can count the number |
|
64 /// of nodes in graph \c G of type \c Graph like this: |
|
65 /// \code |
|
66 ///int count=0; |
|
67 ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++; |
|
68 /// \endcode |
61 class NodeIt : public Node { |
69 class NodeIt : public Node { |
62 public: |
70 public: |
63 /// @warning The default constructor sets the iterator |
71 /// @warning The default constructor sets the iterator |
64 /// to an undefined value. |
72 /// to an undefined value. |
65 NodeIt() {} //FIXME |
73 NodeIt() {} //FIXME |
89 bool operator==(Edge n) const { return true; } |
97 bool operator==(Edge n) const { return true; } |
90 bool operator!=(Edge n) const { return true; } |
98 bool operator!=(Edge n) const { return true; } |
91 bool operator<(Edge n) const { return true; } |
99 bool operator<(Edge n) const { return true; } |
92 }; |
100 }; |
93 |
101 |
94 /// This iterator goes trought the outgoing edges of a certain graph. |
102 /// This iterator goes trought the outgoing edges of a node. |
|
103 |
|
104 /// This iterator goes trought the \e outgoing edges of a certain node |
|
105 /// of a graph. |
|
106 /// Its usage is quite simple, for example you can count the number |
|
107 /// of outgoing edges of a node \c n |
|
108 /// in graph \c G of type \c Graph as follows. |
|
109 /// \code |
|
110 ///int count=0; |
|
111 ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++; |
|
112 /// \endcode |
95 |
113 |
96 class OutEdgeIt : public Edge { |
114 class OutEdgeIt : public Edge { |
97 public: |
115 public: |
98 /// @warning The default constructor sets the iterator |
116 /// @warning The default constructor sets the iterator |
99 /// to an undefined value. |
117 /// to an undefined value. |
107 ///@param n the node |
125 ///@param n the node |
108 ///@param G the graph |
126 ///@param G the graph |
109 OutEdgeIt(const GraphSkeleton & G, Node n) {} |
127 OutEdgeIt(const GraphSkeleton & G, Node n) {} |
110 }; |
128 }; |
111 |
129 |
|
130 /// This iterator goes trought the incoming edges of a node. |
|
131 |
|
132 /// This iterator goes trought the \e incoming edges of a certain node |
|
133 /// of a graph. |
|
134 /// Its usage is quite simple, for example you can count the number |
|
135 /// of outgoing edges of a node \c n |
|
136 /// in graph \c G of type \c Graph as follows. |
|
137 /// \code |
|
138 ///int count=0; |
|
139 ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++; |
|
140 /// \endcode |
|
141 |
112 class InEdgeIt : public Edge { |
142 class InEdgeIt : public Edge { |
113 public: |
143 public: |
114 /// @warning The default constructor sets the iterator |
144 /// @warning The default constructor sets the iterator |
115 /// to an undefined value. |
145 /// to an undefined value. |
116 InEdgeIt() {} |
146 InEdgeIt() {} |
117 /// Initialize the iterator to be invalid |
147 /// Initialize the iterator to be invalid |
118 InEdgeIt(Invalid) {} |
148 InEdgeIt(Invalid) {} |
119 InEdgeIt(const GraphSkeleton &, Node) {} |
149 InEdgeIt(const GraphSkeleton &, Node) {} |
120 }; |
150 }; |
121 // class SymEdgeIt : public Edge {}; |
151 // class SymEdgeIt : public Edge {}; |
|
152 |
|
153 /// This iterator goes through each edge. |
|
154 |
|
155 /// This iterator goes through each edge of a graph. |
|
156 /// Its usage is quite simple, for example you can count the number |
|
157 /// of edges in a graph \c G of type \c Graph as follows: |
|
158 /// \code |
|
159 ///int count=0; |
|
160 ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++; |
|
161 /// \endcode |
122 class EdgeIt : public Edge { |
162 class EdgeIt : public Edge { |
123 public: |
163 public: |
124 /// @warning The default constructor sets the iterator |
164 /// @warning The default constructor sets the iterator |
125 /// to an undefined value. |
165 /// to an undefined value. |
126 EdgeIt() {} |
166 EdgeIt() {} |
171 // Node bNode(InEdgeIt) const {} |
211 // Node bNode(InEdgeIt) const {} |
172 // Node bNode(OutEdgeIt) const {} |
212 // Node bNode(OutEdgeIt) const {} |
173 // Node bNode(SymEdgeIt) const {} |
213 // Node bNode(SymEdgeIt) const {} |
174 |
214 |
175 /// Checks if a node iterator is valid |
215 /// Checks if a node iterator is valid |
|
216 |
|
217 ///\todo Maybe, it would be better if iterator converted to |
|
218 ///bool directly, as Jacint prefers. |
176 bool valid(const Node) const { return true;} |
219 bool valid(const Node) const { return true;} |
177 /// Checks if an edge iterator is valid |
220 /// Checks if an edge iterator is valid |
|
221 |
|
222 ///\todo Maybe, it would be better if iterator converted to |
|
223 ///bool directly, as Jacint prefers. |
178 bool valid(const Edge) const { return true;} |
224 bool valid(const Edge) const { return true;} |
179 |
225 |
180 ///Gives back the \e id of a node. |
226 ///Gives back the \e id of a node. |
181 |
227 |
182 ///\warning Not all graph structure provide this feature. |
228 ///\warning Not all graph structure provide this feature. |
192 //void setInvalid(Edge &) const {}; |
238 //void setInvalid(Edge &) const {}; |
193 |
239 |
194 ///Add a new node to the graph. |
240 ///Add a new node to the graph. |
195 |
241 |
196 /// \return the new node. |
242 /// \return the new node. |
|
243 /// |
197 Node addNode() { return INVALID;} |
244 Node addNode() { return INVALID;} |
198 ///Add a new edge to the graph. |
245 ///Add a new edge to the graph. |
199 |
246 |
200 ///Add a new edge to the graph with tail node \c tail |
247 ///Add a new edge to the graph with tail node \c tail |
201 ///and head node \c head. |
248 ///and head node \c head. |
225 GraphSkeleton() {} |
272 GraphSkeleton() {} |
226 GraphSkeleton(const GraphSkeleton &G) {} |
273 GraphSkeleton(const GraphSkeleton &G) {} |
227 |
274 |
228 |
275 |
229 |
276 |
230 ///Read/write map of the nodes to type \c T. |
277 ///Read/write/reference map of the nodes to type \c T. |
231 |
278 |
|
279 ///Read/write/reference map of the nodes to type \c T. |
|
280 /// \sa MemoryMapSkeleton |
232 /// \todo We may need copy constructor |
281 /// \todo We may need copy constructor |
233 /// \todo We may need conversion from other nodetype |
282 /// \todo We may need conversion from other nodetype |
234 /// \todo We may need operator= |
283 /// \todo We may need operator= |
235 |
284 |
236 template<class T> class NodeMap |
285 template<class T> class NodeMap |
260 /// |
309 /// |
261 void update() {} |
310 void update() {} |
262 void update(T a) {} //FIXME: Is it necessary |
311 void update(T a) {} //FIXME: Is it necessary |
263 }; |
312 }; |
264 |
313 |
265 ///Read/write map of the edges to type \c T. |
314 ///Read/write/reference map of the edges to type \c T. |
266 |
315 |
267 ///Read/write map of the edges to type \c T. |
316 ///Read/write/reference map of the edges to type \c T. |
268 ///It behaves exactly the same way as \ref NodeMap. |
317 ///It behaves exactly in the same way as \ref NodeMap. |
|
318 /// \sa NodeMap |
|
319 /// \sa MemoryMapSkeleton |
|
320 /// \todo We may need copy constructor |
|
321 /// \todo We may need conversion from other edgetype |
|
322 /// \todo We may need operator= |
269 template<class T> class EdgeMap |
323 template<class T> class EdgeMap |
270 { |
324 { |
271 public: |
325 public: |
272 typedef T ValueType; |
326 typedef T ValueType; |
273 typedef Edge KeyType; |
327 typedef Edge KeyType; |