3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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 void first(Node&) const {}
352 void next(Node&) const {}
354 void first(Arc&) const {}
355 void next(Arc&) const {}
358 void firstIn(Arc&, const Node&) const {}
359 void nextIn(Arc&) const {}
361 void firstOut(Arc&, const Node&) const {}
362 void nextOut(Arc&) const {}
364 /// \brief The base node of the iterator.
366 /// Gives back the base node of the iterator.
367 /// It is always the target of the pointed arc.
368 Node baseNode(const InArcIt&) const { return INVALID; }
370 /// \brief The running node of the iterator.
372 /// Gives back the running node of the iterator.
373 /// It is always the source of the pointed arc.
374 Node runningNode(const InArcIt&) const { return INVALID; }
376 /// \brief The base node of the iterator.
378 /// Gives back the base node of the iterator.
379 /// It is always the source of the pointed arc.
380 Node baseNode(const OutArcIt&) const { return INVALID; }
382 /// \brief The running node of the iterator.
384 /// Gives back the running node of the iterator.
385 /// It is always the target of the pointed arc.
386 Node runningNode(const OutArcIt&) const { return INVALID; }
388 /// \brief The opposite node on the given arc.
390 /// Gives back the opposite node on the given arc.
391 Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
393 /// \brief Read write map of the nodes to type \c T.
395 /// ReadWrite map of the nodes to type \c T.
398 class NodeMap : public ReadWriteMap< Node, T > {
402 NodeMap(const Digraph&) { }
404 NodeMap(const Digraph&, T) { }
407 NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
408 ///Assignment operator
409 template <typename CMap>
410 NodeMap& operator=(const CMap&) {
411 checkConcept<ReadMap<Node, T>, CMap>();
416 /// \brief Read write map of the arcs to type \c T.
418 /// Reference map of the arcs to type \c T.
421 class ArcMap : public ReadWriteMap<Arc,T> {
425 ArcMap(const Digraph&) { }
427 ArcMap(const Digraph&, T) { }
429 ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
430 ///Assignment operator
431 template <typename CMap>
432 ArcMap& operator=(const CMap&) {
433 checkConcept<ReadMap<Arc, T>, CMap>();
438 template <typename RDigraph>
441 checkConcept<IterableDigraphComponent<>, Digraph>();
442 checkConcept<MappableDigraphComponent<>, Digraph>();
448 } //namespace concepts
453 #endif // LEMON_CONCEPT_DIGRAPH_H