lemon/concepts/graph_components.h
changeset 905 de428ebb47ab
parent 786 e20173729589
child 976 426a704d7483
child 998 7fdaa05a69a1
equal deleted inserted replaced
19:d20759e5d736 20:1de95988bd99
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2009
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
    36     /// This class describes the concept of \c Node, \c Arc and \c Edge
    36     /// This class describes the concept of \c Node, \c Arc and \c Edge
    37     /// subtypes of digraph and graph types.
    37     /// subtypes of digraph and graph types.
    38     ///
    38     ///
    39     /// \note This class is a template class so that we can use it to
    39     /// \note This class is a template class so that we can use it to
    40     /// create graph skeleton classes. The reason for this is that \c Node
    40     /// create graph skeleton classes. The reason for this is that \c Node
    41     /// and \c Arc (or \c Edge) types should \e not derive from the same 
    41     /// and \c Arc (or \c Edge) types should \e not derive from the same
    42     /// base class. For \c Node you should instantiate it with character
    42     /// base class. For \c Node you should instantiate it with character
    43     /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
    43     /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
    44 #ifndef DOXYGEN
    44 #ifndef DOXYGEN
    45     template <char sel = '0'>
    45     template <char sel = '0'>
    46 #endif
    46 #endif
    87       bool operator!=(const GraphItem&) const { return false; }
    87       bool operator!=(const GraphItem&) const { return false; }
    88 
    88 
    89       /// \brief Ordering operator.
    89       /// \brief Ordering operator.
    90       ///
    90       ///
    91       /// This operator defines an ordering of the items.
    91       /// This operator defines an ordering of the items.
    92       /// It makes possible to use graph item types as key types in 
    92       /// It makes possible to use graph item types as key types in
    93       /// associative containers (e.g. \c std::map).
    93       /// associative containers (e.g. \c std::map).
    94       ///
    94       ///
    95       /// \note This operator only has to define some strict ordering of
    95       /// \note This operator only has to define some strict ordering of
    96       /// the items; this order has nothing to do with the iteration
    96       /// the items; this order has nothing to do with the iteration
    97       /// ordering of the items.
    97       /// ordering of the items.
   120 
   120 
   121     /// \brief Base skeleton class for directed graphs.
   121     /// \brief Base skeleton class for directed graphs.
   122     ///
   122     ///
   123     /// This class describes the base interface of directed graph types.
   123     /// This class describes the base interface of directed graph types.
   124     /// All digraph %concepts have to conform to this class.
   124     /// All digraph %concepts have to conform to this class.
   125     /// It just provides types for nodes and arcs and functions 
   125     /// It just provides types for nodes and arcs and functions
   126     /// to get the source and the target nodes of arcs.
   126     /// to get the source and the target nodes of arcs.
   127     class BaseDigraphComponent {
   127     class BaseDigraphComponent {
   128     public:
   128     public:
   129 
   129 
   130       typedef BaseDigraphComponent Digraph;
   130       typedef BaseDigraphComponent Digraph;
   424       };
   424       };
   425     };
   425     };
   426 
   426 
   427     /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
   427     /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
   428     ///
   428     ///
   429     /// This class describes the concept of \c NodeIt, \c ArcIt and 
   429     /// This class describes the concept of \c NodeIt, \c ArcIt and
   430     /// \c EdgeIt subtypes of digraph and graph types.
   430     /// \c EdgeIt subtypes of digraph and graph types.
   431     template <typename GR, typename Item>
   431     template <typename GR, typename Item>
   432     class GraphItemIt : public Item {
   432     class GraphItemIt : public Item {
   433     public:
   433     public:
   434       /// \brief Default constructor.
   434       /// \brief Default constructor.
   464       /// \brief Increment the iterator.
   464       /// \brief Increment the iterator.
   465       ///
   465       ///
   466       /// This operator increments the iterator, i.e. assigns it to the
   466       /// This operator increments the iterator, i.e. assigns it to the
   467       /// next item.
   467       /// next item.
   468       GraphItemIt& operator++() { return *this; }
   468       GraphItemIt& operator++() { return *this; }
   469  
   469 
   470       /// \brief Equality operator
   470       /// \brief Equality operator
   471       ///
   471       ///
   472       /// Equality operator.
   472       /// Equality operator.
   473       /// Two iterators are equal if and only if they point to the
   473       /// Two iterators are equal if and only if they point to the
   474       /// same object or both are invalid.
   474       /// same object or both are invalid.
   499         }
   499         }
   500         const GR& g;
   500         const GR& g;
   501       };
   501       };
   502     };
   502     };
   503 
   503 
   504     /// \brief Concept class for \c InArcIt, \c OutArcIt and 
   504     /// \brief Concept class for \c InArcIt, \c OutArcIt and
   505     /// \c IncEdgeIt types.
   505     /// \c IncEdgeIt types.
   506     ///
   506     ///
   507     /// This class describes the concept of \c InArcIt, \c OutArcIt 
   507     /// This class describes the concept of \c InArcIt, \c OutArcIt
   508     /// and \c IncEdgeIt subtypes of digraph and graph types.
   508     /// and \c IncEdgeIt subtypes of digraph and graph types.
   509     ///
   509     ///
   510     /// \note Since these iterator classes do not inherit from the same
   510     /// \note Since these iterator classes do not inherit from the same
   511     /// base class, there is an additional template parameter (selector)
   511     /// base class, there is an additional template parameter (selector)
   512     /// \c sel. For \c InArcIt you should instantiate it with character 
   512     /// \c sel. For \c InArcIt you should instantiate it with character
   513     /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
   513     /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
   514     template <typename GR,
   514     template <typename GR,
   515               typename Item = typename GR::Arc,
   515               typename Item = typename GR::Arc,
   516               typename Base = typename GR::Node,
   516               typename Base = typename GR::Node,
   517               char sel = '0'>
   517               char sel = '0'>
   528       /// \brief Copy constructor.
   528       /// \brief Copy constructor.
   529       ///
   529       ///
   530       /// Copy constructor.
   530       /// Copy constructor.
   531       GraphIncIt(const GraphIncIt& it) : Item(it) {}
   531       GraphIncIt(const GraphIncIt& it) : Item(it) {}
   532 
   532 
   533       /// \brief Constructor that sets the iterator to the first 
   533       /// \brief Constructor that sets the iterator to the first
   534       /// incoming or outgoing arc.
   534       /// incoming or outgoing arc.
   535       ///
   535       ///
   536       /// Constructor that sets the iterator to the first arc 
   536       /// Constructor that sets the iterator to the first arc
   537       /// incoming to or outgoing from the given node.
   537       /// incoming to or outgoing from the given node.
   538       explicit GraphIncIt(const GR&, const Base&) {}
   538       explicit GraphIncIt(const GR&, const Base&) {}
   539 
   539 
   540       /// \brief Constructor for conversion from \c INVALID.
   540       /// \brief Constructor for conversion from \c INVALID.
   541       ///
   541       ///
   802       /// This function gives back the next edge in the iteration order.
   802       /// This function gives back the next edge in the iteration order.
   803       void next(Edge&) const {}
   803       void next(Edge&) const {}
   804 
   804 
   805       /// \brief Return the first edge incident to the given node.
   805       /// \brief Return the first edge incident to the given node.
   806       ///
   806       ///
   807       /// This function gives back the first edge incident to the given 
   807       /// This function gives back the first edge incident to the given
   808       /// node. The bool parameter gives back the direction for which the
   808       /// node. The bool parameter gives back the direction for which the
   809       /// source node of the directed arc representing the edge is the 
   809       /// source node of the directed arc representing the edge is the
   810       /// given node.
   810       /// given node.
   811       void firstInc(Edge&, bool&, const Node&) const {}
   811       void firstInc(Edge&, bool&, const Node&) const {}
   812 
   812 
   813       /// \brief Gives back the next of the edges from the
   813       /// \brief Gives back the next of the edges from the
   814       /// given node.
   814       /// given node.
   815       ///
   815       ///
   816       /// This function gives back the next edge incident to the given 
   816       /// This function gives back the next edge incident to the given
   817       /// node. The bool parameter should be used as \c firstInc() use it.
   817       /// node. The bool parameter should be used as \c firstInc() use it.
   818       void nextInc(Edge&, bool&) const {}
   818       void nextInc(Edge&, bool&) const {}
   819 
   819 
   820       using IterableDigraphComponent<Base>::baseNode;
   820       using IterableDigraphComponent<Base>::baseNode;
   821       using IterableDigraphComponent<Base>::runningNode;
   821       using IterableDigraphComponent<Base>::runningNode;
   988     };
   988     };
   989 
   989 
   990     /// \brief Concept class for standard graph maps.
   990     /// \brief Concept class for standard graph maps.
   991     ///
   991     ///
   992     /// This class describes the concept of standard graph maps, i.e.
   992     /// This class describes the concept of standard graph maps, i.e.
   993     /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and 
   993     /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
   994     /// graph types, which can be used for associating data to graph items.
   994     /// graph types, which can be used for associating data to graph items.
   995     /// The standard graph maps must conform to the ReferenceMap concept.
   995     /// The standard graph maps must conform to the ReferenceMap concept.
   996     template <typename GR, typename K, typename V>
   996     template <typename GR, typename K, typename V>
   997     class GraphMap : public ReferenceMap<K, V, V&, const V&> {
   997     class GraphMap : public ReferenceMap<K, V, V&, const V&> {
   998       typedef ReferenceMap<K, V, V&, const V&> Parent;
   998       typedef ReferenceMap<K, V, V&, const V&> Parent;
  1043         void constraints() {
  1043         void constraints() {
  1044           checkConcept
  1044           checkConcept
  1045             <ReferenceMap<Key, Value, Value&, const Value&>, _Map>();
  1045             <ReferenceMap<Key, Value, Value&, const Value&>, _Map>();
  1046           _Map m1(g);
  1046           _Map m1(g);
  1047           _Map m2(g,t);
  1047           _Map m2(g,t);
  1048           
  1048 
  1049           // Copy constructor
  1049           // Copy constructor
  1050           // _Map m3(m);
  1050           // _Map m3(m);
  1051 
  1051 
  1052           // Assignment operator
  1052           // Assignment operator
  1053           // ReadMap<Key, Value> cmap;
  1053           // ReadMap<Key, Value> cmap;
  1066     };
  1066     };
  1067 
  1067 
  1068     /// \brief Skeleton class for mappable directed graphs.
  1068     /// \brief Skeleton class for mappable directed graphs.
  1069     ///
  1069     ///
  1070     /// This class describes the interface of mappable directed graphs.
  1070     /// This class describes the interface of mappable directed graphs.
  1071     /// It extends \ref BaseDigraphComponent with the standard digraph 
  1071     /// It extends \ref BaseDigraphComponent with the standard digraph
  1072     /// map classes, namely \c NodeMap and \c ArcMap.
  1072     /// map classes, namely \c NodeMap and \c ArcMap.
  1073     /// This concept is part of the Digraph concept.
  1073     /// This concept is part of the Digraph concept.
  1074     template <typename BAS = BaseDigraphComponent>
  1074     template <typename BAS = BaseDigraphComponent>
  1075     class MappableDigraphComponent : public BAS  {
  1075     class MappableDigraphComponent : public BAS  {
  1076     public:
  1076     public:
  1203     };
  1203     };
  1204 
  1204 
  1205     /// \brief Skeleton class for mappable undirected graphs.
  1205     /// \brief Skeleton class for mappable undirected graphs.
  1206     ///
  1206     ///
  1207     /// This class describes the interface of mappable undirected graphs.
  1207     /// This class describes the interface of mappable undirected graphs.
  1208     /// It extends \ref MappableDigraphComponent with the standard graph 
  1208     /// It extends \ref MappableDigraphComponent with the standard graph
  1209     /// map class for edges (\c EdgeMap).
  1209     /// map class for edges (\c EdgeMap).
  1210     /// This concept is part of the Graph concept.
  1210     /// This concept is part of the Graph concept.
  1211     template <typename BAS = BaseGraphComponent>
  1211     template <typename BAS = BaseGraphComponent>
  1212     class MappableGraphComponent : public MappableDigraphComponent<BAS>  {
  1212     class MappableGraphComponent : public MappableDigraphComponent<BAS>  {
  1213     public:
  1213     public:
  1288     };
  1288     };
  1289 
  1289 
  1290     /// \brief Skeleton class for extendable directed graphs.
  1290     /// \brief Skeleton class for extendable directed graphs.
  1291     ///
  1291     ///
  1292     /// This class describes the interface of extendable directed graphs.
  1292     /// This class describes the interface of extendable directed graphs.
  1293     /// It extends \ref BaseDigraphComponent with functions for adding 
  1293     /// It extends \ref BaseDigraphComponent with functions for adding
  1294     /// nodes and arcs to the digraph.
  1294     /// nodes and arcs to the digraph.
  1295     /// This concept requires \ref AlterableDigraphComponent.
  1295     /// This concept requires \ref AlterableDigraphComponent.
  1296     template <typename BAS = BaseDigraphComponent>
  1296     template <typename BAS = BaseDigraphComponent>
  1297     class ExtendableDigraphComponent : public BAS {
  1297     class ExtendableDigraphComponent : public BAS {
  1298     public:
  1298     public:
  1332     };
  1332     };
  1333 
  1333 
  1334     /// \brief Skeleton class for extendable undirected graphs.
  1334     /// \brief Skeleton class for extendable undirected graphs.
  1335     ///
  1335     ///
  1336     /// This class describes the interface of extendable undirected graphs.
  1336     /// This class describes the interface of extendable undirected graphs.
  1337     /// It extends \ref BaseGraphComponent with functions for adding 
  1337     /// It extends \ref BaseGraphComponent with functions for adding
  1338     /// nodes and edges to the graph.
  1338     /// nodes and edges to the graph.
  1339     /// This concept requires \ref AlterableGraphComponent.
  1339     /// This concept requires \ref AlterableGraphComponent.
  1340     template <typename BAS = BaseGraphComponent>
  1340     template <typename BAS = BaseGraphComponent>
  1341     class ExtendableGraphComponent : public BAS {
  1341     class ExtendableGraphComponent : public BAS {
  1342     public:
  1342     public:
  1376     };
  1376     };
  1377 
  1377 
  1378     /// \brief Skeleton class for erasable directed graphs.
  1378     /// \brief Skeleton class for erasable directed graphs.
  1379     ///
  1379     ///
  1380     /// This class describes the interface of erasable directed graphs.
  1380     /// This class describes the interface of erasable directed graphs.
  1381     /// It extends \ref BaseDigraphComponent with functions for removing 
  1381     /// It extends \ref BaseDigraphComponent with functions for removing
  1382     /// nodes and arcs from the digraph.
  1382     /// nodes and arcs from the digraph.
  1383     /// This concept requires \ref AlterableDigraphComponent.
  1383     /// This concept requires \ref AlterableDigraphComponent.
  1384     template <typename BAS = BaseDigraphComponent>
  1384     template <typename BAS = BaseDigraphComponent>
  1385     class ErasableDigraphComponent : public BAS {
  1385     class ErasableDigraphComponent : public BAS {
  1386     public:
  1386     public:
  1389       typedef typename Base::Node Node;
  1389       typedef typename Base::Node Node;
  1390       typedef typename Base::Arc Arc;
  1390       typedef typename Base::Arc Arc;
  1391 
  1391 
  1392       /// \brief Erase a node from the digraph.
  1392       /// \brief Erase a node from the digraph.
  1393       ///
  1393       ///
  1394       /// This function erases the given node from the digraph and all arcs 
  1394       /// This function erases the given node from the digraph and all arcs
  1395       /// connected to the node.
  1395       /// connected to the node.
  1396       void erase(const Node&) {}
  1396       void erase(const Node&) {}
  1397 
  1397 
  1398       /// \brief Erase an arc from the digraph.
  1398       /// \brief Erase an arc from the digraph.
  1399       ///
  1399       ///
  1415     };
  1415     };
  1416 
  1416 
  1417     /// \brief Skeleton class for erasable undirected graphs.
  1417     /// \brief Skeleton class for erasable undirected graphs.
  1418     ///
  1418     ///
  1419     /// This class describes the interface of erasable undirected graphs.
  1419     /// This class describes the interface of erasable undirected graphs.
  1420     /// It extends \ref BaseGraphComponent with functions for removing 
  1420     /// It extends \ref BaseGraphComponent with functions for removing
  1421     /// nodes and edges from the graph.
  1421     /// nodes and edges from the graph.
  1422     /// This concept requires \ref AlterableGraphComponent.
  1422     /// This concept requires \ref AlterableGraphComponent.
  1423     template <typename BAS = BaseGraphComponent>
  1423     template <typename BAS = BaseGraphComponent>
  1424     class ErasableGraphComponent : public BAS {
  1424     class ErasableGraphComponent : public BAS {
  1425     public:
  1425     public: