COIN-OR::LEMON - Graph Library

Changeset 2121:09a07a851506 in lemon-0.x


Ignore:
Timestamp:
07/10/06 21:04:17 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2834
Message:

Modifications in the Graph Component concepts

Files:
5 edited

Legend:

Unmodified
Added
Removed
  • lemon/concept/graph.h

    r2120 r2121  
    3333  namespace concept {
    3434
    35    
    36     /**************** The full-featured graph concepts ****************/
    37 
    38 
    39     // \brief Modular static graph class.
    40     //     
    41     // It should be the same as the \c Graph class.
    42     class _Graph
    43       :  virtual public BaseGraphComponent,
    44          public IterableGraphComponent, public MappableGraphComponent {
    45     public:
    46 
    47       typedef BaseGraphComponent::Node Node;
    48       typedef BaseGraphComponent::Edge Edge;
    49 
    50       template <typename _Graph>
    51       struct Constraints {
    52         void constraints() {
    53           checkConcept<IterableGraphComponent, _Graph>();
    54           checkConcept<MappableGraphComponent, _Graph>();
    55         }
    56       };
    57     };
    58 
    5935    /// \addtogroup graph_concepts
    6036    /// @{
     
    411387      /// \warning Making maps that can handle bool type (NodeMap<bool>)
    412388      /// needs some extra attention!
    413       /// \todo Wrong documentation
    414389      template<class T>
    415       class NodeMap : public ReadWriteMap< Node, T >
    416       {
     390      class NodeMap : public ReadWriteMap< Node, T > {
    417391      public:
    418392
     
    425399        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
    426400        ///Assignment operator
    427         NodeMap& operator=(const NodeMap&) { return *this; }
    428         // \todo fix this concept
     401        template <typename CMap>
     402        NodeMap& operator=(const CMap&) {
     403          checkConcept<ReadMap<Node, T>, CMap>();
     404          return *this;
     405        }
    429406      };
    430407
     
    435412      /// \warning Making maps that can handle bool type (EdgeMap<bool>)
    436413      /// needs some extra attention!
    437       /// \todo Wrong documentation
    438414      template<class T>
    439       class EdgeMap : public ReadWriteMap<Edge,T>
    440       {
     415      class EdgeMap : public ReadWriteMap<Edge,T> {
    441416      public:
    442417
     
    448423        EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
    449424        ///Assignment operator
    450         EdgeMap& operator=(const EdgeMap&) { return *this; }
    451         // \todo fix this concept   
     425        template <typename CMap>
     426        EdgeMap& operator=(const CMap&) {
     427          checkConcept<ReadMap<Edge, T>, CMap>();
     428          return *this;
     429        }
    452430      };
    453431
    454432      template <typename RGraph>
    455       struct Constraints : public _Graph::Constraints<RGraph> {};
     433      struct Constraints {
     434        void constraints() {
     435          checkConcept<BaseIterableGraphComponent<>, Graph>();
     436          checkConcept<IterableGraphComponent<>, Graph>();
     437          checkConcept<MappableGraphComponent<>, Graph>();
     438        }
     439      };
    456440
    457441    };
  • lemon/concept/graph_component.h

    r2111 r2121  
    3333  namespace concept {
    3434
    35     /****************   Graph iterator concepts   ****************/
    36 
    37     /// Skeleton class for graph Node and Edge types
    38 
     35    /// \brief Skeleton class for graph Node and Edge types
     36    ///
    3937    /// This class describes the interface of Node and Edge (and UEdge
    4038    /// in undirected graphs) subtypes of graph types.
     
    5149    class GraphItem {
    5250    public:
    53       /// Default constructor.
    54      
     51      /// \brief Default constructor.
     52      ///     
    5553      /// \warning The default constructor is not required to set
    5654      /// the item to some well-defined value. So you should consider it
    5755      /// as uninitialized.
    5856      GraphItem() {}
     57      /// \brief Copy constructor.
     58      ///
    5959      /// Copy constructor.
    60      
    61       /// Copy constructor.
    62       ///
    63       GraphItem(GraphItem const&) {}
    64       /// Invalid constructor \& conversion.
    65 
     60      ///
     61      GraphItem(const GraphItem &) {}
     62      /// \brief Invalid constructor \& conversion.
     63      ///
    6664      /// This constructor initializes the item to be invalid.
    6765      /// \sa Invalid for more details.
    6866      GraphItem(Invalid) {}
    69       /// Assign operator for nodes.
    70 
     67      /// \brief Assign operator for nodes.
     68      ///
    7169      /// The nodes are assignable.
    7270      ///
    7371      GraphItem& operator=(GraphItem const&) { return *this; }
    74       /// Equality operator.
    75      
     72      /// \brief Equality operator.
     73      ///
    7674      /// Two iterators are equal if and only if they represents the
    7775      /// same node in the graph or both are invalid.
    7876      bool operator==(GraphItem) const { return false; }
    79       /// Inequality operator.
    80        
     77      /// \brief Inequality operator.
     78      ///
    8179      /// \sa operator==(const Node& n)
    8280      ///
    8381      bool operator!=(GraphItem) const { return false; }
    8482
    85       /// Artificial ordering operator.
    86 
     83      /// \brief Artificial ordering operator.
     84      ///
    8785      /// To allow the use of graph descriptors as key type in std::map or
    8886      /// similar associative container we require this.
     
    9189      /// the items; this order has nothing to do with the iteration
    9290      /// ordering of the items.
    93       ///
    94       /// \bug This is a technical requirement. Do we really need this?
    9591      bool operator<(GraphItem) const { return false; }
    9692
     
    108104          b = (ia == ib) && (ia != ib);
    109105          b = (ia == INVALID) && (ib != INVALID);
    110           //      b = (ia < ib);
     106          b = (ia < ib);
    111107        }
    112108
     
    116112    };
    117113
    118     /// A type describing the concept of graph node
    119 
    120     /// This is an instantiation of \ref GraphItem which can be used as a
    121     /// Node subtype in graph skeleton definitions
    122     typedef GraphItem<'n'> GraphNode;
    123 
    124     /// A type describing the concept of graph edge
    125 
    126     /// This is an instantiation of \ref GraphItem which can be used as a
    127     /// Edge subtype in graph skeleton definitions
    128     typedef GraphItem<'e'> GraphEdge;
    129 
    130 
    131     /**************** Basic features of graphs ****************/
    132 
    133     /// An empty base graph class.
    134  
     114    /// \brief An empty base graph class.
     115    /// 
    135116    /// This class provides the minimal set of features needed for a graph
    136117    /// structure. All graph concepts have to be conform to this base
    137     /// graph.
    138     ///
    139     /// \bug This is not true. The minimal graph concept is the
    140     /// BaseIterableGraphComponent.
    141 
     118    /// graph. It just provides types for nodes and edges and functions to
     119    /// get the source and the target of the edges.
    142120    class BaseGraphComponent {
    143121    public:
     
    145123      typedef BaseGraphComponent Graph;
    146124     
    147       /// Node class of the graph.
    148 
     125      /// \brief Node class of the graph.
     126      ///
    149127      /// This class represents the Nodes of the graph.
    150128      ///
    151129      typedef GraphItem<'n'> Node;
    152130
    153       /// Edge class of the graph.
    154 
     131      /// \brief Edge class of the graph.
     132      ///
    155133      /// This class represents the Edges of the graph.
    156134      ///
    157135      typedef GraphItem<'e'> Edge;
    158136
    159       ///Gives back the target node of an edge.
    160 
    161       ///Gives back the target node of an edge.
     137      /// \brief Gives back the target node of an edge.
     138      ///
     139      /// Gives back the target node of an edge.
    162140      ///
    163141      Node target(const Edge&) const { return INVALID;}
    164142
    165       ///Gives back the source node of an edge.
    166 
    167       ///Gives back the source node of an edge.
     143      /// \brief Gives back the source node of an edge.
     144      ///
     145      /// Gives back the source node of an edge.
    168146      ///
    169147      Node source(const Edge&) const { return INVALID;}
    170148
     149      /// \brief Gives back the opposite node on the given edge.
     150      ///
     151      /// Gives back the opposite node on the given edge.
     152      Node oppositeNode(const Node&, const Edge&) const {
     153        return INVALID;
     154      }
    171155
    172156      template <typename _Graph>
     
    183167            n = graph.source(e);
    184168            n = graph.target(e);
     169            n = graph.oppositeNode(n, e);
    185170          }     
    186171        }
     
    190175    };
    191176
    192     /// An empty iterable base graph class.
    193  
     177    /// \brief An empty base undirected graph class.
     178    /// 
     179    /// This class provides the minimal set of features needed for an
     180    /// undirected graph structure. All undirected graph concepts have
     181    /// to be conform to this base graph. It just provides types for
     182    /// nodes, edges and undirected edges and functions to get the
     183    /// source and the target of the edges and undirected edges,
     184    /// conversion from edges to undirected edges and function to get
     185    /// both direction of the undirected edges.
     186    class BaseUGraphComponent : public BaseGraphComponent {
     187    public:
     188      typedef BaseGraphComponent::Node Node;
     189      typedef BaseGraphComponent::Edge Edge;
     190      /// \brief Undirected edge class of the graph.
     191      ///
     192      /// This class represents the undirected edges of the graph.
     193      /// The undirected graphs can be used as a directed graph which
     194      /// for each edge contains the opposite edge too so the graph is
     195      /// bidirected. The undirected edge represents two opposite
     196      /// directed edges.
     197      class UEdge : public GraphItem<'u'> {
     198      public:
     199        typedef GraphItem<'u'> Parent;
     200        /// \brief Default constructor.
     201        ///     
     202        /// \warning The default constructor is not required to set
     203        /// the item to some well-defined value. So you should consider it
     204        /// as uninitialized.
     205        UEdge() {}
     206        /// \brief Copy constructor.
     207        ///
     208        /// Copy constructor.
     209        ///
     210        UEdge(const UEdge &) : Parent() {}
     211        /// \brief Invalid constructor \& conversion.
     212        ///
     213        /// This constructor initializes the item to be invalid.
     214        /// \sa Invalid for more details.
     215        UEdge(Invalid) {}
     216        /// \brief Converter from edge to undirected edge.
     217        ///
     218        /// Besides the core graph item functionality each edge should
     219        /// be convertible to the represented undirected edge.
     220        UEdge(const Edge&) {}
     221      };
     222
     223      /// \brief Returns the direction of the edge.
     224      ///
     225      /// Returns the direction of the edge. Each edge represents an
     226      /// undirected edge with a direction. It gives back the
     227      /// direction.
     228      bool direction(const Edge&) const { return true; }
     229
     230      /// \brief Returns the directed edge.
     231      ///
     232      /// Returns the directed edge from its direction and the
     233      /// represented undirected edge.
     234      Edge direct(const UEdge&, bool) const { return INVALID;}
     235
     236      /// \brief Returns the directed edge.
     237      ///
     238      /// Returns the directed edge from its source and the
     239      /// represented undirected edge.
     240      Edge direct(const UEdge&, const Node&) const { return INVALID;}
     241
     242      /// \brief Returns the opposite edge.
     243      ///
     244      /// Returns the opposite edge. It is the edge representing the
     245      /// same undirected edge and has opposite direction.
     246      Edge oppositeEdge(const Edge&) const { return INVALID;}
     247
     248      /// \brief Gives back the target node of an undirected edge.
     249      ///
     250      /// Gives back the target node of an undirected edge. The name
     251      /// target is a little confusing because the undirected edge
     252      /// does not have target but it just means that one of the end
     253      /// node.
     254      Node target(const UEdge&) const { return INVALID;}
     255
     256      /// \brief Gives back the source node of an undirected edge.
     257      ///
     258      /// Gives back the source node of an undirected edge. The name
     259      /// source is a little confusing because the undirected edge
     260      /// does not have source but it just means that one of the end
     261      /// node.
     262      Node source(const UEdge&) const { return INVALID;}
     263     
     264      template <typename _Graph>
     265      struct Constraints {
     266        typedef typename _Graph::Node Node;
     267        typedef typename _Graph::Edge Edge;
     268        typedef typename _Graph::UEdge UEdge;
     269     
     270        void constraints() {
     271          checkConcept<BaseGraphComponent, _Graph>();
     272          checkConcept<GraphItem<'u'>, UEdge>();
     273          {
     274            Node n;
     275            UEdge ue(INVALID);
     276            Edge e;
     277            n = graph.source(ue);
     278            n = graph.target(ue);
     279            e = graph.direct(ue, true);
     280            e = graph.direct(ue, n);
     281            e = graph.oppositeEdge(e);
     282            ue = e;
     283            bool d = graph.direction(e);
     284            ignore_unused_variable_warning(d);
     285          }     
     286        }
     287     
     288        const _Graph& graph;
     289      };
     290
     291    };
     292
     293    /// \brief An empty iterable base graph class.
     294    /// 
    194295    /// This class provides beside the core graph features
    195296    /// core iterable interface for the graph structure.
    196297    /// Most of the base graphs should be conform to this concept.
    197 
    198     class BaseIterableGraphComponent : virtual public BaseGraphComponent {
    199     public:
    200 
    201       typedef BaseGraphComponent::Node Node;
    202       typedef BaseGraphComponent::Edge Edge;
    203 
    204       /// Gives back the first Node in the iterating order.
    205      
    206       /// Gives back the first Node in the iterating order.
     298    template <typename _Base = BaseGraphComponent>
     299    class BaseIterableGraphComponent : public _Base {
     300    public:
     301
     302      typedef _Base Base;
     303      typedef typename Base::Node Node;
     304      typedef typename Base::Edge Edge;
     305
     306      /// \brief Gives back the first node in the iterating order.
     307      ///     
     308      /// Gives back the first node in the iterating order.
    207309      ///     
    208310      void first(Node&) const {}
    209311
    210       /// Gives back the next Node in the iterating order.
    211      
    212       /// Gives back the next Node in the iterating order.
     312      /// \brief Gives back the next node in the iterating order.
     313      ///
     314      /// Gives back the next node in the iterating order.
    213315      ///     
    214316      void next(Node&) const {}
    215317
    216       /// Gives back the first Edge in the iterating order.
    217      
    218       /// Gives back the first Edge in the iterating order.
     318      /// \brief Gives back the first edge in the iterating order.
     319      ///
     320      /// Gives back the first edge in the iterating order.
    219321      ///     
    220322      void first(Edge&) const {}
    221       /// Gives back the next Edge in the iterating order.
    222      
    223       /// Gives back the next Edge in the iterating order.
     323
     324      /// \brief Gives back the next edge in the iterating order.
     325      ///
     326      /// Gives back the next edge in the iterating order.
    224327      ///     
    225328      void next(Edge&) const {}
    226329
    227330
    228       /// Gives back the first of the Edges point to the given Node.
    229      
    230       /// Gives back the first of the Edges point to the given Node.
     331      /// \brief Gives back the first of the edges point to the given
     332      /// node.
     333      ///
     334      /// Gives back the first of the edges point to the given node.
    231335      ///     
    232336      void firstIn(Edge&, const Node&) const {}
    233337
    234       /// Gives back the next of the Edges points to the given Node.
    235 
    236 
    237       /// Gives back the next of the Edges points to the given Node.
     338      /// \brief Gives back the next of the edges points to the given
     339      /// node.
     340      ///
     341      /// Gives back the next of the edges points to the given node.
    238342      ///
    239343      void nextIn(Edge&) const {}
    240344
    241       /// Gives back the first of the Edges start from the given Node.
    242      
    243       /// Gives back the first of the Edges start from the given Node.
     345      /// \brief Gives back the first of the edges start from the
     346      /// given node.
     347      ///     
     348      /// Gives back the first of the edges start from the given node.
    244349      ///     
    245350      void firstOut(Edge&, const Node&) const {}
    246351
    247       /// Gives back the next of the Edges start from the given Node.
    248      
    249       /// Gives back the next of the Edges start from the given Node.
     352      /// \brief Gives back the next of the edges start from the given
     353      /// node.
     354      ///
     355      /// Gives back the next of the edges start from the given node.
    250356      ///     
    251357      void nextOut(Edge&) const {}
     
    281387    };
    282388
    283     /// An empty idable base graph class.
    284  
     389    /// \brief An empty iterable base undirected graph class.
     390    /// 
     391    /// This class provides beside the core undirceted graph features
     392    /// core iterable interface for the undirected graph structure.
     393    /// Most of the base undirected graphs should be conform to this
     394    /// concept.
     395    template <typename _Base = BaseUGraphComponent>
     396    class BaseIterableUGraphComponent
     397      : public BaseIterableGraphComponent<_Base> {
     398    public:
     399
     400      typedef _Base Base;
     401      typedef typename Base::UEdge UEdge;
     402      typedef typename Base::Node Node;
     403
     404      using BaseIterableGraphComponent<_Base>::first;
     405      using BaseIterableGraphComponent<_Base>::next;
     406
     407      /// \brief Gives back the first undirected edge in the iterating
     408      /// order.
     409      ///
     410      /// Gives back the first undirected edge in the iterating order.
     411      ///     
     412      void first(UEdge&) const {}
     413
     414      /// \brief Gives back the next undirected edge in the iterating
     415      /// order.
     416      ///
     417      /// Gives back the next undirected edge in the iterating order.
     418      ///     
     419      void next(UEdge&) const {}
     420
     421
     422      /// \brief Gives back the first of the undirected edges from the
     423      /// given node.
     424      ///
     425      /// Gives back the first of the undirected edges from the given
     426      /// node. The bool parameter gives back that direction which
     427      /// gives a good direction of the uedge so the source of the
     428      /// directed edge is the given node.
     429      void firstInc(UEdge&, bool&, const Node&) const {}
     430
     431      /// \brief Gives back the next of the undirected edges from the
     432      /// given node.
     433      ///
     434      /// Gives back the next of the undirected edges from the given
     435      /// node. The bool parameter should be used as the \c firstInc()
     436      /// use it.
     437      void nextInc(UEdge&, bool&) const {}
     438
     439      template <typename _Graph>
     440      struct Constraints {
     441     
     442        void constraints() {
     443          checkConcept<Base, _Graph >();
     444          checkConcept<BaseIterableGraphComponent<Base>, _Graph>();
     445          typename _Graph::Node node;
     446          typename _Graph::UEdge uedge;
     447          bool dir;
     448          {
     449            graph.first(uedge);
     450            graph.next(uedge);
     451          }
     452          {
     453            graph.firstInc(uedge, dir, node);
     454            graph.nextInc(uedge, dir);
     455          }
     456        }
     457
     458        const _Graph& graph;
     459      };
     460    };
     461
     462    /// \brief An empty idable base graph class.
     463    /// 
    285464    /// This class provides beside the core graph features
    286465    /// core id functions for the graph structure.
    287466    /// The most of the base graphs should be conform to this concept.
    288467    /// The id's are unique and immutable.
    289     class IDableGraphComponent : virtual public BaseGraphComponent {
    290     public:
    291 
    292       typedef BaseGraphComponent::Node Node;
    293       typedef BaseGraphComponent::Edge Edge;
    294 
    295       /// Gives back an unique integer id for the Node.
    296 
     468    template <typename _Base = BaseGraphComponent>
     469    class IDableGraphComponent : public _Base {
     470    public:
     471
     472      typedef _Base Base;
     473      typedef typename Base::Node Node;
     474      typedef typename Base::Edge Edge;
     475
     476      /// \brief Gives back an unique integer id for the Node.
     477      ///
    297478      /// Gives back an unique integer id for the Node.
    298479      ///
     
    304485      /// If the graph does not contain node with the given id
    305486      /// then the result of the function is undetermined.
    306       Node fromId(int , Node) const { return INVALID;}
     487      Node nodeFromId(int) const { return INVALID;}
    307488
    308489      /// \brief Gives back an unique integer id for the Edge.
     
    317498      /// If the graph does not contain edge with the given id
    318499      /// then the result of the function is undetermined.
    319       Edge fromId(int, Edge) const { return INVALID;}
     500      Edge edgeFromId(int) const { return INVALID;}
     501
     502      /// \brief Gives back an integer greater or equal to the maximum
     503      /// Node id.
     504      ///
     505      /// Gives back an integer greater or equal to the maximum Node
     506      /// id.
     507      int maxNodeId() const { return -1;}
     508
     509      /// \brief Gives back an integer greater or equal to the maximum
     510      /// Edge id.
     511      ///
     512      /// Gives back an integer greater or equal to the maximum Edge
     513      /// id.
     514      int maxEdgeId() const { return -1;}
    320515
    321516      template <typename _Graph>
     
    327522          int nid = graph.id(node);
    328523          nid = graph.id(node);
    329           node = graph.fromId(nid, Node());
     524          node = graph.nodeFromId(nid);
    330525          typename _Graph::Edge edge;
    331526          int eid = graph.id(edge);
    332527          eid = graph.id(edge);
    333           edge = graph.fromId(eid, Edge());
     528          edge = graph.edgeFromId(eid);
     529
     530          nid = graph.maxNodeId();
     531          ignore_unused_variable_warning(nid);
     532          eid = graph.maxEdgeId();
     533          ignore_unused_variable_warning(eid);
    334534        }
    335535
     
    338538    };
    339539
    340 
    341     /// An empty max-idable base graph class.
    342  
    343     /// This class provides beside the core graph features
    344     /// core max id functions for the graph structure.
    345     /// The most of the base graphs should be conform to this concept.
    346     /// The id's are unique and immutable.
    347     class MaxIDableGraphComponent : virtual public BaseGraphComponent {
    348     public:
    349 
    350       /// Gives back an integer greater or equal to the maximum Node id.
    351 
    352       /// Gives back an integer greater or equal to the maximum Node id.
    353       ///
    354       int maxId(Node = INVALID) const { return -1;}
    355 
    356       /// Gives back an integer greater or equal to the maximum Edge id.
    357 
    358       /// Gives back an integer greater or equal to the maximum Edge id.
    359       ///
    360       int maxId(Edge = INVALID) const { return -1;}
    361 
    362       template <typename _Graph>
    363       struct Constraints {
    364 
    365         void constraints() {
    366           checkConcept<BaseGraphComponent, _Graph>();
    367           int nid = graph.maxId(typename _Graph::Node());
    368           ignore_unused_variable_warning(nid);
    369           int eid = graph.maxId(typename _Graph::Edge());
    370           ignore_unused_variable_warning(eid);
    371         }
    372      
     540    /// \brief An empty idable base undirected graph class.
     541    /// 
     542    /// This class provides beside the core undirected graph features
     543    /// core id functions for the undirected graph structure.  The
     544    /// most of the base undirected graphs should be conform to this
     545    /// concept.  The id's are unique and immutable.
     546    template <typename _Base = BaseUGraphComponent>
     547    class IDableUGraphComponent : public IDableGraphComponent<_Base> {
     548    public:
     549
     550      typedef _Base Base;
     551      typedef typename Base::UEdge UEdge;
     552
     553      using IDableGraphComponent<_Base>::id;
     554
     555      /// \brief Gives back an unique integer id for the UEdge.
     556      ///
     557      /// Gives back an unique integer id for the UEdge.
     558      ///
     559      int id(const UEdge&) const { return -1;}
     560
     561      /// \brief Gives back the undirected edge by the unique id.
     562      ///
     563      /// Gives back the undirected edge by the unique id.  If the
     564      /// graph does not contain edge with the given id then the
     565      /// result of the function is undetermined.
     566      UEdge uEdgeFromId(int) const { return INVALID;}
     567
     568      /// \brief Gives back an integer greater or equal to the maximum
     569      /// UEdge id.
     570      ///
     571      /// Gives back an integer greater or equal to the maximum UEdge
     572      /// id.
     573      int maxUEdgeId() const { return -1;}
     574
     575      template <typename _Graph>
     576      struct Constraints {
     577
     578        void constraints() {
     579          checkConcept<Base, _Graph >();
     580          checkConcept<IDableGraphComponent<Base>, _Graph >();
     581          typename _Graph::UEdge uedge;
     582          int ueid = graph.id(uedge);
     583          ueid = graph.id(uedge);
     584          uedge = graph.uEdgeFromId(ueid);
     585          ueid = graph.maxUEdgeId();
     586          ignore_unused_variable_warning(ueid);
     587        }
     588
    373589        const _Graph& graph;
    374590      };
    375591    };
    376592
    377     /// An empty extendable base graph class.
    378  
     593    /// \brief An empty extendable base graph class.
     594    ///
    379595    /// This class provides beside the core graph features
    380596    /// core graph extend interface for the graph structure.
    381597    /// The most of the base graphs should be conform to this concept.
    382     class BaseExtendableGraphComponent : virtual public BaseGraphComponent {
    383     public:
    384 
    385       typedef BaseGraphComponent::Node Node;
    386       typedef BaseGraphComponent::Edge Edge;
    387 
    388       /// Adds a new Node to the graph.
    389 
    390       /// Adds a new Node to the graph.
     598    template <typename _Base = BaseGraphComponent>
     599    class BaseExtendableGraphComponent : public _Base {
     600    public:
     601
     602      typedef typename _Base::Node Node;
     603      typedef typename _Base::Edge Edge;
     604
     605      /// \brief Adds a new node to the graph.
     606      ///
     607      /// Adds a new node to the graph.
    391608      ///
    392609      Node addNode() {
     
    394611      }
    395612   
    396       /// Adds a new Edge connects the two Nodes to the graph.
    397 
    398       /// Adds a new Edge connects the two Nodes to the graph.
    399       ///
     613      /// \brief Adds a new edge connects the given two nodes.
     614      ///
     615      /// Adds a new edge connects the the given two nodes.
    400616      Edge addEdge(const Node&, const Node&) {
    401617        return INVALID;
     
    405621      struct Constraints {
    406622        void constraints() {
    407           checkConcept<BaseGraphComponent, _Graph >();
    408623          typename _Graph::Node node_a, node_b;
    409624          node_a = graph.addNode();
     
    417632    };
    418633
    419     /// An empty erasable base graph class.
    420  
     634    /// \brief An empty extendable base undirected graph class.
     635    ///
     636    /// This class provides beside the core undirected graph features
     637    /// core undircted graph extend interface for the graph structure.
     638    /// The most of the base graphs should be conform to this concept.
     639    template <typename _Base = BaseUGraphComponent>
     640    class BaseExtendableUGraphComponent : public _Base {
     641    public:
     642
     643      typedef typename _Base::Node Node;
     644      typedef typename _Base::UEdge UEdge;
     645
     646      /// \brief Adds a new node to the graph.
     647      ///
     648      /// Adds a new node to the graph.
     649      ///
     650      Node addNode() {
     651        return INVALID;
     652      }
     653   
     654      /// \brief Adds a new edge connects the given two nodes.
     655      ///
     656      /// Adds a new edge connects the the given two nodes.
     657      UEdge addEdge(const Node&, const Node&) {
     658        return INVALID;
     659      }
     660
     661      template <typename _Graph>
     662      struct Constraints {
     663        void constraints() {
     664          typename _Graph::Node node_a, node_b;
     665          node_a = graph.addNode();
     666          node_b = graph.addNode();
     667          typename _Graph::UEdge uedge;
     668          uedge = graph.addUEdge(node_a, node_b);
     669        }
     670
     671        _Graph& graph;
     672      };
     673    };
     674
     675    /// \brief An empty erasable base graph class.
     676    /// 
    421677    /// This class provides beside the core graph features
    422678    /// core erase functions for the graph structure.
    423679    /// The most of the base graphs should be conform to this concept.
    424     class BaseErasableGraphComponent : virtual public BaseGraphComponent {
    425     public:
    426 
    427       typedef BaseGraphComponent::Node Node;
    428       typedef BaseGraphComponent::Edge Edge;
    429 
    430       /// Erase a Node from the graph.
    431      
    432       /// Erase a Node from the graph. This function should not
     680    template <typename _Base = BaseGraphComponent>
     681    class BaseErasableGraphComponent : public _Base {
     682    public:
     683
     684      typedef _Base Base;
     685      typedef typename Base::Node Node;
     686      typedef typename Base::Edge Edge;
     687
     688      /// \brief Erase a node from the graph.
     689      ///
     690      /// Erase a node from the graph. This function should not
    433691      /// erase edges connecting to the Node.
    434692      void erase(const Node&) {}   
    435693
    436       /// Erase an Edge from the graph.
    437 
    438       /// Erase an Edge from the graph.
     694      /// \brief Erase an edge from the graph.
     695      ///
     696      /// Erase an edge from the graph.
    439697      ///
    440698      void erase(const Edge&) {}
     
    443701      struct Constraints {
    444702        void constraints() {
    445           checkConcept<BaseGraphComponent, _Graph>();
    446703          typename _Graph::Node node;
    447704          graph.erase(node);
     
    454711    };
    455712
    456     /// An empty clearable base graph class.
    457  
     713    /// \brief An empty erasable base undirected graph class.
     714    /// 
     715    /// This class provides beside the core undirected graph features
     716    /// core erase functions for the undirceted graph structure.
     717    template <typename _Base = BaseUGraphComponent>
     718    class BaseErasableUGraphComponent : public _Base {
     719    public:
     720
     721      typedef _Base Base;
     722      typedef typename Base::Node Node;
     723      typedef typename Base::UEdge UEdge;
     724
     725      /// \brief Erase a node from the graph.
     726      ///
     727      /// Erase a node from the graph. This function should not
     728      /// erase edges connecting to the Node.
     729      void erase(const Node&) {}   
     730
     731      /// \brief Erase an edge from the graph.
     732      ///
     733      /// Erase an edge from the graph.
     734      ///
     735      void erase(const UEdge&) {}
     736
     737      template <typename _Graph>
     738      struct Constraints {
     739        void constraints() {
     740          typename _Graph::Node node;
     741          graph.erase(node);
     742          typename _Graph::Edge edge;
     743          graph.erase(edge);
     744        }
     745
     746        _Graph& graph;
     747      };
     748    };
     749
     750    /// \brief An empty clearable base graph class.
     751    ///
    458752    /// This class provides beside the core graph features
    459753    /// core clear functions for the graph structure.
    460754    /// The most of the base graphs should be conform to this concept.
    461     class BaseClearableGraphComponent : virtual public BaseGraphComponent {
    462     public:
    463 
    464       /// Erase all the Nodes and Edges from the graph.
    465 
    466       /// Erase all the Nodes and Edges from the graph.
     755    template <typename _Base = BaseGraphComponent>
     756    class BaseClearableGraphComponent : public _Base {
     757    public:
     758
     759      /// \brief Erase all the nodes and edges from the graph.
     760      ///
     761      /// Erase all the nodes and edges from the graph.
    467762      ///
    468763      void clear() {}   
     
    471766      struct Constraints {
    472767        void constraints() {
    473           checkConcept<BaseGraphComponent, _Graph>();
    474768          graph.clear();
    475769        }
     
    479773    };
    480774
    481 
    482     /// Skeleton class for graph NodeIt and EdgeIt
    483 
     775    /// \brief An empty clearable base undirected graph class.
     776    ///
     777    /// This class provides beside the core undirected graph features
     778    /// core clear functions for the undirected graph structure.
     779    /// The most of the base graphs should be conform to this concept.
     780    template <typename _Base = BaseUGraphComponent>
     781    class BaseClearableUGraphComponent : public _Base {
     782    public:
     783
     784      /// \brief Erase all the nodes and undirected edges from the graph.
     785      ///
     786      /// Erase all the nodes and undirected edges from the graph.
     787      ///
     788      void clear() {}   
     789
     790      template <typename _Graph>
     791      struct Constraints {
     792        void constraints() {
     793          graph.clear();
     794        }
     795
     796        _Graph graph;
     797      };
     798    };
     799
     800
     801    /// \brief Skeleton class for graph NodeIt and EdgeIt
     802    ///
    484803    /// Skeleton class for graph NodeIt and EdgeIt.
    485804    ///
    486805    template <typename _Graph, typename _Item>
    487     class GraphIterator : public _Item {
    488     public:
    489       /// \todo Don't we need the Item type as typedef?
    490 
    491       /// Default constructor.
    492      
     806    class GraphItemIt : public _Item {
     807    public:
     808      /// \brief Default constructor.
     809      ///
    493810      /// @warning The default constructor sets the iterator
    494811      /// to an undefined value.
    495       GraphIterator() {}
     812      GraphItemIt() {}
     813      /// \brief Copy constructor.
     814      ///
    496815      /// Copy constructor.
    497      
    498       /// Copy constructor.
    499       ///
    500       GraphIterator(GraphIterator const&) {}
    501       /// Sets the iterator to the first item.
    502      
     816      ///
     817      GraphItemIt(const GraphItemIt& ) {}
     818      /// \brief Sets the iterator to the first item.
     819      ///
    503820      /// Sets the iterator to the first item of \c the graph.
    504821      ///
    505       explicit GraphIterator(const _Graph&) {}
    506       /// Invalid constructor \& conversion.
    507 
     822      explicit GraphItemIt(const _Graph&) {}
     823      /// \brief Invalid constructor \& conversion.
     824      ///
    508825      /// This constructor initializes the item to be invalid.
    509826      /// \sa Invalid for more details.
    510       GraphIterator(Invalid) {}
    511       /// Assign operator for items.
    512 
     827      GraphItemIt(Invalid) {}
     828      /// \brief Assign operator for items.
     829      ///
    513830      /// The items are assignable.
    514831      ///
    515       GraphIterator& operator=(GraphIterator const&) { return *this; }     
    516       /// Next item.
    517 
     832      GraphItemIt& operator=(const GraphItemIt&) { return *this; }     
     833      /// \brief Next item.
     834      ///
    518835      /// Assign the iterator to the next item.
    519836      ///
    520       GraphIterator& operator++() { return *this; }
    521       //        Node operator*() const { return INVALID; }
    522       /// Equality operator
    523 
     837      GraphItemIt& operator++() { return *this; }
     838      /// \brief Equality operator
     839      ///
    524840      /// Two iterators are equal if and only if they point to the
    525841      /// same object or both are invalid.
    526       bool operator==(const GraphIterator&) const { return true;}
    527       /// Inequality operator
    528        
     842      bool operator==(const GraphItemIt&) const { return true;}
     843      /// \brief Inequality operator
     844      ///       
    529845      /// \sa operator==(Node n)
    530846      ///
    531       bool operator!=(const GraphIterator&) const { return true;}
     847      bool operator!=(const GraphItemIt&) const { return true;}
    532848     
    533       template<typename _GraphIterator>
    534       struct Constraints {
    535         void constraints() {
    536           //      checkConcept< Item, _GraphIterator >();
    537           _GraphIterator it1(g);
    538        
    539           /// \todo Do we need NodeIt(Node) kind of constructor?
    540           //    _GraphIterator it2(bj);
    541           _GraphIterator it2;
     849      template<typename _GraphItemIt>
     850      struct Constraints {
     851        void constraints() {
     852          _GraphItemIt it1(g); 
     853          _GraphItemIt it2;
    542854
    543855          it2 = ++it1;
    544856          ++it2 = it1;
    545857          ++(++it1);
    546           /// \bug This should be: is_base_and_derived<BaseItem, _GraphIterator>
     858
    547859          _Item bi = it1;
    548860          bi = it2;
     
    552864    };
    553865
    554     /// Skeleton class for graph InEdgeIt and OutEdgeIt
    555 
     866    /// \brief Skeleton class for graph InEdgeIt and OutEdgeIt
     867    ///
    556868    /// \note Because InEdgeIt and OutEdgeIt may not inherit from the same
    557869    /// base class, the _selector is a additional template parameter. For
    558870    /// InEdgeIt you should instantiate it with character 'i' and for
    559871    /// OutEdgeIt with 'o'.
    560     /// \todo Is this a good name for this concept?
    561     template <typename Graph,
    562               typename Edge = typename Graph::Edge,
     872    template <typename _Graph,
     873              typename _Item = typename _Graph::Edge,
     874              typename _Base = typename _Graph::Node,
    563875              char _selector = '0'>
    564     class GraphIncIterator : public Edge {
    565     public:
    566       /// Default constructor.
    567      
     876    class GraphIncIt : public _Item {
     877    public:
     878      /// \brief Default constructor.
     879      ///
    568880      /// @warning The default constructor sets the iterator
    569881      /// to an undefined value.
    570       GraphIncIterator() {}
     882      GraphIncIt() {}
     883      /// \brief Copy constructor.
     884      ///
    571885      /// Copy constructor.
    572      
    573       /// Copy constructor.
    574       ///
    575       GraphIncIterator(GraphIncIterator const& gi) :Edge(gi) {}
     886      ///
     887      GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}
     888      /// \brief Sets the iterator to the first edge incoming into or outgoing
     889      /// from the node.
     890      ///
    576891      /// Sets the iterator to the first edge incoming into or outgoing
    577892      /// from the node.
    578      
    579       /// Sets the iterator to the first edge incoming into or outgoing
    580       /// from the node.
    581       ///
    582       explicit GraphIncIterator(const Graph&, const typename Graph::Node&) {}
    583       /// Invalid constructor \& conversion.
    584 
     893      ///
     894      explicit GraphIncIt(const _Graph&, const _Base&) {}
     895      /// \brief Invalid constructor \& conversion.
     896      ///
    585897      /// This constructor initializes the item to be invalid.
    586898      /// \sa Invalid for more details.
    587       GraphIncIterator(Invalid) {}
    588       /// Assign operator for nodes.
    589 
    590       /// The nodes are assignable.
    591       ///
    592       GraphIncIterator& operator=(GraphIncIterator const&) { return *this; }     
    593       /// Next edge.
    594 
    595       /// Assign the iterator to the next node.
    596       ///
    597       GraphIncIterator& operator++() { return *this; }
    598 
    599       //        Node operator*() const { return INVALID; }
    600 
    601       /// Equality operator
    602 
     899      GraphIncIt(Invalid) {}
     900      /// \brief Assign operator for iterators.
     901      ///
     902      /// The iterators are assignable.
     903      ///
     904      GraphIncIt& operator=(GraphIncIt const&) { return *this; }     
     905      /// \brief Next item.
     906      ///
     907      /// Assign the iterator to the next item.
     908      ///
     909      GraphIncIt& operator++() { return *this; }
     910
     911      /// \brief Equality operator
     912      ///
    603913      /// Two iterators are equal if and only if they point to the
    604914      /// same object or both are invalid.
    605       bool operator==(const GraphIncIterator&) const { return true;}
    606 
    607       /// Inequality operator
    608        
     915      bool operator==(const GraphIncIt&) const { return true;}
     916
     917      /// \brief Inequality operator
     918      ///
    609919      /// \sa operator==(Node n)
    610920      ///
    611       bool operator!=(const GraphIncIterator&) const { return true;}
    612 
    613       template <typename _GraphIncIterator>
    614       struct Constraints {
    615         typedef typename Graph::Node Node;
    616         void constraints() {
    617           checkConcept<GraphItem<'e'>, _GraphIncIterator>();
    618           _GraphIncIterator it1(graph, node);
    619           /// \todo Do we need OutEdgeIt(Edge) kind of constructor?
    620           //    _GraphIncIterator it2(edge);
    621           _GraphIncIterator it2;
     921      bool operator!=(const GraphIncIt&) const { return true;}
     922
     923      template <typename _GraphIncIt>
     924      struct Constraints {
     925        void constraints() {
     926          checkConcept<GraphItem<_selector>, _GraphIncIt>();
     927          _GraphIncIt it1(graph, node);
     928          _GraphIncIt it2;
    622929
    623930          it2 = ++it1;
    624931          ++it2 = it1;
    625932          ++(++it1);
    626           Edge e = it1;
     933          _Item e = it1;
    627934          e = it2;
    628935
    629           const_constraits();
    630         }
    631 
    632         void const_constraits() {
    633           Node n = graph.baseNode(it);
    634           n = graph.runningNode(it);
    635         }
    636 
    637         Edge edge;
    638         Node node;
    639         Graph graph;
    640         _GraphIncIterator it;
    641       };
    642     };
    643 
    644 
    645     /// An empty iterable base graph class.
    646  
     936        }
     937
     938        _Item edge;
     939        _Base node;
     940        _Graph graph;
     941        _GraphIncIt it;
     942      };
     943    };
     944
     945
     946    /// \brief An empty iterable graph class.
     947    ///
    647948    /// This class provides beside the core graph features
    648949    /// iterator based iterable interface for the graph structure.
    649950    /// This concept is part of the GraphConcept.
    650     class IterableGraphComponent : virtual public BaseGraphComponent {
     951    template <typename _Base = BaseGraphComponent>
     952    class IterableGraphComponent : public _Base {
    651953
    652954    public:
    653955   
     956      typedef _Base Base;
     957      typedef typename Base::Node Node;
     958      typedef typename Base::Edge Edge;
     959
    654960      typedef IterableGraphComponent Graph;
    655961
    656       typedef BaseGraphComponent::Node Node;
    657       typedef BaseGraphComponent::Edge Edge;
    658 
     962
     963      /// \brief This iterator goes through each node.
     964      ///
    659965      /// This iterator goes through each node.
    660 
     966      ///
     967      typedef GraphItemIt<Graph, Node> NodeIt;
     968
     969      /// \brief This iterator goes through each node.
     970      ///
    661971      /// This iterator goes through each node.
    662972      ///
    663       typedef GraphIterator<Graph, Node> NodeIt;
    664       /// This iterator goes through each node.
    665 
    666       /// This iterator goes through each node.
    667       ///
    668       typedef GraphIterator<Graph, Edge> EdgeIt;
    669       /// This iterator goes trough the incoming edges of a node.
    670 
     973      typedef GraphItemIt<Graph, Edge> EdgeIt;
     974
     975      /// \brief This iterator goes trough the incoming edges of a node.
     976      ///
    671977      /// This iterator goes trough the \e inccoming edges of a certain node
    672978      /// of a graph.
    673       typedef GraphIncIterator<Graph, Edge, 'i'> InEdgeIt;
    674       /// This iterator goes trough the outgoing edges of a node.
    675 
     979      typedef GraphIncIt<Graph, Edge, Node, 'i'> InEdgeIt;
     980
     981      /// \brief This iterator goes trough the outgoing edges of a node.
     982      ///
    676983      /// This iterator goes trough the \e outgoing edges of a certain node
    677984      /// of a graph.
    678       typedef GraphIncIterator<Graph, Edge, 'o'> OutEdgeIt;
     985      typedef GraphIncIt<Graph, Edge, Node, 'o'> OutEdgeIt;
    679986
    680987      /// \brief The base node of the iterator.
     
    7121019      struct Constraints {
    7131020        void constraints() {
    714           checkConcept< BaseGraphComponent, _Graph>();
     1021          checkConcept<Base, _Graph>();
    7151022         
    716           checkConcept<GraphIterator<_Graph, typename _Graph::Edge>,
     1023          checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
    7171024            typename _Graph::EdgeIt >();
    718           checkConcept<GraphIterator<_Graph, typename _Graph::Node>,
     1025          checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,
    7191026            typename _Graph::NodeIt >();
    720           checkConcept<GraphIncIterator<_Graph>, typename _Graph::InEdgeIt>();
    721           checkConcept<GraphIncIterator<_Graph>, typename _Graph::OutEdgeIt>();
    722 
    723           typename _Graph::Node n(INVALID);
    724           typename _Graph::Edge e(INVALID);
    725           n = graph.oppositeNode(n, e);
    726         }
     1027          checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
     1028            typename _Graph::Node, 'i'>, typename _Graph::InEdgeIt>();
     1029          checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
     1030            typename _Graph::Node, 'o'>, typename _Graph::OutEdgeIt>();
     1031
     1032          typename _Graph::Node n;
     1033          typename _Graph::InEdgeIt ieit(INVALID);
     1034          typename _Graph::OutEdgeIt oeit(INVALID);
     1035          n = graph.baseNode(ieit);
     1036          n = graph.runningNode(ieit);
     1037          n = graph.baseNode(oeit);
     1038          n = graph.runningNode(oeit);
     1039          ignore_unused_variable_warning(n);
     1040        }
    7271041       
    7281042        const _Graph& graph;
     
    7311045    };
    7321046
    733     /// An empty alteration notifier base graph class.
    734  
    735     /// This class provides beside the core graph features
    736     /// alteration notifier interface for the graph structure.
    737     /// This is an observer-notifier pattern. More Obsevers can
    738     /// be registered into the notifier and whenever an alteration
    739     /// occured in the graph all the observers will notified about it.
    740     class AlterableGraphComponent : virtual public BaseIterableGraphComponent {
    741     public:
    742 
     1047    /// \brief An empty iterable undirected graph class.
     1048    ///
     1049    /// This class provides beside the core graph features iterator
     1050    /// based iterable interface for the undirected graph structure.
     1051    /// This concept is part of the GraphConcept.
     1052    template <typename _Base = BaseUGraphComponent>
     1053    class IterableUGraphComponent : public IterableGraphComponent<_Base> {
     1054    public:
     1055
     1056      typedef _Base Base;
     1057      typedef typename Base::Node Node;
     1058      typedef typename Base::Edge Edge;
     1059      typedef typename Base::UEdge UEdge;
     1060
     1061   
     1062      typedef IterableUGraphComponent Graph;
     1063      using IterableGraphComponent<_Base>::baseNode;
     1064      using IterableGraphComponent<_Base>::runningNode;
     1065
     1066
     1067      /// \brief This iterator goes through each node.
     1068      ///
     1069      /// This iterator goes through each node.
     1070      typedef GraphItemIt<Graph, UEdge> UEdgeIt;
     1071      /// \brief This iterator goes trough the incident edges of a
     1072      /// node.
     1073      ///
     1074      /// This iterator goes trough the incident edges of a certain
     1075      /// node of a graph.
     1076      typedef GraphIncIt<Graph, UEdge, Node, 'u'> IncEdgeIt;
     1077      /// \brief The base node of the iterator.
     1078      ///
     1079      /// Gives back the base node of the iterator.
     1080      Node baseNode(const IncEdgeIt&) const { return INVALID; }
     1081
     1082      /// \brief The running node of the iterator.
     1083      ///
     1084      /// Gives back the running node of the iterator.
     1085      Node runningNode(const IncEdgeIt&) const { return INVALID; }
     1086
     1087      template <typename _Graph>
     1088      struct Constraints {
     1089        void constraints() {
     1090          checkConcept<Base, _Graph>();
     1091          checkConcept<IterableGraphComponent<Base>, _Graph>();
     1092         
     1093          checkConcept<GraphItemIt<_Graph, typename _Graph::UEdge>,
     1094            typename _Graph::UEdgeIt >();
     1095          checkConcept<GraphIncIt<_Graph, typename _Graph::UEdge,
     1096            typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
     1097
     1098          typename _Graph::Node n;
     1099          typename _Graph::IncEdgeIt ueit(INVALID);
     1100          n = graph.baseNode(ueit);
     1101          n = graph.runningNode(ueit);
     1102        }
     1103       
     1104        const _Graph& graph;
     1105       
     1106      };
     1107    };
     1108
     1109    /// \brief An empty alteration notifier graph class.
     1110    /// 
     1111    /// This class provides beside the core graph features alteration
     1112    /// notifier interface for the graph structure.  This implements
     1113    /// an observer-notifier pattern for each graph item. More
     1114    /// obsevers can be registered into the notifier and whenever an
     1115    /// alteration occured in the graph all the observers will
     1116    /// notified about it.
     1117    template <typename _Base = BaseGraphComponent>
     1118    class AlterableGraphComponent : public _Base {
     1119    public:
     1120
     1121      typedef _Base Base;
     1122      typedef typename Base::Node Node;
     1123      typedef typename Base::Edge Edge;
     1124
     1125
     1126      /// The node observer registry.
     1127      typedef AlterationNotifier<AlterableGraphComponent, Node>
     1128      NodeNotifier;
    7431129      /// The edge observer registry.
    7441130      typedef AlterationNotifier<AlterableGraphComponent, Edge>
    7451131      EdgeNotifier;
    746       /// The node observer registry.
    747       typedef AlterationNotifier<AlterableGraphComponent, Node>
    748       NodeNotifier;
    749      
    750       /// \brief Gives back the edge alteration notifier.
    751       ///
    752       /// Gives back the edge alteration notifier.
    753       EdgeNotifier getNotifier(Edge) const {
    754         return EdgeNotifier();
    755       }
    7561132     
    7571133      /// \brief Gives back the node alteration notifier.
    7581134      ///
    7591135      /// Gives back the node alteration notifier.
    760       NodeNotifier getNotifier(Node) const {
     1136      NodeNotifier& getNotifier(Node) const {
    7611137        return NodeNotifier();
    7621138      }
    7631139     
    764     };
    765 
    766 
    767     /// Class describing the concept of graph maps
    768 
     1140      /// \brief Gives back the edge alteration notifier.
     1141      ///
     1142      /// Gives back the edge alteration notifier.
     1143      EdgeNotifier& getNotifier(Edge) const {
     1144        return EdgeNotifier();
     1145      }
     1146
     1147      template <typename _Graph>
     1148      struct Constraints {
     1149        void constraints() {
     1150          checkConcept<Base, _Graph>();
     1151          typename _Graph::NodeNotifier& nn
     1152            = graph.getNotifier(typename _Graph::Node());
     1153
     1154          typename _Graph::EdgeNotifier& en
     1155            = graph.getNotifier(typename _Graph::Edge());
     1156         
     1157          ignore_unused_variable_warning(nn);
     1158          ignore_unused_variable_warning(en);
     1159        }
     1160       
     1161        const _Graph& graph;
     1162       
     1163      };
     1164     
     1165    };
     1166
     1167    /// \brief An empty alteration notifier undirected graph class.
     1168    /// 
     1169    /// This class provides beside the core graph features alteration
     1170    /// notifier interface for the graph structure.  This implements
     1171    /// an observer-notifier pattern for each graph item. More
     1172    /// obsevers can be registered into the notifier and whenever an
     1173    /// alteration occured in the graph all the observers will
     1174    /// notified about it.
     1175    template <typename _Base = BaseUGraphComponent>
     1176    class AlterableUGraphComponent : public AlterableGraphComponent<_Base> {
     1177    public:
     1178
     1179      typedef _Base Base;
     1180      typedef typename Base::UEdge UEdge;
     1181
     1182
     1183      /// The edge observer registry.
     1184      typedef AlterationNotifier<AlterableUGraphComponent, UEdge>
     1185      UEdgeNotifier;
     1186     
     1187      /// \brief Gives back the edge alteration notifier.
     1188      ///
     1189      /// Gives back the edge alteration notifier.
     1190      UEdgeNotifier& getNotifier(UEdge) const {
     1191        return UEdgeNotifier();
     1192      }
     1193
     1194      template <typename _Graph>
     1195      struct Constraints {
     1196        void constraints() {
     1197          checkConcept<Base, _Graph>();
     1198          checkConcept<AlterableGraphComponent, _Graph>();
     1199          typename _Graph::UEdgeNotifier& uen
     1200            = graph.getNotifier(typename _Graph::UEdge());
     1201          ignore_unused_variable_warning(uen);
     1202        }
     1203       
     1204        const _Graph& graph;
     1205       
     1206      };
     1207     
     1208    };
     1209
     1210
     1211    /// \brief Class describing the concept of graph maps
     1212    ///
    7691213    /// This class describes the common interface of the graph maps
    7701214    /// (NodeMap, EdgeMap), that is \ref maps-page "maps" which can be used to
    7711215    /// associate data to graph descriptors (nodes or edges).
    772     template <typename Graph, typename Item, typename _Value>
    773     class GraphMap : public ReadWriteMap<Item, _Value> {
    774     protected:     
    775       GraphMap() {}
    776     public:
     1216    template <typename _Graph, typename _Item, typename _Value>
     1217    class GraphMap : public ReadWriteMap<_Item, _Value> {
     1218    public:
     1219
     1220      typedef ReadWriteMap<_Item, _Value> Parent;
     1221
     1222      /// The graph type of the map.
     1223      typedef _Graph Graph;
     1224      /// The key type of the map.
     1225      typedef _Item Key;
     1226      /// The value type of the map.
     1227      typedef _Value Value;
     1228
    7771229      /// \brief Construct a new map.
    7781230      ///
     
    7821234      ///
    7831235      /// Construct a new map for the graph and initalise the values.
    784       GraphMap(const Graph&, const _Value&) {}
     1236      GraphMap(const Graph&, const Value&) {}
    7851237      /// \brief Copy constructor.
    7861238      ///
    7871239      /// Copy Constructor.
    788       GraphMap(const GraphMap& gm) :ReadWriteMap<Item, _Value>(gm) {}
     1240      GraphMap(const GraphMap&) : Parent() {}
    7891241     
    7901242      /// \brief Assign operator.
    7911243      ///
    792       /// Assign operator.
    793       GraphMap& operator=(const GraphMap&) { return *this;}
     1244      /// Assign operator. It does not mofify the underlying graph,
     1245      /// it just iterates on the current item set and set the  map
     1246      /// with the value returned by the assigned map.
     1247      template <typename CMap>
     1248      GraphMap& operator=(const CMap&) {
     1249        checkConcept<ReadMap<Key, Value>, CMap>();
     1250        return *this;
     1251      }
    7941252
    7951253      template<typename _Map>
    7961254      struct Constraints {
    7971255        void constraints() {
    798           checkConcept<ReadWriteMap<Item, _Value>, _Map >();
     1256          checkConcept<ReadWriteMap<Key, Value>, _Map >();
    7991257          // Construction with a graph parameter
    8001258          _Map a(g);
    8011259          // Constructor with a graph and a default value parameter
    8021260          _Map a2(g,t);
    803           // Copy constructor. Do we need it?
    804           _Map b=c;
     1261          // Copy constructor.
     1262          _Map b(c);
     1263         
     1264          ReadMap<Key, Value> cmap;
     1265          b = cmap;
    8051266
    8061267          ignore_unused_variable_warning(a2);
     1268          ignore_unused_variable_warning(b);
    8071269        }
    8081270
     
    8141276    };
    8151277
    816     /// An empty mappable base graph class.
    817  
     1278    /// \brief An empty mappable graph class.
     1279    ///
    8181280    /// This class provides beside the core graph features
    8191281    /// map interface for the graph structure.
    820     /// This concept is part of the GraphConcept.
    821     class MappableGraphComponent : virtual public BaseGraphComponent {
    822     public:
     1282    /// This concept is part of the Graph concept.
     1283    template <typename _Base = BaseGraphComponent>
     1284    class MappableGraphComponent : public _Base  {
     1285    public:
     1286
     1287      typedef _Base Base;
     1288      typedef typename Base::Node Node;
     1289      typedef typename Base::Edge Edge;
    8231290
    8241291      typedef MappableGraphComponent Graph;
    8251292
    826       typedef BaseGraphComponent::Node Node;
    827       typedef BaseGraphComponent::Edge Edge;
    828 
     1293      /// \brief ReadWrite map of the nodes.
     1294      ///
    8291295      /// ReadWrite map of the nodes.
    830    
    831       /// ReadWrite map of the nodes.
    832       ///
    833       template <typename _Value>
    834       class NodeMap : public GraphMap<Graph, Node, _Value> {
     1296      ///
     1297      template <typename Value>
     1298      class NodeMap : public GraphMap<Graph, Node, Value> {
    8351299      private:
    8361300        NodeMap();
    8371301      public:
     1302        typedef GraphMap<Graph, Node, Value> Parent;
     1303
    8381304        /// \brief Construct a new map.
    8391305        ///
    8401306        /// Construct a new map for the graph.
    8411307        /// \todo call the right parent class constructor
    842         explicit NodeMap(const Graph&) {}
     1308        explicit NodeMap(const Graph& graph) : Parent(graph) {}
     1309
    8431310        /// \brief Construct a new map with default value.
    8441311        ///
    8451312        /// Construct a new map for the graph and initalise the values.
    846         NodeMap(const Graph&, const _Value&) {}
     1313        NodeMap(const Graph& graph, const Value& value)
     1314          : Parent(graph, value) {}
     1315
    8471316        /// \brief Copy constructor.
    8481317        ///
    8491318        /// Copy Constructor.
    850         NodeMap(const NodeMap& nm) : GraphMap<Graph, Node, _Value>(nm) {}
     1319        NodeMap(const NodeMap& nm) : Parent(nm) {}
    8511320
    8521321        /// \brief Assign operator.
    8531322        ///
    8541323        /// Assign operator.
    855         NodeMap& operator=(const NodeMap&) { return *this;}
    856 
    857       };
    858 
     1324        template <typename CMap>
     1325        NodeMap& operator=(const CMap&) {
     1326          checkConcept<ReadMap<Node, Value>, CMap>();
     1327          return *this;
     1328        }
     1329
     1330      };
     1331
     1332      /// \brief ReadWrite map of the edges.
     1333      ///
    8591334      /// ReadWrite map of the edges.
    860    
    861       /// ReadWrite map of the edges.
    862       ///
    863       template <typename _Value>
    864       class EdgeMap : public GraphMap<Graph, Edge, _Value> {
     1335      ///
     1336      template <typename Value>
     1337      class EdgeMap : public GraphMap<Graph, Edge, Value> {
    8651338      private:
    8661339        EdgeMap();
    8671340      public:
     1341        typedef GraphMap<Graph, Edge, Value> Parent;
     1342
    8681343        /// \brief Construct a new map.
    8691344        ///
    8701345        /// Construct a new map for the graph.
    8711346        /// \todo call the right parent class constructor
    872         explicit EdgeMap(const Graph&) {}
     1347        explicit EdgeMap(const Graph& graph) : Parent(graph) {}
     1348
    8731349        /// \brief Construct a new map with default value.
    8741350        ///
    8751351        /// Construct a new map for the graph and initalise the values.
    876         EdgeMap(const Graph&, const _Value&) {}
     1352        EdgeMap(const Graph& graph, const Value& value)
     1353          : Parent(graph, value) {}
     1354
    8771355        /// \brief Copy constructor.
    8781356        ///
    8791357        /// Copy Constructor.
    880         EdgeMap(const EdgeMap& em) :GraphMap<Graph, Edge, _Value>(em) {}
     1358        EdgeMap(const EdgeMap& nm) : Parent(nm) {}
    8811359
    8821360        /// \brief Assign operator.
    8831361        ///
    8841362        /// Assign operator.
    885         EdgeMap& operator=(const EdgeMap&) { return *this;}
    886 
    887       };
    888 
    889       template <typename _Graph>
    890       struct Constraints {
    891 
    892         struct Type {
     1363        template <typename CMap>
     1364        EdgeMap& operator=(const CMap&) {
     1365          checkConcept<ReadMap<Edge, Value>, CMap>();
     1366          return *this;
     1367        }
     1368
     1369      };
     1370
     1371
     1372      template <typename _Graph>
     1373      struct Constraints {
     1374
     1375        struct Dummy {
    8931376          int value;
    894           Type() : value(0) {}
    895           Type(int _v) : value(_v) {}
     1377          Dummy() : value(0) {}
     1378          Dummy(int _v) : value(_v) {}
    8961379        };
    8971380
    8981381        void constraints() {
    899           checkConcept<BaseGraphComponent, _Graph>();
     1382          checkConcept<Base, _Graph>();
    9001383          { // int map test
    9011384            typedef typename _Graph::template NodeMap<int> IntNodeMap;
     
    9061389            checkConcept<GraphMap<_Graph, typename _Graph::Node, bool>,
    9071390              BoolNodeMap >();
    908           } { // Type map test
    909             typedef typename _Graph::template NodeMap<Type> TypeNodeMap;
    910             checkConcept<GraphMap<_Graph, typename _Graph::Node, Type>,
    911               TypeNodeMap >();
     1391          } { // Dummy map test
     1392            typedef typename _Graph::template NodeMap<Dummy> DummyNodeMap;
     1393            checkConcept<GraphMap<_Graph, typename _Graph::Node, Dummy>,
     1394              DummyNodeMap >();
    9121395          }
    9131396
     
    9201403            checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
    9211404              BoolEdgeMap >();
    922           } { // Type map test
    923             typedef typename _Graph::template EdgeMap<Type> TypeEdgeMap;
    924             checkConcept<GraphMap<_Graph, typename _Graph::Edge, Type>,
    925               TypeEdgeMap >();
     1405          } { // Dummy map test
     1406            typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
     1407            checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
     1408              DummyEdgeMap >();
    9261409          }
    9271410        }
     
    9311414    };
    9321415
    933 
    934 //     /// Skeleton class which describes an edge with direction in \ref
    935 //     /// UGraph "undirected graph".
    936     template <typename UGraph>
    937     class UGraphEdge : public UGraph::UEdge {
    938       typedef typename UGraph::UEdge UEdge;
    939       typedef typename UGraph::Node Node;
    940     public:
    941 
    942       /// \e
    943       UGraphEdge() {}
    944 
    945       /// \e
    946       UGraphEdge(const UGraphEdge& e) : UGraph::UEdge(e) {}
    947 
    948       /// \e
    949       UGraphEdge(Invalid) {}
    950 
    951       /// \brief Directed edge from undirected edge and a source node.
    952       ///
    953       /// Constructs a directed edge from undirected edge and a source node.
    954       ///
    955       /// \note You have to specify the graph for this constructor.
    956       UGraphEdge(const UGraph &g,
    957                      UEdge u_edge, Node n) {
    958         ignore_unused_variable_warning(u_edge);
    959         ignore_unused_variable_warning(g);
    960         ignore_unused_variable_warning(n);
    961       }
    962 
    963       /// \e
    964       UGraphEdge& operator=(UGraphEdge) { return *this; }
    965 
    966       /// \e
    967       bool operator==(UGraphEdge) const { return true; }
    968       /// \e
    969       bool operator!=(UGraphEdge) const { return false; }
    970 
    971       /// \e
    972       bool operator<(UGraphEdge) const { return false; }
    973 
    974       template <typename Edge>
    975       struct Constraints {
    976         void constraints() {
    977           const_constraints();
    978         }
    979         void const_constraints() const {
    980           /// \bug This should be is_base_and_derived ...
    981           UEdge ue = e;
    982           ue = e;
    983 
    984           Edge e_with_source(graph,ue,n);
    985           ignore_unused_variable_warning(e_with_source);
    986         }
    987         Edge e;
    988         UEdge ue;
    989         UGraph graph;
    990         Node n;
    991       };
    992     };
    993    
    994 
    995     struct BaseIterableUGraphConcept {
    996 
    997       template <typename Graph>
    998       struct Constraints {
    999 
    1000         typedef typename Graph::UEdge UEdge;
    1001         typedef typename Graph::Edge Edge;
    1002         typedef typename Graph::Node Node;
    1003 
    1004         void constraints() {
    1005           checkConcept<BaseIterableGraphComponent, Graph>();
    1006           checkConcept<GraphItem<>, UEdge>();
    1007           //checkConcept<UGraphEdge<Graph>, Edge>();
    1008 
    1009           graph.first(ue);
    1010           graph.next(ue);
    1011 
    1012           const_constraints();
    1013         }
    1014         void const_constraints() {
    1015           Node n;
    1016           n = graph.target(ue);
    1017           n = graph.source(ue);
    1018           n = graph.oppositeNode(n0, ue);
    1019 
    1020           bool b;
    1021           b = graph.direction(e);
    1022           Edge e = graph.direct(UEdge(), true);
    1023           e = graph.direct(UEdge(), n);
    1024  
    1025           ignore_unused_variable_warning(b);
    1026         }
    1027 
    1028         Graph graph;
    1029         Edge e;
    1030         Node n0;
    1031         UEdge ue;
    1032       };
    1033 
    1034     };
    1035 
    1036 
    1037     struct IterableUGraphConcept {
    1038 
    1039       template <typename Graph>
    1040       struct Constraints {
    1041         void constraints() {
    1042           /// \todo we don't need the iterable component to be base iterable
    1043           /// Don't we really???
    1044           //checkConcept< BaseIterableUGraphConcept, Graph > ();
    1045 
    1046           checkConcept<IterableGraphComponent, Graph> ();
    1047 
    1048           typedef typename Graph::UEdge UEdge;
    1049           typedef typename Graph::UEdgeIt UEdgeIt;
    1050           typedef typename Graph::IncEdgeIt IncEdgeIt;
    1051 
    1052           checkConcept<GraphIterator<Graph, UEdge>, UEdgeIt>();
    1053           checkConcept<GraphIncIterator<Graph, UEdge>, IncEdgeIt>();
    1054         }
    1055       };
    1056 
    1057     };
    1058 
    1059     struct MappableUGraphConcept {
    1060 
    1061       template <typename Graph>
     1416    /// \brief An empty mappable base graph class.
     1417    ///
     1418    /// This class provides beside the core graph features
     1419    /// map interface for the graph structure.
     1420    /// This concept is part of the UGraph concept.
     1421    template <typename _Base = BaseUGraphComponent>
     1422    class MappableUGraphComponent : public MappableGraphComponent<_Base>  {
     1423    public:
     1424
     1425      typedef _Base Base;
     1426      typedef typename Base::UEdge UEdge;
     1427
     1428      typedef MappableUGraphComponent Graph;
     1429
     1430      /// \brief ReadWrite map of the uedges.
     1431      ///
     1432      /// ReadWrite map of the uedges.
     1433      ///
     1434      template <typename Value>
     1435      class UEdgeMap : public GraphMap<Graph, UEdge, Value> { 
     1436      public:
     1437        typedef GraphMap<Graph, UEdge, Value> Parent;
     1438
     1439        /// \brief Construct a new map.
     1440        ///
     1441        /// Construct a new map for the graph.
     1442        /// \todo call the right parent class constructor
     1443        explicit UEdgeMap(const Graph& graph) : Parent(graph) {}
     1444
     1445        /// \brief Construct a new map with default value.
     1446        ///
     1447        /// Construct a new map for the graph and initalise the values.
     1448        UEdgeMap(const Graph& graph, const Value& value)
     1449          : Parent(graph, value) {}
     1450
     1451        /// \brief Copy constructor.
     1452        ///
     1453        /// Copy Constructor.
     1454        UEdgeMap(const UEdgeMap& nm) : Parent(nm) {}
     1455
     1456        /// \brief Assign operator.
     1457        ///
     1458        /// Assign operator.
     1459        template <typename CMap>
     1460        UEdgeMap& operator=(const CMap&) {
     1461          checkConcept<ReadMap<UEdge, Value>, CMap>();
     1462          return *this;
     1463        }
     1464
     1465      };
     1466
     1467
     1468      template <typename _Graph>
    10621469      struct Constraints {
    10631470
     
    10691476
    10701477        void constraints() {
    1071           checkConcept<MappableGraphComponent, Graph>();
    1072 
    1073           typedef typename Graph::template UEdgeMap<int> IntMap;
    1074           checkConcept<GraphMap<Graph, typename Graph::UEdge, int>,
    1075             IntMap >();
    1076 
    1077           typedef typename Graph::template UEdgeMap<bool> BoolMap;
    1078           checkConcept<GraphMap<Graph, typename Graph::UEdge, bool>,
    1079             BoolMap >();
    1080 
    1081           typedef typename Graph::template UEdgeMap<Dummy> DummyMap;
    1082           checkConcept<GraphMap<Graph, typename Graph::UEdge, Dummy>,
    1083             DummyMap >();
    1084         }
    1085       };
    1086 
     1478          checkConcept<Base, _Graph>();
     1479          checkConcept<MappableGraphComponent<Base>, _Graph>();
     1480
     1481          { // int map test
     1482            typedef typename _Graph::template UEdgeMap<int> IntUEdgeMap;
     1483            checkConcept<GraphMap<_Graph, typename _Graph::UEdge, int>,
     1484              IntUEdgeMap >();
     1485          } { // bool map test
     1486            typedef typename _Graph::template UEdgeMap<bool> BoolUEdgeMap;
     1487            checkConcept<GraphMap<_Graph, typename _Graph::UEdge, bool>,
     1488              BoolUEdgeMap >();
     1489          } { // Dummy map test
     1490            typedef typename _Graph::template UEdgeMap<Dummy> DummyUEdgeMap;
     1491            checkConcept<GraphMap<_Graph, typename _Graph::UEdge, Dummy>,
     1492              DummyUEdgeMap >();
     1493          }
     1494        }
     1495
     1496        _Graph& graph;
     1497      };
     1498    };
     1499
     1500
     1501    /// \brief An empty extendable graph class.
     1502    ///
     1503    /// This class provides beside the core graph features graph
     1504    /// extendable interface for the graph structure.  The main
     1505    /// difference between the base and this interface is that the
     1506    /// graph alterations should handled already on this level.
     1507    template <typename _Base = BaseGraphComponent>
     1508    class ExtendableGraphComponent : public _Base {
     1509    public:
     1510
     1511      typedef typename _Base::Node Node;
     1512      typedef typename _Base::Edge Edge;
     1513
     1514      /// \brief Adds a new node to the graph.
     1515      ///
     1516      /// Adds a new node to the graph.
     1517      ///
     1518      Node addNode() {
     1519        return INVALID;
     1520      }
     1521   
     1522      /// \brief Adds a new edge connects the given two nodes.
     1523      ///
     1524      /// Adds a new edge connects the the given two nodes.
     1525      Edge addEdge(const Node&, const Node&) {
     1526        return INVALID;
     1527      }
     1528
     1529      template <typename _Graph>
     1530      struct Constraints {
     1531        void constraints() {
     1532          typename _Graph::Node node_a, node_b;
     1533          node_a = graph.addNode();
     1534          node_b = graph.addNode();
     1535          typename _Graph::Edge edge;
     1536          edge = graph.addEdge(node_a, node_b);
     1537        }
     1538
     1539        _Graph& graph;
     1540      };
     1541    };
     1542
     1543    /// \brief An empty extendable base undirected graph class.
     1544    ///
     1545    /// This class provides beside the core undirected graph features
     1546    /// core undircted graph extend interface for the graph structure.
     1547    /// The main difference between the base and this interface is
     1548    /// that the graph alterations should handled already on this
     1549    /// level.
     1550    template <typename _Base = BaseUGraphComponent>
     1551    class ExtendableUGraphComponent : public _Base {
     1552    public:
     1553
     1554      typedef typename _Base::Node Node;
     1555      typedef typename _Base::UEdge UEdge;
     1556
     1557      /// \brief Adds a new node to the graph.
     1558      ///
     1559      /// Adds a new node to the graph.
     1560      ///
     1561      Node addNode() {
     1562        return INVALID;
     1563      }
     1564   
     1565      /// \brief Adds a new edge connects the given two nodes.
     1566      ///
     1567      /// Adds a new edge connects the the given two nodes.
     1568      UEdge addEdge(const Node&, const Node&) {
     1569        return INVALID;
     1570      }
     1571
     1572      template <typename _Graph>
     1573      struct Constraints {
     1574        void constraints() {
     1575          typename _Graph::Node node_a, node_b;
     1576          node_a = graph.addNode();
     1577          node_b = graph.addNode();
     1578          typename _Graph::UEdge uedge;
     1579          uedge = graph.addUEdge(node_a, node_b);
     1580        }
     1581
     1582        _Graph& graph;
     1583      };
     1584    };
     1585
     1586    /// \brief An empty erasable graph class.
     1587    /// 
     1588    /// This class provides beside the core graph features core erase
     1589    /// functions for the graph structure. The main difference between
     1590    /// the base and this interface is that the graph alterations
     1591    /// should handled already on this level.
     1592    template <typename _Base = BaseGraphComponent>
     1593    class ErasableGraphComponent : public _Base {
     1594    public:
     1595
     1596      typedef _Base Base;
     1597      typedef typename Base::Node Node;
     1598      typedef typename Base::Edge Edge;
     1599
     1600      /// \brief Erase a node from the graph.
     1601      ///
     1602      /// Erase a node from the graph. This function should
     1603      /// erase all edges connecting to the node.
     1604      void erase(const Node&) {}   
     1605
     1606      /// \brief Erase an edge from the graph.
     1607      ///
     1608      /// Erase an edge from the graph.
     1609      ///
     1610      void erase(const Edge&) {}
     1611
     1612      template <typename _Graph>
     1613      struct Constraints {
     1614        void constraints() {
     1615          typename _Graph::Node node;
     1616          graph.erase(node);
     1617          typename _Graph::Edge edge;
     1618          graph.erase(edge);
     1619        }
     1620
     1621        _Graph& graph;
     1622      };
     1623    };
     1624
     1625    /// \brief An empty erasable base undirected graph class.
     1626    /// 
     1627    /// This class provides beside the core undirected graph features
     1628    /// core erase functions for the undirceted graph structure. The
     1629    /// main difference between the base and this interface is that
     1630    /// the graph alterations should handled already on this level.
     1631    template <typename _Base = BaseUGraphComponent>
     1632    class ErasableUGraphComponent : public _Base {
     1633    public:
     1634
     1635      typedef _Base Base;
     1636      typedef typename Base::Node Node;
     1637      typedef typename Base::UEdge UEdge;
     1638
     1639      /// \brief Erase a node from the graph.
     1640      ///
     1641      /// Erase a node from the graph. This function should erase
     1642      /// edges connecting to the node.
     1643      void erase(const Node&) {}   
     1644
     1645      /// \brief Erase an edge from the graph.
     1646      ///
     1647      /// Erase an edge from the graph.
     1648      ///
     1649      void erase(const UEdge&) {}
     1650
     1651      template <typename _Graph>
     1652      struct Constraints {
     1653        void constraints() {
     1654          typename _Graph::Node node;
     1655          graph.erase(node);
     1656          typename _Graph::Edge edge;
     1657          graph.erase(edge);
     1658        }
     1659
     1660        _Graph& graph;
     1661      };
     1662    };
     1663
     1664    /// \brief An empty clearable base graph class.
     1665    ///
     1666    /// This class provides beside the core graph features core clear
     1667    /// functions for the graph structure. The main difference between
     1668    /// the base and this interface is that the graph alterations
     1669    /// should handled already on this level.
     1670    template <typename _Base = BaseGraphComponent>
     1671    class ClearableGraphComponent : public _Base {
     1672    public:
     1673
     1674      /// \brief Erase all nodes and edges from the graph.
     1675      ///
     1676      /// Erase all nodes and edges from the graph.
     1677      ///
     1678      void clear() {}   
     1679
     1680      template <typename _Graph>
     1681      struct Constraints {
     1682        void constraints() {
     1683          graph.clear();
     1684        }
     1685
     1686        _Graph graph;
     1687      };
     1688    };
     1689
     1690    /// \brief An empty clearable base undirected graph class.
     1691    ///
     1692    /// This class provides beside the core undirected graph features
     1693    /// core clear functions for the undirected graph structure. The
     1694    /// main difference between the base and this interface is that
     1695    /// the graph alterations should handled already on this level.
     1696    template <typename _Base = BaseUGraphComponent>
     1697    class ClearableUGraphComponent : public _Base {
     1698    public:
     1699
     1700      /// \brief Erase all nodes and undirected edges from the graph.
     1701      ///
     1702      /// Erase all nodes and undirected edges from the graph.
     1703      ///
     1704      void clear() {}   
     1705
     1706      template <typename _Graph>
     1707      struct Constraints {
     1708        void constraints() {
     1709          graph.clear();
     1710        }
     1711
     1712        _Graph graph;
     1713      };
    10871714    };
    10881715
  • lemon/concept/ugraph.h

    r2120 r2121  
    490490      /// \warning Making maps that can handle bool type (NodeMap<bool>)
    491491      /// needs some extra attention!
    492       /// \todo Wrong documentation
    493492      template<class T>
    494493      class NodeMap : public ReadWriteMap< Node, T >
     
    504503        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
    505504        ///Assignment operator
    506         NodeMap& operator=(const NodeMap&) { return *this; }
    507         // \todo fix this concept
     505        template <typename CMap>
     506        NodeMap& operator=(const CMap&) {
     507          checkConcept<ReadMap<Node, T>, CMap>();
     508          return *this;
     509        }
    508510      };
    509511
     
    514516      /// \warning Making maps that can handle bool type (EdgeMap<bool>)
    515517      /// needs some extra attention!
    516       /// \todo Wrong documentation
    517518      template<class T>
    518519      class EdgeMap : public ReadWriteMap<Edge,T>
     
    527528        EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
    528529        ///Assignment operator
    529         EdgeMap& operator=(const EdgeMap&) { return *this; }
    530         // \todo fix this concept   
     530        template <typename CMap>
     531        EdgeMap& operator=(const CMap&) {
     532          checkConcept<ReadMap<Edge, T>, CMap>();
     533          return *this;
     534        }
    531535      };
    532536
     
    537541      /// \warning Making maps that can handle bool type (UEdgeMap<bool>)
    538542      /// needs some extra attention!
    539       /// \todo Wrong documentation
    540543      template<class T>
    541544      class UEdgeMap : public ReadWriteMap<UEdge,T>
     
    550553        UEdgeMap(const UEdgeMap& em) : ReadWriteMap<UEdge,T>(em) {}
    551554        ///Assignment operator
    552         UEdgeMap &operator=(const UEdgeMap&) { return *this; }
    553         // \todo fix this concept   
     555        template <typename CMap>
     556        UEdgeMap& operator=(const CMap&) {
     557          checkConcept<ReadMap<UEdge, T>, CMap>();
     558          return *this;
     559        }
    554560      };
    555561
     
    673679      struct Constraints {
    674680        void constraints() {
    675           checkConcept<BaseIterableUGraphConcept, Graph>();
    676           checkConcept<IterableUGraphConcept, Graph>();
    677           checkConcept<MappableUGraphConcept, Graph>();
     681          checkConcept<BaseIterableUGraphComponent<>, Graph>();
     682          checkConcept<IterableUGraphComponent<>, Graph>();
     683          checkConcept<MappableUGraphComponent<>, Graph>();
    678684        }
    679685      };
  • test/graph_test.cc

    r2111 r2121  
    3939    checkConcept<BaseGraphComponent, BaseGraphComponent >();
    4040
    41     checkConcept<BaseIterableGraphComponent, BaseIterableGraphComponent >();
     41    checkConcept<BaseIterableGraphComponent<>,
     42      BaseIterableGraphComponent<> >();
    4243
    43     checkConcept<IDableGraphComponent, IDableGraphComponent >();
    44     checkConcept<MaxIDableGraphComponent, MaxIDableGraphComponent >();
     44    checkConcept<IDableGraphComponent<>,
     45      IDableGraphComponent<> >();
    4546
    46     checkConcept<IterableGraphComponent, IterableGraphComponent >();
     47    checkConcept<IterableGraphComponent<>,
     48      IterableGraphComponent<> >();
    4749
    48     checkConcept<MappableGraphComponent, MappableGraphComponent >();
     50    checkConcept<MappableGraphComponent<>,
     51      MappableGraphComponent<> >();
    4952
    5053  }
    5154  { // checking skeleton graphs
    52     checkConcept<Graph, Graph >();
     55    checkConcept<Graph, Graph>();
    5356  }
    5457  { // checking list graph
    5558    checkConcept<Graph, ListGraph >();
     59    checkConcept<AlterableGraphComponent<>, ListGraph>();
     60    checkConcept<ExtendableGraphComponent<>, ListGraph>();
     61    checkConcept<ClearableGraphComponent<>, ListGraph>();
     62    checkConcept<ErasableGraphComponent<>, ListGraph>();
    5663
    5764    checkGraph<ListGraph>();
  • test/ugraph_test.cc

    r2116 r2121  
    3333
    3434void check_concepts() {
    35   checkConcept<UGraph, ListUGraph>();
    36 
    37   checkConcept<UGraph, SmartUGraph>();
    38 
    39   checkConcept<UGraph, FullUGraph>();
    40 
    41   checkConcept<UGraph, UGraph>();
    42 
    43   checkConcept<UGraph, GridUGraph>();
     35
     36  { // checking graph components
     37    checkConcept<BaseUGraphComponent, BaseUGraphComponent >();
     38
     39    checkConcept<BaseIterableUGraphComponent<>,
     40      BaseIterableUGraphComponent<> >();
     41
     42    checkConcept<IDableUGraphComponent<>,
     43      IDableUGraphComponent<> >();
     44
     45    checkConcept<IterableUGraphComponent<>,
     46      IterableUGraphComponent<> >();
     47
     48    checkConcept<MappableUGraphComponent<>,
     49      MappableUGraphComponent<> >();
     50
     51  }
     52  {
     53    checkConcept<UGraph, ListUGraph>();
     54   
     55    checkConcept<UGraph, SmartUGraph>();
     56   
     57    checkConcept<UGraph, FullUGraph>();
     58   
     59    checkConcept<UGraph, UGraph>();
     60   
     61    checkConcept<UGraph, GridUGraph>();
     62  }
    4463}
    4564
Note: See TracChangeset for help on using the changeset viewer.