Branch data Line data Source code
1 : : /* -*- mode: C++; indent-tabs-mode: nil; -*-
2 : : *
3 : : * This file is a part of LEMON, a generic C++ optimization library.
4 : : *
5 : : * Copyright (C) 2003-2010
6 : : * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 : : * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 : : *
9 : : * Permission to use, modify and distribute this software is granted
10 : : * provided that this copyright notice appears in all copies. For
11 : : * precise terms see the accompanying LICENSE file.
12 : : *
13 : : * This software is provided "AS IS" with no warranty of any kind,
14 : : * express or implied, and with no claim as to its suitability for any
15 : : * purpose.
16 : : *
17 : : */
18 : :
19 : : #ifndef LEMON_CONCEPTS_DIGRAPH_H
20 : : #define LEMON_CONCEPTS_DIGRAPH_H
21 : :
22 : : ///\ingroup graph_concepts
23 : : ///\file
24 : : ///\brief The concept of directed graphs.
25 : :
26 : : #include <lemon/core.h>
27 : : #include <lemon/concepts/maps.h>
28 : : #include <lemon/concept_check.h>
29 : : #include <lemon/concepts/graph_components.h>
30 : :
31 : : namespace lemon {
32 : : namespace concepts {
33 : :
34 : : /// \ingroup graph_concepts
35 : : ///
36 : : /// \brief Class describing the concept of directed graphs.
37 : : ///
38 : : /// This class describes the common interface of all directed
39 : : /// graphs (digraphs).
40 : : ///
41 : : /// Like all concept classes, it only provides an interface
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.
47 : : ///
48 : : /// \sa Graph
49 : : class Digraph {
50 : : private:
51 : : /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
52 : : Digraph(const Digraph &) {}
53 : : /// \brief Assignment of a digraph to another one is \e not allowed.
54 : : /// Use DigraphCopy instead.
55 : : void operator=(const Digraph &) {}
56 : :
57 : : public:
58 : : /// Default constructor.
59 : : Digraph() { }
60 : :
61 : : /// The node type of the digraph
62 : :
63 : : /// This class identifies a node of the digraph. It also serves
64 : : /// as a base class of the node iterators,
65 : : /// thus they convert to this type.
66 : : class Node {
67 : : public:
68 : : /// Default constructor
69 : :
70 : : /// Default constructor.
71 : : /// \warning It sets the object to an undefined value.
72 : : Node() { }
73 : : /// Copy constructor.
74 : :
75 : : /// Copy constructor.
76 : : ///
77 : : Node(const Node&) { }
78 : :
79 : : /// %Invalid constructor \& conversion.
80 : :
81 : : /// Initializes the object to be invalid.
82 : : /// \sa Invalid for more details.
83 : : Node(Invalid) { }
84 : : /// Equality operator
85 : :
86 : : /// Equality operator.
87 : : ///
88 : : /// Two iterators are equal if and only if they point to the
89 : : /// same object or both are \c INVALID.
90 : : bool operator==(Node) const { return true; }
91 : :
92 : : /// Inequality operator
93 : :
94 : : /// Inequality operator.
95 : : bool operator!=(Node) const { return true; }
96 : :
97 : : /// Artificial ordering operator.
98 : :
99 : : /// Artificial ordering operator.
100 : : ///
101 : : /// \note This operator only has to define some strict ordering of
102 : : /// the nodes; this order has nothing to do with the iteration
103 : : /// ordering of the nodes.
104 : : bool operator<(Node) const { return false; }
105 : : };
106 : :
107 : : /// Iterator class for the nodes.
108 : :
109 : : /// This iterator goes through each node of the digraph.
110 : : /// Its usage is quite simple, for example, you can count the number
111 : : /// of nodes in a digraph \c g of type \c %Digraph like this:
112 : : ///\code
113 : : /// int count=0;
114 : : /// for (Digraph::NodeIt n(g); n!=INVALID; ++n) ++count;
115 : : ///\endcode
116 : : class NodeIt : public Node {
117 : : public:
118 : : /// Default constructor
119 : :
120 : : /// Default constructor.
121 : : /// \warning It sets the iterator to an undefined value.
122 : : NodeIt() { }
123 : : /// Copy constructor.
124 : :
125 : : /// Copy constructor.
126 : : ///
127 : : NodeIt(const NodeIt& n) : Node(n) { }
128 : : /// %Invalid constructor \& conversion.
129 : :
130 : : /// Initializes the iterator to be invalid.
131 : : /// \sa Invalid for more details.
132 : : NodeIt(Invalid) { }
133 : : /// Sets the iterator to the first node.
134 : :
135 : : /// Sets the iterator to the first node of the given digraph.
136 : : ///
137 : : explicit NodeIt(const Digraph&) { }
138 : : /// Sets the iterator to the given node.
139 : :
140 : : /// Sets the iterator to the given node of the given digraph.
141 : : ///
142 : : NodeIt(const Digraph&, const Node&) { }
143 : : /// Next node.
144 : :
145 : : /// Assign the iterator to the next node.
146 : : ///
147 : : NodeIt& operator++() { return *this; }
148 : : };
149 : :
150 : :
151 : : /// The arc type of the digraph
152 : :
153 : : /// This class identifies an arc of the digraph. It also serves
154 : : /// as a base class of the arc iterators,
155 : : /// thus they will convert to this type.
156 : : class Arc {
157 : : public:
158 : : /// Default constructor
159 : :
160 : : /// Default constructor.
161 : : /// \warning It sets the object to an undefined value.
162 : : Arc() { }
163 : : /// Copy constructor.
164 : :
165 : : /// Copy constructor.
166 : : ///
167 : : Arc(const Arc&) { }
168 : : /// %Invalid constructor \& conversion.
169 : :
170 : : /// Initializes the object to be invalid.
171 : : /// \sa Invalid for more details.
172 : : Arc(Invalid) { }
173 : : /// Equality operator
174 : :
175 : : /// Equality operator.
176 : : ///
177 : : /// Two iterators are equal if and only if they point to the
178 : : /// same object or both are \c INVALID.
179 : : bool operator==(Arc) const { return true; }
180 : : /// Inequality operator
181 : :
182 : : /// Inequality operator.
183 : : bool operator!=(Arc) const { return true; }
184 : :
185 : : /// Artificial ordering operator.
186 : :
187 : : /// Artificial ordering operator.
188 : : ///
189 : : /// \note This operator only has to define some strict ordering of
190 : : /// the arcs; this order has nothing to do with the iteration
191 : : /// ordering of the arcs.
192 : : bool operator<(Arc) const { return false; }
193 : : };
194 : :
195 : : /// Iterator class for the outgoing arcs of a node.
196 : :
197 : : /// This iterator goes trough the \e outgoing arcs of a certain node
198 : : /// of a digraph.
199 : : /// Its usage is quite simple, for example, you can count the number
200 : : /// of outgoing arcs of a node \c n
201 : : /// in a digraph \c g of type \c %Digraph as follows.
202 : : ///\code
203 : : /// int count=0;
204 : : /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
205 : : ///\endcode
206 : : class OutArcIt : public Arc {
207 : : public:
208 : : /// Default constructor
209 : :
210 : : /// Default constructor.
211 : : /// \warning It sets the iterator to an undefined value.
212 : : OutArcIt() { }
213 : : /// Copy constructor.
214 : :
215 : : /// Copy constructor.
216 : : ///
217 : : OutArcIt(const OutArcIt& e) : Arc(e) { }
218 : : /// %Invalid constructor \& conversion.
219 : :
220 : : /// Initializes the iterator to be invalid.
221 : : /// \sa Invalid for more details.
222 : : OutArcIt(Invalid) { }
223 : : /// Sets the iterator to the first outgoing arc.
224 : :
225 : : /// Sets the iterator to the first outgoing arc of the given node.
226 : : ///
227 : : OutArcIt(const Digraph&, const Node&) { }
228 : : /// Sets the iterator to the given arc.
229 : :
230 : : /// Sets the iterator to the given arc of the given digraph.
231 : : ///
232 : : OutArcIt(const Digraph&, const Arc&) { }
233 : : /// Next outgoing arc
234 : :
235 : : /// Assign the iterator to the next
236 : : /// outgoing arc of the corresponding node.
237 : : OutArcIt& operator++() { return *this; }
238 : : };
239 : :
240 : : /// Iterator class for the incoming arcs of a node.
241 : :
242 : : /// This iterator goes trough the \e incoming arcs of a certain node
243 : : /// of a digraph.
244 : : /// Its usage is quite simple, for example, you can count the number
245 : : /// of incoming arcs of a node \c n
246 : : /// in a digraph \c g of type \c %Digraph as follows.
247 : : ///\code
248 : : /// int count=0;
249 : : /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
250 : : ///\endcode
251 : : class InArcIt : public Arc {
252 : : public:
253 : : /// Default constructor
254 : :
255 : : /// Default constructor.
256 : : /// \warning It sets the iterator to an undefined value.
257 : : InArcIt() { }
258 : : /// Copy constructor.
259 : :
260 : : /// Copy constructor.
261 : : ///
262 : : InArcIt(const InArcIt& e) : Arc(e) { }
263 : : /// %Invalid constructor \& conversion.
264 : :
265 : : /// Initializes the iterator to be invalid.
266 : : /// \sa Invalid for more details.
267 : : InArcIt(Invalid) { }
268 : : /// Sets the iterator to the first incoming arc.
269 : :
270 : : /// Sets the iterator to the first incoming arc of the given node.
271 : : ///
272 : : InArcIt(const Digraph&, const Node&) { }
273 : : /// Sets the iterator to the given arc.
274 : :
275 : : /// Sets the iterator to the given arc of the given digraph.
276 : : ///
277 : : InArcIt(const Digraph&, const Arc&) { }
278 : : /// Next incoming arc
279 : :
280 : : /// Assign the iterator to the next
281 : : /// incoming arc of the corresponding node.
282 : : InArcIt& operator++() { return *this; }
283 : : };
284 : :
285 : : /// Iterator class for the arcs.
286 : :
287 : : /// This iterator goes through each arc of the digraph.
288 : : /// Its usage is quite simple, for example, you can count the number
289 : : /// of arcs in a digraph \c g of type \c %Digraph as follows:
290 : : ///\code
291 : : /// int count=0;
292 : : /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
293 : : ///\endcode
294 : : class ArcIt : public Arc {
295 : : public:
296 : : /// Default constructor
297 : :
298 : : /// Default constructor.
299 : : /// \warning It sets the iterator to an undefined value.
300 : : ArcIt() { }
301 : : /// Copy constructor.
302 : :
303 : : /// Copy constructor.
304 : : ///
305 : : ArcIt(const ArcIt& e) : Arc(e) { }
306 : : /// %Invalid constructor \& conversion.
307 : :
308 : : /// Initializes the iterator to be invalid.
309 : : /// \sa Invalid for more details.
310 : : ArcIt(Invalid) { }
311 : : /// Sets the iterator to the first arc.
312 : :
313 : : /// Sets the iterator to the first arc of the given digraph.
314 : : ///
315 : : explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
316 : : /// Sets the iterator to the given arc.
317 : :
318 : : /// Sets the iterator to the given arc of the given digraph.
319 : : ///
320 : : ArcIt(const Digraph&, const Arc&) { }
321 : : /// Next arc
322 : :
323 : : /// Assign the iterator to the next arc.
324 : : ///
325 : : ArcIt& operator++() { return *this; }
326 : : };
327 : :
328 : : /// \brief The source node of the arc.
329 : : ///
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.
336 : : Node target(Arc) const { return INVALID; }
337 : :
338 : : /// \brief The ID of the node.
339 : : ///
340 : : /// Returns the ID of the given node.
341 : : int id(Node) const { return -1; }
342 : :
343 : : /// \brief The ID of the arc.
344 : : ///
345 : : /// Returns the ID of the given arc.
346 : : int id(Arc) const { return -1; }
347 : :
348 : : /// \brief The node with the given ID.
349 : : ///
350 : : /// Returns the node with the given ID.
351 : : /// \pre The argument should be a valid node ID in the digraph.
352 : : Node nodeFromId(int) const { return INVALID; }
353 : :
354 : : /// \brief The arc with the given ID.
355 : : ///
356 : : /// Returns the arc with the given ID.
357 : : /// \pre The argument should be a valid arc ID in the digraph.
358 : : Arc arcFromId(int) const { return INVALID; }
359 : :
360 : : /// \brief An upper bound on the node IDs.
361 : : ///
362 : : /// Returns an upper bound on the node IDs.
363 : : int maxNodeId() const { return -1; }
364 : :
365 : : /// \brief An upper bound on the arc IDs.
366 : : ///
367 : : /// Returns an upper bound on the arc IDs.
368 : : int maxArcId() const { return -1; }
369 : :
370 : : void first(Node&) const {}
371 : : void next(Node&) const {}
372 : :
373 : : void first(Arc&) const {}
374 : : void next(Arc&) const {}
375 : :
376 : :
377 : : void firstIn(Arc&, const Node&) const {}
378 : : void nextIn(Arc&) const {}
379 : :
380 : : void firstOut(Arc&, const Node&) const {}
381 : : void nextOut(Arc&) const {}
382 : :
383 : : // The second parameter is dummy.
384 : : Node fromId(int, Node) const { return INVALID; }
385 : : // The second parameter is dummy.
386 : : Arc fromId(int, Arc) const { return INVALID; }
387 : :
388 : : // Dummy parameter.
389 : : int maxId(Node) const { return -1; }
390 : : // Dummy parameter.
391 : : int maxId(Arc) const { return -1; }
392 : :
393 : : /// \brief The opposite node on the arc.
394 : : ///
395 : : /// Returns the opposite node on the given arc.
396 : : Node oppositeNode(Node, Arc) const { return INVALID; }
397 : :
398 : : /// \brief The base node of the iterator.
399 : : ///
400 : : /// Returns the base node of the given outgoing arc iterator
401 : : /// (i.e. the source node of the corresponding arc).
402 : : Node baseNode(OutArcIt) const { return INVALID; }
403 : :
404 : : /// \brief The running node of the iterator.
405 : : ///
406 : : /// Returns the running node of the given outgoing arc iterator
407 : : /// (i.e. the target node of the corresponding arc).
408 : : Node runningNode(OutArcIt) const { return INVALID; }
409 : :
410 : : /// \brief The base node of the iterator.
411 : : ///
412 : : /// Returns the base node of the given incomming arc iterator
413 : : /// (i.e. the target node of the corresponding arc).
414 : : Node baseNode(InArcIt) const { return INVALID; }
415 : :
416 : : /// \brief The running node of the iterator.
417 : : ///
418 : : /// Returns the running node of the given incomming arc iterator
419 : : /// (i.e. the source node of the corresponding arc).
420 : : Node runningNode(InArcIt) const { return INVALID; }
421 : :
422 : : /// \brief Standard graph map type for the nodes.
423 : : ///
424 : : /// Standard graph map type for the nodes.
425 : : /// It conforms to the ReferenceMap concept.
426 : : template<class T>
427 : : class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
428 : : public:
429 : :
430 : : /// Constructor
431 : : explicit NodeMap(const Digraph&) { }
432 : : /// Constructor with given initial value
433 : : NodeMap(const Digraph&, T) { }
434 : :
435 : : private:
436 : : ///Copy constructor
437 : : NodeMap(const NodeMap& nm) :
438 : : ReferenceMap<Node, T, T&, const T&>(nm) { }
439 : : ///Assignment operator
440 : : template <typename CMap>
441 : : NodeMap& operator=(const CMap&) {
442 : : checkConcept<ReadMap<Node, T>, CMap>();
443 : : return *this;
444 : : }
445 : : };
446 : :
447 : : /// \brief Standard graph map type for the arcs.
448 : : ///
449 : : /// Standard graph map type for the arcs.
450 : : /// It conforms to the ReferenceMap concept.
451 : : template<class T>
452 : : class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
453 : : public:
454 : :
455 : : /// Constructor
456 : : explicit ArcMap(const Digraph&) { }
457 : : /// Constructor with given initial value
458 : : ArcMap(const Digraph&, T) { }
459 : :
460 : : private:
461 : : ///Copy constructor
462 : : ArcMap(const ArcMap& em) :
463 : : ReferenceMap<Arc, T, T&, const T&>(em) { }
464 : : ///Assignment operator
465 : : template <typename CMap>
466 : : ArcMap& operator=(const CMap&) {
467 : : checkConcept<ReadMap<Arc, T>, CMap>();
468 : : return *this;
469 : : }
470 : : };
471 : :
472 : : template <typename _Digraph>
473 : : struct Constraints {
474 : 0 : void constraints() {
475 : 0 : checkConcept<BaseDigraphComponent, _Digraph>();
476 : 0 : checkConcept<IterableDigraphComponent<>, _Digraph>();
477 : 0 : checkConcept<IDableDigraphComponent<>, _Digraph>();
478 : 0 : checkConcept<MappableDigraphComponent<>, _Digraph>();
479 : 0 : }
480 : : };
481 : :
482 : : };
483 : :
484 : : } //namespace concepts
485 : : } //namespace lemon
486 : :
487 : :
488 : :
489 : : #endif
|
