1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2013
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_CONCEPTS_DIGRAPH_H
20 #define LEMON_CONCEPTS_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>
30 #include <lemon/bits/stl_iterators.h>
35 /// \ingroup graph_concepts
37 /// \brief Class describing the concept of directed graphs.
39 /// This class describes the common interface of all directed
40 /// graphs (digraphs).
42 /// Like all concept classes, it only provides an interface
43 /// without any sensible implementation. So any general algorithm for
44 /// directed graphs should compile with this class, but it will not
45 /// run properly, of course.
46 /// An actual digraph implementation like \ref ListDigraph or
47 /// \ref SmartDigraph may have additional functionality.
52 /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
53 Digraph(const Digraph &) {}
54 /// \brief Assignment of a digraph to another one is \e not allowed.
55 /// Use DigraphCopy instead.
56 void operator=(const Digraph &) {}
59 /// Default constructor.
62 /// The node type of the digraph
64 /// This class identifies a node of the digraph. It also serves
65 /// as a base class of the node iterators,
66 /// thus they convert to this type.
69 /// Default constructor
71 /// Default constructor.
72 /// \warning It sets the object to an undefined value.
80 /// Assignment operator
82 /// Assignment operator.
84 const Node &operator=(const Node&) { return *this; }
86 /// %Invalid constructor \& conversion.
88 /// Initializes the object to be invalid.
89 /// \sa Invalid for more details.
93 /// Equality operator.
95 /// Two iterators are equal if and only if they point to the
96 /// same object or both are \c INVALID.
97 bool operator==(Node) const { return true; }
99 /// Inequality operator
101 /// Inequality operator.
102 bool operator!=(Node) const { return true; }
104 /// Artificial ordering operator.
106 /// Artificial ordering operator.
108 /// \note This operator only has to define some strict ordering of
109 /// the nodes; this order has nothing to do with the iteration
110 /// ordering of the nodes.
111 bool operator<(Node) const { return false; }
114 /// Iterator class for the nodes.
116 /// This iterator goes through each node of the digraph.
117 /// Its usage is quite simple, for example, you can count the number
118 /// of nodes in a 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 /// Default constructor.
128 /// \warning It sets the iterator to an undefined value.
130 /// Copy constructor.
132 /// Copy constructor.
134 NodeIt(const NodeIt& n) : Node(n) { }
135 /// Assignment operator
137 /// Assignment operator.
139 const NodeIt &operator=(const NodeIt&) { return *this; }
141 /// %Invalid constructor \& conversion.
143 /// Initializes the iterator to be invalid.
144 /// \sa Invalid for more details.
146 /// Sets the iterator to the first node.
148 /// Sets the iterator to the first node of the given digraph.
150 explicit NodeIt(const Digraph&) { }
151 /// Sets the iterator to the given node.
153 /// Sets the iterator to the given node of the given digraph.
155 NodeIt(const Digraph&, const Node&) { }
158 /// Assign the iterator to the next node.
160 NodeIt& operator++() { return *this; }
163 /// \brief Gets the collection of the nodes of the digraph.
165 /// This function can be used for iterating on
166 /// the nodes of the digraph. It returns a wrapped NodeIt, which looks
167 /// like an STL container (by having begin() and end())
168 /// which you can use in range-based for loops, STL algorithms, etc.
169 /// For example you can write:
172 /// for(auto v: g.nodes())
175 /// //Using an STL algorithm:
176 /// copy(g.nodes().begin(), g.nodes().end(), vect.begin());
178 LemonRangeWrapper1<NodeIt, Digraph> nodes() const {
179 return LemonRangeWrapper1<NodeIt, Digraph>(*this);
183 /// The arc type of the digraph
185 /// This class identifies an arc of the digraph. It also serves
186 /// as a base class of the arc iterators,
187 /// thus they will convert to this type.
190 /// Default constructor
192 /// Default constructor.
193 /// \warning It sets the object to an undefined value.
195 /// Copy constructor.
197 /// Copy constructor.
200 /// Assignment operator
202 /// Assignment operator.
204 const Arc &operator=(const Arc&) { return *this; }
206 /// %Invalid constructor \& conversion.
208 /// Initializes the object to be invalid.
209 /// \sa Invalid for more details.
211 /// Equality operator
213 /// Equality operator.
215 /// Two iterators are equal if and only if they point to the
216 /// same object or both are \c INVALID.
217 bool operator==(Arc) const { return true; }
218 /// Inequality operator
220 /// Inequality operator.
221 bool operator!=(Arc) const { return true; }
223 /// Artificial ordering operator.
225 /// Artificial ordering operator.
227 /// \note This operator only has to define some strict ordering of
228 /// the arcs; this order has nothing to do with the iteration
229 /// ordering of the arcs.
230 bool operator<(Arc) const { return false; }
233 /// Iterator class for the outgoing arcs of a node.
235 /// This iterator goes trough the \e outgoing arcs of a certain node
237 /// Its usage is quite simple, for example, you can count the number
238 /// of outgoing arcs of a node \c n
239 /// in a digraph \c g of type \c %Digraph as follows.
242 /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
244 class OutArcIt : public Arc {
246 /// Default constructor
248 /// Default constructor.
249 /// \warning It sets the iterator to an undefined value.
251 /// Copy constructor.
253 /// Copy constructor.
255 OutArcIt(const OutArcIt& e) : Arc(e) { }
256 /// Assignment operator
258 /// Assignment operator.
260 const OutArcIt &operator=(const OutArcIt&) { return *this; }
261 /// %Invalid constructor \& conversion.
263 /// Initializes the iterator to be invalid.
264 /// \sa Invalid for more details.
265 OutArcIt(Invalid) { }
266 /// Sets the iterator to the first outgoing arc.
268 /// Sets the iterator to the first outgoing arc of the given node.
270 OutArcIt(const Digraph&, const Node&) { }
271 /// Sets the iterator to the given arc.
273 /// Sets the iterator to the given arc of the given digraph.
275 OutArcIt(const Digraph&, const Arc&) { }
276 /// Next outgoing arc
278 /// Assign the iterator to the next
279 /// outgoing arc of the corresponding node.
280 OutArcIt& operator++() { return *this; }
283 /// \brief Gets the collection of the outgoing arcs of a certain node
286 /// This function can be used for iterating on the
287 /// outgoing arcs of a certain node of the digraph. It returns a wrapped
288 /// OutArcIt, which looks like an STL container
289 /// (by having begin() and end()) which you can use in range-based
290 /// for loops, STL algorithms, etc.
291 /// For example if g is a Digraph and u is a node, you can write:
293 /// for(auto a: g.outArcs(u))
296 /// //Using an STL algorithm:
297 /// copy(g.outArcs(u).begin(), g.outArcs(u).end(), vect.begin());
299 LemonRangeWrapper2<OutArcIt, Digraph, Node> outArcs(const Node& u) const {
300 return LemonRangeWrapper2<OutArcIt, Digraph, Node>(*this, u);
304 /// Iterator class for the incoming arcs of a node.
306 /// This iterator goes trough the \e incoming arcs of a certain node
308 /// Its usage is quite simple, for example, you can count the number
309 /// of incoming arcs of a node \c n
310 /// in a digraph \c g of type \c %Digraph as follows.
313 /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
315 class InArcIt : public Arc {
317 /// Default constructor
319 /// Default constructor.
320 /// \warning It sets the iterator to an undefined value.
322 /// Copy constructor.
324 /// Copy constructor.
326 InArcIt(const InArcIt& e) : Arc(e) { }
327 /// Assignment operator
329 /// Assignment operator.
331 const InArcIt &operator=(const InArcIt&) { return *this; }
333 /// %Invalid constructor \& conversion.
335 /// Initializes the iterator to be invalid.
336 /// \sa Invalid for more details.
338 /// Sets the iterator to the first incoming arc.
340 /// Sets the iterator to the first incoming arc of the given node.
342 InArcIt(const Digraph&, const Node&) { }
343 /// Sets the iterator to the given arc.
345 /// Sets the iterator to the given arc of the given digraph.
347 InArcIt(const Digraph&, const Arc&) { }
348 /// Next incoming arc
350 /// Assign the iterator to the next
351 /// incoming arc of the corresponding node.
352 InArcIt& operator++() { return *this; }
355 /// \brief Gets the collection of the incoming arcs of a certain node
358 /// This function can be used for iterating on the
359 /// incoming arcs of a certain node of the digraph. It returns a wrapped
360 /// InArcIt, which looks like an STL container
361 /// (by having begin() and end()) which you can use in range-based
362 /// for loops, STL algorithms, etc.
363 /// For example if g is a Digraph and u is a node, you can write:
365 /// for(auto a: g.inArcs(u))
368 /// //Using an STL algorithm:
369 /// copy(g.inArcs(u).begin(), g.inArcs(u).end(), vect.begin());
371 LemonRangeWrapper2<InArcIt, Digraph, Node> inArcs(const Node& u) const {
372 return LemonRangeWrapper2<InArcIt, Digraph, Node>(*this, u);
376 /// Iterator class for the arcs.
378 /// This iterator goes through each arc of the digraph.
379 /// Its usage is quite simple, for example, you can count the number
380 /// of arcs in a digraph \c g of type \c %Digraph as follows:
383 /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
385 class ArcIt : public Arc {
387 /// Default constructor
389 /// Default constructor.
390 /// \warning It sets the iterator to an undefined value.
392 /// Copy constructor.
394 /// Copy constructor.
396 ArcIt(const ArcIt& e) : Arc(e) { }
397 /// Assignment operator
399 /// Assignment operator.
401 const ArcIt &operator=(const ArcIt&) { return *this; }
403 /// %Invalid constructor \& conversion.
405 /// Initializes the iterator to be invalid.
406 /// \sa Invalid for more details.
408 /// Sets the iterator to the first arc.
410 /// Sets the iterator to the first arc of the given digraph.
412 explicit ArcIt(const Digraph& g) {
413 ::lemon::ignore_unused_variable_warning(g);
415 /// Sets the iterator to the given arc.
417 /// Sets the iterator to the given arc of the given digraph.
419 ArcIt(const Digraph&, const Arc&) { }
422 /// Assign the iterator to the next arc.
424 ArcIt& operator++() { return *this; }
427 /// \brief Gets the collection of the arcs of the digraph.
429 /// This function can be used for iterating on the
430 /// arcs of the digraph. It returns a wrapped
431 /// ArcIt, which looks like an STL container
432 /// (by having begin() and end()) which you can use in range-based
433 /// for loops, STL algorithms, etc.
434 /// For example you can write:
437 /// for(auto a: g.arcs())
440 /// //Using an STL algorithm:
441 /// copy(g.arcs().begin(), g.arcs().end(), vect.begin());
443 LemonRangeWrapper1<ArcIt, Digraph> arcs() const {
444 return LemonRangeWrapper1<ArcIt, Digraph>(*this);
448 /// \brief The source node of the arc.
450 /// Returns the source node of the given arc.
451 Node source(Arc) const { return INVALID; }
453 /// \brief The target node of the arc.
455 /// Returns the target node of the given arc.
456 Node target(Arc) const { return INVALID; }
458 /// \brief The ID of the node.
460 /// Returns the ID of the given node.
461 int id(Node) const { return -1; }
463 /// \brief The ID of the arc.
465 /// Returns the ID of the given arc.
466 int id(Arc) const { return -1; }
468 /// \brief The node with the given ID.
470 /// Returns the node with the given ID.
471 /// \pre The argument should be a valid node ID in the digraph.
472 Node nodeFromId(int) const { return INVALID; }
474 /// \brief The arc with the given ID.
476 /// Returns the arc with the given ID.
477 /// \pre The argument should be a valid arc ID in the digraph.
478 Arc arcFromId(int) const { return INVALID; }
480 /// \brief An upper bound on the node IDs.
482 /// Returns an upper bound on the node IDs.
483 int maxNodeId() const { return -1; }
485 /// \brief An upper bound on the arc IDs.
487 /// Returns an upper bound on the arc IDs.
488 int maxArcId() const { return -1; }
490 void first(Node&) const {}
491 void next(Node&) const {}
493 void first(Arc&) const {}
494 void next(Arc&) const {}
497 void firstIn(Arc&, const Node&) const {}
498 void nextIn(Arc&) const {}
500 void firstOut(Arc&, const Node&) const {}
501 void nextOut(Arc&) const {}
503 // The second parameter is dummy.
504 Node fromId(int, Node) const { return INVALID; }
505 // The second parameter is dummy.
506 Arc fromId(int, Arc) const { return INVALID; }
509 int maxId(Node) const { return -1; }
511 int maxId(Arc) const { return -1; }
513 /// \brief The opposite node on the arc.
515 /// Returns the opposite node on the given arc.
516 Node oppositeNode(Node, Arc) const { return INVALID; }
518 /// \brief The base node of the iterator.
520 /// Returns the base node of the given outgoing arc iterator
521 /// (i.e. the source node of the corresponding arc).
522 Node baseNode(OutArcIt) const { return INVALID; }
524 /// \brief The running node of the iterator.
526 /// Returns the running node of the given outgoing arc iterator
527 /// (i.e. the target node of the corresponding arc).
528 Node runningNode(OutArcIt) const { return INVALID; }
530 /// \brief The base node of the iterator.
532 /// Returns the base node of the given incoming arc iterator
533 /// (i.e. the target node of the corresponding arc).
534 Node baseNode(InArcIt) const { return INVALID; }
536 /// \brief The running node of the iterator.
538 /// Returns the running node of the given incoming arc iterator
539 /// (i.e. the source node of the corresponding arc).
540 Node runningNode(InArcIt) const { return INVALID; }
542 /// \brief Standard graph map type for the nodes.
544 /// Standard graph map type for the nodes.
545 /// It conforms to the ReferenceMap concept.
547 class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
551 explicit NodeMap(const Digraph&) { }
552 /// Constructor with given initial value
553 NodeMap(const Digraph&, T) { }
557 NodeMap(const NodeMap& nm) :
558 ReferenceMap<Node, T, T&, const T&>(nm) { }
560 ///Assignment operator
561 NodeMap& operator=(const NodeMap&) {
564 ///Template Assignment operator
565 template <typename CMap>
566 NodeMap& operator=(const CMap&) {
567 checkConcept<ReadMap<Node, T>, CMap>();
572 /// \brief Standard graph map type for the arcs.
574 /// Standard graph map type for the arcs.
575 /// It conforms to the ReferenceMap concept.
577 class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
581 explicit ArcMap(const Digraph&) { }
582 /// Constructor with given initial value
583 ArcMap(const Digraph&, T) { }
587 ArcMap(const ArcMap& em) :
588 ReferenceMap<Arc, T, T&, const T&>(em) { }
589 ///Assignment operator
590 ArcMap& operator=(const ArcMap&) {
593 ///Template Assignment operator
594 template <typename CMap>
595 ArcMap& operator=(const CMap&) {
596 checkConcept<ReadMap<Arc, T>, CMap>();
601 template <typename _Digraph>
604 checkConcept<BaseDigraphComponent, _Digraph>();
605 checkConcept<IterableDigraphComponent<>, _Digraph>();
606 checkConcept<IDableDigraphComponent<>, _Digraph>();
607 checkConcept<MappableDigraphComponent<>, _Digraph>();
613 } //namespace concepts