3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_CONCEPT_DIGRAPH_H
20 #define LEMON_CONCEPT_DIGRAPH_H
22 ///\ingroup graph_concepts
24 ///\brief The concept of directed graphs.
26 #include <lemon/bits/invalid.h>
27 #include <lemon/bits/utility.h>
28 #include <lemon/concepts/maps.h>
29 #include <lemon/concept_check.h>
30 #include <lemon/concepts/graph_components.h>
35 /// \ingroup graph_concepts
37 /// \brief Class describing the concept of directed graphs.
39 /// This class describes the \ref concept "concept" of the
40 /// immutable directed digraphs.
42 /// Note that actual digraph implementation like @ref ListDigraph or
43 /// @ref SmartDigraph may have several additional functionality.
48 ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
50 ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
52 Digraph(const Digraph &) {};
53 ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
54 ///\e not allowed. Use DigraphCopy() instead.
56 ///Assignment of \ref Digraph "Digraph"s to another ones are
57 ///\e not allowed. Use DigraphCopy() instead.
59 void operator=(const Digraph &) {}
63 /// Defalult constructor.
65 /// Defalult constructor.
68 /// Class for identifying a node of the digraph
70 /// This class identifies a node of the digraph. It also serves
71 /// as a base class of the node iterators,
72 /// thus they will convert to this type.
75 /// Default constructor
77 /// @warning The default constructor sets the iterator
78 /// to an undefined value.
86 /// Invalid constructor \& conversion.
88 /// This constructor initializes the iterator to be invalid.
89 /// \sa Invalid for more details.
93 /// Two iterators are equal if and only if they point to the
94 /// same object or both are invalid.
95 bool operator==(Node) const { return true; }
97 /// Inequality operator
99 /// \sa operator==(Node n)
101 bool operator!=(Node) const { return true; }
103 /// Artificial ordering operator.
105 /// To allow the use of digraph descriptors as key type in std::map or
106 /// similar associative container we require this.
108 /// \note This operator only have to define some strict ordering of
109 /// the items; this order has nothing to do with the iteration
110 /// ordering of the items.
111 bool operator<(Node) const { return false; }
115 /// This iterator goes through each node.
117 /// This iterator goes through each node.
118 /// Its usage is quite simple, for example you can count the number
119 /// of nodes in digraph \c g of type \c Digraph like this:
122 /// for (Digraph::NodeIt n(g); n!=INVALID; ++n) ++count;
124 class NodeIt : public Node {
126 /// Default constructor
128 /// @warning The default constructor sets the iterator
129 /// to an undefined value.
131 /// Copy constructor.
133 /// Copy constructor.
135 NodeIt(const NodeIt& n) : Node(n) { }
136 /// Invalid constructor \& conversion.
138 /// Initialize the iterator to be invalid.
139 /// \sa Invalid for more details.
141 /// Sets the iterator to the first node.
143 /// Sets the iterator to the first node of \c g.
145 NodeIt(const Digraph&) { }
146 /// Node -> NodeIt conversion.
148 /// Sets the iterator to the node of \c the digraph pointed by
149 /// the trivial iterator.
150 /// This feature necessitates that each time we
151 /// iterate the arc-set, the iteration order is the same.
152 NodeIt(const Digraph&, const Node&) { }
155 /// Assign the iterator to the next node.
157 NodeIt& operator++() { return *this; }
161 /// Class for identifying an arc of the digraph
163 /// This class identifies an arc of the digraph. It also serves
164 /// as a base class of the arc iterators,
165 /// thus they will convert to this type.
168 /// Default constructor
170 /// @warning The default constructor sets the iterator
171 /// to an undefined value.
173 /// Copy constructor.
175 /// Copy constructor.
178 /// Initialize the iterator to be invalid.
180 /// Initialize the iterator to be invalid.
183 /// Equality operator
185 /// Two iterators are equal if and only if they point to the
186 /// same object or both are invalid.
187 bool operator==(Arc) const { return true; }
188 /// Inequality operator
190 /// \sa operator==(Arc n)
192 bool operator!=(Arc) const { return true; }
194 /// Artificial ordering operator.
196 /// To allow the use of digraph descriptors as key type in std::map or
197 /// similar associative container we require this.
199 /// \note This operator only have to define some strict ordering of
200 /// the items; this order has nothing to do with the iteration
201 /// ordering of the items.
202 bool operator<(Arc) const { return false; }
205 /// This iterator goes trough the outgoing arcs of a node.
207 /// This iterator goes trough the \e outgoing arcs of a certain node
209 /// Its usage is quite simple, for example you can count the number
210 /// of outgoing arcs of a node \c n
211 /// in digraph \c g of type \c Digraph as follows.
214 /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
217 class OutArcIt : public Arc {
219 /// Default constructor
221 /// @warning The default constructor sets the iterator
222 /// to an undefined value.
224 /// Copy constructor.
226 /// Copy constructor.
228 OutArcIt(const OutArcIt& e) : Arc(e) { }
229 /// Initialize the iterator to be invalid.
231 /// Initialize the iterator to be invalid.
233 OutArcIt(Invalid) { }
234 /// This constructor sets the iterator to the first outgoing arc.
236 /// This constructor sets the iterator to the first outgoing arc of
238 OutArcIt(const Digraph&, const Node&) { }
239 /// Arc -> OutArcIt conversion
241 /// Sets the iterator to the value of the trivial iterator.
242 /// This feature necessitates that each time we
243 /// iterate the arc-set, the iteration order is the same.
244 OutArcIt(const Digraph&, const Arc&) { }
247 /// Assign the iterator to the next
248 /// outgoing arc of the corresponding node.
249 OutArcIt& operator++() { return *this; }
252 /// This iterator goes trough the incoming arcs of a node.
254 /// This iterator goes trough the \e incoming arcs of a certain node
256 /// Its usage is quite simple, for example you can count the number
257 /// of outgoing arcs of a node \c n
258 /// in digraph \c g of type \c Digraph as follows.
261 /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
264 class InArcIt : public Arc {
266 /// Default constructor
268 /// @warning The default constructor sets the iterator
269 /// to an undefined value.
271 /// Copy constructor.
273 /// Copy constructor.
275 InArcIt(const InArcIt& e) : Arc(e) { }
276 /// Initialize the iterator to be invalid.
278 /// Initialize the iterator to be invalid.
281 /// This constructor sets the iterator to first incoming arc.
283 /// This constructor set the iterator to the first incoming arc of
285 InArcIt(const Digraph&, const Node&) { }
286 /// Arc -> InArcIt conversion
288 /// Sets the iterator to the value of the trivial iterator \c e.
289 /// This feature necessitates that each time we
290 /// iterate the arc-set, the iteration order is the same.
291 InArcIt(const Digraph&, const Arc&) { }
292 /// Next incoming arc
294 /// Assign the iterator to the next inarc of the corresponding node.
296 InArcIt& operator++() { return *this; }
298 /// This iterator goes through each arc.
300 /// This iterator goes through each arc of a digraph.
301 /// Its usage is quite simple, for example you can count the number
302 /// of arcs in a digraph \c g of type \c Digraph as follows:
305 /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
307 class ArcIt : public Arc {
309 /// Default constructor
311 /// @warning The default constructor sets the iterator
312 /// to an undefined value.
314 /// Copy constructor.
316 /// Copy constructor.
318 ArcIt(const ArcIt& e) : Arc(e) { }
319 /// Initialize the iterator to be invalid.
321 /// Initialize the iterator to be invalid.
324 /// This constructor sets the iterator to the first arc.
326 /// This constructor sets the iterator to the first arc of \c g.
327 ///@param g the digraph
328 ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
329 /// Arc -> ArcIt conversion
331 /// Sets the iterator to the value of the trivial iterator \c e.
332 /// This feature necessitates that each time we
333 /// iterate the arc-set, the iteration order is the same.
334 ArcIt(const Digraph&, const Arc&) { }
337 /// Assign the iterator to the next arc.
338 ArcIt& operator++() { return *this; }
340 ///Gives back the target node of an arc.
342 ///Gives back the target node of an arc.
344 Node target(Arc) const { return INVALID; }
345 ///Gives back the source node of an arc.
347 ///Gives back the source node of an arc.
349 Node source(Arc) const { return INVALID; }
351 /// \brief Returns the ID of the node.
352 int id(Node) const { return -1; }
354 /// \brief Returns the ID of the arc.
355 int id(Arc) const { return -1; }
357 /// \brief Returns the node with the given ID.
359 /// \pre The argument should be a valid node ID in the graph.
360 Node nodeFromId(int) const { return INVALID; }
362 /// \brief Returns the arc with the given ID.
364 /// \pre The argument should be a valid arc ID in the graph.
365 Arc arcFromId(int) const { return INVALID; }
367 /// \brief Returns an upper bound on the node IDs.
368 int maxNodeId() const { return -1; }
370 /// \brief Returns an upper bound on the arc IDs.
371 int maxArcId() const { return -1; }
373 void first(Node&) const {}
374 void next(Node&) const {}
376 void first(Arc&) const {}
377 void next(Arc&) const {}
380 void firstIn(Arc&, const Node&) const {}
381 void nextIn(Arc&) const {}
383 void firstOut(Arc&, const Node&) const {}
384 void nextOut(Arc&) const {}
386 // The second parameter is dummy.
387 Node fromId(int, Node) const { return INVALID; }
388 // The second parameter is dummy.
389 Arc fromId(int, Arc) const { return INVALID; }
392 int maxId(Node) const { return -1; }
394 int maxId(Arc) const { return -1; }
396 /// \brief The base node of the iterator.
398 /// Gives back the base node of the iterator.
399 /// It is always the target of the pointed arc.
400 Node baseNode(const InArcIt&) const { return INVALID; }
402 /// \brief The running node of the iterator.
404 /// Gives back the running node of the iterator.
405 /// It is always the source of the pointed arc.
406 Node runningNode(const InArcIt&) const { return INVALID; }
408 /// \brief The base node of the iterator.
410 /// Gives back the base node of the iterator.
411 /// It is always the source of the pointed arc.
412 Node baseNode(const OutArcIt&) const { return INVALID; }
414 /// \brief The running node of the iterator.
416 /// Gives back the running node of the iterator.
417 /// It is always the target of the pointed arc.
418 Node runningNode(const OutArcIt&) const { return INVALID; }
420 /// \brief The opposite node on the given arc.
422 /// Gives back the opposite node on the given arc.
423 Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
425 /// \brief Read write map of the nodes to type \c T.
427 /// ReadWrite map of the nodes to type \c T.
430 class NodeMap : public ReadWriteMap< Node, T > {
434 NodeMap(const Digraph&) { }
436 NodeMap(const Digraph&, T) { }
439 NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
440 ///Assignment operator
441 template <typename CMap>
442 NodeMap& operator=(const CMap&) {
443 checkConcept<ReadMap<Node, T>, CMap>();
448 /// \brief Read write map of the arcs to type \c T.
450 /// Reference map of the arcs to type \c T.
453 class ArcMap : public ReadWriteMap<Arc,T> {
457 ArcMap(const Digraph&) { }
459 ArcMap(const Digraph&, T) { }
461 ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
462 ///Assignment operator
463 template <typename CMap>
464 ArcMap& operator=(const CMap&) {
465 checkConcept<ReadMap<Arc, T>, CMap>();
470 template <typename _Digraph>
473 checkConcept<IterableDigraphComponent<>, _Digraph>();
474 checkConcept<IDableDigraphComponent<>, _Digraph>();
475 checkConcept<MappableDigraphComponent<>, _Digraph>();
481 } //namespace concepts
486 #endif // LEMON_CONCEPT_DIGRAPH_H