COIN-OR::LEMON - Graph Library

Changeset 209:765619b7cbb2 in lemon-1.0 for lemon/concepts


Ignore:
Timestamp:
07/13/08 20:51:02 (11 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
Message:

Apply unify-sources.sh to the source tree

Location:
lemon/concepts
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • lemon/concepts/digraph.h

    r125 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    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.
    44 *
    55 * Copyright (C) 2003-2008
     
    4747    private:
    4848      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
    49      
     49
    5050      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
    5151      ///
     
    5353      ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
    5454      ///\e not allowed. Use DigraphCopy() instead.
    55      
     55
    5656      ///Assignment of \ref Digraph "Digraph"s to another ones are
    5757      ///\e not allowed.  Use DigraphCopy() instead.
     
    9696
    9797        /// Inequality operator
    98        
     98
    9999        /// \sa operator==(Node n)
    100100        ///
    101101        bool operator!=(Node) const { return true; }
    102102
    103         /// Artificial ordering operator.
    104        
    105         /// To allow the use of digraph descriptors as key type in std::map or
    106         /// similar associative container we require this.
    107         ///
    108         /// \note This operator only have to define some strict ordering of
    109         /// the items; this order has nothing to do with the iteration
    110         /// ordering of the items.
    111         bool operator<(Node) const { return false; }
    112 
    113       };
    114    
     103        /// Artificial ordering operator.
     104
     105        /// To allow the use of digraph descriptors as key type in std::map or
     106        /// similar associative container we require this.
     107        ///
     108        /// \note This operator only have to define some strict ordering of
     109        /// the items; this order has nothing to do with the iteration
     110        /// ordering of the items.
     111        bool operator<(Node) const { return false; }
     112
     113      };
     114
    115115      /// This iterator goes through each node.
    116116
     
    130130        NodeIt() { }
    131131        /// Copy constructor.
    132        
     132
    133133        /// Copy constructor.
    134134        ///
     
    146146        /// Node -> NodeIt conversion.
    147147
    148         /// Sets the iterator to the node of \c the digraph pointed by 
    149         /// the trivial iterator.
    150         /// This feature necessitates that each time we 
     148        /// Sets the iterator to the node of \c the digraph pointed by
     149        /// the trivial iterator.
     150        /// This feature necessitates that each time we
    151151        /// iterate the arc-set, the iteration order is the same.
    152152        NodeIt(const Digraph&, const Node&) { }
     
    157157        NodeIt& operator++() { return *this; }
    158158      };
    159    
    160    
     159
     160
    161161      /// Class for identifying an arc of the digraph
    162162
     
    192192        bool operator!=(Arc) const { return true; }
    193193
    194         /// Artificial ordering operator.
    195        
    196         /// To allow the use of digraph descriptors as key type in std::map or
    197         /// similar associative container we require this.
    198         ///
    199         /// \note This operator only have to define some strict ordering of
    200         /// the items; this order has nothing to do with the iteration
    201         /// ordering of the items.
    202         bool operator<(Arc) const { return false; }
    203       };
    204    
     194        /// Artificial ordering operator.
     195
     196        /// To allow the use of digraph descriptors as key type in std::map or
     197        /// similar associative container we require this.
     198        ///
     199        /// \note This operator only have to define some strict ordering of
     200        /// the items; this order has nothing to do with the iteration
     201        /// ordering of the items.
     202        bool operator<(Arc) const { return false; }
     203      };
     204
    205205      /// This iterator goes trough the outgoing arcs of a node.
    206206
     
    214214      /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
    215215      ///\endcode
    216    
     216
    217217      class OutArcIt : public Arc {
    218218      public:
     
    233233        OutArcIt(Invalid) { }
    234234        /// This constructor sets the iterator to the first outgoing arc.
    235    
     235
    236236        /// This constructor sets the iterator to the first outgoing arc of
    237237        /// the node.
     
    240240
    241241        /// Sets the iterator to the value of the trivial iterator.
    242         /// This feature necessitates that each time we
     242        /// This feature necessitates that each time we
    243243        /// iterate the arc-set, the iteration order is the same.
    244244        OutArcIt(const Digraph&, const Arc&) { }
    245245        ///Next outgoing arc
    246        
    247         /// Assign the iterator to the next 
     246
     247        /// Assign the iterator to the next
    248248        /// outgoing arc of the corresponding node.
    249249        OutArcIt& operator++() { return *this; }
     
    280280        InArcIt(Invalid) { }
    281281        /// This constructor sets the iterator to first incoming arc.
    282    
     282
    283283        /// This constructor set the iterator to the first incoming arc of
    284284        /// the node.
     
    287287
    288288        /// Sets the iterator to the value of the trivial iterator \c e.
    289         /// This feature necessitates that each time we 
     289        /// This feature necessitates that each time we
    290290        /// iterate the arc-set, the iteration order is the same.
    291291        InArcIt(const Digraph&, const Arc&) { }
     
    323323        ArcIt(Invalid) { }
    324324        /// This constructor sets the iterator to the first arc.
    325    
     325
    326326        /// This constructor sets the iterator to the first arc of \c g.
    327327        ///@param g the digraph
     
    330330
    331331        /// Sets the iterator to the value of the trivial iterator \c e.
    332         /// This feature necessitates that each time we 
     332        /// This feature necessitates that each time we
    333333        /// iterate the arc-set, the iteration order is the same.
    334         ArcIt(const Digraph&, const Arc&) { } 
     334        ArcIt(const Digraph&, const Arc&) { }
    335335        ///Next arc
    336        
     336
    337337        /// Assign the iterator to the next arc.
    338338        ArcIt& operator++() { return *this; }
     
    350350
    351351      /// \brief Returns the ID of the node.
    352       int id(Node) const { return -1; } 
     352      int id(Node) const { return -1; }
    353353
    354354      /// \brief Returns the ID of the arc.
    355       int id(Arc) const { return -1; } 
     355      int id(Arc) const { return -1; }
    356356
    357357      /// \brief Returns the node with the given ID.
    358358      ///
    359359      /// \pre The argument should be a valid node ID in the graph.
    360       Node nodeFromId(int) const { return INVALID; } 
     360      Node nodeFromId(int) const { return INVALID; }
    361361
    362362      /// \brief Returns the arc with the given ID.
    363363      ///
    364364      /// \pre The argument should be a valid arc ID in the graph.
    365       Arc arcFromId(int) const { return INVALID; } 
     365      Arc arcFromId(int) const { return INVALID; }
    366366
    367367      /// \brief Returns an upper bound on the node IDs.
    368       int maxNodeId() const { return -1; } 
     368      int maxNodeId() const { return -1; }
    369369
    370370      /// \brief Returns an upper bound on the arc IDs.
    371       int maxArcId() const { return -1; } 
     371      int maxArcId() const { return -1; }
    372372
    373373      void first(Node&) const {}
     
    390390
    391391      // Dummy parameter.
    392       int maxId(Node) const { return -1; } 
     392      int maxId(Node) const { return -1; }
    393393      // Dummy parameter.
    394       int maxId(Arc) const { return -1; } 
     394      int maxId(Arc) const { return -1; }
    395395
    396396      /// \brief The base node of the iterator.
     
    424424
    425425      /// \brief Read write map of the nodes to type \c T.
    426       /// 
     426      ///
    427427      /// ReadWrite map of the nodes to type \c T.
    428428      /// \sa Reference
    429       template<class T> 
     429      template<class T>
    430430      class NodeMap : public ReadWriteMap< Node, T > {
    431431      public:
     
    440440        ///Assignment operator
    441441        template <typename CMap>
    442         NodeMap& operator=(const CMap&) { 
     442        NodeMap& operator=(const CMap&) {
    443443          checkConcept<ReadMap<Node, T>, CMap>();
    444           return *this; 
     444          return *this;
    445445        }
    446446      };
     
    450450      /// Reference map of the arcs to type \c T.
    451451      /// \sa Reference
    452       template<class T> 
     452      template<class T>
    453453      class ArcMap : public ReadWriteMap<Arc,T> {
    454454      public:
     
    462462        ///Assignment operator
    463463        template <typename CMap>
    464         ArcMap& operator=(const CMap&) { 
     464        ArcMap& operator=(const CMap&) {
    465465          checkConcept<ReadMap<Arc, T>, CMap>();
    466           return *this; 
     466          return *this;
    467467        }
    468468      };
     
    472472        void constraints() {
    473473          checkConcept<IterableDigraphComponent<>, _Digraph>();
    474           checkConcept<IDableDigraphComponent<>, _Digraph>();
     474          checkConcept<IDableDigraphComponent<>, _Digraph>();
    475475          checkConcept<MappableDigraphComponent<>, _Digraph>();
    476476        }
     
    478478
    479479    };
    480    
    481   } //namespace concepts 
     480
     481  } //namespace concepts
    482482} //namespace lemon
    483483
  • lemon/concepts/graph.h

    r125 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    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.
    44 *
    55 * Copyright (C) 2003-2008
     
    6666    /// direction. The IncEdgeIt iterates also on the same edges
    6767    /// as the OutArcIt and InArcIt but it is not convertible to Arc just
    68     /// to Edge. 
     68    /// to Edge.
    6969    class Graph {
    7070    public:
     
    7373      ///
    7474      /// The undirected graph should be tagged by the UndirectedTag. This
    75       /// tag helps the enable_if technics to make compile time 
    76       /// specializations for undirected graphs. 
     75      /// tag helps the enable_if technics to make compile time
     76      /// specializations for undirected graphs.
    7777      typedef True UndirectedTag;
    7878
    79       /// \brief The base type of node iterators, 
     79      /// \brief The base type of node iterators,
    8080      /// or in other words, the trivial node iterator.
    8181      ///
    8282      /// This is the base type of each node iterator,
    8383      /// thus each kind of node iterator converts to this.
    84       /// More precisely each kind of node iterator should be inherited 
     84      /// More precisely each kind of node iterator should be inherited
    8585      /// from the trivial node iterator.
    8686      class Node {
     
    109109
    110110        /// Inequality operator
    111        
     111
    112112        /// \sa operator==(Node n)
    113113        ///
    114114        bool operator!=(Node) const { return true; }
    115115
    116         /// Artificial ordering operator.
    117        
    118         /// To allow the use of graph descriptors as key type in std::map or
    119         /// similar associative container we require this.
    120         ///
    121         /// \note This operator only have to define some strict ordering of
    122         /// the items; this order has nothing to do with the iteration
    123         /// ordering of the items.
    124         bool operator<(Node) const { return false; }
    125 
    126       };
    127    
     116        /// Artificial ordering operator.
     117
     118        /// To allow the use of graph descriptors as key type in std::map or
     119        /// similar associative container we require this.
     120        ///
     121        /// \note This operator only have to define some strict ordering of
     122        /// the items; this order has nothing to do with the iteration
     123        /// ordering of the items.
     124        bool operator<(Node) const { return false; }
     125
     126      };
     127
    128128      /// This iterator goes through each node.
    129129
     
    143143        NodeIt() { }
    144144        /// Copy constructor.
    145        
     145
    146146        /// Copy constructor.
    147147        ///
     
    159159        /// Node -> NodeIt conversion.
    160160
    161         /// Sets the iterator to the node of \c the graph pointed by 
    162         /// the trivial iterator.
    163         /// This feature necessitates that each time we 
     161        /// Sets the iterator to the node of \c the graph pointed by
     162        /// the trivial iterator.
     163        /// This feature necessitates that each time we
    164164        /// iterate the arc-set, the iteration order is the same.
    165165        NodeIt(const Graph&, const Node&) { }
     
    170170        NodeIt& operator++() { return *this; }
    171171      };
    172    
    173    
     172
     173
    174174      /// The base type of the edge iterators.
    175175
     
    204204        bool operator!=(Edge) const { return true; }
    205205
    206         /// Artificial ordering operator.
    207        
    208         /// To allow the use of graph descriptors as key type in std::map or
    209         /// similar associative container we require this.
    210         ///
    211         /// \note This operator only have to define some strict ordering of
    212         /// the items; this order has nothing to do with the iteration
    213         /// ordering of the items.
    214         bool operator<(Edge) const { return false; }
     206        /// Artificial ordering operator.
     207
     208        /// To allow the use of graph descriptors as key type in std::map or
     209        /// similar associative container we require this.
     210        ///
     211        /// \note This operator only have to define some strict ordering of
     212        /// the items; this order has nothing to do with the iteration
     213        /// ordering of the items.
     214        bool operator<(Edge) const { return false; }
    215215      };
    216216
     
    242242        EdgeIt(Invalid) { }
    243243        /// This constructor sets the iterator to the first edge.
    244    
     244
    245245        /// This constructor sets the iterator to the first edge.
    246246        EdgeIt(const Graph&) { }
     
    249249        /// Sets the iterator to the value of the trivial iterator.
    250250        /// This feature necessitates that each time we
    251         /// iterate the edge-set, the iteration order is the 
    252         /// same.
    253         EdgeIt(const Graph&, const Edge&) { } 
     251        /// iterate the edge-set, the iteration order is the
     252        /// same.
     253        EdgeIt(const Graph&, const Edge&) { }
    254254        /// Next edge
    255        
     255
    256256        /// Assign the iterator to the next edge.
    257257        EdgeIt& operator++() { return *this; }
    258258      };
    259259
    260       /// \brief This iterator goes trough the incident undirected 
     260      /// \brief This iterator goes trough the incident undirected
    261261      /// arcs of a node.
    262262      ///
    263263      /// This iterator goes trough the incident edges
    264       /// of a certain node of a graph. You should assume that the 
     264      /// of a certain node of a graph. You should assume that the
    265265      /// loop arcs will be iterated twice.
    266       /// 
     266      ///
    267267      /// Its usage is quite simple, for example you can compute the
    268268      /// degree (i.e. count the number of incident arcs of a node \c n
    269       /// in graph \c g of type \c Graph as follows. 
     269      /// in graph \c g of type \c Graph as follows.
    270270      ///
    271271      ///\code
     
    291291        IncEdgeIt(Invalid) { }
    292292        /// This constructor sets the iterator to first incident arc.
    293    
     293
    294294        /// This constructor set the iterator to the first incident arc of
    295295        /// the node.
     
    298298
    299299        /// Sets the iterator to the value of the trivial iterator \c e.
    300         /// This feature necessitates that each time we 
     300        /// This feature necessitates that each time we
    301301        /// iterate the arc-set, the iteration order is the same.
    302302        IncEdgeIt(const Graph&, const Edge&) { }
     
    304304
    305305        /// Assign the iterator to the next incident arc
    306         /// of the corresponding node.
     306        /// of the corresponding node.
    307307        IncEdgeIt& operator++() { return *this; }
    308308      };
     
    341341        bool operator!=(Arc) const { return true; }
    342342
    343         /// Artificial ordering operator.
    344        
    345         /// To allow the use of graph descriptors as key type in std::map or
    346         /// similar associative container we require this.
    347         ///
    348         /// \note This operator only have to define some strict ordering of
    349         /// the items; this order has nothing to do with the iteration
    350         /// ordering of the items.
    351         bool operator<(Arc) const { return false; }
    352        
    353       }; 
     343        /// Artificial ordering operator.
     344
     345        /// To allow the use of graph descriptors as key type in std::map or
     346        /// similar associative container we require this.
     347        ///
     348        /// \note This operator only have to define some strict ordering of
     349        /// the items; this order has nothing to do with the iteration
     350        /// ordering of the items.
     351        bool operator<(Arc) const { return false; }
     352
     353      };
    354354      /// This iterator goes through each directed arc.
    355355
     
    379379        ArcIt(Invalid) { }
    380380        /// This constructor sets the iterator to the first arc.
    381    
     381
    382382        /// This constructor sets the iterator to the first arc of \c g.
    383383        ///@param g the graph
     
    386386
    387387        /// Sets the iterator to the value of the trivial iterator \c e.
    388         /// This feature necessitates that each time we 
     388        /// This feature necessitates that each time we
    389389        /// iterate the arc-set, the iteration order is the same.
    390         ArcIt(const Graph&, const Arc&) { } 
     390        ArcIt(const Graph&, const Arc&) { }
    391391        ///Next arc
    392        
     392
    393393        /// Assign the iterator to the next arc.
    394394        ArcIt& operator++() { return *this; }
    395395      };
    396    
     396
    397397      /// This iterator goes trough the outgoing directed arcs of a node.
    398398
     
    406406      /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
    407407      ///\endcode
    408    
     408
    409409      class OutArcIt : public Arc {
    410410      public:
     
    425425        OutArcIt(Invalid) { }
    426426        /// This constructor sets the iterator to the first outgoing arc.
    427    
     427
    428428        /// This constructor sets the iterator to the first outgoing arc of
    429429        /// the node.
     
    431431        ///@param g the graph
    432432        OutArcIt(const Graph& n, const Node& g) {
    433           ignore_unused_variable_warning(n);
    434           ignore_unused_variable_warning(g);
    435         }
     433          ignore_unused_variable_warning(n);
     434          ignore_unused_variable_warning(g);
     435        }
    436436        /// Arc -> OutArcIt conversion
    437437
    438438        /// Sets the iterator to the value of the trivial iterator.
    439         /// This feature necessitates that each time we
     439        /// This feature necessitates that each time we
    440440        /// iterate the arc-set, the iteration order is the same.
    441441        OutArcIt(const Graph&, const Arc&) { }
    442442        ///Next outgoing arc
    443        
    444         /// Assign the iterator to the next 
     443
     444        /// Assign the iterator to the next
    445445        /// outgoing arc of the corresponding node.
    446446        OutArcIt& operator++() { return *this; }
     
    477477        InArcIt(Invalid) { }
    478478        /// This constructor sets the iterator to first incoming arc.
    479    
     479
    480480        /// This constructor set the iterator to the first incoming arc of
    481481        /// the node.
    482482        ///@param n the node
    483483        ///@param g the graph
    484         InArcIt(const Graph& g, const Node& n) { 
    485           ignore_unused_variable_warning(n);
    486           ignore_unused_variable_warning(g);
    487         }
     484        InArcIt(const Graph& g, const Node& n) {
     485          ignore_unused_variable_warning(n);
     486          ignore_unused_variable_warning(g);
     487        }
    488488        /// Arc -> InArcIt conversion
    489489
    490490        /// Sets the iterator to the value of the trivial iterator \c e.
    491         /// This feature necessitates that each time we 
     491        /// This feature necessitates that each time we
    492492        /// iterate the arc-set, the iteration order is the same.
    493493        InArcIt(const Graph&, const Arc&) { }
     
    500500
    501501      /// \brief Read write map of the nodes to type \c T.
    502       /// 
     502      ///
    503503      /// ReadWrite map of the nodes to type \c T.
    504504      /// \sa Reference
    505       template<class T> 
     505      template<class T>
    506506      class NodeMap : public ReadWriteMap< Node, T >
    507507      {
     
    517517        ///Assignment operator
    518518        template <typename CMap>
    519         NodeMap& operator=(const CMap&) { 
     519        NodeMap& operator=(const CMap&) {
    520520          checkConcept<ReadMap<Node, T>, CMap>();
    521           return *this; 
     521          return *this;
    522522        }
    523523      };
     
    527527      /// Reference map of the directed arcs to type \c T.
    528528      /// \sa Reference
    529       template<class T> 
     529      template<class T>
    530530      class ArcMap : public ReadWriteMap<Arc,T>
    531531      {
     
    540540        ///Assignment operator
    541541        template <typename CMap>
    542         ArcMap& operator=(const CMap&) { 
     542        ArcMap& operator=(const CMap&) {
    543543          checkConcept<ReadMap<Arc, T>, CMap>();
    544           return *this; 
     544          return *this;
    545545        }
    546546      };
     
    550550      /// Reference map of the arcs to type \c T.
    551551      /// \sa Reference
    552       template<class T> 
     552      template<class T>
    553553      class EdgeMap : public ReadWriteMap<Edge,T>
    554554      {
     
    563563        ///Assignment operator
    564564        template <typename CMap>
    565         EdgeMap& operator=(const CMap&) { 
     565        EdgeMap& operator=(const CMap&) {
    566566          checkConcept<ReadMap<Edge, T>, CMap>();
    567           return *this; 
     567          return *this;
    568568        }
    569569      };
     
    574574      /// will be the given node.
    575575      Arc direct(const Edge&, const Node&) const {
    576         return INVALID;
     576        return INVALID;
    577577      }
    578578
     
    584584      /// the directed arc is the same when the given bool is true.
    585585      Arc direct(const Edge&, bool) const {
    586         return INVALID;
     586        return INVALID;
    587587      }
    588588
     
    626626
    627627      /// \brief Returns the id of the node.
    628       int id(Node) const { return -1; } 
     628      int id(Node) const { return -1; }
    629629
    630630      /// \brief Returns the id of the edge.
    631       int id(Edge) const { return -1; } 
     631      int id(Edge) const { return -1; }
    632632
    633633      /// \brief Returns the id of the arc.
    634       int id(Arc) const { return -1; } 
     634      int id(Arc) const { return -1; }
    635635
    636636      /// \brief Returns the node with the given id.
    637637      ///
    638638      /// \pre The argument should be a valid node id in the graph.
    639       Node nodeFromId(int) const { return INVALID; } 
     639      Node nodeFromId(int) const { return INVALID; }
    640640
    641641      /// \brief Returns the edge with the given id.
    642642      ///
    643643      /// \pre The argument should be a valid edge id in the graph.
    644       Edge edgeFromId(int) const { return INVALID; } 
     644      Edge edgeFromId(int) const { return INVALID; }
    645645
    646646      /// \brief Returns the arc with the given id.
    647647      ///
    648648      /// \pre The argument should be a valid arc id in the graph.
    649       Arc arcFromId(int) const { return INVALID; } 
     649      Arc arcFromId(int) const { return INVALID; }
    650650
    651651      /// \brief Returns an upper bound on the node IDs.
    652       int maxNodeId() const { return -1; } 
     652      int maxNodeId() const { return -1; }
    653653
    654654      /// \brief Returns an upper bound on the edge IDs.
    655       int maxEdgeId() const { return -1; } 
     655      int maxEdgeId() const { return -1; }
    656656
    657657      /// \brief Returns an upper bound on the arc IDs.
    658       int maxArcId() const { return -1; } 
     658      int maxArcId() const { return -1; }
    659659
    660660      void first(Node&) const {}
     
    684684
    685685      // Dummy parameter.
    686       int maxId(Node) const { return -1; } 
     686      int maxId(Node) const { return -1; }
    687687      // Dummy parameter.
    688       int maxId(Edge) const { return -1; } 
     688      int maxId(Edge) const { return -1; }
    689689      // Dummy parameter.
    690       int maxId(Arc) const { return -1; } 
     690      int maxId(Arc) const { return -1; }
    691691
    692692      /// \brief Base node of the iterator
     
    694694      /// Returns the base node (the source in this case) of the iterator
    695695      Node baseNode(OutArcIt e) const {
    696         return source(e);
     696        return source(e);
    697697      }
    698698      /// \brief Running node of the iterator
     
    701701      /// iterator
    702702      Node runningNode(OutArcIt e) const {
    703         return target(e);
     703        return target(e);
    704704      }
    705705
     
    708708      /// Returns the base node (the target in this case) of the iterator
    709709      Node baseNode(InArcIt e) const {
    710         return target(e);
     710        return target(e);
    711711      }
    712712      /// \brief Running node of the iterator
     
    715715      /// iterator
    716716      Node runningNode(InArcIt e) const {
    717         return source(e);
     717        return source(e);
    718718      }
    719719
     
    722722      /// Returns the base node of the iterator
    723723      Node baseNode(IncEdgeIt) const {
    724         return INVALID;
     724        return INVALID;
    725725      }
    726      
     726
    727727      /// \brief Running node of the iterator
    728728      ///
    729729      /// Returns the running node of the iterator
    730730      Node runningNode(IncEdgeIt) const {
    731         return INVALID;
     731        return INVALID;
    732732      }
    733733
    734734      template <typename _Graph>
    735735      struct Constraints {
    736         void constraints() {
    737           checkConcept<IterableGraphComponent<>, _Graph>();
    738           checkConcept<IDableGraphComponent<>, _Graph>();
    739           checkConcept<MappableGraphComponent<>, _Graph>();
    740         }
     736        void constraints() {
     737          checkConcept<IterableGraphComponent<>, _Graph>();
     738          checkConcept<IDableGraphComponent<>, _Graph>();
     739          checkConcept<MappableGraphComponent<>, _Graph>();
     740        }
    741741      };
    742742
  • lemon/concepts/graph_components.h

    r169 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    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.
    44 *
    55 * Copyright (C) 2003-2008
     
    5050    public:
    5151      /// \brief Default constructor.
    52       ///     
     52      ///
    5353      /// \warning The default constructor is not required to set
    5454      /// the item to some well-defined value. So you should consider it
     
    6767      /// \brief Assign operator for nodes.
    6868      ///
    69       /// The nodes are assignable. 
     69      /// The nodes are assignable.
    7070      ///
    7171      GraphItem& operator=(GraphItem const&) { return *this; }
     
    9393      template<typename _GraphItem>
    9494      struct Constraints {
    95         void constraints() {
    96           _GraphItem i1;
    97           _GraphItem i2 = i1;
    98           _GraphItem i3 = INVALID;
    99          
    100           i1 = i2 = i3;
    101 
    102           bool b;
    103           //      b = (ia == ib) && (ia != ib) && (ia < ib);
    104           b = (ia == ib) && (ia != ib);
    105           b = (ia == INVALID) && (ib != INVALID);
     95        void constraints() {
     96          _GraphItem i1;
     97          _GraphItem i2 = i1;
     98          _GraphItem i3 = INVALID;
     99
     100          i1 = i2 = i3;
     101
     102          bool b;
     103          //          b = (ia == ib) && (ia != ib) && (ia < ib);
     104          b = (ia == ib) && (ia != ib);
     105          b = (ia == INVALID) && (ib != INVALID);
    106106          b = (ia < ib);
    107         }
    108 
    109         const _GraphItem &ia;
    110         const _GraphItem &ib;
     107        }
     108
     109        const _GraphItem &ia;
     110        const _GraphItem &ib;
    111111      };
    112112    };
    113113
    114114    /// \brief An empty base directed graph class.
    115     /// 
     115    ///
    116116    /// This class provides the minimal set of features needed for a
    117117    /// directed graph structure. All digraph concepts have to be
     
    123123
    124124      typedef BaseDigraphComponent Digraph;
    125      
     125
    126126      /// \brief Node class of the digraph.
    127127      ///
    128       /// This class represents the Nodes of the digraph. 
     128      /// This class represents the Nodes of the digraph.
    129129      ///
    130130      typedef GraphItem<'n'> Node;
     
    132132      /// \brief Arc class of the digraph.
    133133      ///
    134       /// This class represents the Arcs of the digraph. 
     134      /// This class represents the Arcs of the digraph.
    135135      ///
    136136      typedef GraphItem<'e'> Arc;
     
    157157      template <typename _Digraph>
    158158      struct Constraints {
    159         typedef typename _Digraph::Node Node;
    160         typedef typename _Digraph::Arc Arc;
    161      
    162         void constraints() {
    163           checkConcept<GraphItem<'n'>, Node>();
    164           checkConcept<GraphItem<'a'>, Arc>();
    165           {
    166             Node n;
    167             Arc e(INVALID);
    168             n = digraph.source(e);
    169             n = digraph.target(e);
     159        typedef typename _Digraph::Node Node;
     160        typedef typename _Digraph::Arc Arc;
     161
     162        void constraints() {
     163          checkConcept<GraphItem<'n'>, Node>();
     164          checkConcept<GraphItem<'a'>, Arc>();
     165          {
     166            Node n;
     167            Arc e(INVALID);
     168            n = digraph.source(e);
     169            n = digraph.target(e);
    170170            n = digraph.oppositeNode(n, e);
    171           }     
    172         }
    173      
    174         const _Digraph& digraph;
     171          }
     172        }
     173
     174        const _Digraph& digraph;
    175175      };
    176176    };
    177177
    178178    /// \brief An empty base undirected graph class.
    179     /// 
     179    ///
    180180    /// This class provides the minimal set of features needed for an
    181181    /// undirected graph structure. All undirected graph concepts have
     
    200200        typedef GraphItem<'u'> Parent;
    201201        /// \brief Default constructor.
    202         ///     
     202        ///
    203203        /// \warning The default constructor is not required to set
    204204        /// the item to some well-defined value. So you should consider it
     
    218218        ///
    219219        /// Besides the core graph item functionality each arc should
    220         /// be convertible to the represented edge. 
     220        /// be convertible to the represented edge.
    221221        Edge(const Arc&) {}
    222222        /// \brief Assign arc to edge.
    223223        ///
    224224        /// Besides the core graph item functionality each arc should
    225         /// be convertible to the represented edge. 
     225        /// be convertible to the represented edge.
    226226        Edge& operator=(const Arc&) { return *this; }
    227227      };
     
    238238      /// Returns the directed arc from its direction and the
    239239      /// represented edge.
    240       Arc direct(const Edge&, bool) const { return INVALID;} 
     240      Arc direct(const Edge&, bool) const { return INVALID;}
    241241
    242242      /// \brief Returns the directed arc.
     
    244244      /// Returns the directed arc from its source and the
    245245      /// represented edge.
    246       Arc direct(const Edge&, const Node&) const { return INVALID;} 
     246      Arc direct(const Edge&, const Node&) const { return INVALID;}
    247247
    248248      /// \brief Returns the opposite arc.
     
    261261      /// Gives back the other ending of an edge.
    262262      Node v(const Edge&) const { return INVALID;}
    263      
     263
    264264      template <typename _Graph>
    265265      struct Constraints {
    266         typedef typename _Graph::Node Node;
    267         typedef typename _Graph::Arc Arc;
    268         typedef typename _Graph::Edge Edge;
    269      
    270         void constraints() {
     266        typedef typename _Graph::Node Node;
     267        typedef typename _Graph::Arc Arc;
     268        typedef typename _Graph::Edge Edge;
     269
     270        void constraints() {
    271271          checkConcept<BaseDigraphComponent, _Graph>();
    272           checkConcept<GraphItem<'u'>, Edge>();
    273           {
    274             Node n;
    275             Edge ue(INVALID);
     272          checkConcept<GraphItem<'u'>, Edge>();
     273          {
     274            Node n;
     275            Edge ue(INVALID);
    276276            Arc e;
    277             n = graph.u(ue);
    278             n = graph.v(ue);
     277            n = graph.u(ue);
     278            n = graph.v(ue);
    279279            e = graph.direct(ue, true);
    280280            e = graph.direct(ue, n);
     
    283283            bool d = graph.direction(e);
    284284            ignore_unused_variable_warning(d);
    285           }     
    286         }
    287      
    288         const _Graph& graph;
     285          }
     286        }
     287
     288        const _Graph& graph;
    289289      };
    290290
     
    292292
    293293    /// \brief An empty idable base digraph class.
    294     /// 
     294    ///
    295295    /// This class provides beside the core digraph features
    296296    /// core id functions for the digraph structure.
     
    305305      typedef typename Base::Arc Arc;
    306306
    307       /// \brief Gives back an unique integer id for the Node. 
    308       ///
    309       /// Gives back an unique integer id for the Node. 
     307      /// \brief Gives back an unique integer id for the Node.
     308      ///
     309      /// Gives back an unique integer id for the Node.
    310310      ///
    311311      int id(const Node&) const { return -1;}
     
    315315      /// Gives back the node by the unique id.
    316316      /// If the digraph does not contain node with the given id
    317       /// then the result of the function is undetermined. 
     317      /// then the result of the function is undetermined.
    318318      Node nodeFromId(int) const { return INVALID;}
    319319
    320       /// \brief Gives back an unique integer id for the Arc. 
    321       ///
    322       /// Gives back an unique integer id for the Arc. 
     320      /// \brief Gives back an unique integer id for the Arc.
     321      ///
     322      /// Gives back an unique integer id for the Arc.
    323323      ///
    324324      int id(const Arc&) const { return -1;}
     
    328328      /// Gives back the arc by the unique id.
    329329      /// If the digraph does not contain arc with the given id
    330       /// then the result of the function is undetermined. 
     330      /// then the result of the function is undetermined.
    331331      Arc arcFromId(int) const { return INVALID;}
    332332
     
    348348      struct Constraints {
    349349
    350         void constraints() {
    351           checkConcept<Base, _Digraph >();
    352           typename _Digraph::Node node;
    353           int nid = digraph.id(node);
    354           nid = digraph.id(node);
    355           node = digraph.nodeFromId(nid);
    356           typename _Digraph::Arc arc;
    357           int eid = digraph.id(arc);
    358           eid = digraph.id(arc);
    359           arc = digraph.arcFromId(eid);
    360 
    361           nid = digraph.maxNodeId();
    362           ignore_unused_variable_warning(nid);
    363           eid = digraph.maxArcId();
    364           ignore_unused_variable_warning(eid);
    365         }
    366 
    367         const _Digraph& digraph;
     350        void constraints() {
     351          checkConcept<Base, _Digraph >();
     352          typename _Digraph::Node node;
     353          int nid = digraph.id(node);
     354          nid = digraph.id(node);
     355          node = digraph.nodeFromId(nid);
     356          typename _Digraph::Arc arc;
     357          int eid = digraph.id(arc);
     358          eid = digraph.id(arc);
     359          arc = digraph.arcFromId(eid);
     360
     361          nid = digraph.maxNodeId();
     362          ignore_unused_variable_warning(nid);
     363          eid = digraph.maxArcId();
     364          ignore_unused_variable_warning(eid);
     365        }
     366
     367        const _Digraph& digraph;
    368368      };
    369369    };
    370370
    371371    /// \brief An empty idable base undirected graph class.
    372     /// 
     372    ///
    373373    /// This class provides beside the core undirected graph features
    374374    /// core id functions for the undirected graph structure.  The
     
    384384      using IDableDigraphComponent<_Base>::id;
    385385
    386       /// \brief Gives back an unique integer id for the Edge. 
    387       ///
    388       /// Gives back an unique integer id for the Edge. 
     386      /// \brief Gives back an unique integer id for the Edge.
     387      ///
     388      /// Gives back an unique integer id for the Edge.
    389389      ///
    390390      int id(const Edge&) const { return -1;}
     
    407407      struct Constraints {
    408408
    409         void constraints() {
    410           checkConcept<Base, _Graph >();
    411           checkConcept<IDableDigraphComponent<Base>, _Graph >();
    412           typename _Graph::Edge edge;
    413           int ueid = graph.id(edge);
    414           ueid = graph.id(edge);
    415           edge = graph.edgeFromId(ueid);
    416           ueid = graph.maxEdgeId();
    417           ignore_unused_variable_warning(ueid);
    418         }
    419 
    420         const _Graph& graph;
     409        void constraints() {
     410          checkConcept<Base, _Graph >();
     411          checkConcept<IDableDigraphComponent<Base>, _Graph >();
     412          typename _Graph::Edge edge;
     413          int ueid = graph.id(edge);
     414          ueid = graph.id(edge);
     415          edge = graph.edgeFromId(ueid);
     416          ueid = graph.maxEdgeId();
     417          ignore_unused_variable_warning(ueid);
     418        }
     419
     420        const _Graph& graph;
    421421      };
    422422    };
     
    451451      /// \brief Assign operator for items.
    452452      ///
    453       /// The items are assignable. 
    454       ///
    455       GraphItemIt& operator=(const GraphItemIt&) { return *this; }     
     453      /// The items are assignable.
     454      ///
     455      GraphItemIt& operator=(const GraphItemIt&) { return *this; }
    456456      /// \brief Next item.
    457       /// 
     457      ///
    458458      /// Assign the iterator to the next item.
    459459      ///
    460460      GraphItemIt& operator++() { return *this; }
    461461      /// \brief Equality operator
    462       /// 
     462      ///
    463463      /// Two iterators are equal if and only if they point to the
    464464      /// same object or both are invalid.
    465465      bool operator==(const GraphItemIt&) const { return true;}
    466466      /// \brief Inequality operator
    467       ///       
     467      ///
    468468      /// \sa operator==(Node n)
    469469      ///
    470470      bool operator!=(const GraphItemIt&) const { return true;}
    471      
     471
    472472      template<typename _GraphItemIt>
    473473      struct Constraints {
    474         void constraints() {
    475           _GraphItemIt it1(g); 
    476           _GraphItemIt it2;
    477 
    478           it2 = ++it1;
    479           ++it2 = it1;
    480           ++(++it1);
    481 
    482           _Item bi = it1;
    483           bi = it2;
    484         }
    485         _Graph& g;
     474        void constraints() {
     475          _GraphItemIt it1(g);
     476          _GraphItemIt it2;
     477
     478          it2 = ++it1;
     479          ++it2 = it1;
     480          ++(++it1);
     481
     482          _Item bi = it1;
     483          bi = it2;
     484        }
     485        _Graph& g;
    486486      };
    487487    };
     
    490490    ///
    491491    /// \note Because InArcIt and OutArcIt may not inherit from the same
    492     /// base class, the _selector is a additional template parameter. For 
    493     /// InArcIt you should instantiate it with character 'i' and for 
     492    /// base class, the _selector is a additional template parameter. For
     493    /// InArcIt you should instantiate it with character 'i' and for
    494494    /// OutArcIt with 'o'.
    495495    template <typename _Graph,
    496               typename _Item = typename _Graph::Arc,
    497               typename _Base = typename _Graph::Node, 
    498               char _selector = '0'>
     496              typename _Item = typename _Graph::Arc,
     497              typename _Base = typename _Graph::Node,
     498              char _selector = '0'>
    499499    class GraphIncIt : public _Item {
    500500    public:
     
    509509      ///
    510510      GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}
    511       /// \brief Sets the iterator to the first arc incoming into or outgoing 
     511      /// \brief Sets the iterator to the first arc incoming into or outgoing
    512512      /// from the node.
    513513      ///
    514       /// Sets the iterator to the first arc incoming into or outgoing 
     514      /// Sets the iterator to the first arc incoming into or outgoing
    515515      /// from the node.
    516516      ///
     
    523523      /// \brief Assign operator for iterators.
    524524      ///
    525       /// The iterators are assignable. 
    526       ///
    527       GraphIncIt& operator=(GraphIncIt const&) { return *this; }     
     525      /// The iterators are assignable.
     526      ///
     527      GraphIncIt& operator=(GraphIncIt const&) { return *this; }
    528528      /// \brief Next item.
    529529      ///
     
    546546      template <typename _GraphIncIt>
    547547      struct Constraints {
    548         void constraints() {
    549           checkConcept<GraphItem<_selector>, _GraphIncIt>();
    550           _GraphIncIt it1(graph, node);
    551           _GraphIncIt it2;
    552 
    553           it2 = ++it1;
    554           ++it2 = it1;
    555           ++(++it1);
    556           _Item e = it1;
    557           e = it2;
    558 
    559         }
    560 
    561         _Item arc;
    562         _Base node;
    563         _Graph graph;
    564         _GraphIncIt it;
     548        void constraints() {
     549          checkConcept<GraphItem<_selector>, _GraphIncIt>();
     550          _GraphIncIt it1(graph, node);
     551          _GraphIncIt it2;
     552
     553          it2 = ++it1;
     554          ++it2 = it1;
     555          ++(++it1);
     556          _Item e = it1;
     557          e = it2;
     558
     559        }
     560
     561        _Item arc;
     562        _Base node;
     563        _Graph graph;
     564        _GraphIncIt it;
    565565      };
    566566    };
     
    576576
    577577    public:
    578    
     578
    579579      typedef _Base Base;
    580580      typedef typename Base::Node Node;
     
    584584
    585585      /// \name Base iteration
    586       /// 
     586      ///
    587587      /// This interface provides functions for iteration on digraph items
    588588      ///
    589       /// @{ 
     589      /// @{
    590590
    591591      /// \brief Gives back the first node in the iterating order.
    592       ///     
     592      ///
    593593      /// Gives back the first node in the iterating order.
    594       ///     
     594      ///
    595595      void first(Node&) const {}
    596596
     
    598598      ///
    599599      /// Gives back the next node in the iterating order.
    600       ///     
     600      ///
    601601      void next(Node&) const {}
    602602
     
    604604      ///
    605605      /// Gives back the first arc in the iterating order.
    606       ///     
     606      ///
    607607      void first(Arc&) const {}
    608608
     
    610610      ///
    611611      /// Gives back the next arc in the iterating order.
    612       ///     
     612      ///
    613613      void next(Arc&) const {}
    614614
     
    618618      ///
    619619      /// Gives back the first of the arcs point to the given node.
    620       ///     
     620      ///
    621621      void firstIn(Arc&, const Node&) const {}
    622622
     
    630630      /// \brief Gives back the first of the arcs start from the
    631631      /// given node.
    632       ///     
     632      ///
    633633      /// Gives back the first of the arcs start from the given node.
    634       ///     
     634      ///
    635635      void firstOut(Arc&, const Node&) const {}
    636636
     
    639639      ///
    640640      /// Gives back the next of the arcs start from the given node.
    641       ///     
     641      ///
    642642      void nextOut(Arc&) const {}
    643643
     
    645645
    646646      /// \name Class based iteration
    647       /// 
     647      ///
    648648      /// This interface provides functions for iteration on digraph items
    649649      ///
     
    700700      /// @}
    701701
    702       template <typename _Digraph> 
    703       struct Constraints {
    704         void constraints() {
    705           checkConcept<Base, _Digraph>();
     702      template <typename _Digraph>
     703      struct Constraints {
     704        void constraints() {
     705          checkConcept<Base, _Digraph>();
    706706
    707707          {
    708             typename _Digraph::Node node(INVALID);     
     708            typename _Digraph::Node node(INVALID);
    709709            typename _Digraph::Arc arc(INVALID);
    710710            {
     
    724724              digraph.nextOut(arc);
    725725            }
    726           }           
     726          }
    727727
    728728          {
     
    731731            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Node>,
    732732              typename _Digraph::NodeIt >();
    733             checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc, 
     733            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
    734734              typename _Digraph::Node, 'i'>, typename _Digraph::InArcIt>();
    735             checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc, 
     735            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
    736736              typename _Digraph::Node, 'o'>, typename _Digraph::OutArcIt>();
    737737
     
    746746          }
    747747        }
    748        
    749         const _Digraph& digraph;
    750        
     748
     749        const _Digraph& digraph;
     750
    751751      };
    752752    };
     
    766766      typedef typename Base::Edge Edge;
    767767
    768    
     768
    769769      typedef IterableGraphComponent Graph;
    770770
    771771      /// \name Base iteration
    772       /// 
     772      ///
    773773      /// This interface provides functions for iteration on graph items
    774       /// @{ 
     774      /// @{
    775775
    776776      using IterableDigraphComponent<_Base>::first;
     
    781781      ///
    782782      /// Gives back the first edge in the iterating order.
    783       ///     
     783      ///
    784784      void first(Edge&) const {}
    785785
     
    788788      ///
    789789      /// Gives back the next edge in the iterating order.
    790       ///     
     790      ///
    791791      void next(Edge&) const {}
    792792
     
    815815
    816816      /// \name Class based iteration
    817       /// 
     817      ///
    818818      /// This interface provides functions for iteration on graph items
    819819      ///
     
    842842      /// @}
    843843
    844       template <typename _Graph> 
    845       struct Constraints {
    846         void constraints() {
    847           checkConcept<IterableDigraphComponent<Base>, _Graph>();
     844      template <typename _Graph>
     845      struct Constraints {
     846        void constraints() {
     847          checkConcept<IterableDigraphComponent<Base>, _Graph>();
    848848
    849849          {
     
    859859              graph.nextInc(edge, dir);
    860860            }
    861            
    862           }     
    863  
     861
     862          }
     863
    864864          {
    865865            checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
    866866              typename _Graph::EdgeIt >();
    867             checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 
     867            checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
    868868              typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
    869            
     869
    870870            typename _Graph::Node n;
    871871            typename _Graph::IncEdgeIt ueit(INVALID);
     
    874874          }
    875875        }
    876        
    877         const _Graph& graph;
    878        
     876
     877        const _Graph& graph;
     878
    879879      };
    880880    };
    881881
    882882    /// \brief An empty alteration notifier digraph class.
    883     /// 
     883    ///
    884884    /// This class provides beside the core digraph features alteration
    885885    /// notifier interface for the digraph structure.  This implements
     
    898898
    899899      /// The node observer registry.
    900       typedef AlterationNotifier<AlterableDigraphComponent, Node> 
     900      typedef AlterationNotifier<AlterableDigraphComponent, Node>
    901901      NodeNotifier;
    902902      /// The arc observer registry.
    903       typedef AlterationNotifier<AlterableDigraphComponent, Arc> 
     903      typedef AlterationNotifier<AlterableDigraphComponent, Arc>
    904904      ArcNotifier;
    905      
     905
    906906      /// \brief Gives back the node alteration notifier.
    907907      ///
    908908      /// Gives back the node alteration notifier.
    909909      NodeNotifier& notifier(Node) const {
    910         return NodeNotifier();
     910        return NodeNotifier();
    911911      }
    912      
     912
    913913      /// \brief Gives back the arc alteration notifier.
    914914      ///
    915915      /// Gives back the arc alteration notifier.
    916916      ArcNotifier& notifier(Arc) const {
    917         return ArcNotifier();
     917        return ArcNotifier();
    918918      }
    919919
    920       template <typename _Digraph> 
    921       struct Constraints {
    922         void constraints() {
    923           checkConcept<Base, _Digraph>();
    924           typename _Digraph::NodeNotifier& nn 
     920      template <typename _Digraph>
     921      struct Constraints {
     922        void constraints() {
     923          checkConcept<Base, _Digraph>();
     924          typename _Digraph::NodeNotifier& nn
    925925            = digraph.notifier(typename _Digraph::Node());
    926926
    927           typename _Digraph::ArcNotifier& en 
     927          typename _Digraph::ArcNotifier& en
    928928            = digraph.notifier(typename _Digraph::Arc());
    929          
     929
    930930          ignore_unused_variable_warning(nn);
    931931          ignore_unused_variable_warning(en);
    932         }
    933        
    934         const _Digraph& digraph;
    935        
    936       };
    937      
     932        }
     933
     934        const _Digraph& digraph;
     935
     936      };
     937
    938938    };
    939939
    940940    /// \brief An empty alteration notifier undirected graph class.
    941     /// 
     941    ///
    942942    /// This class provides beside the core graph features alteration
    943943    /// notifier interface for the graph structure.  This implements
     
    955955
    956956      /// The arc observer registry.
    957       typedef AlterationNotifier<AlterableGraphComponent, Edge> 
     957      typedef AlterationNotifier<AlterableGraphComponent, Edge>
    958958      EdgeNotifier;
    959      
     959
    960960      /// \brief Gives back the arc alteration notifier.
    961961      ///
    962962      /// Gives back the arc alteration notifier.
    963963      EdgeNotifier& notifier(Edge) const {
    964         return EdgeNotifier();
     964        return EdgeNotifier();
    965965      }
    966966
    967       template <typename _Graph> 
    968       struct Constraints {
    969         void constraints() {
    970           checkConcept<AlterableGraphComponent<Base>, _Graph>();
    971           typename _Graph::EdgeNotifier& uen 
     967      template <typename _Graph>
     968      struct Constraints {
     969        void constraints() {
     970          checkConcept<AlterableGraphComponent<Base>, _Graph>();
     971          typename _Graph::EdgeNotifier& uen
    972972            = graph.notifier(typename _Graph::Edge());
    973973          ignore_unused_variable_warning(uen);
    974         }
    975        
    976         const _Graph& graph;
    977        
    978       };
    979      
     974        }
     975
     976        const _Graph& graph;
     977
     978      };
     979
    980980    };
    981981
    982982    /// \brief Class describing the concept of graph maps
    983     /// 
     983    ///
    984984    /// This class describes the common interface of the graph maps
    985985    /// (NodeMap, ArcMap), that is \ref maps-page "maps" which can be used to
     
    10101010      /// Copy Constructor.
    10111011      GraphMap(const GraphMap&) : Parent() {}
    1012      
     1012
    10131013      /// \brief Assign operator.
    10141014      ///
    10151015      /// Assign operator. It does not mofify the underlying graph,
    10161016      /// it just iterates on the current item set and set the  map
    1017       /// with the value returned by the assigned map. 
     1017      /// with the value returned by the assigned map.
    10181018      template <typename CMap>
    1019       GraphMap& operator=(const CMap&) { 
     1019      GraphMap& operator=(const CMap&) {
    10201020        checkConcept<ReadMap<Key, Value>, CMap>();
    10211021        return *this;
     
    10241024      template<typename _Map>
    10251025      struct Constraints {
    1026         void constraints() {
    1027           checkConcept<ReadWriteMap<Key, Value>, _Map >();
    1028           // Construction with a graph parameter
    1029           _Map a(g);
    1030           // Constructor with a graph and a default value parameter
    1031           _Map a2(g,t);
    1032           // Copy constructor.
    1033           _Map b(c);
    1034          
     1026        void constraints() {
     1027          checkConcept<ReadWriteMap<Key, Value>, _Map >();
     1028          // Construction with a graph parameter
     1029          _Map a(g);
     1030          // Constructor with a graph and a default value parameter
     1031          _Map a2(g,t);
     1032          // Copy constructor.
     1033          _Map b(c);
     1034
    10351035          ReadMap<Key, Value> cmap;
    10361036          b = cmap;
    10371037
    1038           ignore_unused_variable_warning(a2);
    1039           ignore_unused_variable_warning(b);
    1040         }
    1041 
    1042         const _Map &c;
    1043         const Graph &g;
    1044         const typename GraphMap::Value &t;
     1038          ignore_unused_variable_warning(a2);
     1039          ignore_unused_variable_warning(b);
     1040        }
     1041
     1042        const _Map &c;
     1043        const Graph &g;
     1044        const typename GraphMap::Value &t;
    10451045      };
    10461046
     
    10711071        typedef GraphMap<MappableDigraphComponent, Node, _Value> Parent;
    10721072
    1073         /// \brief Construct a new map.
    1074         ///
    1075         /// Construct a new map for the digraph.
    1076         explicit NodeMap(const MappableDigraphComponent& digraph)
     1073        /// \brief Construct a new map.
     1074        ///
     1075        /// Construct a new map for the digraph.
     1076        explicit NodeMap(const MappableDigraphComponent& digraph)
    10771077          : Parent(digraph) {}
    10781078
    1079         /// \brief Construct a new map with default value.
    1080         ///
    1081         /// Construct a new map for the digraph and initalise the values.
    1082         NodeMap(const MappableDigraphComponent& digraph, const _Value& value)
     1079        /// \brief Construct a new map with default value.
     1080        ///
     1081        /// Construct a new map for the digraph and initalise the values.
     1082        NodeMap(const MappableDigraphComponent& digraph, const _Value& value)
    10831083          : Parent(digraph, value) {}
    10841084
    1085         /// \brief Copy constructor.
    1086         ///
    1087         /// Copy Constructor.
    1088         NodeMap(const NodeMap& nm) : Parent(nm) {}
    1089 
    1090         /// \brief Assign operator.
    1091         ///
    1092         /// Assign operator.
     1085        /// \brief Copy constructor.
     1086        ///
     1087        /// Copy Constructor.
     1088        NodeMap(const NodeMap& nm) : Parent(nm) {}
     1089
     1090        /// \brief Assign operator.
     1091        ///
     1092        /// Assign operator.
    10931093        template <typename CMap>
    1094         NodeMap& operator=(const CMap&) { 
     1094        NodeMap& operator=(const CMap&) {
    10951095          checkConcept<ReadMap<Node, _Value>, CMap>();
    10961096          return *this;
     
    11081108        typedef GraphMap<MappableDigraphComponent, Arc, _Value> Parent;
    11091109
    1110         /// \brief Construct a new map.
    1111         ///
    1112         /// Construct a new map for the digraph.
    1113         explicit ArcMap(const MappableDigraphComponent& digraph)
     1110        /// \brief Construct a new map.
     1111        ///
     1112        /// Construct a new map for the digraph.
     1113        explicit ArcMap(const MappableDigraphComponent& digraph)
    11141114          : Parent(digraph) {}
    11151115
    1116         /// \brief Construct a new map with default value.
    1117         ///
    1118         /// Construct a new map for the digraph and initalise the values.
    1119         ArcMap(const MappableDigraphComponent& digraph, const _Value& value)
     1116        /// \brief Construct a new map with default value.
     1117        ///
     1118        /// Construct a new map for the digraph and initalise the values.
     1119        ArcMap(const MappableDigraphComponent& digraph, const _Value& value)
    11201120          : Parent(digraph, value) {}
    11211121
    1122         /// \brief Copy constructor.
    1123         ///
    1124         /// Copy Constructor.
    1125         ArcMap(const ArcMap& nm) : Parent(nm) {}
    1126 
    1127         /// \brief Assign operator.
    1128         ///
    1129         /// Assign operator.
     1122        /// \brief Copy constructor.
     1123        ///
     1124        /// Copy Constructor.
     1125        ArcMap(const ArcMap& nm) : Parent(nm) {}
     1126
     1127        /// \brief Assign operator.
     1128        ///
     1129        /// Assign operator.
    11301130        template <typename CMap>
    1131         ArcMap& operator=(const CMap&) { 
     1131        ArcMap& operator=(const CMap&) {
    11321132          checkConcept<ReadMap<Arc, _Value>, CMap>();
    11331133          return *this;
     
    11401140      struct Constraints {
    11411141
    1142         struct Dummy {
    1143           int value;
    1144           Dummy() : value(0) {}
    1145           Dummy(int _v) : value(_v) {}
    1146         };
    1147 
    1148         void constraints() {
    1149           checkConcept<Base, _Digraph>();
    1150           { // int map test
    1151             typedef typename _Digraph::template NodeMap<int> IntNodeMap;
    1152             checkConcept<GraphMap<_Digraph, typename _Digraph::Node, int>,
    1153               IntNodeMap >();
    1154           } { // bool map test
    1155             typedef typename _Digraph::template NodeMap<bool> BoolNodeMap;
    1156             checkConcept<GraphMap<_Digraph, typename _Digraph::Node, bool>,
    1157               BoolNodeMap >();
    1158           } { // Dummy map test
    1159             typedef typename _Digraph::template NodeMap<Dummy> DummyNodeMap;
    1160             checkConcept<GraphMap<_Digraph, typename _Digraph::Node, Dummy>,
    1161               DummyNodeMap >();
    1162           }
    1163 
    1164           { // int map test
    1165             typedef typename _Digraph::template ArcMap<int> IntArcMap;
    1166             checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, int>,
    1167               IntArcMap >();
    1168           } { // bool map test
    1169             typedef typename _Digraph::template ArcMap<bool> BoolArcMap;
    1170             checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, bool>,
    1171               BoolArcMap >();
    1172           } { // Dummy map test
    1173             typedef typename _Digraph::template ArcMap<Dummy> DummyArcMap;
    1174             checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, Dummy>,
    1175               DummyArcMap >();
    1176           }
    1177         }
    1178 
    1179         _Digraph& digraph;
     1142        struct Dummy {
     1143          int value;
     1144          Dummy() : value(0) {}
     1145          Dummy(int _v) : value(_v) {}
     1146        };
     1147
     1148        void constraints() {
     1149          checkConcept<Base, _Digraph>();
     1150          { // int map test
     1151            typedef typename _Digraph::template NodeMap<int> IntNodeMap;
     1152            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, int>,
     1153              IntNodeMap >();
     1154          } { // bool map test
     1155            typedef typename _Digraph::template NodeMap<bool> BoolNodeMap;
     1156            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, bool>,
     1157              BoolNodeMap >();
     1158          } { // Dummy map test
     1159            typedef typename _Digraph::template NodeMap<Dummy> DummyNodeMap;
     1160            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, Dummy>,
     1161              DummyNodeMap >();
     1162          }
     1163
     1164          { // int map test
     1165            typedef typename _Digraph::template ArcMap<int> IntArcMap;
     1166            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, int>,
     1167              IntArcMap >();
     1168          } { // bool map test
     1169            typedef typename _Digraph::template ArcMap<bool> BoolArcMap;
     1170            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, bool>,
     1171              BoolArcMap >();
     1172          } { // Dummy map test
     1173            typedef typename _Digraph::template ArcMap<Dummy> DummyArcMap;
     1174            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, Dummy>,
     1175              DummyArcMap >();
     1176          }
     1177        }
     1178
     1179        _Digraph& digraph;
    11801180      };
    11811181    };
     
    12001200      ///
    12011201      template <typename _Value>
    1202       class EdgeMap : public GraphMap<Graph, Edge, _Value> { 
     1202      class EdgeMap : public GraphMap<Graph, Edge, _Value> {
    12031203      public:
    12041204        typedef GraphMap<MappableGraphComponent, Edge, _Value> Parent;
    12051205
    1206         /// \brief Construct a new map.
    1207         ///
    1208         /// Construct a new map for the graph.
    1209         explicit EdgeMap(const MappableGraphComponent& graph)
     1206        /// \brief Construct a new map.
     1207        ///
     1208        /// Construct a new map for the graph.
     1209        explicit EdgeMap(const MappableGraphComponent& graph)
    12101210          : Parent(graph) {}
    12111211
    1212         /// \brief Construct a new map with default value.
    1213         ///
    1214         /// Construct a new map for the graph and initalise the values.
    1215         EdgeMap(const MappableGraphComponent& graph, const _Value& value)
     1212        /// \brief Construct a new map with default value.
     1213        ///
     1214        /// Construct a new map for the graph and initalise the values.
     1215        EdgeMap(const MappableGraphComponent& graph, const _Value& value)
    12161216          : Parent(graph, value) {}
    12171217
    1218         /// \brief Copy constructor.
    1219         ///
    1220         /// Copy Constructor.
    1221         EdgeMap(const EdgeMap& nm) : Parent(nm) {}
    1222 
    1223         /// \brief Assign operator.
    1224         ///
    1225         /// Assign operator.
     1218        /// \brief Copy constructor.
     1219        ///
     1220        /// Copy Constructor.
     1221        EdgeMap(const EdgeMap& nm) : Parent(nm) {}
     1222
     1223        /// \brief Assign operator.
     1224        ///
     1225        /// Assign operator.
    12261226        template <typename CMap>
    1227         EdgeMap& operator=(const CMap&) { 
     1227        EdgeMap& operator=(const CMap&) {
    12281228          checkConcept<ReadMap<Edge, _Value>, CMap>();
    12291229          return *this;
     
    12361236      struct Constraints {
    12371237
    1238         struct Dummy {
    1239           int value;
    1240           Dummy() : value(0) {}
    1241           Dummy(int _v) : value(_v) {}
    1242         };
    1243 
    1244         void constraints() {
    1245           checkConcept<MappableGraphComponent<Base>, _Graph>();
    1246 
    1247           { // int map test
    1248             typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
    1249             checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
    1250               IntEdgeMap >();
    1251           } { // bool map test
    1252             typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
    1253             checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
    1254               BoolEdgeMap >();
    1255           } { // Dummy map test
    1256             typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
    1257             checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
    1258               DummyEdgeMap >();
    1259           }
    1260         }
    1261 
    1262         _Graph& graph;
     1238        struct Dummy {
     1239          int value;
     1240          Dummy() : value(0) {}
     1241          Dummy(int _v) : value(_v) {}
     1242        };
     1243
     1244        void constraints() {
     1245          checkConcept<MappableGraphComponent<Base>, _Graph>();
     1246
     1247          { // int map test
     1248            typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
     1249            checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
     1250              IntEdgeMap >();
     1251          } { // bool map test
     1252            typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
     1253            checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
     1254              BoolEdgeMap >();
     1255          } { // Dummy map test
     1256            typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
     1257            checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
     1258              DummyEdgeMap >();
     1259          }
     1260        }
     1261
     1262        _Graph& graph;
    12631263      };
    12641264    };
     
    12831283      ///
    12841284      Node addNode() {
    1285         return INVALID;
     1285        return INVALID;
    12861286      }
    1287    
     1287
    12881288      /// \brief Adds a new arc connects the given two nodes.
    12891289      ///
    12901290      /// Adds a new arc connects the the given two nodes.
    12911291      Arc addArc(const Node&, const Node&) {
    1292         return INVALID;
     1292        return INVALID;
    12931293      }
    12941294
    12951295      template <typename _Digraph>
    12961296      struct Constraints {
    1297         void constraints() {
     1297        void constraints() {
    12981298          checkConcept<Base, _Digraph>();
    1299           typename _Digraph::Node node_a, node_b;
    1300           node_a = digraph.addNode();
    1301           node_b = digraph.addNode();
    1302           typename _Digraph::Arc arc;
    1303           arc = digraph.addArc(node_a, node_b);
    1304         }
    1305 
    1306         _Digraph& digraph;
     1299          typename _Digraph::Node node_a, node_b;
     1300          node_a = digraph.addNode();
     1301          node_b = digraph.addNode();
     1302          typename _Digraph::Arc arc;
     1303          arc = digraph.addArc(node_a, node_b);
     1304        }
     1305
     1306        _Digraph& digraph;
    13071307      };
    13081308    };
     
    13281328      ///
    13291329      Node addNode() {
    1330         return INVALID;
     1330        return INVALID;
    13311331      }
    1332    
     1332
    13331333      /// \brief Adds a new arc connects the given two nodes.
    13341334      ///
    13351335      /// Adds a new arc connects the the given two nodes.
    13361336      Edge addArc(const Node&, const Node&) {
    1337         return INVALID;
     1337        return INVALID;
    13381338      }
    13391339
    13401340      template <typename _Graph>
    13411341      struct Constraints {
    1342         void constraints() {
    1343           checkConcept<Base, _Graph>();
    1344           typename _Graph::Node node_a, node_b;
    1345           node_a = graph.addNode();
    1346           node_b = graph.addNode();
    1347           typename _Graph::Edge edge;
    1348           edge = graph.addEdge(node_a, node_b);
    1349         }
    1350 
    1351         _Graph& graph;
     1342        void constraints() {
     1343          checkConcept<Base, _Graph>();
     1344          typename _Graph::Node node_a, node_b;
     1345          node_a = graph.addNode();
     1346          node_b = graph.addNode();
     1347          typename _Graph::Edge edge;
     1348          edge = graph.addEdge(node_a, node_b);
     1349        }
     1350
     1351        _Graph& graph;
    13521352      };
    13531353    };
    13541354
    13551355    /// \brief An empty erasable digraph class.
    1356     /// 
     1356    ///
    13571357    /// This class provides beside the core digraph features core erase
    13581358    /// functions for the digraph structure. The main difference between
     
    13691369      /// \brief Erase a node from the digraph.
    13701370      ///
    1371       /// Erase a node from the digraph. This function should 
     1371      /// Erase a node from the digraph. This function should
    13721372      /// erase all arcs connecting to the node.
    1373       void erase(const Node&) {}   
     1373      void erase(const Node&) {}
    13741374
    13751375      /// \brief Erase an arc from the digraph.
     
    13811381      template <typename _Digraph>
    13821382      struct Constraints {
    1383         void constraints() {
     1383        void constraints() {
    13841384          checkConcept<Base, _Digraph>();
    1385           typename _Digraph::Node node;
    1386           digraph.erase(node);
    1387           typename _Digraph::Arc arc;
    1388           digraph.erase(arc);
    1389         }
    1390 
    1391         _Digraph& digraph;
     1385          typename _Digraph::Node node;
     1386          digraph.erase(node);
     1387          typename _Digraph::Arc arc;
     1388          digraph.erase(arc);
     1389        }
     1390
     1391        _Digraph& digraph;
    13921392      };
    13931393    };
    13941394
    13951395    /// \brief An empty erasable base undirected graph class.
    1396     /// 
     1396    ///
    13971397    /// This class provides beside the core undirected graph features
    13981398    /// core erase functions for the undirceted graph structure. The
     
    14111411      /// Erase a node from the graph. This function should erase
    14121412      /// arcs connecting to the node.
    1413       void erase(const Node&) {}   
     1413      void erase(const Node&) {}
    14141414
    14151415      /// \brief Erase an arc from the graph.
     
    14211421      template <typename _Graph>
    14221422      struct Constraints {
    1423         void constraints() {
     1423        void constraints() {
    14241424          checkConcept<Base, _Graph>();
    1425           typename _Graph::Node node;
    1426           graph.erase(node);
    1427           typename _Graph::Edge edge;
    1428           graph.erase(edge);
    1429         }
    1430 
    1431         _Graph& graph;
     1425          typename _Graph::Node node;
     1426          graph.erase(node);
     1427          typename _Graph::Edge edge;
     1428          graph.erase(edge);
     1429        }
     1430
     1431        _Graph& graph;
    14321432      };
    14331433    };
     
    14491449      /// Erase all nodes and arcs from the digraph.
    14501450      ///
    1451       void clear() {}   
     1451      void clear() {}
    14521452
    14531453      template <typename _Digraph>
    14541454      struct Constraints {
    1455         void constraints() {
     1455        void constraints() {
    14561456          checkConcept<Base, _Digraph>();
    1457           digraph.clear();
    1458         }
    1459 
    1460         _Digraph digraph;
     1457          digraph.clear();
     1458        }
     1459
     1460        _Digraph digraph;
    14611461      };
    14621462    };
     
    14761476      template <typename _Graph>
    14771477      struct Constraints {
    1478         void constraints() {
     1478        void constraints() {
    14791479          checkConcept<ClearableGraphComponent<Base>, _Graph>();
    1480         }
    1481 
    1482         _Graph graph;
     1480        }
     1481
     1482        _Graph graph;
    14831483      };
    14841484    };
  • lemon/concepts/heap.h

    r203 r209  
    1 /* -*- C++ -*-
    2  *
    3  * This file is a part of LEMON, a generic C++ optimization library
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
     
    5353      /// the user.
    5454      ///
    55       /// The \c ItemIntMap must be initialized in such a way, that it 
     55      /// The \c ItemIntMap must be initialized in such a way, that it
    5656      /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item.
    5757      enum State {
    58         IN_HEAP = 0,
    59         PRE_HEAP = -1,
    60         POST_HEAP = -2
     58        IN_HEAP = 0,
     59        PRE_HEAP = -1,
     60        POST_HEAP = -2
    6161      };
    62      
     62
    6363      /// \brief The constructor.
    6464      ///
     
    8686
    8787      /// \brief Inserts an item into the heap with the given priority.
    88       ///   
    89       /// Inserts the given item into the heap with the given priority. 
     88      ///
     89      /// Inserts the given item into the heap with the given priority.
    9090      /// \param i The item to insert.
    9191      /// \param p The priority of the item.
     
    113113      ///
    114114      /// Removes the given item from the heap if it is already stored.
    115       /// \param i The item to delete. 
     115      /// \param i The item to delete.
    116116      void erase(const Item &i) {}
    117117
    118118      /// \brief The priority of an item.
    119119      ///
    120       /// Returns the priority of the given item. 
     120      /// Returns the priority of the given item.
    121121      /// \pre \c i must be in the heap.
    122122      /// \param i The item.
     
    134134      /// \param p The priority.
    135135      void set(const Item &i, const Prio &p) {}
    136      
     136
    137137      /// \brief Decreases the priority of an item to the given value.
    138138      ///
     
    175175      struct Constraints {
    176176      public:
    177         void constraints() {
    178           typedef typename _Heap::Item OwnItem;
    179           typedef typename _Heap::Prio OwnPrio;
    180           typedef typename _Heap::State OwnState;
    181 
    182           Item item;
    183           Prio prio;
    184           item=Item();
    185           prio=Prio();
    186           ignore_unused_variable_warning(item);
    187           ignore_unused_variable_warning(prio);
    188 
    189           OwnItem own_item;
    190           OwnPrio own_prio;
    191           OwnState own_state;
    192           own_item=Item();
    193           own_prio=Prio();
    194           ignore_unused_variable_warning(own_item);
    195           ignore_unused_variable_warning(own_prio);
    196           ignore_unused_variable_warning(own_state);
    197 
    198           _Heap heap1(map);
    199           _Heap heap2 = heap1;
    200           ignore_unused_variable_warning(heap1);
    201           ignore_unused_variable_warning(heap2);
    202          
    203           int s = heap.size();
    204           ignore_unused_variable_warning(s);
    205           bool e = heap.empty();
    206           ignore_unused_variable_warning(e);
    207 
    208           prio = heap.prio();
    209           item = heap.top();
    210           prio = heap[item];
    211           own_prio = heap.prio();
    212           own_item = heap.top();
    213           own_prio = heap[own_item];
    214 
    215           heap.push(item, prio);
    216           heap.push(own_item, own_prio);
    217           heap.pop();
    218 
    219           heap.set(item, prio);
    220           heap.decrease(item, prio);
    221           heap.increase(item, prio);
    222           heap.set(own_item, own_prio);
    223           heap.decrease(own_item, own_prio);
    224           heap.increase(own_item, own_prio);
    225 
    226           heap.erase(item);
    227           heap.erase(own_item);
    228           heap.clear();
    229 
    230           own_state = heap.state(own_item);
    231           heap.state(own_item, own_state);
    232 
    233           own_state = _Heap::PRE_HEAP;
    234           own_state = _Heap::IN_HEAP;
    235           own_state = _Heap::POST_HEAP;
    236         }
    237 
    238         _Heap& heap;
    239         ItemIntMap& map;
     177        void constraints() {
     178          typedef typename _Heap::Item OwnItem;
     179          typedef typename _Heap::Prio OwnPrio;
     180          typedef typename _Heap::State OwnState;
     181
     182          Item item;
     183          Prio prio;
     184          item=Item();
     185          prio=Prio();
     186          ignore_unused_variable_warning(item);
     187          ignore_unused_variable_warning(prio);
     188
     189          OwnItem own_item;
     190          OwnPrio own_prio;
     191          OwnState own_state;
     192          own_item=Item();
     193          own_prio=Prio();
     194          ignore_unused_variable_warning(own_item);
     195          ignore_unused_variable_warning(own_prio);
     196          ignore_unused_variable_warning(own_state);
     197
     198          _Heap heap1(map);
     199          _Heap heap2 = heap1;
     200          ignore_unused_variable_warning(heap1);
     201          ignore_unused_variable_warning(heap2);
     202
     203          int s = heap.size();
     204          ignore_unused_variable_warning(s);
     205          bool e = heap.empty();
     206          ignore_unused_variable_warning(e);
     207
     208          prio = heap.prio();
     209          item = heap.top();
     210          prio = heap[item];
     211          own_prio = heap.prio();
     212          own_item = heap.top();
     213          own_prio = heap[own_item];
     214
     215          heap.push(item, prio);
     216          heap.push(own_item, own_prio);
     217          heap.pop();
     218
     219          heap.set(item, prio);
     220          heap.decrease(item, prio);
     221          heap.increase(item, prio);
     222          heap.set(own_item, own_prio);
     223          heap.decrease(own_item, own_prio);
     224          heap.increase(own_item, own_prio);
     225
     226          heap.erase(item);
     227          heap.erase(own_item);
     228          heap.clear();
     229
     230          own_state = heap.state(own_item);
     231          heap.state(own_item, own_state);
     232
     233          own_state = _Heap::PRE_HEAP;
     234          own_state = _Heap::IN_HEAP;
     235          own_state = _Heap::POST_HEAP;
     236        }
     237
     238        _Heap& heap;
     239        ItemIntMap& map;
    240240      };
    241241    };
  • lemon/concepts/maps.h

    r114 r209  
    1 /* -*- C++ -*-
    2  *
    3  * This file is a part of LEMON, a generic C++ optimization library
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
     
    4848
    4949      /// Returns the value associated with the given key.
    50       Value operator[](const Key &) const { 
     50      Value operator[](const Key &) const {
    5151        return *static_cast<Value *>(0);
    5252      }
     
    5454      template<typename _ReadMap>
    5555      struct Constraints {
    56         void constraints() {
    57           Value val = m[key];
    58           val = m[key];
    59           typename _ReadMap::Value own_val = m[own_key];
    60           own_val = m[own_key];
    61 
    62           ignore_unused_variable_warning(key);
    63           ignore_unused_variable_warning(val);
    64           ignore_unused_variable_warning(own_key);
    65           ignore_unused_variable_warning(own_val);
    66         }
    67         const Key& key;
    68         const typename _ReadMap::Key& own_key;
    69         const _ReadMap& m;
     56        void constraints() {
     57          Value val = m[key];
     58          val = m[key];
     59          typename _ReadMap::Value own_val = m[own_key];
     60          own_val = m[own_key];
     61
     62          ignore_unused_variable_warning(key);
     63          ignore_unused_variable_warning(val);
     64          ignore_unused_variable_warning(own_key);
     65          ignore_unused_variable_warning(own_val);
     66        }
     67        const Key& key;
     68        const typename _ReadMap::Key& own_key;
     69        const _ReadMap& m;
    7070      };
    7171
     
    9494      template <typename _WriteMap>
    9595      struct Constraints {
    96         void constraints() {
    97           m.set(key, val);
    98           m.set(own_key, own_val);
    99 
    100           ignore_unused_variable_warning(key);
    101           ignore_unused_variable_warning(val);
    102           ignore_unused_variable_warning(own_key);
    103           ignore_unused_variable_warning(own_val);
    104         }
    105         const Key& key;
    106         const Value& val;
    107         const typename _WriteMap::Key& own_key;
    108         const typename _WriteMap::Value& own_val;
    109         _WriteMap& m;
     96        void constraints() {
     97          m.set(key, val);
     98          m.set(own_key, own_val);
     99
     100          ignore_unused_variable_warning(key);
     101          ignore_unused_variable_warning(val);
     102          ignore_unused_variable_warning(own_key);
     103          ignore_unused_variable_warning(own_val);
     104        }
     105        const Key& key;
     106        const Value& val;
     107        const typename _WriteMap::Key& own_key;
     108        const typename _WriteMap::Value& own_val;
     109        _WriteMap& m;
    110110      };
    111111    };
     
    117117    template<typename K, typename T>
    118118    class ReadWriteMap : public ReadMap<K,T>,
    119                         public WriteMap<K,T>
     119                        public WriteMap<K,T>
    120120    {
    121121    public:
     
    126126
    127127      /// Returns the value associated with the given key.
    128       Value operator[](const Key &) const { 
     128      Value operator[](const Key &) const {
    129129        return *static_cast<Value *>(0);
    130130      }
     
    135135      template<typename _ReadWriteMap>
    136136      struct Constraints {
    137         void constraints() {
    138           checkConcept<ReadMap<K, T>, _ReadWriteMap >();
    139           checkConcept<WriteMap<K, T>, _ReadWriteMap >();
    140         }
     137        void constraints() {
     138          checkConcept<ReadMap<K, T>, _ReadWriteMap >();
     139          checkConcept<WriteMap<K, T>, _ReadWriteMap >();
     140        }
    141141      };
    142142    };
     
    165165
    166166      /// Returns a reference to the value associated with the given key.
    167       Reference operator[](const Key &) { 
     167      Reference operator[](const Key &) {
    168168        return *static_cast<Value *>(0);
    169169      }
     
    179179      template<typename _ReferenceMap>
    180180      struct Constraints {
    181         void constraints() {
    182           checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
    183           ref = m[key];
    184           m[key] = val;
    185           m[key] = ref;
    186           m[key] = cref;
    187           own_ref = m[own_key];
    188           m[own_key] = own_val;
    189           m[own_key] = own_ref;
    190           m[own_key] = own_cref;
    191           m[key] = m[own_key];
    192           m[own_key] = m[key];
    193         }
    194         const Key& key;
    195         Value& val;
    196         Reference ref;
    197         ConstReference cref;
    198         const typename _ReferenceMap::Key& own_key;
    199         typename _ReferenceMap::Value& own_val;
    200         typename _ReferenceMap::Reference own_ref;
    201         typename _ReferenceMap::ConstReference own_cref;
    202         _ReferenceMap& m;
     181        void constraints() {
     182          checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
     183          ref = m[key];
     184          m[key] = val;
     185          m[key] = ref;
     186          m[key] = cref;
     187          own_ref = m[own_key];
     188          m[own_key] = own_val;
     189          m[own_key] = own_ref;
     190          m[own_key] = own_cref;
     191          m[key] = m[own_key];
     192          m[own_key] = m[key];
     193        }
     194        const Key& key;
     195        Value& val;
     196        Reference ref;
     197        ConstReference cref;
     198        const typename _ReferenceMap::Key& own_key;
     199        typename _ReferenceMap::Value& own_val;
     200        typename _ReferenceMap::Reference own_ref;
     201        typename _ReferenceMap::ConstReference own_cref;
     202        _ReferenceMap& m;
    203203      };
    204204    };
  • lemon/concepts/path.h

    r157 r209  
    1 /* -*- C++ -*-
    2  *
    3  * This file is a part of LEMON, a generic C++ optimization library
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
     
    4040    ///
    4141    /// A skeleton structure for representing directed paths in a
    42     /// digraph. 
     42    /// digraph.
    4343    /// \tparam _Digraph The digraph type in which the path is.
    4444    ///
     
    8484      class ArcIt {
    8585      public:
    86         /// Default constructor
    87         ArcIt() {}
    88         /// Invalid constructor
    89         ArcIt(Invalid) {}
    90         /// Constructor for first arc
    91         ArcIt(const Path &) {}
     86        /// Default constructor
     87        ArcIt() {}
     88        /// Invalid constructor
     89        ArcIt(Invalid) {}
     90        /// Constructor for first arc
     91        ArcIt(const Path &) {}
    9292
    9393        /// Conversion to Arc
    94         operator Arc() const { return INVALID; }
    95 
    96         /// Next arc
    97         ArcIt& operator++() {return *this;}
    98 
    99         /// Comparison operator
    100         bool operator==(const ArcIt&) const {return true;}
    101         /// Comparison operator
    102         bool operator!=(const ArcIt&) const {return true;}
    103         /// Comparison operator
    104         bool operator<(const ArcIt&) const {return false;}
     94        operator Arc() const { return INVALID; }
     95
     96        /// Next arc
     97        ArcIt& operator++() {return *this;}
     98
     99        /// Comparison operator
     100        bool operator==(const ArcIt&) const {return true;}
     101        /// Comparison operator
     102        bool operator!=(const ArcIt&) const {return true;}
     103         /// Comparison operator
     104         bool operator<(const ArcIt&) const {return false;}
    105105
    106106      };
     
    138138
    139139    namespace _path_bits {
    140      
     140
    141141      template <typename _Digraph, typename _Path, typename RevPathTag = void>
    142142      struct PathDumperConstraints {
     
    163163      template <typename _Digraph, typename _Path>
    164164      struct PathDumperConstraints<
    165         _Digraph, _Path, 
     165        _Digraph, _Path,
    166166        typename enable_if<typename _Path::RevPathTag, void>::type
    167167      > {
     
    185185        _Path& p;
    186186      };
    187    
     187
    188188    }
    189189
     
    210210    /// The paths can be constructed from any path type by a
    211211    /// template constructor or a template assignment operator.
    212     /// 
     212    ///
    213213    template <typename _Digraph>
    214214    class PathDumper {
     
    239239      class ArcIt {
    240240      public:
    241         /// Default constructor
    242         ArcIt() {}
    243         /// Invalid constructor
    244         ArcIt(Invalid) {}
    245         /// Constructor for first arc
    246         ArcIt(const PathDumper&) {}
     241        /// Default constructor
     242        ArcIt() {}
     243        /// Invalid constructor
     244        ArcIt(Invalid) {}
     245        /// Constructor for first arc
     246        ArcIt(const PathDumper&) {}
    247247
    248248        /// Conversion to Arc
    249         operator Arc() const { return INVALID; }
    250 
    251         /// Next arc
    252         ArcIt& operator++() {return *this;}
    253 
    254         /// Comparison operator
    255         bool operator==(const ArcIt&) const {return true;}
    256         /// Comparison operator
    257         bool operator!=(const ArcIt&) const {return true;}
    258         /// Comparison operator
    259         bool operator<(const ArcIt&) const {return false;}
     249        operator Arc() const { return INVALID; }
     250
     251        /// Next arc
     252        ArcIt& operator++() {return *this;}
     253
     254        /// Comparison operator
     255        bool operator==(const ArcIt&) const {return true;}
     256        /// Comparison operator
     257        bool operator!=(const ArcIt&) const {return true;}
     258         /// Comparison operator
     259         bool operator<(const ArcIt&) const {return false;}
    260260
    261261      };
     
    267267      class RevArcIt {
    268268      public:
    269         /// Default constructor
    270         RevArcIt() {}
    271         /// Invalid constructor
    272         RevArcIt(Invalid) {}
    273         /// Constructor for first arc
    274         RevArcIt(const PathDumper &) {}
     269        /// Default constructor
     270        RevArcIt() {}
     271        /// Invalid constructor
     272        RevArcIt(Invalid) {}
     273        /// Constructor for first arc
     274        RevArcIt(const PathDumper &) {}
    275275
    276276        /// Conversion to Arc
    277         operator Arc() const { return INVALID; }
    278 
    279         /// Next arc
    280         RevArcIt& operator++() {return *this;}
    281 
    282         /// Comparison operator
    283         bool operator==(const RevArcIt&) const {return true;}
    284         /// Comparison operator
    285         bool operator!=(const RevArcIt&) const {return true;}
    286         /// Comparison operator
    287         bool operator<(const RevArcIt&) const {return false;}
     277        operator Arc() const { return INVALID; }
     278
     279        /// Next arc
     280        RevArcIt& operator++() {return *this;}
     281
     282        /// Comparison operator
     283        bool operator==(const RevArcIt&) const {return true;}
     284        /// Comparison operator
     285        bool operator!=(const RevArcIt&) const {return true;}
     286         /// Comparison operator
     287         bool operator<(const RevArcIt&) const {return false;}
    288288
    289289      };
Note: See TracChangeset for help on using the changeset viewer.