33 /// @ref SmartGraph will just refer to this structure. |
33 /// @ref SmartGraph will just refer to this structure. |
34 class StaticGraphSkeleton |
34 class StaticGraphSkeleton |
35 { |
35 { |
36 public: |
36 public: |
37 /// Defalult constructor. |
37 /// Defalult constructor. |
|
38 |
|
39 /// Defalult constructor. |
|
40 /// |
38 StaticGraphSkeleton() { } |
41 StaticGraphSkeleton() { } |
39 ///Copy consructor. |
42 ///Copy consructor. |
40 |
43 |
41 ///\todo It is not clear, what we expect from a copy constructor. |
44 // ///\todo It is not clear, what we expect from a copy constructor. |
42 ///E.g. How to assign the nodes/edges to each other? What about maps? |
45 // ///E.g. How to assign the nodes/edges to each other? What about maps? |
43 StaticGraphSkeleton(const StaticGraphSkeleton& g) { } |
46 // StaticGraphSkeleton(const StaticGraphSkeleton& g) { } |
44 |
47 |
45 /// The base type of node iterators, |
48 /// The base type of node iterators, |
46 /// or in other words, the trivial node iterator. |
49 /// or in other words, the trivial node iterator. |
47 |
50 |
48 /// This is the base type of each node iterator, |
51 /// This is the base type of each node iterator, |
49 /// thus each kind of node iterator converts to this. |
52 /// thus each kind of node iterator converts to this. |
50 /// More precisely each kind of node iterator have to be inherited |
53 /// More precisely each kind of node iterator should be inherited |
51 /// from the trivial node iterator. |
54 /// from the trivial node iterator. |
52 class Node { |
55 class Node { |
53 public: |
56 public: |
|
57 /// Default constructor |
|
58 |
54 /// @warning The default constructor sets the iterator |
59 /// @warning The default constructor sets the iterator |
55 /// to an undefined value. |
60 /// to an undefined value. |
56 Node() { } |
61 Node() { } |
57 /// Copy constructor. |
62 /// Copy constructor. |
|
63 |
|
64 /// Copy constructor. |
|
65 /// |
58 Node(const Node&) { } |
66 Node(const Node&) { } |
|
67 |
59 /// Invalid constructor \& conversion. |
68 /// Invalid constructor \& conversion. |
60 |
69 |
61 /// This constructor initializes the iterator to be invalid. |
70 /// This constructor initializes the iterator to be invalid. |
62 /// \sa Invalid for more details. |
71 /// \sa Invalid for more details. |
63 Node(Invalid) { } |
72 Node(Invalid) { } |
|
73 /// Equality operator |
|
74 |
64 /// Two iterators are equal if and only if they point to the |
75 /// Two iterators are equal if and only if they point to the |
65 /// same object or both are invalid. |
76 /// same object or both are invalid. |
66 bool operator==(Node) const { return true; } |
77 bool operator==(Node) const { return true; } |
67 |
78 |
|
79 /// Inequality operator |
|
80 |
68 /// \sa \ref operator==(Node n) |
81 /// \sa \ref operator==(Node n) |
69 /// |
82 /// |
70 bool operator!=(Node) const { return true; } |
83 bool operator!=(Node) const { return true; } |
71 |
84 |
|
85 ///Comparison operator. |
|
86 |
|
87 ///This is a strict ordering between the nodes. |
|
88 /// |
|
89 ///This ordering can be different from the order in which NodeIt |
|
90 ///goes through the nodes. |
|
91 ///\todo Possibly we don't need it. |
72 bool operator<(Node) const { return true; } |
92 bool operator<(Node) const { return true; } |
73 }; |
93 }; |
74 |
94 |
75 /// This iterator goes through each node. |
95 /// This iterator goes through each node. |
76 |
96 |
77 /// This iterator goes through each node. |
97 /// This iterator goes through each node. |
78 /// Its usage is quite simple, for example you can count the number |
98 /// Its usage is quite simple, for example you can count the number |
79 /// of nodes in graph \c g of type \c Graph like this: |
99 /// of nodes in graph \c g of type \c Graph like this: |
80 /// \code |
100 /// \code |
81 /// int count=0; |
101 /// int count=0; |
82 /// for (Graph::NodeIt n(g); g.valid(n); ++n) ++count; |
102 /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count; |
83 /// \endcode |
103 /// \endcode |
84 class NodeIt : public Node { |
104 class NodeIt : public Node { |
85 public: |
105 public: |
|
106 /// Default constructor |
|
107 |
86 /// @warning The default constructor sets the iterator |
108 /// @warning The default constructor sets the iterator |
87 /// to an undefined value. |
109 /// to an undefined value. |
88 NodeIt() { } |
110 NodeIt() { } |
89 /// Copy constructor. |
111 /// Copy constructor. |
|
112 |
|
113 /// Copy constructor. |
|
114 /// |
90 NodeIt(const NodeIt&) { } |
115 NodeIt(const NodeIt&) { } |
91 /// Invalid constructor \& conversion. |
116 /// Invalid constructor \& conversion. |
92 |
117 |
93 /// Initialize the iterator to be invalid. |
118 /// Initialize the iterator to be invalid. |
94 /// \sa Invalid for more details. |
119 /// \sa Invalid for more details. |
95 NodeIt(Invalid) { } |
120 NodeIt(Invalid) { } |
|
121 /// Sets the iterator to the first node. |
|
122 |
96 /// Sets the iterator to the first node of \c g. |
123 /// Sets the iterator to the first node of \c g. |
|
124 /// |
97 NodeIt(const StaticGraphSkeleton& g) { } |
125 NodeIt(const StaticGraphSkeleton& g) { } |
|
126 /// Node -> NodeIt conversion. |
|
127 |
98 /// Sets the iterator to the node of \c g pointed by the trivial |
128 /// Sets the iterator to the node of \c g pointed by the trivial |
99 /// iterator n. This feature necessitates that each time we |
129 /// iterator n. |
100 /// iterate the node-set, the iteration order is the same. |
130 /// This feature necessitates that each time we |
|
131 /// iterate the edge-set, the iteration order is the same. |
101 NodeIt(const StaticGraphSkeleton& g, const Node& n) { } |
132 NodeIt(const StaticGraphSkeleton& g, const Node& n) { } |
|
133 /// Next node. |
|
134 |
102 /// Assign the iterator to the next node. |
135 /// Assign the iterator to the next node. |
|
136 /// |
103 NodeIt& operator++() { return *this; } |
137 NodeIt& operator++() { return *this; } |
104 }; |
138 }; |
105 |
139 |
106 |
140 |
107 /// The base type of the edge iterators. |
141 /// The base type of the edge iterators. |
|
142 |
|
143 /// The base type of the edge iterators. |
|
144 /// |
108 class Edge { |
145 class Edge { |
109 public: |
146 public: |
|
147 /// Default constructor |
|
148 |
110 /// @warning The default constructor sets the iterator |
149 /// @warning The default constructor sets the iterator |
111 /// to an undefined value. |
150 /// to an undefined value. |
112 Edge() { } |
151 Edge() { } |
113 /// Copy constructor. |
152 /// Copy constructor. |
|
153 |
|
154 /// Copy constructor. |
|
155 /// |
114 Edge(const Edge&) { } |
156 Edge(const Edge&) { } |
115 /// Initialize the iterator to be invalid. |
157 /// Initialize the iterator to be invalid. |
|
158 |
|
159 /// Initialize the iterator to be invalid. |
|
160 /// |
116 Edge(Invalid) { } |
161 Edge(Invalid) { } |
|
162 /// Equality operator |
|
163 |
117 /// Two iterators are equal if and only if they point to the |
164 /// Two iterators are equal if and only if they point to the |
118 /// same object or both are invalid. |
165 /// same object or both are invalid. |
119 bool operator==(Edge) const { return true; } |
166 bool operator==(Edge) const { return true; } |
|
167 /// Inequality operator |
|
168 |
|
169 /// \sa \ref operator==(Node n) |
|
170 /// |
120 bool operator!=(Edge) const { return true; } |
171 bool operator!=(Edge) const { return true; } |
121 bool operator<(Edge) const { return true; } |
172 ///Comparison operator. |
|
173 |
|
174 ///This is a strict ordering between the nodes. |
|
175 /// |
|
176 ///This ordering can be different from the order in which NodeIt |
|
177 ///goes through the nodes. |
|
178 ///\todo Possibly we don't need it. |
|
179 bool operator<(Edge) const { return true; } |
122 }; |
180 }; |
123 |
181 |
124 /// This iterator goes trough the outgoing edges of a node. |
182 /// This iterator goes trough the outgoing edges of a node. |
125 |
183 |
126 /// This iterator goes trough the \e outgoing edges of a certain node |
184 /// This iterator goes trough the \e outgoing edges of a certain node |
128 /// Its usage is quite simple, for example you can count the number |
186 /// Its usage is quite simple, for example you can count the number |
129 /// of outgoing edges of a node \c n |
187 /// of outgoing edges of a node \c n |
130 /// in graph \c g of type \c Graph as follows. |
188 /// in graph \c g of type \c Graph as follows. |
131 /// \code |
189 /// \code |
132 /// int count=0; |
190 /// int count=0; |
133 /// for (Graph::OutEdgeIt e(g, n); g.valid(e); ++e) ++count; |
191 /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count; |
134 /// \endcode |
192 /// \endcode |
135 |
193 |
136 class OutEdgeIt : public Edge { |
194 class OutEdgeIt : public Edge { |
137 public: |
195 public: |
|
196 /// Default constructor |
|
197 |
138 /// @warning The default constructor sets the iterator |
198 /// @warning The default constructor sets the iterator |
139 /// to an undefined value. |
199 /// to an undefined value. |
140 OutEdgeIt() { } |
200 OutEdgeIt() { } |
141 /// Copy constructor. |
201 /// Copy constructor. |
|
202 |
|
203 /// Copy constructor. |
|
204 /// |
142 OutEdgeIt(const OutEdgeIt&) { } |
205 OutEdgeIt(const OutEdgeIt&) { } |
143 /// Initialize the iterator to be invalid. |
206 /// Initialize the iterator to be invalid. |
|
207 |
|
208 /// Initialize the iterator to be invalid. |
|
209 /// |
144 OutEdgeIt(Invalid) { } |
210 OutEdgeIt(Invalid) { } |
145 /// This constructor sets the iterator to first outgoing edge. |
211 /// This constructor sets the iterator to first outgoing edge. |
146 |
212 |
147 /// This constructor set the iterator to the first outgoing edge of |
213 /// This constructor set the iterator to the first outgoing edge of |
148 /// node |
214 /// node |
149 ///@param n the node |
215 ///@param n the node |
150 ///@param g the graph |
216 ///@param g the graph |
151 OutEdgeIt(const StaticGraphSkeleton& g, const Node& n) { } |
217 OutEdgeIt(const StaticGraphSkeleton& g, const Node& n) { } |
|
218 /// Edge -> OutEdgeIt conversion |
|
219 |
152 /// Sets the iterator to the value of the trivial iterator \c e. |
220 /// Sets the iterator to the value of the trivial iterator \c e. |
153 /// This feature necessitates that each time we |
221 /// This feature necessitates that each time we |
154 /// iterate the edge-set, the iteration order is the same. |
222 /// iterate the edge-set, the iteration order is the same. |
155 OutEdgeIt(const StaticGraphSkeleton& g, const Edge& e) { } |
223 OutEdgeIt(const StaticGraphSkeleton& g, const Edge& e) { } |
156 /// Assign the iterator to the next outedge of the corresponding node. |
224 ///Next outgoing edge |
|
225 |
|
226 /// Assign the iterator to the next |
|
227 /// outgoing edge of the corresponding node. |
157 OutEdgeIt& operator++() { return *this; } |
228 OutEdgeIt& operator++() { return *this; } |
158 }; |
229 }; |
159 |
230 |
160 /// This iterator goes trough the incoming edges of a node. |
231 /// This iterator goes trough the incoming edges of a node. |
161 |
232 |
164 /// Its usage is quite simple, for example you can count the number |
235 /// Its usage is quite simple, for example you can count the number |
165 /// of outgoing edges of a node \c n |
236 /// of outgoing edges of a node \c n |
166 /// in graph \c g of type \c Graph as follows. |
237 /// in graph \c g of type \c Graph as follows. |
167 /// \code |
238 /// \code |
168 /// int count=0; |
239 /// int count=0; |
169 /// for(Graph::InEdgeIt e(g, n); g.valid(e); ++) ++count; |
240 /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count; |
170 /// \endcode |
241 /// \endcode |
171 |
242 |
172 class InEdgeIt : public Edge { |
243 class InEdgeIt : public Edge { |
173 public: |
244 public: |
|
245 /// Default constructor |
|
246 |
174 /// @warning The default constructor sets the iterator |
247 /// @warning The default constructor sets the iterator |
175 /// to an undefined value. |
248 /// to an undefined value. |
176 InEdgeIt() { } |
249 InEdgeIt() { } |
177 /// Copy constructor. |
250 /// Copy constructor. |
|
251 |
|
252 /// Copy constructor. |
|
253 /// |
178 InEdgeIt(const InEdgeIt&) { } |
254 InEdgeIt(const InEdgeIt&) { } |
179 /// Initialize the iterator to be invalid. |
255 /// Initialize the iterator to be invalid. |
|
256 |
|
257 /// Initialize the iterator to be invalid. |
|
258 /// |
180 InEdgeIt(Invalid) { } |
259 InEdgeIt(Invalid) { } |
181 /// . |
260 /// This constructor sets the iterator to first incoming edge. |
182 InEdgeIt(const StaticGraphSkeleton&, const Node&) { } |
261 |
183 /// . |
262 /// This constructor set the iterator to the first incoming edge of |
184 InEdgeIt(const StaticGraphSkeleton&, const Edge&) { } |
263 /// node |
|
264 ///@param n the node |
|
265 ///@param g the graph |
|
266 InEdgeIt(const StaticGraphSkeleton& g, const Node& n) { } |
|
267 /// Edge -> InEdgeIt conversion |
|
268 |
|
269 /// Sets the iterator to the value of the trivial iterator \c e. |
|
270 /// This feature necessitates that each time we |
|
271 /// iterate the edge-set, the iteration order is the same. |
|
272 InEdgeIt(const StaticGraphSkeleton& g, const Edge& n) { } |
|
273 /// Next incoming edge |
|
274 |
185 /// Assign the iterator to the next inedge of the corresponding node. |
275 /// Assign the iterator to the next inedge of the corresponding node. |
|
276 /// |
186 InEdgeIt& operator++() { return *this; } |
277 InEdgeIt& operator++() { return *this; } |
187 }; |
278 }; |
188 // class SymEdgeIt : public Edge {}; |
|
189 |
|
190 /// This iterator goes through each edge. |
279 /// This iterator goes through each edge. |
191 |
280 |
192 /// This iterator goes through each edge of a graph. |
281 /// This iterator goes through each edge of a graph. |
193 /// Its usage is quite simple, for example you can count the number |
282 /// Its usage is quite simple, for example you can count the number |
194 /// of edges in a graph \c g of type \c Graph as follows: |
283 /// of edges in a graph \c g of type \c Graph as follows: |
195 /// \code |
284 /// \code |
196 /// int count=0; |
285 /// int count=0; |
197 /// for(Graph::EdgeIt e(g); g.valid(e); ++e) ++count; |
286 /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; |
198 /// \endcode |
287 /// \endcode |
199 class EdgeIt : public Edge { |
288 class EdgeIt : public Edge { |
200 public: |
289 public: |
|
290 /// Default constructor |
|
291 |
201 /// @warning The default constructor sets the iterator |
292 /// @warning The default constructor sets the iterator |
202 /// to an undefined value. |
293 /// to an undefined value. |
203 EdgeIt() { } |
294 EdgeIt() { } |
204 /// Copy constructor. |
295 /// Copy constructor. |
|
296 |
|
297 /// Copy constructor. |
|
298 /// |
205 EdgeIt(const EdgeIt&) { } |
299 EdgeIt(const EdgeIt&) { } |
206 /// Initialize the iterator to be invalid. |
300 /// Initialize the iterator to be invalid. |
|
301 |
|
302 /// Initialize the iterator to be invalid. |
|
303 /// |
207 EdgeIt(Invalid) { } |
304 EdgeIt(Invalid) { } |
208 /// . |
305 /// This constructor sets the iterator to first edge. |
209 EdgeIt(const StaticGraphSkeleton&) { } |
306 |
210 /// . |
307 /// This constructor set the iterator to the first edge of |
|
308 /// node |
|
309 ///@param g the graph |
|
310 EdgeIt(const StaticGraphSkeleton& g) { } |
|
311 /// Edge -> EdgeIt conversion |
|
312 |
|
313 /// Sets the iterator to the value of the trivial iterator \c e. |
|
314 /// This feature necessitates that each time we |
|
315 /// iterate the edge-set, the iteration order is the same. |
211 EdgeIt(const StaticGraphSkeleton&, const Edge&) { } |
316 EdgeIt(const StaticGraphSkeleton&, const Edge&) { } |
|
317 ///Next edge |
|
318 |
|
319 /// Assign the iterator to the next |
|
320 /// edge of the corresponding node. |
212 EdgeIt& operator++() { return *this; } |
321 EdgeIt& operator++() { return *this; } |
213 }; |
322 }; |
214 |
323 |
215 /// First node of the graph. |
324 /// First node of the graph. |
216 |
325 |
218 /// \return the first node. |
327 /// \return the first node. |
219 /// |
328 /// |
220 NodeIt& first(NodeIt& i) const { return i; } |
329 NodeIt& first(NodeIt& i) const { return i; } |
221 |
330 |
222 /// The first incoming edge. |
331 /// The first incoming edge. |
|
332 |
|
333 /// The first incoming edge. |
|
334 /// |
223 InEdgeIt& first(InEdgeIt &i, Node) const { return i; } |
335 InEdgeIt& first(InEdgeIt &i, Node) const { return i; } |
224 /// The first outgoing edge. |
336 /// The first outgoing edge. |
|
337 |
|
338 /// The first outgoing edge. |
|
339 /// |
225 OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; } |
340 OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; } |
226 // SymEdgeIt& first(SymEdgeIt&, Node) const { return i; } |
|
227 /// The first edge of the Graph. |
341 /// The first edge of the Graph. |
|
342 |
|
343 /// The first edge of the Graph. |
|
344 /// |
228 EdgeIt& first(EdgeIt& i) const { return i; } |
345 EdgeIt& first(EdgeIt& i) const { return i; } |
229 |
346 |
230 // Node getNext(Node) const {} |
|
231 // InEdgeIt getNext(InEdgeIt) const {} |
|
232 // OutEdgeIt getNext(OutEdgeIt) const {} |
|
233 // //SymEdgeIt getNext(SymEdgeIt) const {} |
|
234 // EdgeIt getNext(EdgeIt) const {} |
|
235 |
|
236 /// Go to the next node. |
|
237 NodeIt& next(NodeIt& i) const { return i; } |
|
238 /// Go to the next incoming edge. |
|
239 InEdgeIt& next(InEdgeIt& i) const { return i; } |
|
240 /// Go to the next outgoing edge. |
|
241 OutEdgeIt& next(OutEdgeIt& i) const { return i; } |
|
242 //SymEdgeIt& next(SymEdgeIt&) const { } |
|
243 /// Go to the next edge. |
|
244 EdgeIt& next(EdgeIt& i) const { return i; } |
|
245 |
|
246 ///Gives back the head node of an edge. |
347 ///Gives back the head node of an edge. |
|
348 |
|
349 ///Gives back the head node of an edge. |
|
350 /// |
247 Node head(Edge) const { return INVALID; } |
351 Node head(Edge) const { return INVALID; } |
248 ///Gives back the tail node of an edge. |
352 ///Gives back the tail node of an edge. |
|
353 |
|
354 ///Gives back the tail node of an edge. |
|
355 /// |
249 Node tail(Edge) const { return INVALID; } |
356 Node tail(Edge) const { return INVALID; } |
250 |
357 |
251 // Node aNode(InEdgeIt) const {} |
|
252 // Node aNode(OutEdgeIt) const {} |
|
253 // Node aNode(SymEdgeIt) const {} |
|
254 |
|
255 // Node bNode(InEdgeIt) const {} |
|
256 // Node bNode(OutEdgeIt) const {} |
|
257 // Node bNode(SymEdgeIt) const {} |
|
258 |
|
259 /// Checks if a node iterator is valid |
|
260 |
|
261 ///\todo Maybe, it would be better if iterator converted to |
|
262 ///bool directly, as Jacint prefers. |
|
263 bool valid(const Node&) const { return true; } |
|
264 /// Checks if an edge iterator is valid |
|
265 |
|
266 ///\todo Maybe, it would be better if iterator converted to |
|
267 ///bool directly, as Jacint prefers. |
|
268 bool valid(const Edge&) const { return true; } |
|
269 |
|
270 ///Gives back the \e id of a node. |
358 ///Gives back the \e id of a node. |
271 |
359 |
272 ///\warning Not all graph structures provide this feature. |
360 ///\warning Not all graph structures provide this feature. |
273 /// |
361 /// |
|
362 ///\todo Should each graph provide \c id? |
274 int id(const Node&) const { return 0; } |
363 int id(const Node&) const { return 0; } |
275 ///Gives back the \e id of an edge. |
364 ///Gives back the \e id of an edge. |
276 |
365 |
277 ///\warning Not all graph structures provide this feature. |
366 ///\warning Not all graph structures provide this feature. |
278 /// |
367 /// |
|
368 ///\todo Should each graph provide \c id? |
279 int id(const Edge&) const { return 0; } |
369 int id(const Edge&) const { return 0; } |
280 |
370 |
281 /// Resets the graph. |
371 /// . |
282 |
372 |
283 /// This function deletes all edges and nodes of the graph. |
373 ///\todo What is this? |
284 /// It also frees the memory allocated to store them. |
374 /// |
285 void clear() { } |
|
286 |
|
287 int nodeNum() const { return 0; } |
375 int nodeNum() const { return 0; } |
|
376 /// . |
|
377 ///\todo What is this? |
|
378 /// |
288 int edgeNum() const { return 0; } |
379 int edgeNum() const { return 0; } |
289 |
380 |
290 |
381 |
291 ///Reference map of the nodes to type \c T. |
382 ///Reference map of the nodes to type \c T. |
292 |
383 |
293 ///Reference map of the nodes to type \c T. |
384 ///Reference map of the nodes to type \c T. |
294 /// \sa ReferenceSkeleton |
385 /// \sa ReferenceSkeleton |
295 /// \warning Making maps that can handle bool type (NodeMap<bool>) |
386 /// \warning Making maps that can handle bool type (NodeMap<bool>) |
296 /// needs extra attention! |
387 /// needs some extra attention! |
297 |
388 template<class T> class NodeMap: public ReferenceMap< Node, T > |
298 template<class T> class NodeMap |
|
299 : public ReferenceMap< Node, T > |
|
300 { |
389 { |
301 public: |
390 public: |
302 |
391 |
|
392 /// . |
303 NodeMap(const StaticGraphSkeleton&) { } |
393 NodeMap(const StaticGraphSkeleton&) { } |
|
394 /// . |
304 NodeMap(const StaticGraphSkeleton&, T) { } |
395 NodeMap(const StaticGraphSkeleton&, T) { } |
305 |
396 |
306 ///Copy constructor |
397 ///Copy constructor |
307 template<typename TT> NodeMap(const NodeMap<TT>&) { } |
398 template<typename TT> NodeMap(const NodeMap<TT>&) { } |
308 ///Assignment operator |
399 ///Assignment operator |