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