COIN-OR::LEMON - Graph Library

source: lemon/lemon/concepts/graph_components.h @ 1369:9fd86ec2cb81

Last change on this file since 1369:9fd86ec2cb81 was 1270:dceba191c00d, checked in by Alpar Juttner <alpar@…>, 11 years ago

Apply unify-sources.sh to the source tree

File size: 69.0 KB
RevLine 
[209]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
[57]2 *
[209]3 * This file is a part of LEMON, a generic C++ optimization library.
[57]4 *
[1270]5 * Copyright (C) 2003-2013
[57]6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19///\ingroup graph_concepts
20///\file
[833]21///\brief The concepts of graph components.
[57]22
[576]23#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
24#define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
[57]25
[220]26#include <lemon/core.h>
[57]27#include <lemon/concepts/maps.h>
28
29#include <lemon/bits/alteration_notifier.h>
30
31namespace lemon {
32  namespace concepts {
33
[626]34    /// \brief Concept class for \c Node, \c Arc and \c Edge types.
[57]35    ///
[626]36    /// This class describes the concept of \c Node, \c Arc and \c Edge
37    /// subtypes of digraph and graph types.
[57]38    ///
39    /// \note This class is a template class so that we can use it to
[626]40    /// create graph skeleton classes. The reason for this is that \c Node
[956]41    /// and \c Arc (or \c Edge) types should \e not derive from the same
[626]42    /// base class. For \c Node you should instantiate it with character
43    /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
[57]44#ifndef DOXYGEN
[606]45    template <char sel = '0'>
[57]46#endif
47    class GraphItem {
48    public:
49      /// \brief Default constructor.
[209]50      ///
[626]51      /// Default constructor.
[57]52      /// \warning The default constructor is not required to set
53      /// the item to some well-defined value. So you should consider it
54      /// as uninitialized.
55      GraphItem() {}
[626]56
[57]57      /// \brief Copy constructor.
58      ///
59      /// Copy constructor.
[626]60      GraphItem(const GraphItem &) {}
61
62      /// \brief Constructor for conversion from \c INVALID.
[57]63      ///
[626]64      /// Constructor for conversion from \c INVALID.
65      /// It initializes the item to be invalid.
[57]66      /// \sa Invalid for more details.
67      GraphItem(Invalid) {}
[626]68
69      /// \brief Assignment operator.
[57]70      ///
[626]71      /// Assignment operator for the item.
72      GraphItem& operator=(const GraphItem&) { return *this; }
73
[713]74      /// \brief Assignment operator for INVALID.
75      ///
76      /// This operator makes the item invalid.
77      GraphItem& operator=(Invalid) { return *this; }
78
[57]79      /// \brief Equality operator.
80      ///
[626]81      /// Equality operator.
82      bool operator==(const GraphItem&) const { return false; }
83
[57]84      /// \brief Inequality operator.
85      ///
[626]86      /// Inequality operator.
87      bool operator!=(const GraphItem&) const { return false; }
88
89      /// \brief Ordering operator.
[57]90      ///
[626]91      /// This operator defines an ordering of the items.
[956]92      /// It makes possible to use graph item types as key types in
[626]93      /// associative containers (e.g. \c std::map).
[57]94      ///
[781]95      /// \note This operator only has to define some strict ordering of
[57]96      /// the items; this order has nothing to do with the iteration
97      /// ordering of the items.
[626]98      bool operator<(const GraphItem&) const { return false; }
[57]99
100      template<typename _GraphItem>
101      struct Constraints {
[209]102        void constraints() {
103          _GraphItem i1;
[713]104          i1=INVALID;
[209]105          _GraphItem i2 = i1;
106          _GraphItem i3 = INVALID;
[57]107
[209]108          i1 = i2 = i3;
109
110          bool b;
[1257]111          ::lemon::ignore_unused_variable_warning(b);
[1171]112
[209]113          b = (ia == ib) && (ia != ib);
114          b = (ia == INVALID) && (ib != INVALID);
[57]115          b = (ia < ib);
[209]116        }
[57]117
[209]118        const _GraphItem &ia;
119        const _GraphItem &ib;
[1125]120        Constraints() {}
[57]121      };
122    };
123
[626]124    /// \brief Base skeleton class for directed graphs.
[209]125    ///
[626]126    /// This class describes the base interface of directed graph types.
127    /// All digraph %concepts have to conform to this class.
[956]128    /// It just provides types for nodes and arcs and functions
[626]129    /// to get the source and the target nodes of arcs.
[57]130    class BaseDigraphComponent {
131    public:
132
133      typedef BaseDigraphComponent Digraph;
[209]134
[57]135      /// \brief Node class of the digraph.
136      ///
[626]137      /// This class represents the nodes of the digraph.
[57]138      typedef GraphItem<'n'> Node;
139
140      /// \brief Arc class of the digraph.
141      ///
[626]142      /// This class represents the arcs of the digraph.
143      typedef GraphItem<'a'> Arc;
144
145      /// \brief Return the source node of an arc.
[57]146      ///
[626]147      /// This function returns the source node of an arc.
148      Node source(const Arc&) const { return INVALID; }
[57]149
[626]150      /// \brief Return the target node of an arc.
[57]151      ///
[626]152      /// This function returns the target node of an arc.
153      Node target(const Arc&) const { return INVALID; }
154
155      /// \brief Return the opposite node on the given arc.
[57]156      ///
[626]157      /// This function returns the opposite node on the given arc.
[57]158      Node oppositeNode(const Node&, const Arc&) const {
159        return INVALID;
160      }
161
162      template <typename _Digraph>
163      struct Constraints {
[209]164        typedef typename _Digraph::Node Node;
165        typedef typename _Digraph::Arc Arc;
166
167        void constraints() {
168          checkConcept<GraphItem<'n'>, Node>();
169          checkConcept<GraphItem<'a'>, Arc>();
170          {
171            Node n;
172            Arc e(INVALID);
173            n = digraph.source(e);
174            n = digraph.target(e);
[57]175            n = digraph.oppositeNode(n, e);
[209]176          }
177        }
178
179        const _Digraph& digraph;
[1125]180        Constraints() {}
[57]181      };
182    };
183
[626]184    /// \brief Base skeleton class for undirected graphs.
[209]185    ///
[626]186    /// This class describes the base interface of undirected graph types.
187    /// All graph %concepts have to conform to this class.
188    /// It extends the interface of \ref BaseDigraphComponent with an
189    /// \c Edge type and functions to get the end nodes of edges,
190    /// to convert from arcs to edges and to get both direction of edges.
[57]191    class BaseGraphComponent : public BaseDigraphComponent {
192    public:
[664]193
194      typedef BaseGraphComponent Graph;
195
[57]196      typedef BaseDigraphComponent::Node Node;
197      typedef BaseDigraphComponent::Arc Arc;
[626]198
199      /// \brief Undirected edge class of the graph.
[57]200      ///
[626]201      /// This class represents the undirected edges of the graph.
202      /// Undirected graphs can be used as directed graphs, each edge is
203      /// represented by two opposite directed arcs.
204      class Edge : public GraphItem<'e'> {
205        typedef GraphItem<'e'> Parent;
206
[664]207      public:
[57]208        /// \brief Default constructor.
[209]209        ///
[626]210        /// Default constructor.
[57]211        /// \warning The default constructor is not required to set
212        /// the item to some well-defined value. So you should consider it
213        /// as uninitialized.
214        Edge() {}
[626]215
[57]216        /// \brief Copy constructor.
217        ///
218        /// Copy constructor.
[626]219        Edge(const Edge &) : Parent() {}
220
221        /// \brief Constructor for conversion from \c INVALID.
[57]222        ///
[626]223        /// Constructor for conversion from \c INVALID.
224        /// It initializes the item to be invalid.
[57]225        /// \sa Invalid for more details.
226        Edge(Invalid) {}
[626]227
228        /// \brief Constructor for conversion from an arc.
[57]229        ///
[626]230        /// Constructor for conversion from an arc.
[57]231        /// Besides the core graph item functionality each arc should
[209]232        /// be convertible to the represented edge.
[57]233        Edge(const Arc&) {}
[713]234     };
[57]235
[626]236      /// \brief Return one end node of an edge.
237      ///
238      /// This function returns one end node of an edge.
239      Node u(const Edge&) const { return INVALID; }
240
241      /// \brief Return the other end node of an edge.
242      ///
243      /// This function returns the other end node of an edge.
244      Node v(const Edge&) const { return INVALID; }
245
246      /// \brief Return a directed arc related to an edge.
247      ///
248      /// This function returns a directed arc from its direction and the
249      /// represented edge.
250      Arc direct(const Edge&, bool) const { return INVALID; }
251
252      /// \brief Return a directed arc related to an edge.
253      ///
254      /// This function returns a directed arc from its source node and the
255      /// represented edge.
256      Arc direct(const Edge&, const Node&) const { return INVALID; }
257
258      /// \brief Return the direction of the arc.
[57]259      ///
260      /// Returns the direction of the arc. Each arc represents an
261      /// edge with a direction. It gives back the
262      /// direction.
263      bool direction(const Arc&) const { return true; }
264
[626]265      /// \brief Return the opposite arc.
[57]266      ///
[626]267      /// This function returns the opposite arc, i.e. the arc representing
268      /// the same edge and has opposite direction.
269      Arc oppositeArc(const Arc&) const { return INVALID; }
[209]270
[57]271      template <typename _Graph>
272      struct Constraints {
[209]273        typedef typename _Graph::Node Node;
274        typedef typename _Graph::Arc Arc;
275        typedef typename _Graph::Edge Edge;
276
277        void constraints() {
[57]278          checkConcept<BaseDigraphComponent, _Graph>();
[626]279          checkConcept<GraphItem<'e'>, Edge>();
[209]280          {
281            Node n;
282            Edge ue(INVALID);
[57]283            Arc e;
[209]284            n = graph.u(ue);
285            n = graph.v(ue);
[57]286            e = graph.direct(ue, true);
[626]287            e = graph.direct(ue, false);
[57]288            e = graph.direct(ue, n);
289            e = graph.oppositeArc(e);
290            ue = e;
291            bool d = graph.direction(e);
[1257]292            ::lemon::ignore_unused_variable_warning(d);
[209]293          }
294        }
295
296        const _Graph& graph;
[1125]297      Constraints() {}
[57]298      };
299
300    };
301
[1186]302    /// \brief Base skeleton class for undirected bipartite graphs.
303    ///
304    /// This class describes the base interface of undirected
305    /// bipartite graph types.  All bipartite graph %concepts have to
306    /// conform to this class.  It extends the interface of \ref
307    /// BaseGraphComponent with an \c Edge type and functions to get
308    /// the end nodes of edges, to convert from arcs to edges and to
309    /// get both direction of edges.
310    class BaseBpGraphComponent : public BaseGraphComponent {
311    public:
312
313      typedef BaseBpGraphComponent BpGraph;
314
315      typedef BaseDigraphComponent::Node Node;
316      typedef BaseDigraphComponent::Arc Arc;
317
318      /// \brief Class to represent red nodes.
319      ///
[1193]320      /// This class represents the red nodes of the graph. The red
[1196]321      /// nodes can also be used as normal nodes.
[1186]322      class RedNode : public Node {
323        typedef Node Parent;
324
325      public:
326        /// \brief Default constructor.
327        ///
328        /// Default constructor.
329        /// \warning The default constructor is not required to set
330        /// the item to some well-defined value. So you should consider it
331        /// as uninitialized.
332        RedNode() {}
333
334        /// \brief Copy constructor.
335        ///
336        /// Copy constructor.
337        RedNode(const RedNode &) : Parent() {}
338
339        /// \brief Constructor for conversion from \c INVALID.
340        ///
341        /// Constructor for conversion from \c INVALID.
342        /// It initializes the item to be invalid.
343        /// \sa Invalid for more details.
344        RedNode(Invalid) {}
345      };
346
347      /// \brief Class to represent blue nodes.
348      ///
[1193]349      /// This class represents the blue nodes of the graph. The blue
[1196]350      /// nodes can also be used as normal nodes.
[1186]351      class BlueNode : public Node {
352        typedef Node Parent;
353
354      public:
355        /// \brief Default constructor.
356        ///
357        /// Default constructor.
358        /// \warning The default constructor is not required to set
359        /// the item to some well-defined value. So you should consider it
360        /// as uninitialized.
361        BlueNode() {}
362
363        /// \brief Copy constructor.
364        ///
365        /// Copy constructor.
366        BlueNode(const BlueNode &) : Parent() {}
367
368        /// \brief Constructor for conversion from \c INVALID.
369        ///
370        /// Constructor for conversion from \c INVALID.
371        /// It initializes the item to be invalid.
372        /// \sa Invalid for more details.
373        BlueNode(Invalid) {}
374
375        /// \brief Constructor for conversion from a node.
376        ///
377        /// Constructor for conversion from a node. The conversion can
378        /// be invalid, since the Node can be member of the red
379        /// set.
380        BlueNode(const Node&) {}
381      };
382
383      /// \brief Gives back %true for red nodes.
384      ///
385      /// Gives back %true for red nodes.
386      bool red(const Node&) const { return true; }
387
388      /// \brief Gives back %true for blue nodes.
389      ///
390      /// Gives back %true for blue nodes.
391      bool blue(const Node&) const { return true; }
392
393      /// \brief Gives back the red end node of the edge.
[1270]394      ///
[1186]395      /// Gives back the red end node of the edge.
[1193]396      RedNode redNode(const Edge&) const { return RedNode(); }
[1186]397
398      /// \brief Gives back the blue end node of the edge.
[1270]399      ///
[1186]400      /// Gives back the blue end node of the edge.
[1193]401      BlueNode blueNode(const Edge&) const { return BlueNode(); }
402
403      /// \brief Converts the node to red node object.
404      ///
[1196]405      /// This function converts unsafely the node to red node
[1193]406      /// object. It should be called only if the node is from the red
407      /// partition or INVALID.
408      RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
409
410      /// \brief Converts the node to blue node object.
411      ///
[1196]412      /// This function converts unsafely the node to blue node
[1193]413      /// object. It should be called only if the node is from the red
414      /// partition or INVALID.
415      BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
416
417      /// \brief Converts the node to red node object.
418      ///
[1196]419      /// This function converts safely the node to red node
[1193]420      /// object. If the node is not from the red partition, then it
421      /// returns INVALID.
422      RedNode asRedNode(const Node&) const { return RedNode(); }
423
424      /// \brief Converts the node to blue node object.
425      ///
[1196]426      /// This function converts unsafely the node to blue node
[1193]427      /// object. If the node is not from the blue partition, then it
428      /// returns INVALID.
429      BlueNode asBlueNode(const Node&) const { return BlueNode(); }
430
[1186]431      template <typename _BpGraph>
432      struct Constraints {
433        typedef typename _BpGraph::Node Node;
434        typedef typename _BpGraph::RedNode RedNode;
435        typedef typename _BpGraph::BlueNode BlueNode;
436        typedef typename _BpGraph::Arc Arc;
437        typedef typename _BpGraph::Edge Edge;
438
439        void constraints() {
440          checkConcept<BaseGraphComponent, _BpGraph>();
441          checkConcept<GraphItem<'n'>, RedNode>();
442          checkConcept<GraphItem<'n'>, BlueNode>();
443          {
444            Node n;
[1193]445            RedNode rn;
446            BlueNode bn;
447            Node rnan = rn;
448            Node bnan = bn;
[1186]449            Edge e;
450            bool b;
[1193]451            b = bpgraph.red(rnan);
452            b = bpgraph.blue(bnan);
453            rn = bpgraph.redNode(e);
454            bn = bpgraph.blueNode(e);
455            rn = bpgraph.asRedNodeUnsafe(rnan);
456            bn = bpgraph.asBlueNodeUnsafe(bnan);
457            rn = bpgraph.asRedNode(rnan);
458            bn = bpgraph.asBlueNode(bnan);
[1262]459            ::lemon::ignore_unused_variable_warning(b);
[1186]460          }
461        }
462
463        const _BpGraph& bpgraph;
464      };
465
466    };
467
[626]468    /// \brief Skeleton class for \e idable directed graphs.
[209]469    ///
[626]470    /// This class describes the interface of \e idable directed graphs.
471    /// It extends \ref BaseDigraphComponent with the core ID functions.
472    /// The ids of the items must be unique and immutable.
473    /// This concept is part of the Digraph concept.
[606]474    template <typename BAS = BaseDigraphComponent>
475    class IDableDigraphComponent : public BAS {
[57]476    public:
477
[606]478      typedef BAS Base;
[57]479      typedef typename Base::Node Node;
480      typedef typename Base::Arc Arc;
481
[626]482      /// \brief Return a unique integer id for the given node.
[57]483      ///
[626]484      /// This function returns a unique integer id for the given node.
485      int id(const Node&) const { return -1; }
486
487      /// \brief Return the node by its unique id.
[57]488      ///
[626]489      /// This function returns the node by its unique id.
490      /// If the digraph does not contain a node with the given id,
491      /// then the result of the function is undefined.
492      Node nodeFromId(int) const { return INVALID; }
[57]493
[626]494      /// \brief Return a unique integer id for the given arc.
[57]495      ///
[626]496      /// This function returns a unique integer id for the given arc.
497      int id(const Arc&) const { return -1; }
[57]498
[626]499      /// \brief Return the arc by its unique id.
[57]500      ///
[626]501      /// This function returns the arc by its unique id.
502      /// If the digraph does not contain an arc with the given id,
503      /// then the result of the function is undefined.
504      Arc arcFromId(int) const { return INVALID; }
505
506      /// \brief Return an integer greater or equal to the maximum
507      /// node id.
[57]508      ///
[626]509      /// This function returns an integer greater or equal to the
510      /// maximum node id.
511      int maxNodeId() const { return -1; }
[57]512
[626]513      /// \brief Return an integer greater or equal to the maximum
514      /// arc id.
[57]515      ///
[626]516      /// This function returns an integer greater or equal to the
517      /// maximum arc id.
518      int maxArcId() const { return -1; }
[57]519
520      template <typename _Digraph>
521      struct Constraints {
522
[209]523        void constraints() {
524          checkConcept<Base, _Digraph >();
525          typename _Digraph::Node node;
[713]526          node=INVALID;
[209]527          int nid = digraph.id(node);
528          nid = digraph.id(node);
529          node = digraph.nodeFromId(nid);
530          typename _Digraph::Arc arc;
[713]531          arc=INVALID;
[209]532          int eid = digraph.id(arc);
533          eid = digraph.id(arc);
534          arc = digraph.arcFromId(eid);
[57]535
[209]536          nid = digraph.maxNodeId();
[1257]537          ::lemon::ignore_unused_variable_warning(nid);
[209]538          eid = digraph.maxArcId();
[1257]539          ::lemon::ignore_unused_variable_warning(eid);
[209]540        }
[57]541
[209]542        const _Digraph& digraph;
[1125]543        Constraints() {}
[57]544      };
545    };
546
[626]547    /// \brief Skeleton class for \e idable undirected graphs.
[209]548    ///
[626]549    /// This class describes the interface of \e idable undirected
550    /// graphs. It extends \ref IDableDigraphComponent with the core ID
551    /// functions of undirected graphs.
552    /// The ids of the items must be unique and immutable.
553    /// This concept is part of the Graph concept.
[606]554    template <typename BAS = BaseGraphComponent>
555    class IDableGraphComponent : public IDableDigraphComponent<BAS> {
[57]556    public:
557
[606]558      typedef BAS Base;
[57]559      typedef typename Base::Edge Edge;
560
[606]561      using IDableDigraphComponent<Base>::id;
[57]562
[626]563      /// \brief Return a unique integer id for the given edge.
[57]564      ///
[626]565      /// This function returns a unique integer id for the given edge.
566      int id(const Edge&) const { return -1; }
567
568      /// \brief Return the edge by its unique id.
[57]569      ///
[626]570      /// This function returns the edge by its unique id.
571      /// If the graph does not contain an edge with the given id,
572      /// then the result of the function is undefined.
573      Edge edgeFromId(int) const { return INVALID; }
[57]574
[626]575      /// \brief Return an integer greater or equal to the maximum
576      /// edge id.
[57]577      ///
[626]578      /// This function returns an integer greater or equal to the
579      /// maximum edge id.
580      int maxEdgeId() const { return -1; }
[57]581
582      template <typename _Graph>
583      struct Constraints {
584
[209]585        void constraints() {
586          checkConcept<IDableDigraphComponent<Base>, _Graph >();
587          typename _Graph::Edge edge;
588          int ueid = graph.id(edge);
589          ueid = graph.id(edge);
590          edge = graph.edgeFromId(ueid);
591          ueid = graph.maxEdgeId();
[1257]592          ::lemon::ignore_unused_variable_warning(ueid);
[209]593        }
[57]594
[209]595        const _Graph& graph;
[1125]596        Constraints() {}
[57]597      };
598    };
599
[1186]600    /// \brief Skeleton class for \e idable undirected bipartite graphs.
601    ///
602    /// This class describes the interface of \e idable undirected
603    /// bipartite graphs. It extends \ref IDableGraphComponent with
604    /// the core ID functions of undirected bipartite graphs. Beside
605    /// the regular node ids, this class also provides ids within the
606    /// the red and blue sets of the nodes. This concept is part of
607    /// the BpGraph concept.
608    template <typename BAS = BaseBpGraphComponent>
609    class IDableBpGraphComponent : public IDableGraphComponent<BAS> {
610    public:
611
612      typedef BAS Base;
613      typedef IDableGraphComponent<BAS> Parent;
614      typedef typename Base::Node Node;
615      typedef typename Base::RedNode RedNode;
616      typedef typename Base::BlueNode BlueNode;
617
618      using Parent::id;
619
620      /// \brief Return a unique integer id for the given node in the red set.
621      ///
622      /// Return a unique integer id for the given node in the red set.
623      int id(const RedNode&) const { return -1; }
624
625      /// \brief Return a unique integer id for the given node in the blue set.
626      ///
627      /// Return a unique integer id for the given node in the blue set.
628      int id(const BlueNode&) const { return -1; }
629
630      /// \brief Return an integer greater or equal to the maximum
631      /// node id in the red set.
632      ///
633      /// Return an integer greater or equal to the maximum
634      /// node id in the red set.
635      int maxRedId() const { return -1; }
636
637      /// \brief Return an integer greater or equal to the maximum
638      /// node id in the blue set.
639      ///
640      /// Return an integer greater or equal to the maximum
641      /// node id in the blue set.
642      int maxBlueId() const { return -1; }
643
644      template <typename _BpGraph>
645      struct Constraints {
646
647        void constraints() {
648          checkConcept<IDableGraphComponent<Base>, _BpGraph>();
649          typename _BpGraph::Node node;
650          typename _BpGraph::RedNode red;
651          typename _BpGraph::BlueNode blue;
[1193]652          int rid = bpgraph.id(red);
653          int bid = bpgraph.id(blue);
[1186]654          rid = bpgraph.maxRedId();
655          bid = bpgraph.maxBlueId();
[1262]656          ::lemon::ignore_unused_variable_warning(rid);
657          ::lemon::ignore_unused_variable_warning(bid);
[1186]658        }
659
660        const _BpGraph& bpgraph;
661      };
662    };
663
[626]664    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
[57]665    ///
[956]666    /// This class describes the concept of \c NodeIt, \c ArcIt and
[626]667    /// \c EdgeIt subtypes of digraph and graph types.
[606]668    template <typename GR, typename Item>
669    class GraphItemIt : public Item {
[57]670    public:
671      /// \brief Default constructor.
672      ///
[626]673      /// Default constructor.
674      /// \warning The default constructor is not required to set
675      /// the iterator to some well-defined value. So you should consider it
676      /// as uninitialized.
[57]677      GraphItemIt() {}
[626]678
[57]679      /// \brief Copy constructor.
680      ///
681      /// Copy constructor.
[626]682      GraphItemIt(const GraphItemIt& it) : Item(it) {}
683
684      /// \brief Constructor that sets the iterator to the first item.
[57]685      ///
[626]686      /// Constructor that sets the iterator to the first item.
687      explicit GraphItemIt(const GR&) {}
688
689      /// \brief Constructor for conversion from \c INVALID.
[57]690      ///
[626]691      /// Constructor for conversion from \c INVALID.
692      /// It initializes the iterator to be invalid.
[57]693      /// \sa Invalid for more details.
694      GraphItemIt(Invalid) {}
[626]695
696      /// \brief Assignment operator.
[57]697      ///
[626]698      /// Assignment operator for the iterator.
699      GraphItemIt& operator=(const GraphItemIt&) { return *this; }
700
701      /// \brief Increment the iterator.
[57]702      ///
[626]703      /// This operator increments the iterator, i.e. assigns it to the
704      /// next item.
[57]705      GraphItemIt& operator++() { return *this; }
[956]706
[57]707      /// \brief Equality operator
[209]708      ///
[626]709      /// Equality operator.
[57]710      /// Two iterators are equal if and only if they point to the
711      /// same object or both are invalid.
712      bool operator==(const GraphItemIt&) const { return true;}
[626]713
[57]714      /// \brief Inequality operator
[209]715      ///
[626]716      /// Inequality operator.
717      /// Two iterators are equal if and only if they point to the
718      /// same object or both are invalid.
[57]719      bool operator!=(const GraphItemIt&) const { return true;}
[209]720
[57]721      template<typename _GraphItemIt>
722      struct Constraints {
[209]723        void constraints() {
[626]724          checkConcept<GraphItem<>, _GraphItemIt>();
[209]725          _GraphItemIt it1(g);
726          _GraphItemIt it2;
[626]727          _GraphItemIt it3 = it1;
728          _GraphItemIt it4 = INVALID;
[1257]729          ::lemon::ignore_unused_variable_warning(it3);
730          ::lemon::ignore_unused_variable_warning(it4);
[57]731
[209]732          it2 = ++it1;
733          ++it2 = it1;
734          ++(++it1);
[57]735
[606]736          Item bi = it1;
[209]737          bi = it2;
738        }
[626]739        const GR& g;
[1125]740        Constraints() {}
[57]741      };
742    };
743
[956]744    /// \brief Concept class for \c InArcIt, \c OutArcIt and
[626]745    /// \c IncEdgeIt types.
[57]746    ///
[956]747    /// This class describes the concept of \c InArcIt, \c OutArcIt
[626]748    /// and \c IncEdgeIt subtypes of digraph and graph types.
749    ///
750    /// \note Since these iterator classes do not inherit from the same
751    /// base class, there is an additional template parameter (selector)
[956]752    /// \c sel. For \c InArcIt you should instantiate it with character
[626]753    /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
[606]754    template <typename GR,
755              typename Item = typename GR::Arc,
756              typename Base = typename GR::Node,
757              char sel = '0'>
758    class GraphIncIt : public Item {
[57]759    public:
760      /// \brief Default constructor.
761      ///
[626]762      /// Default constructor.
763      /// \warning The default constructor is not required to set
764      /// the iterator to some well-defined value. So you should consider it
765      /// as uninitialized.
[57]766      GraphIncIt() {}
[626]767
[57]768      /// \brief Copy constructor.
769      ///
770      /// Copy constructor.
[626]771      GraphIncIt(const GraphIncIt& it) : Item(it) {}
772
[956]773      /// \brief Constructor that sets the iterator to the first
[626]774      /// incoming or outgoing arc.
[57]775      ///
[956]776      /// Constructor that sets the iterator to the first arc
[626]777      /// incoming to or outgoing from the given node.
778      explicit GraphIncIt(const GR&, const Base&) {}
779
780      /// \brief Constructor for conversion from \c INVALID.
[57]781      ///
[626]782      /// Constructor for conversion from \c INVALID.
783      /// It initializes the iterator to be invalid.
[57]784      /// \sa Invalid for more details.
785      GraphIncIt(Invalid) {}
[626]786
787      /// \brief Assignment operator.
[57]788      ///
[626]789      /// Assignment operator for the iterator.
790      GraphIncIt& operator=(const GraphIncIt&) { return *this; }
791
792      /// \brief Increment the iterator.
[57]793      ///
[626]794      /// This operator increments the iterator, i.e. assigns it to the
795      /// next arc incoming to or outgoing from the given node.
[57]796      GraphIncIt& operator++() { return *this; }
797
798      /// \brief Equality operator
799      ///
[626]800      /// Equality operator.
[57]801      /// Two iterators are equal if and only if they point to the
802      /// same object or both are invalid.
803      bool operator==(const GraphIncIt&) const { return true;}
804
805      /// \brief Inequality operator
806      ///
[626]807      /// Inequality operator.
808      /// Two iterators are equal if and only if they point to the
809      /// same object or both are invalid.
[57]810      bool operator!=(const GraphIncIt&) const { return true;}
811
812      template <typename _GraphIncIt>
813      struct Constraints {
[209]814        void constraints() {
[606]815          checkConcept<GraphItem<sel>, _GraphIncIt>();
[209]816          _GraphIncIt it1(graph, node);
817          _GraphIncIt it2;
[626]818          _GraphIncIt it3 = it1;
819          _GraphIncIt it4 = INVALID;
[1257]820          ::lemon::ignore_unused_variable_warning(it3);
821          ::lemon::ignore_unused_variable_warning(it4);
[57]822
[209]823          it2 = ++it1;
824          ++it2 = it1;
825          ++(++it1);
[606]826          Item e = it1;
[209]827          e = it2;
828        }
[626]829        const Base& node;
830        const GR& graph;
[1125]831        Constraints() {}
[57]832      };
833    };
834
[626]835    /// \brief Skeleton class for iterable directed graphs.
[57]836    ///
[626]837    /// This class describes the interface of iterable directed
838    /// graphs. It extends \ref BaseDigraphComponent with the core
839    /// iterable interface.
[57]840    /// This concept is part of the Digraph concept.
[606]841    template <typename BAS = BaseDigraphComponent>
842    class IterableDigraphComponent : public BAS {
[57]843
844    public:
[209]845
[606]846      typedef BAS Base;
[57]847      typedef typename Base::Node Node;
848      typedef typename Base::Arc Arc;
849
850      typedef IterableDigraphComponent Digraph;
851
[631]852      /// \name Base Iteration
[209]853      ///
[626]854      /// This interface provides functions for iteration on digraph items.
[57]855      ///
[209]856      /// @{
[57]857
[626]858      /// \brief Return the first node.
[209]859      ///
[626]860      /// This function gives back the first node in the iteration order.
[57]861      void first(Node&) const {}
862
[626]863      /// \brief Return the next node.
[57]864      ///
[626]865      /// This function gives back the next node in the iteration order.
[57]866      void next(Node&) const {}
867
[626]868      /// \brief Return the first arc.
[57]869      ///
[626]870      /// This function gives back the first arc in the iteration order.
[57]871      void first(Arc&) const {}
872
[626]873      /// \brief Return the next arc.
[57]874      ///
[626]875      /// This function gives back the next arc in the iteration order.
[57]876      void next(Arc&) const {}
877
[1217]878      /// \brief Return the first arc incoming to the given node.
[57]879      ///
[1217]880      /// This function gives back the first arc incoming to the
[626]881      /// given node.
[57]882      void firstIn(Arc&, const Node&) const {}
883
[1217]884      /// \brief Return the next arc incoming to the given node.
[57]885      ///
[1217]886      /// This function gives back the next arc incoming to the
[626]887      /// given node.
[57]888      void nextIn(Arc&) const {}
889
[626]890      /// \brief Return the first arc outgoing form the given node.
891      ///
892      /// This function gives back the first arc outgoing form the
[57]893      /// given node.
894      void firstOut(Arc&, const Node&) const {}
895
[626]896      /// \brief Return the next arc outgoing form the given node.
[57]897      ///
[626]898      /// This function gives back the next arc outgoing form the
899      /// given node.
[57]900      void nextOut(Arc&) const {}
901
902      /// @}
903
[631]904      /// \name Class Based Iteration
[209]905      ///
[626]906      /// This interface provides iterator classes for digraph items.
[57]907      ///
908      /// @{
909
910      /// \brief This iterator goes through each node.
911      ///
912      /// This iterator goes through each node.
913      ///
914      typedef GraphItemIt<Digraph, Node> NodeIt;
915
[626]916      /// \brief This iterator goes through each arc.
[57]917      ///
[626]918      /// This iterator goes through each arc.
[57]919      ///
920      typedef GraphItemIt<Digraph, Arc> ArcIt;
921
922      /// \brief This iterator goes trough the incoming arcs of a node.
923      ///
[626]924      /// This iterator goes trough the \e incoming arcs of a certain node
[57]925      /// of a digraph.
926      typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt;
927
928      /// \brief This iterator goes trough the outgoing arcs of a node.
929      ///
930      /// This iterator goes trough the \e outgoing arcs of a certain node
931      /// of a digraph.
932      typedef GraphIncIt<Digraph, Arc, Node, 'o'> OutArcIt;
933
934      /// \brief The base node of the iterator.
935      ///
[626]936      /// This function gives back the base node of the iterator.
937      /// It is always the target node of the pointed arc.
[57]938      Node baseNode(const InArcIt&) const { return INVALID; }
939
940      /// \brief The running node of the iterator.
941      ///
[626]942      /// This function gives back the running node of the iterator.
943      /// It is always the source node of the pointed arc.
[57]944      Node runningNode(const InArcIt&) const { return INVALID; }
945
946      /// \brief The base node of the iterator.
947      ///
[626]948      /// This function gives back the base node of the iterator.
949      /// It is always the source node of the pointed arc.
[57]950      Node baseNode(const OutArcIt&) const { return INVALID; }
951
952      /// \brief The running node of the iterator.
953      ///
[626]954      /// This function gives back the running node of the iterator.
955      /// It is always the target node of the pointed arc.
[57]956      Node runningNode(const OutArcIt&) const { return INVALID; }
957
958      /// @}
959
[209]960      template <typename _Digraph>
[57]961      struct Constraints {
[209]962        void constraints() {
963          checkConcept<Base, _Digraph>();
[57]964
965          {
[209]966            typename _Digraph::Node node(INVALID);
[57]967            typename _Digraph::Arc arc(INVALID);
968            {
969              digraph.first(node);
970              digraph.next(node);
971            }
972            {
973              digraph.first(arc);
974              digraph.next(arc);
975            }
976            {
977              digraph.firstIn(arc, node);
978              digraph.nextIn(arc);
979            }
980            {
981              digraph.firstOut(arc, node);
982              digraph.nextOut(arc);
983            }
[209]984          }
[57]985
986          {
987            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Arc>,
988              typename _Digraph::ArcIt >();
989            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Node>,
990              typename _Digraph::NodeIt >();
[209]991            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
[57]992              typename _Digraph::Node, 'i'>, typename _Digraph::InArcIt>();
[209]993            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
[57]994              typename _Digraph::Node, 'o'>, typename _Digraph::OutArcIt>();
995
996            typename _Digraph::Node n;
[626]997            const typename _Digraph::InArcIt iait(INVALID);
998            const typename _Digraph::OutArcIt oait(INVALID);
999            n = digraph.baseNode(iait);
1000            n = digraph.runningNode(iait);
1001            n = digraph.baseNode(oait);
1002            n = digraph.runningNode(oait);
[1257]1003            ::lemon::ignore_unused_variable_warning(n);
[57]1004          }
1005        }
[209]1006
1007        const _Digraph& digraph;
[1125]1008        Constraints() {}
[57]1009      };
1010    };
1011
[626]1012    /// \brief Skeleton class for iterable undirected graphs.
[57]1013    ///
[626]1014    /// This class describes the interface of iterable undirected
1015    /// graphs. It extends \ref IterableDigraphComponent with the core
1016    /// iterable interface of undirected graphs.
[57]1017    /// This concept is part of the Graph concept.
[606]1018    template <typename BAS = BaseGraphComponent>
1019    class IterableGraphComponent : public IterableDigraphComponent<BAS> {
[57]1020    public:
1021
[606]1022      typedef BAS Base;
[57]1023      typedef typename Base::Node Node;
1024      typedef typename Base::Arc Arc;
1025      typedef typename Base::Edge Edge;
1026
[209]1027
[57]1028      typedef IterableGraphComponent Graph;
1029
[631]1030      /// \name Base Iteration
[209]1031      ///
[626]1032      /// This interface provides functions for iteration on edges.
1033      ///
[209]1034      /// @{
[57]1035
[606]1036      using IterableDigraphComponent<Base>::first;
1037      using IterableDigraphComponent<Base>::next;
[57]1038
[626]1039      /// \brief Return the first edge.
[57]1040      ///
[626]1041      /// This function gives back the first edge in the iteration order.
[57]1042      void first(Edge&) const {}
1043
[626]1044      /// \brief Return the next edge.
[57]1045      ///
[626]1046      /// This function gives back the next edge in the iteration order.
[57]1047      void next(Edge&) const {}
1048
[626]1049      /// \brief Return the first edge incident to the given node.
1050      ///
[956]1051      /// This function gives back the first edge incident to the given
[626]1052      /// node. The bool parameter gives back the direction for which the
[956]1053      /// source node of the directed arc representing the edge is the
[57]1054      /// given node.
1055      void firstInc(Edge&, bool&, const Node&) const {}
1056
1057      /// \brief Gives back the next of the edges from the
1058      /// given node.
1059      ///
[956]1060      /// This function gives back the next edge incident to the given
[626]1061      /// node. The bool parameter should be used as \c firstInc() use it.
[57]1062      void nextInc(Edge&, bool&) const {}
1063
[606]1064      using IterableDigraphComponent<Base>::baseNode;
1065      using IterableDigraphComponent<Base>::runningNode;
[57]1066
1067      /// @}
1068
[631]1069      /// \name Class Based Iteration
[209]1070      ///
[626]1071      /// This interface provides iterator classes for edges.
[57]1072      ///
1073      /// @{
1074
[626]1075      /// \brief This iterator goes through each edge.
[57]1076      ///
[626]1077      /// This iterator goes through each edge.
[57]1078      typedef GraphItemIt<Graph, Edge> EdgeIt;
[626]1079
1080      /// \brief This iterator goes trough the incident edges of a
[57]1081      /// node.
1082      ///
[626]1083      /// This iterator goes trough the incident edges of a certain
[57]1084      /// node of a graph.
[626]1085      typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt;
1086
[57]1087      /// \brief The base node of the iterator.
1088      ///
[626]1089      /// This function gives back the base node of the iterator.
[78]1090      Node baseNode(const IncEdgeIt&) const { return INVALID; }
[57]1091
1092      /// \brief The running node of the iterator.
1093      ///
[626]1094      /// This function gives back the running node of the iterator.
[78]1095      Node runningNode(const IncEdgeIt&) const { return INVALID; }
[57]1096
1097      /// @}
1098
[209]1099      template <typename _Graph>
[57]1100      struct Constraints {
[209]1101        void constraints() {
1102          checkConcept<IterableDigraphComponent<Base>, _Graph>();
[57]1103
1104          {
1105            typename _Graph::Node node(INVALID);
1106            typename _Graph::Edge edge(INVALID);
1107            bool dir;
1108            {
1109              graph.first(edge);
1110              graph.next(edge);
1111            }
1112            {
1113              graph.firstInc(edge, dir, node);
1114              graph.nextInc(edge, dir);
1115            }
[209]1116
1117          }
1118
[57]1119          {
1120            checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
1121              typename _Graph::EdgeIt >();
[209]1122            checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
[626]1123              typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>();
[209]1124
[57]1125            typename _Graph::Node n;
[626]1126            const typename _Graph::IncEdgeIt ieit(INVALID);
1127            n = graph.baseNode(ieit);
1128            n = graph.runningNode(ieit);
[57]1129          }
1130        }
[209]1131
1132        const _Graph& graph;
[1125]1133        Constraints() {}
[57]1134      };
1135    };
1136
[1186]1137    /// \brief Skeleton class for iterable undirected bipartite graphs.
1138    ///
1139    /// This class describes the interface of iterable undirected
1140    /// bipartite graphs. It extends \ref IterableGraphComponent with
1141    /// the core iterable interface of undirected bipartite graphs.
1142    /// This concept is part of the BpGraph concept.
1143    template <typename BAS = BaseBpGraphComponent>
1144    class IterableBpGraphComponent : public IterableGraphComponent<BAS> {
1145    public:
1146
1147      typedef BAS Base;
1148      typedef typename Base::Node Node;
[1193]1149      typedef typename Base::RedNode RedNode;
1150      typedef typename Base::BlueNode BlueNode;
[1186]1151      typedef typename Base::Arc Arc;
1152      typedef typename Base::Edge Edge;
[1270]1153
[1193]1154      typedef IterableBpGraphComponent BpGraph;
[1186]1155
[1193]1156      using IterableGraphComponent<BAS>::first;
1157      using IterableGraphComponent<BAS>::next;
[1186]1158
1159      /// \name Base Iteration
1160      ///
1161      /// This interface provides functions for iteration on red and blue nodes.
1162      ///
1163      /// @{
1164
1165      /// \brief Return the first red node.
1166      ///
1167      /// This function gives back the first red node in the iteration order.
[1193]1168      void first(RedNode&) const {}
[1186]1169
1170      /// \brief Return the next red node.
1171      ///
1172      /// This function gives back the next red node in the iteration order.
[1193]1173      void next(RedNode&) const {}
[1186]1174
1175      /// \brief Return the first blue node.
1176      ///
1177      /// This function gives back the first blue node in the iteration order.
[1193]1178      void first(BlueNode&) const {}
[1186]1179
1180      /// \brief Return the next blue node.
1181      ///
1182      /// This function gives back the next blue node in the iteration order.
[1193]1183      void next(BlueNode&) const {}
[1186]1184
1185
1186      /// @}
1187
1188      /// \name Class Based Iteration
1189      ///
1190      /// This interface provides iterator classes for red and blue nodes.
1191      ///
1192      /// @{
1193
1194      /// \brief This iterator goes through each red node.
1195      ///
1196      /// This iterator goes through each red node.
[1194]1197      typedef GraphItemIt<BpGraph, RedNode> RedNodeIt;
[1186]1198
1199      /// \brief This iterator goes through each blue node.
1200      ///
1201      /// This iterator goes through each blue node.
[1194]1202      typedef GraphItemIt<BpGraph, BlueNode> BlueNodeIt;
[1186]1203
1204      /// @}
1205
1206      template <typename _BpGraph>
1207      struct Constraints {
1208        void constraints() {
1209          checkConcept<IterableGraphComponent<Base>, _BpGraph>();
1210
[1193]1211          typename _BpGraph::RedNode rn(INVALID);
1212          bpgraph.first(rn);
[1270]1213          bpgraph.next(rn);
[1193]1214          typename _BpGraph::BlueNode bn(INVALID);
1215          bpgraph.first(bn);
1216          bpgraph.next(bn);
[1186]1217
[1193]1218          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::RedNode>,
[1194]1219            typename _BpGraph::RedNodeIt>();
[1193]1220          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::BlueNode>,
[1194]1221            typename _BpGraph::BlueNodeIt>();
[1186]1222        }
1223
1224        const _BpGraph& bpgraph;
1225      };
1226    };
1227
[626]1228    /// \brief Skeleton class for alterable directed graphs.
[209]1229    ///
[626]1230    /// This class describes the interface of alterable directed
1231    /// graphs. It extends \ref BaseDigraphComponent with the alteration
1232    /// notifier interface. It implements
[57]1233    /// an observer-notifier pattern for each digraph item. More
1234    /// obsevers can be registered into the notifier and whenever an
[626]1235    /// alteration occured in the digraph all the observers will be
[57]1236    /// notified about it.
[606]1237    template <typename BAS = BaseDigraphComponent>
1238    class AlterableDigraphComponent : public BAS {
[57]1239    public:
1240
[606]1241      typedef BAS Base;
[57]1242      typedef typename Base::Node Node;
1243      typedef typename Base::Arc Arc;
1244
1245
[626]1246      /// Node alteration notifier class.
[209]1247      typedef AlterationNotifier<AlterableDigraphComponent, Node>
[57]1248      NodeNotifier;
[626]1249      /// Arc alteration notifier class.
[209]1250      typedef AlterationNotifier<AlterableDigraphComponent, Arc>
[57]1251      ArcNotifier;
[209]1252
[1186]1253      mutable NodeNotifier node_notifier;
1254      mutable ArcNotifier arc_notifier;
1255
[626]1256      /// \brief Return the node alteration notifier.
[57]1257      ///
[626]1258      /// This function gives back the node alteration notifier.
[57]1259      NodeNotifier& notifier(Node) const {
[1186]1260        return node_notifier;
[57]1261      }
[209]1262
[626]1263      /// \brief Return the arc alteration notifier.
[57]1264      ///
[626]1265      /// This function gives back the arc alteration notifier.
[57]1266      ArcNotifier& notifier(Arc) const {
[1186]1267        return arc_notifier;
[57]1268      }
1269
[209]1270      template <typename _Digraph>
[57]1271      struct Constraints {
[209]1272        void constraints() {
1273          checkConcept<Base, _Digraph>();
1274          typename _Digraph::NodeNotifier& nn
[57]1275            = digraph.notifier(typename _Digraph::Node());
1276
[209]1277          typename _Digraph::ArcNotifier& en
[57]1278            = digraph.notifier(typename _Digraph::Arc());
[209]1279
[1257]1280          ::lemon::ignore_unused_variable_warning(nn);
1281          ::lemon::ignore_unused_variable_warning(en);
[209]1282        }
1283
1284        const _Digraph& digraph;
[1125]1285        Constraints() {}
[57]1286      };
1287    };
1288
[626]1289    /// \brief Skeleton class for alterable undirected graphs.
[209]1290    ///
[626]1291    /// This class describes the interface of alterable undirected
1292    /// graphs. It extends \ref AlterableDigraphComponent with the alteration
1293    /// notifier interface of undirected graphs. It implements
1294    /// an observer-notifier pattern for the edges. More
[57]1295    /// obsevers can be registered into the notifier and whenever an
[626]1296    /// alteration occured in the graph all the observers will be
[57]1297    /// notified about it.
[606]1298    template <typename BAS = BaseGraphComponent>
1299    class AlterableGraphComponent : public AlterableDigraphComponent<BAS> {
[57]1300    public:
1301
[606]1302      typedef BAS Base;
[1186]1303      typedef AlterableDigraphComponent<Base> Parent;
[57]1304      typedef typename Base::Edge Edge;
1305
1306
[626]1307      /// Edge alteration notifier class.
[209]1308      typedef AlterationNotifier<AlterableGraphComponent, Edge>
[57]1309      EdgeNotifier;
[209]1310
[1186]1311      mutable EdgeNotifier edge_notifier;
1312
1313      using Parent::notifier;
1314
[626]1315      /// \brief Return the edge alteration notifier.
[57]1316      ///
[626]1317      /// This function gives back the edge alteration notifier.
[57]1318      EdgeNotifier& notifier(Edge) const {
[1186]1319        return edge_notifier;
[57]1320      }
1321
[209]1322      template <typename _Graph>
[57]1323      struct Constraints {
[209]1324        void constraints() {
[626]1325          checkConcept<AlterableDigraphComponent<Base>, _Graph>();
[209]1326          typename _Graph::EdgeNotifier& uen
[57]1327            = graph.notifier(typename _Graph::Edge());
[1257]1328          ::lemon::ignore_unused_variable_warning(uen);
[209]1329        }
1330
1331        const _Graph& graph;
[1125]1332        Constraints() {}
[57]1333      };
1334    };
1335
[1186]1336    /// \brief Skeleton class for alterable undirected bipartite graphs.
1337    ///
1338    /// This class describes the interface of alterable undirected
1339    /// bipartite graphs. It extends \ref AlterableGraphComponent with
1340    /// the alteration notifier interface of bipartite graphs. It
1341    /// implements an observer-notifier pattern for the red and blue
1342    /// nodes. More obsevers can be registered into the notifier and
1343    /// whenever an alteration occured in the graph all the observers
1344    /// will be notified about it.
1345    template <typename BAS = BaseBpGraphComponent>
1346    class AlterableBpGraphComponent : public AlterableGraphComponent<BAS> {
1347    public:
1348
1349      typedef BAS Base;
1350      typedef AlterableGraphComponent<Base> Parent;
1351      typedef typename Base::RedNode RedNode;
1352      typedef typename Base::BlueNode BlueNode;
1353
1354
1355      /// Red node alteration notifier class.
1356      typedef AlterationNotifier<AlterableBpGraphComponent, RedNode>
1357      RedNodeNotifier;
1358
1359      /// Blue node alteration notifier class.
1360      typedef AlterationNotifier<AlterableBpGraphComponent, BlueNode>
1361      BlueNodeNotifier;
1362
1363      mutable RedNodeNotifier red_node_notifier;
1364      mutable BlueNodeNotifier blue_node_notifier;
1365
1366      using Parent::notifier;
1367
1368      /// \brief Return the red node alteration notifier.
1369      ///
1370      /// This function gives back the red node alteration notifier.
1371      RedNodeNotifier& notifier(RedNode) const {
1372        return red_node_notifier;
1373      }
1374
1375      /// \brief Return the blue node alteration notifier.
1376      ///
1377      /// This function gives back the blue node alteration notifier.
1378      BlueNodeNotifier& notifier(BlueNode) const {
1379        return blue_node_notifier;
1380      }
1381
1382      template <typename _BpGraph>
1383      struct Constraints {
1384        void constraints() {
1385          checkConcept<AlterableGraphComponent<Base>, _BpGraph>();
1386          typename _BpGraph::RedNodeNotifier& rnn
1387            = bpgraph.notifier(typename _BpGraph::RedNode());
1388          typename _BpGraph::BlueNodeNotifier& bnn
1389            = bpgraph.notifier(typename _BpGraph::BlueNode());
[1262]1390          ::lemon::ignore_unused_variable_warning(rnn);
1391          ::lemon::ignore_unused_variable_warning(bnn);
[1186]1392        }
1393
1394        const _BpGraph& bpgraph;
1395      };
1396    };
1397
[626]1398    /// \brief Concept class for standard graph maps.
[209]1399    ///
[626]1400    /// This class describes the concept of standard graph maps, i.e.
[956]1401    /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
[626]1402    /// graph types, which can be used for associating data to graph items.
[627]1403    /// The standard graph maps must conform to the ReferenceMap concept.
[606]1404    template <typename GR, typename K, typename V>
[627]1405    class GraphMap : public ReferenceMap<K, V, V&, const V&> {
[664]1406      typedef ReferenceMap<K, V, V&, const V&> Parent;
1407
[57]1408    public:
1409
1410      /// The key type of the map.
[606]1411      typedef K Key;
[57]1412      /// The value type of the map.
[606]1413      typedef V Value;
[627]1414      /// The reference type of the map.
1415      typedef Value& Reference;
1416      /// The const reference type of the map.
1417      typedef const Value& ConstReference;
1418
1419      // The reference map tag.
1420      typedef True ReferenceMapTag;
[57]1421
1422      /// \brief Construct a new map.
1423      ///
1424      /// Construct a new map for the graph.
[664]1425      explicit GraphMap(const GR&) {}
[57]1426      /// \brief Construct a new map with default value.
1427      ///
[626]1428      /// Construct a new map for the graph and initalize the values.
[664]1429      GraphMap(const GR&, const Value&) {}
[263]1430
1431    private:
[57]1432      /// \brief Copy constructor.
1433      ///
1434      /// Copy Constructor.
1435      GraphMap(const GraphMap&) : Parent() {}
[209]1436
[626]1437      /// \brief Assignment operator.
[57]1438      ///
[626]1439      /// Assignment operator. It does not mofify the underlying graph,
[57]1440      /// it just iterates on the current item set and set the  map
[209]1441      /// with the value returned by the assigned map.
[57]1442      template <typename CMap>
[209]1443      GraphMap& operator=(const CMap&) {
[57]1444        checkConcept<ReadMap<Key, Value>, CMap>();
1445        return *this;
1446      }
1447
[263]1448    public:
[57]1449      template<typename _Map>
1450      struct Constraints {
[209]1451        void constraints() {
[627]1452          checkConcept
1453            <ReferenceMap<Key, Value, Value&, const Value&>, _Map>();
[626]1454          _Map m1(g);
1455          _Map m2(g,t);
[956]1456
[626]1457          // Copy constructor
1458          // _Map m3(m);
[209]1459
[626]1460          // Assignment operator
[263]1461          // ReadMap<Key, Value> cmap;
[626]1462          // m3 = cmap;
[57]1463
[1257]1464          ::lemon::ignore_unused_variable_warning(m1);
1465          ::lemon::ignore_unused_variable_warning(m2);
1466          // ::lemon::ignore_unused_variable_warning(m3);
[209]1467        }
[57]1468
[626]1469        const _Map &m;
[664]1470        const GR &g;
[209]1471        const typename GraphMap::Value &t;
[1125]1472        Constraints() {}
[57]1473      };
1474
1475    };
1476
[626]1477    /// \brief Skeleton class for mappable directed graphs.
[57]1478    ///
[626]1479    /// This class describes the interface of mappable directed graphs.
[956]1480    /// It extends \ref BaseDigraphComponent with the standard digraph
[626]1481    /// map classes, namely \c NodeMap and \c ArcMap.
[57]1482    /// This concept is part of the Digraph concept.
[606]1483    template <typename BAS = BaseDigraphComponent>
1484    class MappableDigraphComponent : public BAS  {
[57]1485    public:
1486
[606]1487      typedef BAS Base;
[57]1488      typedef typename Base::Node Node;
1489      typedef typename Base::Arc Arc;
1490
1491      typedef MappableDigraphComponent Digraph;
1492
[626]1493      /// \brief Standard graph map for the nodes.
[57]1494      ///
[626]1495      /// Standard graph map for the nodes.
[627]1496      /// It conforms to the ReferenceMap concept.
[606]1497      template <typename V>
[626]1498      class NodeMap : public GraphMap<MappableDigraphComponent, Node, V> {
[606]1499        typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
[57]1500
[664]1501      public:
[209]1502        /// \brief Construct a new map.
1503        ///
1504        /// Construct a new map for the digraph.
1505        explicit NodeMap(const MappableDigraphComponent& digraph)
[57]1506          : Parent(digraph) {}
1507
[209]1508        /// \brief Construct a new map with default value.
1509        ///
[626]1510        /// Construct a new map for the digraph and initalize the values.
[606]1511        NodeMap(const MappableDigraphComponent& digraph, const V& value)
[57]1512          : Parent(digraph, value) {}
1513
[263]1514      private:
[209]1515        /// \brief Copy constructor.
1516        ///
1517        /// Copy Constructor.
1518        NodeMap(const NodeMap& nm) : Parent(nm) {}
[57]1519
[626]1520        /// \brief Assignment operator.
[209]1521        ///
[626]1522        /// Assignment operator.
[57]1523        template <typename CMap>
[209]1524        NodeMap& operator=(const CMap&) {
[606]1525          checkConcept<ReadMap<Node, V>, CMap>();
[57]1526          return *this;
1527        }
1528
1529      };
1530
[626]1531      /// \brief Standard graph map for the arcs.
[57]1532      ///
[626]1533      /// Standard graph map for the arcs.
[627]1534      /// It conforms to the ReferenceMap concept.
[606]1535      template <typename V>
[626]1536      class ArcMap : public GraphMap<MappableDigraphComponent, Arc, V> {
[606]1537        typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;
[57]1538
[664]1539      public:
[209]1540        /// \brief Construct a new map.
1541        ///
1542        /// Construct a new map for the digraph.
1543        explicit ArcMap(const MappableDigraphComponent& digraph)
[57]1544          : Parent(digraph) {}
1545
[209]1546        /// \brief Construct a new map with default value.
1547        ///
[626]1548        /// Construct a new map for the digraph and initalize the values.
[606]1549        ArcMap(const MappableDigraphComponent& digraph, const V& value)
[57]1550          : Parent(digraph, value) {}
1551
[263]1552      private:
[209]1553        /// \brief Copy constructor.
1554        ///
1555        /// Copy Constructor.
1556        ArcMap(const ArcMap& nm) : Parent(nm) {}
[57]1557
[626]1558        /// \brief Assignment operator.
[209]1559        ///
[626]1560        /// Assignment operator.
[57]1561        template <typename CMap>
[209]1562        ArcMap& operator=(const CMap&) {
[606]1563          checkConcept<ReadMap<Arc, V>, CMap>();
[57]1564          return *this;
1565        }
1566
1567      };
1568
1569
1570      template <typename _Digraph>
1571      struct Constraints {
1572
[209]1573        struct Dummy {
1574          int value;
1575          Dummy() : value(0) {}
1576          Dummy(int _v) : value(_v) {}
1577        };
[57]1578
[209]1579        void constraints() {
1580          checkConcept<Base, _Digraph>();
1581          { // int map test
1582            typedef typename _Digraph::template NodeMap<int> IntNodeMap;
1583            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, int>,
1584              IntNodeMap >();
1585          } { // bool map test
1586            typedef typename _Digraph::template NodeMap<bool> BoolNodeMap;
1587            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, bool>,
1588              BoolNodeMap >();
1589          } { // Dummy map test
1590            typedef typename _Digraph::template NodeMap<Dummy> DummyNodeMap;
1591            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, Dummy>,
1592              DummyNodeMap >();
1593          }
[57]1594
[209]1595          { // int map test
1596            typedef typename _Digraph::template ArcMap<int> IntArcMap;
1597            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, int>,
1598              IntArcMap >();
1599          } { // bool map test
1600            typedef typename _Digraph::template ArcMap<bool> BoolArcMap;
1601            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, bool>,
1602              BoolArcMap >();
1603          } { // Dummy map test
1604            typedef typename _Digraph::template ArcMap<Dummy> DummyArcMap;
1605            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, Dummy>,
1606              DummyArcMap >();
1607          }
1608        }
[57]1609
[626]1610        const _Digraph& digraph;
[1125]1611        Constraints() {}
[57]1612      };
1613    };
1614
[626]1615    /// \brief Skeleton class for mappable undirected graphs.
[57]1616    ///
[626]1617    /// This class describes the interface of mappable undirected graphs.
[956]1618    /// It extends \ref MappableDigraphComponent with the standard graph
[626]1619    /// map class for edges (\c EdgeMap).
[57]1620    /// This concept is part of the Graph concept.
[606]1621    template <typename BAS = BaseGraphComponent>
1622    class MappableGraphComponent : public MappableDigraphComponent<BAS>  {
[57]1623    public:
1624
[606]1625      typedef BAS Base;
[57]1626      typedef typename Base::Edge Edge;
1627
1628      typedef MappableGraphComponent Graph;
1629
[626]1630      /// \brief Standard graph map for the edges.
[57]1631      ///
[626]1632      /// Standard graph map for the edges.
[627]1633      /// It conforms to the ReferenceMap concept.
[606]1634      template <typename V>
[626]1635      class EdgeMap : public GraphMap<MappableGraphComponent, Edge, V> {
[606]1636        typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
[57]1637
[664]1638      public:
[209]1639        /// \brief Construct a new map.
1640        ///
1641        /// Construct a new map for the graph.
1642        explicit EdgeMap(const MappableGraphComponent& graph)
[57]1643          : Parent(graph) {}
1644
[209]1645        /// \brief Construct a new map with default value.
1646        ///
[626]1647        /// Construct a new map for the graph and initalize the values.
[606]1648        EdgeMap(const MappableGraphComponent& graph, const V& value)
[57]1649          : Parent(graph, value) {}
1650
[263]1651      private:
[209]1652        /// \brief Copy constructor.
1653        ///
1654        /// Copy Constructor.
1655        EdgeMap(const EdgeMap& nm) : Parent(nm) {}
[57]1656
[626]1657        /// \brief Assignment operator.
[209]1658        ///
[626]1659        /// Assignment operator.
[57]1660        template <typename CMap>
[209]1661        EdgeMap& operator=(const CMap&) {
[606]1662          checkConcept<ReadMap<Edge, V>, CMap>();
[57]1663          return *this;
1664        }
1665
1666      };
1667
1668
1669      template <typename _Graph>
1670      struct Constraints {
1671
[209]1672        struct Dummy {
1673          int value;
1674          Dummy() : value(0) {}
1675          Dummy(int _v) : value(_v) {}
1676        };
[57]1677
[209]1678        void constraints() {
[626]1679          checkConcept<MappableDigraphComponent<Base>, _Graph>();
[57]1680
[209]1681          { // int map test
1682            typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
1683            checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
1684              IntEdgeMap >();
1685          } { // bool map test
1686            typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
1687            checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
1688              BoolEdgeMap >();
1689          } { // Dummy map test
1690            typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
1691            checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
1692              DummyEdgeMap >();
1693          }
1694        }
[57]1695
[626]1696        const _Graph& graph;
[1125]1697        Constraints() {}
[57]1698      };
1699    };
1700
[1186]1701    /// \brief Skeleton class for mappable undirected bipartite graphs.
1702    ///
1703    /// This class describes the interface of mappable undirected
1704    /// bipartite graphs.  It extends \ref MappableGraphComponent with
1705    /// the standard graph map class for red and blue nodes (\c
[1194]1706    /// RedNodeMap and BlueNodeMap). This concept is part of the
1707    /// BpGraph concept.
[1186]1708    template <typename BAS = BaseBpGraphComponent>
1709    class MappableBpGraphComponent : public MappableGraphComponent<BAS>  {
1710    public:
1711
1712      typedef BAS Base;
1713      typedef typename Base::Node Node;
1714
1715      typedef MappableBpGraphComponent BpGraph;
1716
1717      /// \brief Standard graph map for the red nodes.
1718      ///
1719      /// Standard graph map for the red nodes.
1720      /// It conforms to the ReferenceMap concept.
1721      template <typename V>
[1194]1722      class RedNodeMap : public GraphMap<MappableBpGraphComponent, Node, V> {
[1186]1723        typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
1724
1725      public:
1726        /// \brief Construct a new map.
1727        ///
1728        /// Construct a new map for the graph.
[1194]1729        explicit RedNodeMap(const MappableBpGraphComponent& graph)
[1186]1730          : Parent(graph) {}
1731
1732        /// \brief Construct a new map with default value.
1733        ///
1734        /// Construct a new map for the graph and initalize the values.
[1194]1735        RedNodeMap(const MappableBpGraphComponent& graph, const V& value)
[1186]1736          : Parent(graph, value) {}
1737
1738      private:
1739        /// \brief Copy constructor.
1740        ///
1741        /// Copy Constructor.
[1194]1742        RedNodeMap(const RedNodeMap& nm) : Parent(nm) {}
[1186]1743
1744        /// \brief Assignment operator.
1745        ///
1746        /// Assignment operator.
1747        template <typename CMap>
[1194]1748        RedNodeMap& operator=(const CMap&) {
[1186]1749          checkConcept<ReadMap<Node, V>, CMap>();
1750          return *this;
1751        }
1752
1753      };
1754
1755      /// \brief Standard graph map for the blue nodes.
1756      ///
1757      /// Standard graph map for the blue nodes.
1758      /// It conforms to the ReferenceMap concept.
1759      template <typename V>
[1194]1760      class BlueNodeMap : public GraphMap<MappableBpGraphComponent, Node, V> {
[1186]1761        typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
1762
1763      public:
1764        /// \brief Construct a new map.
1765        ///
1766        /// Construct a new map for the graph.
[1194]1767        explicit BlueNodeMap(const MappableBpGraphComponent& graph)
[1186]1768          : Parent(graph) {}
1769
1770        /// \brief Construct a new map with default value.
1771        ///
1772        /// Construct a new map for the graph and initalize the values.
[1194]1773        BlueNodeMap(const MappableBpGraphComponent& graph, const V& value)
[1186]1774          : Parent(graph, value) {}
1775
1776      private:
1777        /// \brief Copy constructor.
1778        ///
1779        /// Copy Constructor.
[1194]1780        BlueNodeMap(const BlueNodeMap& nm) : Parent(nm) {}
[1186]1781
1782        /// \brief Assignment operator.
1783        ///
1784        /// Assignment operator.
1785        template <typename CMap>
[1194]1786        BlueNodeMap& operator=(const CMap&) {
[1186]1787          checkConcept<ReadMap<Node, V>, CMap>();
1788          return *this;
1789        }
1790
1791      };
1792
1793
1794      template <typename _BpGraph>
1795      struct Constraints {
1796
1797        struct Dummy {
1798          int value;
1799          Dummy() : value(0) {}
1800          Dummy(int _v) : value(_v) {}
1801        };
1802
1803        void constraints() {
1804          checkConcept<MappableGraphComponent<Base>, _BpGraph>();
1805
1806          { // int map test
[1194]1807            typedef typename _BpGraph::template RedNodeMap<int>
1808              IntRedNodeMap;
[1193]1809            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, int>,
[1194]1810              IntRedNodeMap >();
[1186]1811          } { // bool map test
[1194]1812            typedef typename _BpGraph::template RedNodeMap<bool>
1813              BoolRedNodeMap;
[1193]1814            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, bool>,
[1194]1815              BoolRedNodeMap >();
[1186]1816          } { // Dummy map test
[1194]1817            typedef typename _BpGraph::template RedNodeMap<Dummy>
1818              DummyRedNodeMap;
[1193]1819            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, Dummy>,
[1194]1820              DummyRedNodeMap >();
[1186]1821          }
1822
1823          { // int map test
[1194]1824            typedef typename _BpGraph::template BlueNodeMap<int>
1825              IntBlueNodeMap;
[1193]1826            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, int>,
[1194]1827              IntBlueNodeMap >();
[1186]1828          } { // bool map test
[1194]1829            typedef typename _BpGraph::template BlueNodeMap<bool>
1830              BoolBlueNodeMap;
[1193]1831            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, bool>,
[1194]1832              BoolBlueNodeMap >();
[1186]1833          } { // Dummy map test
[1194]1834            typedef typename _BpGraph::template BlueNodeMap<Dummy>
1835              DummyBlueNodeMap;
[1193]1836            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, Dummy>,
[1194]1837              DummyBlueNodeMap >();
[1186]1838          }
1839        }
1840
1841        const _BpGraph& bpgraph;
1842      };
1843    };
1844
[626]1845    /// \brief Skeleton class for extendable directed graphs.
[57]1846    ///
[626]1847    /// This class describes the interface of extendable directed graphs.
[956]1848    /// It extends \ref BaseDigraphComponent with functions for adding
[626]1849    /// nodes and arcs to the digraph.
1850    /// This concept requires \ref AlterableDigraphComponent.
[606]1851    template <typename BAS = BaseDigraphComponent>
1852    class ExtendableDigraphComponent : public BAS {
[57]1853    public:
[606]1854      typedef BAS Base;
[57]1855
[606]1856      typedef typename Base::Node Node;
1857      typedef typename Base::Arc Arc;
[57]1858
[626]1859      /// \brief Add a new node to the digraph.
[57]1860      ///
[626]1861      /// This function adds a new node to the digraph.
[57]1862      Node addNode() {
[209]1863        return INVALID;
[57]1864      }
[209]1865
[626]1866      /// \brief Add a new arc connecting the given two nodes.
[57]1867      ///
[626]1868      /// This function adds a new arc connecting the given two nodes
1869      /// of the digraph.
[57]1870      Arc addArc(const Node&, const Node&) {
[209]1871        return INVALID;
[57]1872      }
1873
1874      template <typename _Digraph>
1875      struct Constraints {
[209]1876        void constraints() {
[57]1877          checkConcept<Base, _Digraph>();
[209]1878          typename _Digraph::Node node_a, node_b;
1879          node_a = digraph.addNode();
1880          node_b = digraph.addNode();
1881          typename _Digraph::Arc arc;
1882          arc = digraph.addArc(node_a, node_b);
1883        }
[57]1884
[209]1885        _Digraph& digraph;
[1125]1886        Constraints() {}
[57]1887      };
1888    };
1889
[626]1890    /// \brief Skeleton class for extendable undirected graphs.
[57]1891    ///
[626]1892    /// This class describes the interface of extendable undirected graphs.
[956]1893    /// It extends \ref BaseGraphComponent with functions for adding
[626]1894    /// nodes and edges to the graph.
1895    /// This concept requires \ref AlterableGraphComponent.
[606]1896    template <typename BAS = BaseGraphComponent>
1897    class ExtendableGraphComponent : public BAS {
[57]1898    public:
1899
[606]1900      typedef BAS Base;
1901      typedef typename Base::Node Node;
1902      typedef typename Base::Edge Edge;
[57]1903
[626]1904      /// \brief Add a new node to the digraph.
[57]1905      ///
[626]1906      /// This function adds a new node to the digraph.
[57]1907      Node addNode() {
[209]1908        return INVALID;
[57]1909      }
[209]1910
[626]1911      /// \brief Add a new edge connecting the given two nodes.
[57]1912      ///
[626]1913      /// This function adds a new edge connecting the given two nodes
1914      /// of the graph.
1915      Edge addEdge(const Node&, const Node&) {
[209]1916        return INVALID;
[57]1917      }
1918
1919      template <typename _Graph>
1920      struct Constraints {
[209]1921        void constraints() {
1922          checkConcept<Base, _Graph>();
1923          typename _Graph::Node node_a, node_b;
1924          node_a = graph.addNode();
1925          node_b = graph.addNode();
1926          typename _Graph::Edge edge;
1927          edge = graph.addEdge(node_a, node_b);
1928        }
[57]1929
[209]1930        _Graph& graph;
[1125]1931        Constraints() {}
[57]1932      };
1933    };
1934
[1186]1935    /// \brief Skeleton class for extendable undirected bipartite graphs.
1936    ///
1937    /// This class describes the interface of extendable undirected
1938    /// bipartite graphs. It extends \ref BaseGraphComponent with
1939    /// functions for adding nodes and edges to the graph. This
1940    /// concept requires \ref AlterableBpGraphComponent.
1941    template <typename BAS = BaseBpGraphComponent>
1942    class ExtendableBpGraphComponent : public BAS {
1943    public:
1944
1945      typedef BAS Base;
1946      typedef typename Base::Node Node;
[1193]1947      typedef typename Base::RedNode RedNode;
1948      typedef typename Base::BlueNode BlueNode;
[1186]1949      typedef typename Base::Edge Edge;
1950
1951      /// \brief Add a new red node to the digraph.
1952      ///
1953      /// This function adds a red new node to the digraph.
[1193]1954      RedNode addRedNode() {
[1186]1955        return INVALID;
1956      }
1957
1958      /// \brief Add a new blue node to the digraph.
1959      ///
1960      /// This function adds a blue new node to the digraph.
[1193]1961      BlueNode addBlueNode() {
[1186]1962        return INVALID;
1963      }
1964
1965      /// \brief Add a new edge connecting the given two nodes.
1966      ///
1967      /// This function adds a new edge connecting the given two nodes
1968      /// of the graph. The first node has to be a red node, and the
1969      /// second one a blue node.
[1193]1970      Edge addEdge(const RedNode&, const BlueNode&) {
1971        return INVALID;
1972      }
1973      Edge addEdge(const BlueNode&, const RedNode&) {
[1186]1974        return INVALID;
1975      }
1976
1977      template <typename _BpGraph>
1978      struct Constraints {
1979        void constraints() {
1980          checkConcept<Base, _BpGraph>();
[1193]1981          typename _BpGraph::RedNode red_node;
1982          typename _BpGraph::BlueNode blue_node;
[1186]1983          red_node = bpgraph.addRedNode();
1984          blue_node = bpgraph.addBlueNode();
1985          typename _BpGraph::Edge edge;
1986          edge = bpgraph.addEdge(red_node, blue_node);
[1193]1987          edge = bpgraph.addEdge(blue_node, red_node);
[1186]1988        }
1989
1990        _BpGraph& bpgraph;
1991      };
1992    };
1993
[626]1994    /// \brief Skeleton class for erasable directed graphs.
[209]1995    ///
[626]1996    /// This class describes the interface of erasable directed graphs.
[956]1997    /// It extends \ref BaseDigraphComponent with functions for removing
[626]1998    /// nodes and arcs from the digraph.
1999    /// This concept requires \ref AlterableDigraphComponent.
[606]2000    template <typename BAS = BaseDigraphComponent>
2001    class ErasableDigraphComponent : public BAS {
[57]2002    public:
2003
[606]2004      typedef BAS Base;
[57]2005      typedef typename Base::Node Node;
2006      typedef typename Base::Arc Arc;
2007
2008      /// \brief Erase a node from the digraph.
2009      ///
[956]2010      /// This function erases the given node from the digraph and all arcs
[626]2011      /// connected to the node.
[209]2012      void erase(const Node&) {}
[57]2013
2014      /// \brief Erase an arc from the digraph.
2015      ///
[626]2016      /// This function erases the given arc from the digraph.
[57]2017      void erase(const Arc&) {}
2018
2019      template <typename _Digraph>
2020      struct Constraints {
[209]2021        void constraints() {
[57]2022          checkConcept<Base, _Digraph>();
[626]2023          const typename _Digraph::Node node(INVALID);
[209]2024          digraph.erase(node);
[626]2025          const typename _Digraph::Arc arc(INVALID);
[209]2026          digraph.erase(arc);
2027        }
[57]2028
[209]2029        _Digraph& digraph;
[1125]2030        Constraints() {}
[57]2031      };
2032    };
2033
[626]2034    /// \brief Skeleton class for erasable undirected graphs.
[209]2035    ///
[626]2036    /// This class describes the interface of erasable undirected graphs.
[956]2037    /// It extends \ref BaseGraphComponent with functions for removing
[626]2038    /// nodes and edges from the graph.
2039    /// This concept requires \ref AlterableGraphComponent.
[606]2040    template <typename BAS = BaseGraphComponent>
2041    class ErasableGraphComponent : public BAS {
[57]2042    public:
2043
[606]2044      typedef BAS Base;
[57]2045      typedef typename Base::Node Node;
2046      typedef typename Base::Edge Edge;
2047
2048      /// \brief Erase a node from the graph.
2049      ///
[626]2050      /// This function erases the given node from the graph and all edges
2051      /// connected to the node.
[209]2052      void erase(const Node&) {}
[57]2053
[626]2054      /// \brief Erase an edge from the digraph.
[57]2055      ///
[626]2056      /// This function erases the given edge from the digraph.
[57]2057      void erase(const Edge&) {}
2058
2059      template <typename _Graph>
2060      struct Constraints {
[209]2061        void constraints() {
[57]2062          checkConcept<Base, _Graph>();
[626]2063          const typename _Graph::Node node(INVALID);
[209]2064          graph.erase(node);
[626]2065          const typename _Graph::Edge edge(INVALID);
[209]2066          graph.erase(edge);
2067        }
[57]2068
[209]2069        _Graph& graph;
[1125]2070        Constraints() {}
[57]2071      };
2072    };
2073
[1186]2074    /// \brief Skeleton class for erasable undirected graphs.
2075    ///
2076    /// This class describes the interface of erasable undirected
2077    /// bipartite graphs. It extends \ref BaseBpGraphComponent with
2078    /// functions for removing nodes and edges from the graph. This
2079    /// concept requires \ref AlterableBpGraphComponent.
2080    template <typename BAS = BaseBpGraphComponent>
2081    class ErasableBpGraphComponent : public ErasableGraphComponent<BAS> {};
2082
[626]2083    /// \brief Skeleton class for clearable directed graphs.
[57]2084    ///
[626]2085    /// This class describes the interface of clearable directed graphs.
2086    /// It extends \ref BaseDigraphComponent with a function for clearing
2087    /// the digraph.
2088    /// This concept requires \ref AlterableDigraphComponent.
[606]2089    template <typename BAS = BaseDigraphComponent>
2090    class ClearableDigraphComponent : public BAS {
[57]2091    public:
2092
[606]2093      typedef BAS Base;
[57]2094
2095      /// \brief Erase all nodes and arcs from the digraph.
2096      ///
[626]2097      /// This function erases all nodes and arcs from the digraph.
[209]2098      void clear() {}
[57]2099
2100      template <typename _Digraph>
2101      struct Constraints {
[209]2102        void constraints() {
[57]2103          checkConcept<Base, _Digraph>();
[209]2104          digraph.clear();
2105        }
[57]2106
[626]2107        _Digraph& digraph;
[1125]2108        Constraints() {}
[57]2109      };
2110    };
2111
[626]2112    /// \brief Skeleton class for clearable undirected graphs.
[57]2113    ///
[626]2114    /// This class describes the interface of clearable undirected graphs.
2115    /// It extends \ref BaseGraphComponent with a function for clearing
2116    /// the graph.
2117    /// This concept requires \ref AlterableGraphComponent.
[606]2118    template <typename BAS = BaseGraphComponent>
[1186]2119    class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {};
[57]2120
[1186]2121    /// \brief Skeleton class for clearable undirected biparite graphs.
2122    ///
2123    /// This class describes the interface of clearable undirected
2124    /// bipartite graphs. It extends \ref BaseBpGraphComponent with a
2125    /// function for clearing the graph.  This concept requires \ref
2126    /// AlterableBpGraphComponent.
2127    template <typename BAS = BaseBpGraphComponent>
2128    class ClearableBpGraphComponent : public ClearableGraphComponent<BAS> {};
[57]2129
2130  }
2131
2132}
2133
2134#endif
Note: See TracBrowser for help on using the repository browser.