33 |
33 |
34 /// \ingroup graph_concepts |
34 /// \ingroup graph_concepts |
35 /// |
35 /// |
36 /// \brief Class describing the concept of directed graphs. |
36 /// \brief Class describing the concept of directed graphs. |
37 /// |
37 /// |
38 /// This class describes the \ref concept "concept" of the |
38 /// This class describes the common interface of all directed |
39 /// immutable directed digraphs. |
39 /// graphs (digraphs). |
40 /// |
40 /// |
41 /// Note that actual digraph implementation like @ref ListDigraph or |
41 /// Like all concept classes, it only provides an interface |
42 /// @ref SmartDigraph may have several additional functionality. |
42 /// without any sensible implementation. So any general algorithm for |
|
43 /// directed graphs should compile with this class, but it will not |
|
44 /// run properly, of course. |
|
45 /// An actual digraph implementation like \ref ListDigraph or |
|
46 /// \ref SmartDigraph may have additional functionality. |
43 /// |
47 /// |
44 /// \sa concept |
48 /// \sa Graph |
45 class Digraph { |
49 class Digraph { |
46 private: |
50 private: |
47 ///Digraphs are \e not copy constructible. Use DigraphCopy() instead. |
51 /// Diraphs are \e not copy constructible. Use DigraphCopy instead. |
48 |
52 Digraph(const Digraph &) {} |
49 ///Digraphs are \e not copy constructible. Use DigraphCopy() instead. |
53 /// \brief Assignment of a digraph to another one is \e not allowed. |
50 /// |
54 /// Use DigraphCopy instead. |
51 Digraph(const Digraph &) {}; |
|
52 ///\brief Assignment of \ref Digraph "Digraph"s to another ones are |
|
53 ///\e not allowed. Use DigraphCopy() instead. |
|
54 |
|
55 ///Assignment of \ref Digraph "Digraph"s to another ones are |
|
56 ///\e not allowed. Use DigraphCopy() instead. |
|
57 |
|
58 void operator=(const Digraph &) {} |
55 void operator=(const Digraph &) {} |
|
56 |
59 public: |
57 public: |
60 ///\e |
58 /// Default constructor. |
61 |
|
62 /// Defalult constructor. |
|
63 |
|
64 /// Defalult constructor. |
|
65 /// |
|
66 Digraph() { } |
59 Digraph() { } |
67 /// Class for identifying a node of the digraph |
60 |
|
61 /// The node type of the digraph |
68 |
62 |
69 /// This class identifies a node of the digraph. It also serves |
63 /// This class identifies a node of the digraph. It also serves |
70 /// as a base class of the node iterators, |
64 /// as a base class of the node iterators, |
71 /// thus they will convert to this type. |
65 /// thus they convert to this type. |
72 class Node { |
66 class Node { |
73 public: |
67 public: |
74 /// Default constructor |
68 /// Default constructor |
75 |
69 |
76 /// @warning The default constructor sets the iterator |
70 /// Default constructor. |
77 /// to an undefined value. |
71 /// \warning It sets the object to an undefined value. |
78 Node() { } |
72 Node() { } |
79 /// Copy constructor. |
73 /// Copy constructor. |
80 |
74 |
81 /// Copy constructor. |
75 /// Copy constructor. |
82 /// |
76 /// |
83 Node(const Node&) { } |
77 Node(const Node&) { } |
84 |
78 |
85 /// Invalid constructor \& conversion. |
79 /// %Invalid constructor \& conversion. |
86 |
80 |
87 /// This constructor initializes the iterator to be invalid. |
81 /// Initializes the object to be invalid. |
88 /// \sa Invalid for more details. |
82 /// \sa Invalid for more details. |
89 Node(Invalid) { } |
83 Node(Invalid) { } |
90 /// Equality operator |
84 /// Equality operator |
91 |
85 |
|
86 /// Equality operator. |
|
87 /// |
92 /// Two iterators are equal if and only if they point to the |
88 /// Two iterators are equal if and only if they point to the |
93 /// same object or both are invalid. |
89 /// same object or both are \c INVALID. |
94 bool operator==(Node) const { return true; } |
90 bool operator==(Node) const { return true; } |
95 |
91 |
96 /// Inequality operator |
92 /// Inequality operator |
97 |
93 |
98 /// \sa operator==(Node n) |
94 /// Inequality operator. |
99 /// |
|
100 bool operator!=(Node) const { return true; } |
95 bool operator!=(Node) const { return true; } |
101 |
96 |
102 /// Artificial ordering operator. |
97 /// Artificial ordering operator. |
103 |
98 |
104 /// To allow the use of digraph descriptors as key type in std::map or |
99 /// Artificial ordering operator. |
105 /// similar associative container we require this. |
100 /// |
106 /// |
101 /// \note This operator only has to define some strict ordering of |
107 /// \note This operator only have to define some strict ordering of |
102 /// the nodes; this order has nothing to do with the iteration |
108 /// the items; this order has nothing to do with the iteration |
103 /// ordering of the nodes. |
109 /// ordering of the items. |
|
110 bool operator<(Node) const { return false; } |
104 bool operator<(Node) const { return false; } |
111 |
105 }; |
112 }; |
106 |
113 |
107 /// Iterator class for the nodes. |
114 /// This iterator goes through each node. |
108 |
115 |
109 /// This iterator goes through each node of the digraph. |
116 /// This iterator goes through each node. |
|
117 /// Its usage is quite simple, for example you can count the number |
110 /// Its usage is quite simple, for example you can count the number |
118 /// of nodes in digraph \c g of type \c Digraph like this: |
111 /// of nodes in a digraph \c g of type \c %Digraph like this: |
119 ///\code |
112 ///\code |
120 /// int count=0; |
113 /// int count=0; |
121 /// for (Digraph::NodeIt n(g); n!=INVALID; ++n) ++count; |
114 /// for (Digraph::NodeIt n(g); n!=INVALID; ++n) ++count; |
122 ///\endcode |
115 ///\endcode |
123 class NodeIt : public Node { |
116 class NodeIt : public Node { |
124 public: |
117 public: |
125 /// Default constructor |
118 /// Default constructor |
126 |
119 |
127 /// @warning The default constructor sets the iterator |
120 /// Default constructor. |
128 /// to an undefined value. |
121 /// \warning It sets the iterator to an undefined value. |
129 NodeIt() { } |
122 NodeIt() { } |
130 /// Copy constructor. |
123 /// Copy constructor. |
131 |
124 |
132 /// Copy constructor. |
125 /// Copy constructor. |
133 /// |
126 /// |
134 NodeIt(const NodeIt& n) : Node(n) { } |
127 NodeIt(const NodeIt& n) : Node(n) { } |
135 /// Invalid constructor \& conversion. |
128 /// %Invalid constructor \& conversion. |
136 |
129 |
137 /// Initialize the iterator to be invalid. |
130 /// Initializes the iterator to be invalid. |
138 /// \sa Invalid for more details. |
131 /// \sa Invalid for more details. |
139 NodeIt(Invalid) { } |
132 NodeIt(Invalid) { } |
140 /// Sets the iterator to the first node. |
133 /// Sets the iterator to the first node. |
141 |
134 |
142 /// Sets the iterator to the first node of \c g. |
135 /// Sets the iterator to the first node of the given digraph. |
143 /// |
136 /// |
144 NodeIt(const Digraph&) { } |
137 explicit NodeIt(const Digraph&) { } |
145 /// Node -> NodeIt conversion. |
138 /// Sets the iterator to the given node. |
146 |
139 |
147 /// Sets the iterator to the node of \c the digraph pointed by |
140 /// Sets the iterator to the given node of the given digraph. |
148 /// the trivial iterator. |
141 /// |
149 /// This feature necessitates that each time we |
|
150 /// iterate the arc-set, the iteration order is the same. |
|
151 NodeIt(const Digraph&, const Node&) { } |
142 NodeIt(const Digraph&, const Node&) { } |
152 /// Next node. |
143 /// Next node. |
153 |
144 |
154 /// Assign the iterator to the next node. |
145 /// Assign the iterator to the next node. |
155 /// |
146 /// |
156 NodeIt& operator++() { return *this; } |
147 NodeIt& operator++() { return *this; } |
157 }; |
148 }; |
158 |
149 |
159 |
150 |
160 /// Class for identifying an arc of the digraph |
151 /// The arc type of the digraph |
161 |
152 |
162 /// This class identifies an arc of the digraph. It also serves |
153 /// This class identifies an arc of the digraph. It also serves |
163 /// as a base class of the arc iterators, |
154 /// as a base class of the arc iterators, |
164 /// thus they will convert to this type. |
155 /// thus they will convert to this type. |
165 class Arc { |
156 class Arc { |
166 public: |
157 public: |
167 /// Default constructor |
158 /// Default constructor |
168 |
159 |
169 /// @warning The default constructor sets the iterator |
160 /// Default constructor. |
170 /// to an undefined value. |
161 /// \warning It sets the object to an undefined value. |
171 Arc() { } |
162 Arc() { } |
172 /// Copy constructor. |
163 /// Copy constructor. |
173 |
164 |
174 /// Copy constructor. |
165 /// Copy constructor. |
175 /// |
166 /// |
176 Arc(const Arc&) { } |
167 Arc(const Arc&) { } |
177 /// Initialize the iterator to be invalid. |
168 /// %Invalid constructor \& conversion. |
178 |
169 |
179 /// Initialize the iterator to be invalid. |
170 /// Initializes the object to be invalid. |
180 /// |
171 /// \sa Invalid for more details. |
181 Arc(Invalid) { } |
172 Arc(Invalid) { } |
182 /// Equality operator |
173 /// Equality operator |
183 |
174 |
|
175 /// Equality operator. |
|
176 /// |
184 /// Two iterators are equal if and only if they point to the |
177 /// Two iterators are equal if and only if they point to the |
185 /// same object or both are invalid. |
178 /// same object or both are \c INVALID. |
186 bool operator==(Arc) const { return true; } |
179 bool operator==(Arc) const { return true; } |
187 /// Inequality operator |
180 /// Inequality operator |
188 |
181 |
189 /// \sa operator==(Arc n) |
182 /// Inequality operator. |
190 /// |
|
191 bool operator!=(Arc) const { return true; } |
183 bool operator!=(Arc) const { return true; } |
192 |
184 |
193 /// Artificial ordering operator. |
185 /// Artificial ordering operator. |
194 |
186 |
195 /// To allow the use of digraph descriptors as key type in std::map or |
187 /// Artificial ordering operator. |
196 /// similar associative container we require this. |
188 /// |
197 /// |
189 /// \note This operator only has to define some strict ordering of |
198 /// \note This operator only have to define some strict ordering of |
190 /// the arcs; this order has nothing to do with the iteration |
199 /// the items; this order has nothing to do with the iteration |
191 /// ordering of the arcs. |
200 /// ordering of the items. |
|
201 bool operator<(Arc) const { return false; } |
192 bool operator<(Arc) const { return false; } |
202 }; |
193 }; |
203 |
194 |
204 /// This iterator goes trough the outgoing arcs of a node. |
195 /// Iterator class for the outgoing arcs of a node. |
205 |
196 |
206 /// This iterator goes trough the \e outgoing arcs of a certain node |
197 /// This iterator goes trough the \e outgoing arcs of a certain node |
207 /// of a digraph. |
198 /// of a digraph. |
208 /// Its usage is quite simple, for example you can count the number |
199 /// Its usage is quite simple, for example you can count the number |
209 /// of outgoing arcs of a node \c n |
200 /// of outgoing arcs of a node \c n |
210 /// in digraph \c g of type \c Digraph as follows. |
201 /// in a digraph \c g of type \c %Digraph as follows. |
211 ///\code |
202 ///\code |
212 /// int count=0; |
203 /// int count=0; |
213 /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count; |
204 /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count; |
214 ///\endcode |
205 ///\endcode |
215 |
|
216 class OutArcIt : public Arc { |
206 class OutArcIt : public Arc { |
217 public: |
207 public: |
218 /// Default constructor |
208 /// Default constructor |
219 |
209 |
220 /// @warning The default constructor sets the iterator |
210 /// Default constructor. |
221 /// to an undefined value. |
211 /// \warning It sets the iterator to an undefined value. |
222 OutArcIt() { } |
212 OutArcIt() { } |
223 /// Copy constructor. |
213 /// Copy constructor. |
224 |
214 |
225 /// Copy constructor. |
215 /// Copy constructor. |
226 /// |
216 /// |
227 OutArcIt(const OutArcIt& e) : Arc(e) { } |
217 OutArcIt(const OutArcIt& e) : Arc(e) { } |
228 /// Initialize the iterator to be invalid. |
218 /// %Invalid constructor \& conversion. |
229 |
219 |
230 /// Initialize the iterator to be invalid. |
220 /// Initializes the iterator to be invalid. |
231 /// |
221 /// \sa Invalid for more details. |
232 OutArcIt(Invalid) { } |
222 OutArcIt(Invalid) { } |
233 /// This constructor sets the iterator to the first outgoing arc. |
223 /// Sets the iterator to the first outgoing arc. |
234 |
224 |
235 /// This constructor sets the iterator to the first outgoing arc of |
225 /// Sets the iterator to the first outgoing arc of the given node. |
236 /// the node. |
226 /// |
237 OutArcIt(const Digraph&, const Node&) { } |
227 OutArcIt(const Digraph&, const Node&) { } |
238 /// Arc -> OutArcIt conversion |
228 /// Sets the iterator to the given arc. |
239 |
229 |
240 /// Sets the iterator to the value of the trivial iterator. |
230 /// Sets the iterator to the given arc of the given digraph. |
241 /// This feature necessitates that each time we |
231 /// |
242 /// iterate the arc-set, the iteration order is the same. |
|
243 OutArcIt(const Digraph&, const Arc&) { } |
232 OutArcIt(const Digraph&, const Arc&) { } |
244 ///Next outgoing arc |
233 /// Next outgoing arc |
245 |
234 |
246 /// Assign the iterator to the next |
235 /// Assign the iterator to the next |
247 /// outgoing arc of the corresponding node. |
236 /// outgoing arc of the corresponding node. |
248 OutArcIt& operator++() { return *this; } |
237 OutArcIt& operator++() { return *this; } |
249 }; |
238 }; |
250 |
239 |
251 /// This iterator goes trough the incoming arcs of a node. |
240 /// Iterator class for the incoming arcs of a node. |
252 |
241 |
253 /// This iterator goes trough the \e incoming arcs of a certain node |
242 /// This iterator goes trough the \e incoming arcs of a certain node |
254 /// of a digraph. |
243 /// of a digraph. |
255 /// Its usage is quite simple, for example you can count the number |
244 /// Its usage is quite simple, for example you can count the number |
256 /// of outgoing arcs of a node \c n |
245 /// of incoming arcs of a node \c n |
257 /// in digraph \c g of type \c Digraph as follows. |
246 /// in a digraph \c g of type \c %Digraph as follows. |
258 ///\code |
247 ///\code |
259 /// int count=0; |
248 /// int count=0; |
260 /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count; |
249 /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count; |
261 ///\endcode |
250 ///\endcode |
262 |
|
263 class InArcIt : public Arc { |
251 class InArcIt : public Arc { |
264 public: |
252 public: |
265 /// Default constructor |
253 /// Default constructor |
266 |
254 |
267 /// @warning The default constructor sets the iterator |
255 /// Default constructor. |
268 /// to an undefined value. |
256 /// \warning It sets the iterator to an undefined value. |
269 InArcIt() { } |
257 InArcIt() { } |
270 /// Copy constructor. |
258 /// Copy constructor. |
271 |
259 |
272 /// Copy constructor. |
260 /// Copy constructor. |
273 /// |
261 /// |
274 InArcIt(const InArcIt& e) : Arc(e) { } |
262 InArcIt(const InArcIt& e) : Arc(e) { } |
275 /// Initialize the iterator to be invalid. |
263 /// %Invalid constructor \& conversion. |
276 |
264 |
277 /// Initialize the iterator to be invalid. |
265 /// Initializes the iterator to be invalid. |
278 /// |
266 /// \sa Invalid for more details. |
279 InArcIt(Invalid) { } |
267 InArcIt(Invalid) { } |
280 /// This constructor sets the iterator to first incoming arc. |
268 /// Sets the iterator to the first incoming arc. |
281 |
269 |
282 /// This constructor set the iterator to the first incoming arc of |
270 /// Sets the iterator to the first incoming arc of the given node. |
283 /// the node. |
271 /// |
284 InArcIt(const Digraph&, const Node&) { } |
272 InArcIt(const Digraph&, const Node&) { } |
285 /// Arc -> InArcIt conversion |
273 /// Sets the iterator to the given arc. |
286 |
274 |
287 /// Sets the iterator to the value of the trivial iterator \c e. |
275 /// Sets the iterator to the given arc of the given digraph. |
288 /// This feature necessitates that each time we |
276 /// |
289 /// iterate the arc-set, the iteration order is the same. |
|
290 InArcIt(const Digraph&, const Arc&) { } |
277 InArcIt(const Digraph&, const Arc&) { } |
291 /// Next incoming arc |
278 /// Next incoming arc |
292 |
279 |
293 /// Assign the iterator to the next inarc of the corresponding node. |
280 /// Assign the iterator to the next |
294 /// |
281 /// incoming arc of the corresponding node. |
295 InArcIt& operator++() { return *this; } |
282 InArcIt& operator++() { return *this; } |
296 }; |
283 }; |
297 /// This iterator goes through each arc. |
284 |
298 |
285 /// Iterator class for the arcs. |
299 /// This iterator goes through each arc of a digraph. |
286 |
|
287 /// This iterator goes through each arc of the digraph. |
300 /// Its usage is quite simple, for example you can count the number |
288 /// Its usage is quite simple, for example you can count the number |
301 /// of arcs in a digraph \c g of type \c Digraph as follows: |
289 /// of arcs in a digraph \c g of type \c %Digraph as follows: |
302 ///\code |
290 ///\code |
303 /// int count=0; |
291 /// int count=0; |
304 /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count; |
292 /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count; |
305 ///\endcode |
293 ///\endcode |
306 class ArcIt : public Arc { |
294 class ArcIt : public Arc { |
307 public: |
295 public: |
308 /// Default constructor |
296 /// Default constructor |
309 |
297 |
310 /// @warning The default constructor sets the iterator |
298 /// Default constructor. |
311 /// to an undefined value. |
299 /// \warning It sets the iterator to an undefined value. |
312 ArcIt() { } |
300 ArcIt() { } |
313 /// Copy constructor. |
301 /// Copy constructor. |
314 |
302 |
315 /// Copy constructor. |
303 /// Copy constructor. |
316 /// |
304 /// |
317 ArcIt(const ArcIt& e) : Arc(e) { } |
305 ArcIt(const ArcIt& e) : Arc(e) { } |
318 /// Initialize the iterator to be invalid. |
306 /// %Invalid constructor \& conversion. |
319 |
307 |
320 /// Initialize the iterator to be invalid. |
308 /// Initializes the iterator to be invalid. |
321 /// |
309 /// \sa Invalid for more details. |
322 ArcIt(Invalid) { } |
310 ArcIt(Invalid) { } |
323 /// This constructor sets the iterator to the first arc. |
311 /// Sets the iterator to the first arc. |
324 |
312 |
325 /// This constructor sets the iterator to the first arc of \c g. |
313 /// Sets the iterator to the first arc of the given digraph. |
326 ///@param g the digraph |
314 /// |
327 ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); } |
315 explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); } |
328 /// Arc -> ArcIt conversion |
316 /// Sets the iterator to the given arc. |
329 |
317 |
330 /// Sets the iterator to the value of the trivial iterator \c e. |
318 /// Sets the iterator to the given arc of the given digraph. |
331 /// This feature necessitates that each time we |
319 /// |
332 /// iterate the arc-set, the iteration order is the same. |
|
333 ArcIt(const Digraph&, const Arc&) { } |
320 ArcIt(const Digraph&, const Arc&) { } |
334 ///Next arc |
321 /// Next arc |
335 |
322 |
336 /// Assign the iterator to the next arc. |
323 /// Assign the iterator to the next arc. |
|
324 /// |
337 ArcIt& operator++() { return *this; } |
325 ArcIt& operator++() { return *this; } |
338 }; |
326 }; |
339 ///Gives back the target node of an arc. |
327 |
340 |
328 /// \brief The source node of the arc. |
341 ///Gives back the target node of an arc. |
329 /// |
342 /// |
330 /// Returns the source node of the given arc. |
|
331 Node source(Arc) const { return INVALID; } |
|
332 |
|
333 /// \brief The target node of the arc. |
|
334 /// |
|
335 /// Returns the target node of the given arc. |
343 Node target(Arc) const { return INVALID; } |
336 Node target(Arc) const { return INVALID; } |
344 ///Gives back the source node of an arc. |
337 |
345 |
338 /// \brief The ID of the node. |
346 ///Gives back the source node of an arc. |
339 /// |
347 /// |
340 /// Returns the ID of the given node. |
348 Node source(Arc) const { return INVALID; } |
|
349 |
|
350 /// \brief Returns the ID of the node. |
|
351 int id(Node) const { return -1; } |
341 int id(Node) const { return -1; } |
352 |
342 |
353 /// \brief Returns the ID of the arc. |
343 /// \brief The ID of the arc. |
|
344 /// |
|
345 /// Returns the ID of the given arc. |
354 int id(Arc) const { return -1; } |
346 int id(Arc) const { return -1; } |
355 |
347 |
356 /// \brief Returns the node with the given ID. |
348 /// \brief The node with the given ID. |
357 /// |
349 /// |
358 /// \pre The argument should be a valid node ID in the graph. |
350 /// Returns the node with the given ID. |
|
351 /// \pre The argument should be a valid node ID in the digraph. |
359 Node nodeFromId(int) const { return INVALID; } |
352 Node nodeFromId(int) const { return INVALID; } |
360 |
353 |
361 /// \brief Returns the arc with the given ID. |
354 /// \brief The arc with the given ID. |
362 /// |
355 /// |
363 /// \pre The argument should be a valid arc ID in the graph. |
356 /// Returns the arc with the given ID. |
|
357 /// \pre The argument should be a valid arc ID in the digraph. |
364 Arc arcFromId(int) const { return INVALID; } |
358 Arc arcFromId(int) const { return INVALID; } |
365 |
359 |
366 /// \brief Returns an upper bound on the node IDs. |
360 /// \brief An upper bound on the node IDs. |
|
361 /// |
|
362 /// Returns an upper bound on the node IDs. |
367 int maxNodeId() const { return -1; } |
363 int maxNodeId() const { return -1; } |
368 |
364 |
369 /// \brief Returns an upper bound on the arc IDs. |
365 /// \brief An upper bound on the arc IDs. |
|
366 /// |
|
367 /// Returns an upper bound on the arc IDs. |
370 int maxArcId() const { return -1; } |
368 int maxArcId() const { return -1; } |
371 |
369 |
372 void first(Node&) const {} |
370 void first(Node&) const {} |
373 void next(Node&) const {} |
371 void next(Node&) const {} |
374 |
372 |