1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
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/core.h>
27 #include <lemon/concepts/maps.h>
28 #include <lemon/concept_check.h>
29 #include <lemon/concepts/graph_components.h>
34 /// \ingroup graph_concepts
36 /// \brief Class describing the concept of directed graphs.
38 /// This class describes the \ref concept "concept" of the
39 /// immutable directed digraphs.
41 /// Note that actual digraph implementation like @ref ListDigraph or
42 /// @ref SmartDigraph may have several additional functionality.
47 ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
49 ///Digraphs are \e not copy constructible. 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.
55 ///Assignment of \ref Digraph "Digraph"s to another ones are
56 ///\e not allowed. Use DigraphCopy() instead.
58 void operator=(const Digraph &) {}
62 /// Defalult constructor.
64 /// Defalult constructor.
67 /// Class for identifying a node of the digraph
69 /// This class identifies a node of the digraph. It also serves
70 /// as a base class of the node iterators,
71 /// thus they will convert to this type.
74 /// Default constructor
76 /// @warning The default constructor sets the iterator
77 /// to an undefined value.
85 /// Invalid constructor \& conversion.
87 /// This constructor initializes the iterator to be invalid.
88 /// \sa Invalid for more details.
92 /// Two iterators are equal if and only if they point to the
93 /// same object or both are invalid.
94 bool operator==(Node) const { return true; }
96 /// Inequality operator
98 /// \sa operator==(Node n)
100 bool operator!=(Node) const { return true; }
102 /// Artificial ordering operator.
104 /// To allow the use of digraph descriptors as key type in std::map or
105 /// similar associative container we require this.
107 /// \note This operator only have to define some strict ordering of
108 /// the items; this order has nothing to do with the iteration
109 /// ordering of the items.
110 bool operator<(Node) const { return false; }
114 /// This iterator goes through each node.
116 /// This iterator goes through each node.
117 /// 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:
121 /// for (Digraph::NodeIt n(g); n!=INVALID; ++n) ++count;
123 class NodeIt : public Node {
125 /// Default constructor
127 /// @warning The default constructor sets the iterator
128 /// to an undefined value.
130 /// Copy constructor.
132 /// Copy constructor.
134 NodeIt(const NodeIt& n) : Node(n) { }
135 /// Invalid constructor \& conversion.
137 /// Initialize the iterator to be invalid.
138 /// \sa Invalid for more details.
140 /// Sets the iterator to the first node.
142 /// Sets the iterator to the first node of \c g.
144 NodeIt(const Digraph&) { }
145 /// Node -> NodeIt conversion.
147 /// Sets the iterator to the node of \c the digraph pointed by
148 /// the trivial iterator.
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&) { }
154 /// Assign the iterator to the next node.
156 NodeIt& operator++() { return *this; }
160 /// Class for identifying an arc of the digraph
162 /// This class identifies an arc of the digraph. It also serves
163 /// as a base class of the arc iterators,
164 /// thus they will convert to this type.
167 /// Default constructor
169 /// @warning The default constructor sets the iterator
170 /// to an undefined value.
172 /// Copy constructor.
174 /// Copy constructor.
177 /// Initialize the iterator to be invalid.
179 /// Initialize the iterator to be invalid.
182 /// Equality operator
184 /// Two iterators are equal if and only if they point to the
185 /// same object or both are invalid.
186 bool operator==(Arc) const { return true; }
187 /// Inequality operator
189 /// \sa operator==(Arc n)
191 bool operator!=(Arc) const { return true; }
193 /// Artificial ordering operator.
195 /// To allow the use of digraph descriptors as key type in std::map or
196 /// similar associative container we require this.
198 /// \note This operator only have to define some strict ordering of
199 /// the items; this order has nothing to do with the iteration
200 /// ordering of the items.
201 bool operator<(Arc) const { return false; }
204 /// This iterator goes trough the outgoing arcs of a node.
206 /// This iterator goes trough the \e outgoing arcs of a certain node
208 /// Its usage is quite simple, for example you can count the number
209 /// of outgoing arcs of a node \c n
210 /// in digraph \c g of type \c Digraph as follows.
213 /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
216 class OutArcIt : public Arc {
218 /// Default constructor
220 /// @warning The default constructor sets the iterator
221 /// to an undefined value.
223 /// Copy constructor.
225 /// Copy constructor.
227 OutArcIt(const OutArcIt& e) : Arc(e) { }
228 /// Initialize the iterator to be invalid.
230 /// Initialize the iterator to be invalid.
232 OutArcIt(Invalid) { }
233 /// This constructor sets the iterator to the first outgoing arc.
235 /// This constructor sets the iterator to the first outgoing arc of
237 OutArcIt(const Digraph&, const Node&) { }
238 /// Arc -> OutArcIt conversion
240 /// Sets the iterator to the value of the trivial iterator.
241 /// This feature necessitates that each time we
242 /// iterate the arc-set, the iteration order is the same.
243 OutArcIt(const Digraph&, const Arc&) { }
246 /// Assign the iterator to the next
247 /// outgoing arc of the corresponding node.
248 OutArcIt& operator++() { return *this; }
251 /// This iterator goes trough the incoming arcs of a node.
253 /// This iterator goes trough the \e incoming arcs of a certain node
255 /// Its usage is quite simple, for example you can count the number
256 /// of outgoing arcs of a node \c n
257 /// in digraph \c g of type \c Digraph as follows.
260 /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
263 class InArcIt : public Arc {
265 /// Default constructor
267 /// @warning The default constructor sets the iterator
268 /// to an undefined value.
270 /// Copy constructor.
272 /// Copy constructor.
274 InArcIt(const InArcIt& e) : Arc(e) { }
275 /// Initialize the iterator to be invalid.
277 /// Initialize the iterator to be invalid.
280 /// This constructor sets the iterator to first incoming arc.
282 /// This constructor set the iterator to the first incoming arc of
284 InArcIt(const Digraph&, const Node&) { }
285 /// Arc -> InArcIt conversion
287 /// Sets the iterator to the value of the trivial iterator \c e.
288 /// This feature necessitates that each time we
289 /// iterate the arc-set, the iteration order is the same.
290 InArcIt(const Digraph&, const Arc&) { }
291 /// Next incoming arc
293 /// Assign the iterator to the next inarc of the corresponding node.
295 InArcIt& operator++() { return *this; }
297 /// This iterator goes through each arc.
299 /// This iterator goes through each arc of a digraph.
300 /// 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:
304 /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
306 class ArcIt : public Arc {
308 /// Default constructor
310 /// @warning The default constructor sets the iterator
311 /// to an undefined value.
313 /// Copy constructor.
315 /// Copy constructor.
317 ArcIt(const ArcIt& e) : Arc(e) { }
318 /// Initialize the iterator to be invalid.
320 /// Initialize the iterator to be invalid.
323 /// This constructor sets the iterator to the first arc.
325 /// This constructor sets the iterator to the first arc of \c g.
326 ///@param g the digraph
327 ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
328 /// Arc -> ArcIt conversion
330 /// Sets the iterator to the value of the trivial iterator \c e.
331 /// This feature necessitates that each time we
332 /// iterate the arc-set, the iteration order is the same.
333 ArcIt(const Digraph&, const Arc&) { }
336 /// Assign the iterator to the next arc.
337 ArcIt& operator++() { return *this; }
339 ///Gives back the target node of an arc.
341 ///Gives back the target node of an arc.
343 Node target(Arc) const { return INVALID; }
344 ///Gives back the source node of an arc.
346 ///Gives back the source node of an arc.
348 Node source(Arc) const { return INVALID; }
350 /// \brief Returns the ID of the node.
351 int id(Node) const { return -1; }
353 /// \brief Returns the ID of the arc.
354 int id(Arc) const { return -1; }
356 /// \brief Returns the node with the given ID.
358 /// \pre The argument should be a valid node ID in the graph.
359 Node nodeFromId(int) const { return INVALID; }
361 /// \brief Returns the arc with the given ID.
363 /// \pre The argument should be a valid arc ID in the graph.
364 Arc arcFromId(int) const { return INVALID; }
366 /// \brief Returns an upper bound on the node IDs.
367 int maxNodeId() const { return -1; }
369 /// \brief Returns an upper bound on the arc IDs.
370 int maxArcId() const { return -1; }
372 void first(Node&) const {}
373 void next(Node&) const {}
375 void first(Arc&) const {}
376 void next(Arc&) const {}
379 void firstIn(Arc&, const Node&) const {}
380 void nextIn(Arc&) const {}
382 void firstOut(Arc&, const Node&) const {}
383 void nextOut(Arc&) const {}
385 // The second parameter is dummy.
386 Node fromId(int, Node) const { return INVALID; }
387 // The second parameter is dummy.
388 Arc fromId(int, Arc) const { return INVALID; }
391 int maxId(Node) const { return -1; }
393 int maxId(Arc) const { return -1; }
395 /// \brief The base node of the iterator.
397 /// Gives back the base node of the iterator.
398 /// It is always the target of the pointed arc.
399 Node baseNode(const InArcIt&) const { return INVALID; }
401 /// \brief The running node of the iterator.
403 /// Gives back the running node of the iterator.
404 /// It is always the source of the pointed arc.
405 Node runningNode(const InArcIt&) const { return INVALID; }
407 /// \brief The base node of the iterator.
409 /// Gives back the base node of the iterator.
410 /// It is always the source of the pointed arc.
411 Node baseNode(const OutArcIt&) const { return INVALID; }
413 /// \brief The running node of the iterator.
415 /// Gives back the running node of the iterator.
416 /// It is always the target of the pointed arc.
417 Node runningNode(const OutArcIt&) const { return INVALID; }
419 /// \brief The opposite node on the given arc.
421 /// Gives back the opposite node on the given arc.
422 Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
424 /// \brief Read write map of the nodes to type \c T.
426 /// ReadWrite map of the nodes to type \c T.
429 class NodeMap : public ReadWriteMap< Node, T > {
433 NodeMap(const Digraph&) { }
435 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) { }
462 ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
463 ///Assignment operator
464 template <typename CMap>
465 ArcMap& operator=(const CMap&) {
466 checkConcept<ReadMap<Arc, T>, CMap>();
471 template <typename _Digraph>
474 checkConcept<IterableDigraphComponent<>, _Digraph>();
475 checkConcept<IDableDigraphComponent<>, _Digraph>();
476 checkConcept<MappableDigraphComponent<>, _Digraph>();
482 } //namespace concepts
487 #endif // LEMON_CONCEPT_DIGRAPH_H