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 ///\ingroup graph_concepts
21 ///\brief The concept of Undirected Graphs.
23 #ifndef LEMON_CONCEPT_GRAPH_H
24 #define LEMON_CONCEPT_GRAPH_H
26 #include <lemon/concepts/graph_components.h>
27 #include <lemon/concepts/graph.h>
28 #include <lemon/bits/utility.h>
33 /// \ingroup graph_concepts
35 /// \brief Class describing the concept of Undirected Graphs.
37 /// This class describes the common interface of all Undirected
40 /// As all concept describing classes it provides only interface
41 /// without any sensible implementation. So any algorithm for
42 /// undirected graph should compile with this class, but it will not
43 /// run properly, of course.
45 /// The LEMON undirected graphs also fulfill the concept of
46 /// directed graphs (\ref lemon::concepts::Digraph "Digraph
47 /// Concept"). Each edges can be seen as two opposite
48 /// directed arc and consequently the undirected graph can be
49 /// seen as the direceted graph of these directed arcs. The
50 /// Graph has the Edge inner class for the edges and
51 /// the Arc type for the directed arcs. The Arc type is
52 /// convertible to Edge or inherited from it so from a directed
53 /// arc we can get the represented edge.
55 /// In the sense of the LEMON each edge has a default
56 /// direction (it should be in every computer implementation,
57 /// because the order of edge's nodes defines an
58 /// orientation). With the default orientation we can define that
59 /// the directed arc is forward or backward directed. With the \c
60 /// direction() and \c direct() function we can get the direction
61 /// of the directed arc and we can direct an edge.
63 /// The EdgeIt is an iterator for the edges. We can use
64 /// the EdgeMap to map values for the edges. The InArcIt and
65 /// OutArcIt iterates on the same edges but with opposite
66 /// direction. The IncEdgeIt iterates also on the same edges
67 /// as the OutArcIt and InArcIt but it is not convertible to Arc just
71 /// \brief The undirected graph should be tagged by the
74 /// The undirected graph should be tagged by the UndirectedTag. This
75 /// tag helps the enable_if technics to make compile time
76 /// specializations for undirected graphs.
77 typedef True UndirectedTag;
79 /// \brief The base type of node iterators,
80 /// or in other words, the trivial node iterator.
82 /// This is the base type of each node iterator,
83 /// thus each kind of node iterator converts to this.
84 /// More precisely each kind of node iterator should be inherited
85 /// from the trivial node iterator.
88 /// Default constructor
90 /// @warning The default constructor sets the iterator
91 /// to an undefined value.
99 /// Invalid constructor \& conversion.
101 /// This constructor initializes the iterator to be invalid.
102 /// \sa Invalid for more details.
104 /// Equality operator
106 /// Two iterators are equal if and only if they point to the
107 /// same object or both are invalid.
108 bool operator==(Node) const { return true; }
110 /// Inequality operator
112 /// \sa operator==(Node n)
114 bool operator!=(Node) const { return true; }
116 /// Artificial ordering operator.
118 /// To allow the use of graph descriptors as key type in std::map or
119 /// similar associative container we require this.
121 /// \note This operator only have to define some strict ordering of
122 /// the items; this order has nothing to do with the iteration
123 /// ordering of the items.
124 bool operator<(Node) const { return false; }
128 /// This iterator goes through each node.
130 /// This iterator goes through each node.
131 /// Its usage is quite simple, for example you can count the number
132 /// of nodes in graph \c g of type \c Graph like this:
135 /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
137 class NodeIt : public Node {
139 /// Default constructor
141 /// @warning The default constructor sets the iterator
142 /// to an undefined value.
144 /// Copy constructor.
146 /// Copy constructor.
148 NodeIt(const NodeIt& n) : Node(n) { }
149 /// Invalid constructor \& conversion.
151 /// Initialize the iterator to be invalid.
152 /// \sa Invalid for more details.
154 /// Sets the iterator to the first node.
156 /// Sets the iterator to the first node of \c g.
158 NodeIt(const Graph&) { }
159 /// Node -> NodeIt conversion.
161 /// Sets the iterator to the node of \c the graph pointed by
162 /// the trivial iterator.
163 /// This feature necessitates that each time we
164 /// iterate the arc-set, the iteration order is the same.
165 NodeIt(const Graph&, const Node&) { }
168 /// Assign the iterator to the next node.
170 NodeIt& operator++() { return *this; }
174 /// The base type of the edge iterators.
176 /// The base type of the edge iterators.
180 /// Default constructor
182 /// @warning The default constructor sets the iterator
183 /// to an undefined value.
185 /// Copy constructor.
187 /// Copy constructor.
189 Edge(const Edge&) { }
190 /// Initialize the iterator to be invalid.
192 /// Initialize the iterator to be invalid.
195 /// Equality operator
197 /// Two iterators are equal if and only if they point to the
198 /// same object or both are invalid.
199 bool operator==(Edge) const { return true; }
200 /// Inequality operator
202 /// \sa operator==(Edge n)
204 bool operator!=(Edge) const { return true; }
206 /// Artificial ordering operator.
208 /// To allow the use of graph descriptors as key type in std::map or
209 /// similar associative container we require this.
211 /// \note This operator only have to define some strict ordering of
212 /// the items; this order has nothing to do with the iteration
213 /// ordering of the items.
214 bool operator<(Edge) const { return false; }
217 /// This iterator goes through each edge.
219 /// This iterator goes through each edge of a graph.
220 /// Its usage is quite simple, for example you can count the number
221 /// of edges in a graph \c g of type \c Graph as follows:
224 /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
226 class EdgeIt : public Edge {
228 /// Default constructor
230 /// @warning The default constructor sets the iterator
231 /// to an undefined value.
233 /// Copy constructor.
235 /// Copy constructor.
237 EdgeIt(const EdgeIt& e) : Edge(e) { }
238 /// Initialize the iterator to be invalid.
240 /// Initialize the iterator to be invalid.
243 /// This constructor sets the iterator to the first edge.
245 /// This constructor sets the iterator to the first edge.
246 EdgeIt(const Graph&) { }
247 /// Edge -> EdgeIt conversion
249 /// Sets the iterator to the value of the trivial iterator.
250 /// This feature necessitates that each time we
251 /// iterate the edge-set, the iteration order is the
253 EdgeIt(const Graph&, const Edge&) { }
256 /// Assign the iterator to the next edge.
257 EdgeIt& operator++() { return *this; }
260 /// \brief This iterator goes trough the incident undirected
263 /// This iterator goes trough the incident edges
264 /// of a certain node of a graph. You should assume that the
265 /// loop arcs will be iterated twice.
267 /// Its usage is quite simple, for example you can compute the
268 /// degree (i.e. count the number of incident arcs of a node \c n
269 /// in graph \c g of type \c Graph as follows.
273 /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
275 class IncEdgeIt : public Edge {
277 /// Default constructor
279 /// @warning The default constructor sets the iterator
280 /// to an undefined value.
282 /// Copy constructor.
284 /// Copy constructor.
286 IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
287 /// Initialize the iterator to be invalid.
289 /// Initialize the iterator to be invalid.
291 IncEdgeIt(Invalid) { }
292 /// This constructor sets the iterator to first incident arc.
294 /// This constructor set the iterator to the first incident arc of
296 IncEdgeIt(const Graph&, const Node&) { }
297 /// Edge -> IncEdgeIt conversion
299 /// Sets the iterator to the value of the trivial iterator \c e.
300 /// This feature necessitates that each time we
301 /// iterate the arc-set, the iteration order is the same.
302 IncEdgeIt(const Graph&, const Edge&) { }
303 /// Next incident arc
305 /// Assign the iterator to the next incident arc
306 /// of the corresponding node.
307 IncEdgeIt& operator++() { return *this; }
310 /// The directed arc type.
312 /// The directed arc type. It can be converted to the
313 /// edge or it should be inherited from the undirected
315 class Arc : public Edge {
317 /// Default constructor
319 /// @warning The default constructor sets the iterator
320 /// to an undefined value.
322 /// Copy constructor.
324 /// Copy constructor.
326 Arc(const Arc& e) : Edge(e) { }
327 /// Initialize the iterator to be invalid.
329 /// Initialize the iterator to be invalid.
332 /// Equality operator
334 /// Two iterators are equal if and only if they point to the
335 /// same object or both are invalid.
336 bool operator==(Arc) const { return true; }
337 /// Inequality operator
339 /// \sa operator==(Arc n)
341 bool operator!=(Arc) const { return true; }
343 /// Artificial ordering operator.
345 /// To allow the use of graph descriptors as key type in std::map or
346 /// similar associative container we require this.
348 /// \note This operator only have to define some strict ordering of
349 /// the items; this order has nothing to do with the iteration
350 /// ordering of the items.
351 bool operator<(Arc) const { return false; }
354 /// This iterator goes through each directed arc.
356 /// This iterator goes through each arc of a graph.
357 /// Its usage is quite simple, for example you can count the number
358 /// of arcs in a graph \c g of type \c Graph as follows:
361 /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
363 class ArcIt : public Arc {
365 /// Default constructor
367 /// @warning The default constructor sets the iterator
368 /// to an undefined value.
370 /// Copy constructor.
372 /// Copy constructor.
374 ArcIt(const ArcIt& e) : Arc(e) { }
375 /// Initialize the iterator to be invalid.
377 /// Initialize the iterator to be invalid.
380 /// This constructor sets the iterator to the first arc.
382 /// This constructor sets the iterator to the first arc of \c g.
383 ///@param g the graph
384 ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
385 /// Arc -> ArcIt conversion
387 /// Sets the iterator to the value of the trivial iterator \c e.
388 /// This feature necessitates that each time we
389 /// iterate the arc-set, the iteration order is the same.
390 ArcIt(const Graph&, const Arc&) { }
393 /// Assign the iterator to the next arc.
394 ArcIt& operator++() { return *this; }
397 /// This iterator goes trough the outgoing directed arcs of a node.
399 /// This iterator goes trough the \e outgoing arcs of a certain node
401 /// Its usage is quite simple, for example you can count the number
402 /// of outgoing arcs of a node \c n
403 /// in graph \c g of type \c Graph as follows.
406 /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
409 class OutArcIt : public Arc {
411 /// Default constructor
413 /// @warning The default constructor sets the iterator
414 /// to an undefined value.
416 /// Copy constructor.
418 /// Copy constructor.
420 OutArcIt(const OutArcIt& e) : Arc(e) { }
421 /// Initialize the iterator to be invalid.
423 /// Initialize the iterator to be invalid.
425 OutArcIt(Invalid) { }
426 /// This constructor sets the iterator to the first outgoing arc.
428 /// This constructor sets the iterator to the first outgoing arc of
431 ///@param g the graph
432 OutArcIt(const Graph& n, const Node& g) {
433 ignore_unused_variable_warning(n);
434 ignore_unused_variable_warning(g);
436 /// Arc -> OutArcIt conversion
438 /// Sets the iterator to the value of the trivial iterator.
439 /// This feature necessitates that each time we
440 /// iterate the arc-set, the iteration order is the same.
441 OutArcIt(const Graph&, const Arc&) { }
444 /// Assign the iterator to the next
445 /// outgoing arc of the corresponding node.
446 OutArcIt& operator++() { return *this; }
449 /// This iterator goes trough the incoming directed arcs of a node.
451 /// This iterator goes trough the \e incoming arcs of a certain node
453 /// Its usage is quite simple, for example you can count the number
454 /// of outgoing arcs of a node \c n
455 /// in graph \c g of type \c Graph as follows.
458 /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
461 class InArcIt : public Arc {
463 /// Default constructor
465 /// @warning The default constructor sets the iterator
466 /// to an undefined value.
468 /// Copy constructor.
470 /// Copy constructor.
472 InArcIt(const InArcIt& e) : Arc(e) { }
473 /// Initialize the iterator to be invalid.
475 /// Initialize the iterator to be invalid.
478 /// This constructor sets the iterator to first incoming arc.
480 /// This constructor set the iterator to the first incoming arc of
483 ///@param g the graph
484 InArcIt(const Graph& g, const Node& n) {
485 ignore_unused_variable_warning(n);
486 ignore_unused_variable_warning(g);
488 /// Arc -> InArcIt conversion
490 /// Sets the iterator to the value of the trivial iterator \c e.
491 /// This feature necessitates that each time we
492 /// iterate the arc-set, the iteration order is the same.
493 InArcIt(const Graph&, const Arc&) { }
494 /// Next incoming arc
496 /// Assign the iterator to the next inarc of the corresponding node.
498 InArcIt& operator++() { return *this; }
501 /// \brief Read write map of the nodes to type \c T.
503 /// ReadWrite map of the nodes to type \c T.
506 class NodeMap : public ReadWriteMap< Node, T >
511 NodeMap(const Graph&) { }
513 NodeMap(const Graph&, T) { }
516 NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
517 ///Assignment operator
518 template <typename CMap>
519 NodeMap& operator=(const CMap&) {
520 checkConcept<ReadMap<Node, T>, CMap>();
525 /// \brief Read write map of the directed arcs to type \c T.
527 /// Reference map of the directed arcs to type \c T.
530 class ArcMap : public ReadWriteMap<Arc,T>
535 ArcMap(const Graph&) { }
537 ArcMap(const Graph&, T) { }
539 ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
540 ///Assignment operator
541 template <typename CMap>
542 ArcMap& operator=(const CMap&) {
543 checkConcept<ReadMap<Arc, T>, CMap>();
548 /// Read write map of the edges to type \c T.
550 /// Reference map of the arcs to type \c T.
553 class EdgeMap : public ReadWriteMap<Edge,T>
558 EdgeMap(const Graph&) { }
560 EdgeMap(const Graph&, T) { }
562 EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}
563 ///Assignment operator
564 template <typename CMap>
565 EdgeMap& operator=(const CMap&) {
566 checkConcept<ReadMap<Edge, T>, CMap>();
571 /// \brief Direct the given edge.
573 /// Direct the given edge. The returned arc source
574 /// will be the given node.
575 Arc direct(const Edge&, const Node&) const {
579 /// \brief Direct the given edge.
581 /// Direct the given edge. The returned arc
582 /// represents the given edge and the direction comes
583 /// from the bool parameter. The source of the edge and
584 /// the directed arc is the same when the given bool is true.
585 Arc direct(const Edge&, bool) const {
589 /// \brief Returns true if the arc has default orientation.
591 /// Returns whether the given directed arc is same orientation as
592 /// the corresponding edge's default orientation.
593 bool direction(Arc) const { return true; }
595 /// \brief Returns the opposite directed arc.
597 /// Returns the opposite directed arc.
598 Arc oppositeArc(Arc) const { return INVALID; }
600 /// \brief Opposite node on an arc
602 /// \return the opposite of the given Node on the given Edge
603 Node oppositeNode(Node, Edge) const { return INVALID; }
605 /// \brief First node of the edge.
607 /// \return the first node of the given Edge.
609 /// Naturally edges don't have direction and thus
610 /// don't have source and target node. But we use these two methods
611 /// to query the two nodes of the arc. The direction of the arc
612 /// which arises this way is called the inherent direction of the
613 /// edge, and is used to define the "default" direction
614 /// of the directed versions of the arcs.
616 Node u(Edge) const { return INVALID; }
618 /// \brief Second node of the edge.
619 Node v(Edge) const { return INVALID; }
621 /// \brief Source node of the directed arc.
622 Node source(Arc) const { return INVALID; }
624 /// \brief Target node of the directed arc.
625 Node target(Arc) const { return INVALID; }
627 /// \brief Returns the id of the node.
628 int id(Node) const { return -1; }
630 /// \brief Returns the id of the edge.
631 int id(Edge) const { return -1; }
633 /// \brief Returns the id of the arc.
634 int id(Arc) const { return -1; }
636 /// \brief Returns the node with the given id.
638 /// \pre The argument should be a valid node id in the graph.
639 Node nodeFromId(int) const { return INVALID; }
641 /// \brief Returns the edge with the given id.
643 /// \pre The argument should be a valid edge id in the graph.
644 Edge edgeFromId(int) const { return INVALID; }
646 /// \brief Returns the arc with the given id.
648 /// \pre The argument should be a valid arc id in the graph.
649 Arc arcFromId(int) const { return INVALID; }
651 /// \brief Returns an upper bound on the node IDs.
652 int maxNodeId() const { return -1; }
654 /// \brief Returns an upper bound on the edge IDs.
655 int maxEdgeId() const { return -1; }
657 /// \brief Returns an upper bound on the arc IDs.
658 int maxArcId() const { return -1; }
660 void first(Node&) const {}
661 void next(Node&) const {}
663 void first(Edge&) const {}
664 void next(Edge&) const {}
666 void first(Arc&) const {}
667 void next(Arc&) const {}
669 void firstOut(Arc&, Node) const {}
670 void nextOut(Arc&) const {}
672 void firstIn(Arc&, Node) const {}
673 void nextIn(Arc&) const {}
675 void firstInc(Edge &, bool &, const Node &) const {}
676 void nextInc(Edge &, bool &) const {}
678 // The second parameter is dummy.
679 Node fromId(int, Node) const { return INVALID; }
680 // The second parameter is dummy.
681 Edge fromId(int, Edge) const { return INVALID; }
682 // The second parameter is dummy.
683 Arc fromId(int, Arc) const { return INVALID; }
686 int maxId(Node) const { return -1; }
688 int maxId(Edge) const { return -1; }
690 int maxId(Arc) const { return -1; }
692 /// \brief Base node of the iterator
694 /// Returns the base node (the source in this case) of the iterator
695 Node baseNode(OutArcIt e) const {
698 /// \brief Running node of the iterator
700 /// Returns the running node (the target in this case) of the
702 Node runningNode(OutArcIt e) const {
706 /// \brief Base node of the iterator
708 /// Returns the base node (the target in this case) of the iterator
709 Node baseNode(InArcIt e) const {
712 /// \brief Running node of the iterator
714 /// Returns the running node (the source in this case) of the
716 Node runningNode(InArcIt e) const {
720 /// \brief Base node of the iterator
722 /// Returns the base node of the iterator
723 Node baseNode(IncEdgeIt) const {
727 /// \brief Running node of the iterator
729 /// Returns the running node of the iterator
730 Node runningNode(IncEdgeIt) const {
734 template <typename _Graph>
737 checkConcept<IterableGraphComponent<>, _Graph>();
738 checkConcept<IDableGraphComponent<>, _Graph>();
739 checkConcept<MappableGraphComponent<>, _Graph>();