COIN-OR::LEMON - Graph Library

Changeset 983:8b2d4e5d96e4 in lemon-1.2


Ignore:
Timestamp:
08/07/13 06:55:05 (6 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
971:a26b90a17c81 (diff), 982:3e711ee55d31 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge #294 to branches >=1.2

Files:
50 edited

Legend:

Unmodified
Added
Removed
  • lemon/concepts/digraph.h

    r877 r983  
    313313        /// Sets the iterator to the first arc of the given digraph.
    314314        ///
    315         explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
     315        explicit ArcIt(const Digraph& g) { ::lemon::ignore_unused_variable_warning(g); }
    316316        /// Sets the iterator to the given arc.
    317317
  • lemon/concepts/digraph.h

    r982 r983  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3636    /// \brief Class describing the concept of directed graphs.
    3737    ///
    38     /// This class describes the \ref concept "concept" of the
    39     /// immutable directed digraphs.
     38    /// This class describes the common interface of all directed
     39    /// graphs (digraphs).
    4040    ///
    41     /// Note that actual digraph implementation like @ref ListDigraph or
    42     /// @ref SmartDigraph may have several additional functionality.
     41    /// Like all concept classes, it only provides an interface
     42    /// without any sensible implementation. So any general algorithm for
     43    /// directed graphs should compile with this class, but it will not
     44    /// run properly, of course.
     45    /// An actual digraph implementation like \ref ListDigraph or
     46    /// \ref SmartDigraph may have additional functionality.
    4347    ///
    44     /// \sa concept
     48    /// \sa Graph
    4549    class Digraph {
    4650    private:
    47       ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
    48 
    49       ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
    50       ///
    51       Digraph(const Digraph &) {};
    52       ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
    53       ///\e not allowed. Use DigraphCopy() instead.
    54 
    55       ///Assignment of \ref Digraph "Digraph"s to another ones are
    56       ///\e not allowed.  Use DigraphCopy() instead.
    57 
     51      /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
     52      Digraph(const Digraph &) {}
     53      /// \brief Assignment of a digraph to another one is \e not allowed.
     54      /// Use DigraphCopy instead.
    5855      void operator=(const Digraph &) {}
     56
    5957    public:
    60       ///\e
    61 
    62       /// Defalult constructor.
    63 
    64       /// Defalult constructor.
    65       ///
     58      /// Default constructor.
    6659      Digraph() { }
    67       /// Class for identifying a node of the digraph
     60
     61      /// The node type of the digraph
    6862
    6963      /// This class identifies a node of the digraph. It also serves
    7064      /// as a base class of the node iterators,
    71       /// thus they will convert to this type.
     65      /// thus they convert to this type.
    7266      class Node {
    7367      public:
    7468        /// Default constructor
    7569
    76         /// @warning The default constructor sets the iterator
    77         /// to an undefined value.
     70        /// Default constructor.
     71        /// \warning It sets the object to an undefined value.
    7872        Node() { }
    7973        /// Copy constructor.
     
    8377        Node(const Node&) { }
    8478
    85         /// Invalid constructor \& conversion.
    86 
    87         /// This constructor initializes the iterator to be invalid.
     79        /// %Invalid constructor \& conversion.
     80
     81        /// Initializes the object to be invalid.
    8882        /// \sa Invalid for more details.
    8983        Node(Invalid) { }
    9084        /// Equality operator
    9185
     86        /// Equality operator.
     87        ///
    9288        /// Two iterators are equal if and only if they point to the
    93         /// same object or both are invalid.
     89        /// same object or both are \c INVALID.
    9490        bool operator==(Node) const { return true; }
    9591
    9692        /// Inequality operator
    9793
    98         /// \sa operator==(Node n)
    99         ///
     94        /// Inequality operator.
    10095        bool operator!=(Node) const { return true; }
    10196
    10297        /// Artificial ordering operator.
    10398
    104         /// To allow the use of digraph descriptors as key type in std::map or
    105         /// similar associative container we require this.
    106         ///
    107         /// \note This operator only have to define some strict ordering of
    108         /// the items; this order has nothing to do with the iteration
    109         /// ordering of the items.
     99        /// Artificial ordering operator.
     100        ///
     101        /// \note This operator only has to define some strict ordering of
     102        /// the nodes; this order has nothing to do with the iteration
     103        /// ordering of the nodes.
    110104        bool operator<(Node) const { return false; }
    111 
    112       };
    113 
    114       /// This iterator goes through each node.
    115 
    116       /// This iterator goes through each node.
    117       /// Its usage is quite simple, for example you can count the number
    118       /// of nodes in digraph \c g of type \c Digraph like this:
     105      };
     106
     107      /// Iterator class for the nodes.
     108
     109      /// This iterator goes through each node of the digraph.
     110      /// Its usage is quite simple, for example, you can count the number
     111      /// of nodes in a digraph \c g of type \c %Digraph like this:
    119112      ///\code
    120113      /// int count=0;
     
    125118        /// Default constructor
    126119
    127         /// @warning The default constructor sets the iterator
    128         /// to an undefined value.
     120        /// Default constructor.
     121        /// \warning It sets the iterator to an undefined value.
    129122        NodeIt() { }
    130123        /// Copy constructor.
     
    133126        ///
    134127        NodeIt(const NodeIt& n) : Node(n) { }
    135         /// Invalid constructor \& conversion.
    136 
    137         /// Initialize the iterator to be invalid.
     128        /// %Invalid constructor \& conversion.
     129
     130        /// Initializes the iterator to be invalid.
    138131        /// \sa Invalid for more details.
    139132        NodeIt(Invalid) { }
    140133        /// Sets the iterator to the first node.
    141134
    142         /// Sets the iterator to the first node of \c g.
    143         ///
    144         NodeIt(const Digraph&) { }
    145         /// Node -> NodeIt conversion.
    146 
    147         /// Sets the iterator to the node of \c the digraph pointed by
    148         /// the trivial iterator.
    149         /// This feature necessitates that each time we
    150         /// iterate the arc-set, the iteration order is the same.
     135        /// Sets the iterator to the first node of the given digraph.
     136        ///
     137        explicit NodeIt(const Digraph&) { }
     138        /// Sets the iterator to the given node.
     139
     140        /// Sets the iterator to the given node of the given digraph.
     141        ///
    151142        NodeIt(const Digraph&, const Node&) { }
    152143        /// Next node.
     
    158149
    159150
    160       /// Class for identifying an arc of the digraph
     151      /// The arc type of the digraph
    161152
    162153      /// This class identifies an arc of the digraph. It also serves
     
    167158        /// Default constructor
    168159
    169         /// @warning The default constructor sets the iterator
    170         /// to an undefined value.
     160        /// Default constructor.
     161        /// \warning It sets the object to an undefined value.
    171162        Arc() { }
    172163        /// Copy constructor.
     
    175166        ///
    176167        Arc(const Arc&) { }
    177         /// Initialize the iterator to be invalid.
    178 
    179         /// Initialize the iterator to be invalid.
    180         ///
     168        /// %Invalid constructor \& conversion.
     169
     170        /// Initializes the object to be invalid.
     171        /// \sa Invalid for more details.
    181172        Arc(Invalid) { }
    182173        /// Equality operator
    183174
     175        /// Equality operator.
     176        ///
    184177        /// Two iterators are equal if and only if they point to the
    185         /// same object or both are invalid.
     178        /// same object or both are \c INVALID.
    186179        bool operator==(Arc) const { return true; }
    187180        /// Inequality operator
    188181
    189         /// \sa operator==(Arc n)
    190         ///
     182        /// Inequality operator.
    191183        bool operator!=(Arc) const { return true; }
    192184
    193185        /// Artificial ordering operator.
    194186
    195         /// To allow the use of digraph descriptors as key type in std::map or
    196         /// similar associative container we require this.
    197         ///
    198         /// \note This operator only have to define some strict ordering of
    199         /// the items; this order has nothing to do with the iteration
    200         /// ordering of the items.
     187        /// Artificial ordering operator.
     188        ///
     189        /// \note This operator only has to define some strict ordering of
     190        /// the arcs; this order has nothing to do with the iteration
     191        /// ordering of the arcs.
    201192        bool operator<(Arc) const { return false; }
    202193      };
    203194
    204       /// This iterator goes trough the outgoing arcs of a node.
     195      /// Iterator class for the outgoing arcs of a node.
    205196
    206197      /// This iterator goes trough the \e outgoing arcs of a certain node
    207198      /// of a digraph.
    208       /// Its usage is quite simple, for example you can count the number
     199      /// Its usage is quite simple, for example, you can count the number
    209200      /// of outgoing arcs of a node \c n
    210       /// in digraph \c g of type \c Digraph as follows.
     201      /// in a digraph \c g of type \c %Digraph as follows.
    211202      ///\code
    212203      /// int count=0;
    213       /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
     204      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
    214205      ///\endcode
    215 
    216206      class OutArcIt : public Arc {
    217207      public:
    218208        /// Default constructor
    219209
    220         /// @warning The default constructor sets the iterator
    221         /// to an undefined value.
     210        /// Default constructor.
     211        /// \warning It sets the iterator to an undefined value.
    222212        OutArcIt() { }
    223213        /// Copy constructor.
     
    226216        ///
    227217        OutArcIt(const OutArcIt& e) : Arc(e) { }
    228         /// Initialize the iterator to be invalid.
    229 
    230         /// Initialize the iterator to be invalid.
    231         ///
     218        /// %Invalid constructor \& conversion.
     219
     220        /// Initializes the iterator to be invalid.
     221        /// \sa Invalid for more details.
    232222        OutArcIt(Invalid) { }
    233         /// This constructor sets the iterator to the first outgoing arc.
    234 
    235         /// This constructor sets the iterator to the first outgoing arc of
    236         /// the node.
     223        /// Sets the iterator to the first outgoing arc.
     224
     225        /// Sets the iterator to the first outgoing arc of the given node.
     226        ///
    237227        OutArcIt(const Digraph&, const Node&) { }
    238         /// Arc -> OutArcIt conversion
    239 
    240         /// Sets the iterator to the value of the trivial iterator.
    241         /// This feature necessitates that each time we
    242         /// iterate the arc-set, the iteration order is the same.
     228        /// Sets the iterator to the given arc.
     229
     230        /// Sets the iterator to the given arc of the given digraph.
     231        ///
    243232        OutArcIt(const Digraph&, const Arc&) { }
    244         ///Next outgoing arc
     233        /// Next outgoing arc
    245234
    246235        /// Assign the iterator to the next
     
    249238      };
    250239
    251       /// This iterator goes trough the incoming arcs of a node.
     240      /// Iterator class for the incoming arcs of a node.
    252241
    253242      /// This iterator goes trough the \e incoming arcs of a certain node
    254243      /// of a digraph.
    255       /// Its usage is quite simple, for example you can count the number
    256       /// of outgoing arcs of a node \c n
    257       /// in digraph \c g of type \c Digraph as follows.
     244      /// Its usage is quite simple, for example, you can count the number
     245      /// of incoming arcs of a node \c n
     246      /// in a digraph \c g of type \c %Digraph as follows.
    258247      ///\code
    259248      /// int count=0;
    260       /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
     249      /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
    261250      ///\endcode
    262 
    263251      class InArcIt : public Arc {
    264252      public:
    265253        /// Default constructor
    266254
    267         /// @warning The default constructor sets the iterator
    268         /// to an undefined value.
     255        /// Default constructor.
     256        /// \warning It sets the iterator to an undefined value.
    269257        InArcIt() { }
    270258        /// Copy constructor.
     
    273261        ///
    274262        InArcIt(const InArcIt& e) : Arc(e) { }
    275         /// Initialize the iterator to be invalid.
    276 
    277         /// Initialize the iterator to be invalid.
    278         ///
     263        /// %Invalid constructor \& conversion.
     264
     265        /// Initializes the iterator to be invalid.
     266        /// \sa Invalid for more details.
    279267        InArcIt(Invalid) { }
    280         /// This constructor sets the iterator to first incoming arc.
    281 
    282         /// This constructor set the iterator to the first incoming arc of
    283         /// the node.
     268        /// Sets the iterator to the first incoming arc.
     269
     270        /// Sets the iterator to the first incoming arc of the given node.
     271        ///
    284272        InArcIt(const Digraph&, const Node&) { }
    285         /// Arc -> InArcIt conversion
    286 
    287         /// Sets the iterator to the value of the trivial iterator \c e.
    288         /// This feature necessitates that each time we
    289         /// iterate the arc-set, the iteration order is the same.
     273        /// Sets the iterator to the given arc.
     274
     275        /// Sets the iterator to the given arc of the given digraph.
     276        ///
    290277        InArcIt(const Digraph&, const Arc&) { }
    291278        /// Next incoming arc
    292279
    293         /// Assign the iterator to the next inarc of the corresponding node.
    294         ///
     280        /// Assign the iterator to the next
     281        /// incoming arc of the corresponding node.
    295282        InArcIt& operator++() { return *this; }
    296283      };
    297       /// This iterator goes through each arc.
    298 
    299       /// This iterator goes through each arc of a digraph.
    300       /// Its usage is quite simple, for example you can count the number
    301       /// of arcs in a digraph \c g of type \c Digraph as follows:
     284
     285      /// Iterator class for the arcs.
     286
     287      /// This iterator goes through each arc of the digraph.
     288      /// Its usage is quite simple, for example, you can count the number
     289      /// of arcs in a digraph \c g of type \c %Digraph as follows:
    302290      ///\code
    303291      /// int count=0;
    304       /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
     292      /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
    305293      ///\endcode
    306294      class ArcIt : public Arc {
     
    308296        /// Default constructor
    309297
    310         /// @warning The default constructor sets the iterator
    311         /// to an undefined value.
     298        /// Default constructor.
     299        /// \warning It sets the iterator to an undefined value.
    312300        ArcIt() { }
    313301        /// Copy constructor.
     
    316304        ///
    317305        ArcIt(const ArcIt& e) : Arc(e) { }
    318         /// Initialize the iterator to be invalid.
    319 
    320         /// Initialize the iterator to be invalid.
    321         ///
     306        /// %Invalid constructor \& conversion.
     307
     308        /// Initializes the iterator to be invalid.
     309        /// \sa Invalid for more details.
    322310        ArcIt(Invalid) { }
    323         /// This constructor sets the iterator to the first arc.
    324 
    325         /// This constructor sets the iterator to the first arc of \c g.
    326         ///@param g the digraph
    327         ArcIt(const Digraph& g) { ::lemon::ignore_unused_variable_warning(g); }
    328         /// Arc -> ArcIt conversion
    329 
    330         /// Sets the iterator to the value of the trivial iterator \c e.
    331         /// This feature necessitates that each time we
    332         /// iterate the arc-set, the iteration order is the same.
     311        /// Sets the iterator to the first arc.
     312
     313        /// Sets the iterator to the first arc of the given digraph.
     314        ///
     315        explicit ArcIt(const Digraph& g) { ::lemon::ignore_unused_variable_warning(g); }
     316        /// Sets the iterator to the given arc.
     317
     318        /// Sets the iterator to the given arc of the given digraph.
     319        ///
    333320        ArcIt(const Digraph&, const Arc&) { }
    334         ///Next arc
     321        /// Next arc
    335322
    336323        /// Assign the iterator to the next arc.
     324        ///
    337325        ArcIt& operator++() { return *this; }
    338326      };
    339       ///Gives back the target node of an arc.
    340 
    341       ///Gives back the target node of an arc.
    342       ///
     327
     328      /// \brief The source node of the arc.
     329      ///
     330      /// Returns the source node of the given arc.
     331      Node source(Arc) const { return INVALID; }
     332
     333      /// \brief The target node of the arc.
     334      ///
     335      /// Returns the target node of the given arc.
    343336      Node target(Arc) const { return INVALID; }
    344       ///Gives back the source node of an arc.
    345 
    346       ///Gives back the source node of an arc.
    347       ///
    348       Node source(Arc) const { return INVALID; }
    349 
    350       /// \brief Returns the ID of the node.
     337
     338      /// \brief The ID of the node.
     339      ///
     340      /// Returns the ID of the given node.
    351341      int id(Node) const { return -1; }
    352342
    353       /// \brief Returns the ID of the arc.
     343      /// \brief The ID of the arc.
     344      ///
     345      /// Returns the ID of the given arc.
    354346      int id(Arc) const { return -1; }
    355347
    356       /// \brief Returns the node with the given ID.
    357       ///
    358       /// \pre The argument should be a valid node ID in the graph.
     348      /// \brief The node with the given ID.
     349      ///
     350      /// Returns the node with the given ID.
     351      /// \pre The argument should be a valid node ID in the digraph.
    359352      Node nodeFromId(int) const { return INVALID; }
    360353
    361       /// \brief Returns the arc with the given ID.
    362       ///
    363       /// \pre The argument should be a valid arc ID in the graph.
     354      /// \brief The arc with the given ID.
     355      ///
     356      /// Returns the arc with the given ID.
     357      /// \pre The argument should be a valid arc ID in the digraph.
    364358      Arc arcFromId(int) const { return INVALID; }
    365359
    366       /// \brief Returns an upper bound on the node IDs.
     360      /// \brief An upper bound on the node IDs.
     361      ///
     362      /// Returns an upper bound on the node IDs.
    367363      int maxNodeId() const { return -1; }
    368364
    369       /// \brief Returns an upper bound on the arc IDs.
     365      /// \brief An upper bound on the arc IDs.
     366      ///
     367      /// Returns an upper bound on the arc IDs.
    370368      int maxArcId() const { return -1; }
    371369
     
    393391      int maxId(Arc) const { return -1; }
    394392
     393      /// \brief The opposite node on the arc.
     394      ///
     395      /// Returns the opposite node on the given arc.
     396      Node oppositeNode(Node, Arc) const { return INVALID; }
     397
    395398      /// \brief The base node of the iterator.
    396399      ///
    397       /// Gives back the base node of the iterator.
    398       /// It is always the target of the pointed arc.
    399       Node baseNode(const InArcIt&) const { return INVALID; }
     400      /// Returns the base node of the given outgoing arc iterator
     401      /// (i.e. the source node of the corresponding arc).
     402      Node baseNode(OutArcIt) const { return INVALID; }
    400403
    401404      /// \brief The running node of the iterator.
    402405      ///
    403       /// Gives back the running node of the iterator.
    404       /// It is always the source of the pointed arc.
    405       Node runningNode(const InArcIt&) const { return INVALID; }
     406      /// Returns the running node of the given outgoing arc iterator
     407      /// (i.e. the target node of the corresponding arc).
     408      Node runningNode(OutArcIt) const { return INVALID; }
    406409
    407410      /// \brief The base node of the iterator.
    408411      ///
    409       /// Gives back the base node of the iterator.
    410       /// It is always the source of the pointed arc.
    411       Node baseNode(const OutArcIt&) const { return INVALID; }
     412      /// Returns the base node of the given incomming arc iterator
     413      /// (i.e. the target node of the corresponding arc).
     414      Node baseNode(InArcIt) const { return INVALID; }
    412415
    413416      /// \brief The running node of the iterator.
    414417      ///
    415       /// Gives back the running node of the iterator.
    416       /// It is always the target of the pointed arc.
    417       Node runningNode(const OutArcIt&) const { return INVALID; }
    418 
    419       /// \brief The opposite node on the given arc.
    420       ///
    421       /// Gives back the opposite node on the given arc.
    422       Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
    423 
    424       /// \brief Reference map of the nodes to type \c T.
    425       ///
    426       /// Reference map of the nodes to type \c T.
     418      /// Returns the running node of the given incomming arc iterator
     419      /// (i.e. the source node of the corresponding arc).
     420      Node runningNode(InArcIt) const { return INVALID; }
     421
     422      /// \brief Standard graph map type for the nodes.
     423      ///
     424      /// Standard graph map type for the nodes.
     425      /// It conforms to the ReferenceMap concept.
    427426      template<class T>
    428427      class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
    429428      public:
    430429
    431         ///\e
    432         NodeMap(const Digraph&) { }
    433         ///\e
     430        /// Constructor
     431        explicit NodeMap(const Digraph&) { }
     432        /// Constructor with given initial value
    434433        NodeMap(const Digraph&, T) { }
    435434
    436435      private:
    437436        ///Copy constructor
    438         NodeMap(const NodeMap& nm) : 
     437        NodeMap(const NodeMap& nm) :
    439438          ReferenceMap<Node, T, T&, const T&>(nm) { }
    440439        ///Assignment operator
     
    446445      };
    447446
    448       /// \brief Reference map of the arcs to type \c T.
    449       ///
    450       /// Reference map of the arcs to type \c T.
     447      /// \brief Standard graph map type for the arcs.
     448      ///
     449      /// Standard graph map type for the arcs.
     450      /// It conforms to the ReferenceMap concept.
    451451      template<class T>
    452452      class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
    453453      public:
    454454
    455         ///\e
    456         ArcMap(const Digraph&) { }
    457         ///\e
     455        /// Constructor
     456        explicit ArcMap(const Digraph&) { }
     457        /// Constructor with given initial value
    458458        ArcMap(const Digraph&, T) { }
     459
    459460      private:
    460461        ///Copy constructor
  • lemon/concepts/graph.h

    r877 r983  
    397397        /// Sets the iterator to the first arc of the given graph.
    398398        ///
    399         explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
     399        explicit ArcIt(const Graph &g) { ::lemon::ignore_unused_variable_warning(g); }
    400400        /// Sets the iterator to the given arc.
    401401
     
    443443        ///
    444444        OutArcIt(const Graph& n, const Node& g) {
    445           ignore_unused_variable_warning(n);
    446           ignore_unused_variable_warning(g);
     445          ::lemon::ignore_unused_variable_warning(n);
     446          ::lemon::ignore_unused_variable_warning(g);
    447447        }
    448448        /// Sets the iterator to the given arc.
     
    491491        ///
    492492        InArcIt(const Graph& g, const Node& n) {
    493           ignore_unused_variable_warning(n);
    494           ignore_unused_variable_warning(g);
     493          ::lemon::ignore_unused_variable_warning(n);
     494          ::lemon::ignore_unused_variable_warning(g);
    495495        }
    496496        /// Sets the iterator to the given arc.
  • lemon/concepts/graph.h

    r982 r983  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    1919///\ingroup graph_concepts
    2020///\file
    21 ///\brief The concept of Undirected Graphs.
     21///\brief The concept of undirected graphs.
    2222
    2323#ifndef LEMON_CONCEPTS_GRAPH_H
     
    2525
    2626#include <lemon/concepts/graph_components.h>
     27#include <lemon/concepts/maps.h>
     28#include <lemon/concept_check.h>
    2729#include <lemon/core.h>
    2830
     
    3234    /// \ingroup graph_concepts
    3335    ///
    34     /// \brief Class describing the concept of Undirected Graphs.
     36    /// \brief Class describing the concept of undirected graphs.
    3537    ///
    36     /// This class describes the common interface of all Undirected
    37     /// Graphs.
     38    /// This class describes the common interface of all undirected
     39    /// graphs.
    3840    ///
    39     /// As all concept describing classes it provides only interface
    40     /// without any sensible implementation. So any algorithm for
    41     /// undirected graph should compile with this class, but it will not
     41    /// Like all concept classes, it only provides an interface
     42    /// without any sensible implementation. So any general algorithm for
     43    /// undirected graphs should compile with this class, but it will not
    4244    /// run properly, of course.
     45    /// An actual graph implementation like \ref ListGraph or
     46    /// \ref SmartGraph may have additional functionality.
    4347    ///
    44     /// The LEMON undirected graphs also fulfill the concept of
    45     /// directed graphs (\ref lemon::concepts::Digraph "Digraph
    46     /// Concept"). Each edges can be seen as two opposite
    47     /// directed arc and consequently the undirected graph can be
    48     /// seen as the direceted graph of these directed arcs. The
    49     /// Graph has the Edge inner class for the edges and
    50     /// the Arc type for the directed arcs. The Arc type is
    51     /// convertible to Edge or inherited from it so from a directed
    52     /// arc we can get the represented edge.
     48    /// The undirected graphs also fulfill the concept of \ref Digraph
     49    /// "directed graphs", since each edge can also be regarded as two
     50    /// oppositely directed arcs.
     51    /// Undirected graphs provide an Edge type for the undirected edges and
     52    /// an Arc type for the directed arcs. The Arc type is convertible to
     53    /// Edge or inherited from it, i.e. the corresponding edge can be
     54    /// obtained from an arc.
     55    /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt
     56    /// and ArcMap classes can be used for the arcs (just like in digraphs).
     57    /// Both InArcIt and OutArcIt iterates on the same edges but with
     58    /// opposite direction. IncEdgeIt also iterates on the same edges
     59    /// as OutArcIt and InArcIt, but it is not convertible to Arc,
     60    /// only to Edge.
    5361    ///
    54     /// In the sense of the LEMON each edge has a default
    55     /// direction (it should be in every computer implementation,
    56     /// because the order of edge's nodes defines an
    57     /// orientation). With the default orientation we can define that
    58     /// the directed arc is forward or backward directed. With the \c
    59     /// direction() and \c direct() function we can get the direction
    60     /// of the directed arc and we can direct an edge.
     62    /// In LEMON, each undirected edge has an inherent orientation.
     63    /// Thus it can defined if an arc is forward or backward oriented in
     64    /// an undirected graph with respect to this default oriantation of
     65    /// the represented edge.
     66    /// With the direction() and direct() functions the direction
     67    /// of an arc can be obtained and set, respectively.
    6168    ///
    62     /// The EdgeIt is an iterator for the edges. We can use
    63     /// the EdgeMap to map values for the edges. The InArcIt and
    64     /// OutArcIt iterates on the same edges but with opposite
    65     /// direction. The IncEdgeIt iterates also on the same edges
    66     /// as the OutArcIt and InArcIt but it is not convertible to Arc just
    67     /// to Edge.
     69    /// Only nodes and edges can be added to or removed from an undirected
     70    /// graph and the corresponding arcs are added or removed automatically.
     71    ///
     72    /// \sa Digraph
    6873    class Graph {
     74    private:
     75      /// Graphs are \e not copy constructible. Use DigraphCopy instead.
     76      Graph(const Graph&) {}
     77      /// \brief Assignment of a graph to another one is \e not allowed.
     78      /// Use DigraphCopy instead.
     79      void operator=(const Graph&) {}
     80
    6981    public:
    70       /// \brief The undirected graph should be tagged by the
    71       /// UndirectedTag.
    72       ///
    73       /// The undirected graph should be tagged by the UndirectedTag. This
    74       /// tag helps the enable_if technics to make compile time
     82      /// Default constructor.
     83      Graph() {}
     84
     85      /// \brief Undirected graphs should be tagged with \c UndirectedTag.
     86      ///
     87      /// Undirected graphs should be tagged with \c UndirectedTag.
     88      ///
     89      /// This tag helps the \c enable_if technics to make compile time
    7590      /// specializations for undirected graphs.
    7691      typedef True UndirectedTag;
    7792
    78       /// \brief The base type of node iterators,
    79       /// or in other words, the trivial node iterator.
    80       ///
    81       /// This is the base type of each node iterator,
    82       /// thus each kind of node iterator converts to this.
    83       /// More precisely each kind of node iterator should be inherited
    84       /// from the trivial node iterator.
     93      /// The node type of the graph
     94
     95      /// This class identifies a node of the graph. It also serves
     96      /// as a base class of the node iterators,
     97      /// thus they convert to this type.
    8598      class Node {
    8699      public:
    87100        /// Default constructor
    88101
    89         /// @warning The default constructor sets the iterator
    90         /// to an undefined value.
     102        /// Default constructor.
     103        /// \warning It sets the object to an undefined value.
    91104        Node() { }
    92105        /// Copy constructor.
     
    96109        Node(const Node&) { }
    97110
    98         /// Invalid constructor \& conversion.
    99 
    100         /// This constructor initializes the iterator to be invalid.
     111        /// %Invalid constructor \& conversion.
     112
     113        /// Initializes the object to be invalid.
    101114        /// \sa Invalid for more details.
    102115        Node(Invalid) { }
    103116        /// Equality operator
    104117
     118        /// Equality operator.
     119        ///
    105120        /// Two iterators are equal if and only if they point to the
    106         /// same object or both are invalid.
     121        /// same object or both are \c INVALID.
    107122        bool operator==(Node) const { return true; }
    108123
    109124        /// Inequality operator
    110125
    111         /// \sa operator==(Node n)
    112         ///
     126        /// Inequality operator.
    113127        bool operator!=(Node) const { return true; }
    114128
    115129        /// Artificial ordering operator.
    116130
    117         /// To allow the use of graph descriptors as key type in std::map or
    118         /// similar associative container we require this.
    119         ///
    120         /// \note This operator only have to define some strict ordering of
     131        /// Artificial ordering operator.
     132        ///
     133        /// \note This operator only has to define some strict ordering of
    121134        /// the items; this order has nothing to do with the iteration
    122135        /// ordering of the items.
     
    125138      };
    126139
    127       /// This iterator goes through each node.
    128 
    129       /// This iterator goes through each node.
    130       /// Its usage is quite simple, for example you can count the number
    131       /// of nodes in graph \c g of type \c Graph like this:
     140      /// Iterator class for the nodes.
     141
     142      /// This iterator goes through each node of the graph.
     143      /// Its usage is quite simple, for example, you can count the number
     144      /// of nodes in a graph \c g of type \c %Graph like this:
    132145      ///\code
    133146      /// int count=0;
     
    138151        /// Default constructor
    139152
    140         /// @warning The default constructor sets the iterator
    141         /// to an undefined value.
     153        /// Default constructor.
     154        /// \warning It sets the iterator to an undefined value.
    142155        NodeIt() { }
    143156        /// Copy constructor.
     
    146159        ///
    147160        NodeIt(const NodeIt& n) : Node(n) { }
    148         /// Invalid constructor \& conversion.
    149 
    150         /// Initialize the iterator to be invalid.
     161        /// %Invalid constructor \& conversion.
     162
     163        /// Initializes the iterator to be invalid.
    151164        /// \sa Invalid for more details.
    152165        NodeIt(Invalid) { }
    153166        /// Sets the iterator to the first node.
    154167
    155         /// Sets the iterator to the first node of \c g.
    156         ///
    157         NodeIt(const Graph&) { }
    158         /// Node -> NodeIt conversion.
    159 
    160         /// Sets the iterator to the node of \c the graph pointed by
    161         /// the trivial iterator.
    162         /// This feature necessitates that each time we
    163         /// iterate the arc-set, the iteration order is the same.
     168        /// Sets the iterator to the first node of the given digraph.
     169        ///
     170        explicit NodeIt(const Graph&) { }
     171        /// Sets the iterator to the given node.
     172
     173        /// Sets the iterator to the given node of the given digraph.
     174        ///
    164175        NodeIt(const Graph&, const Node&) { }
    165176        /// Next node.
     
    171182
    172183
    173       /// The base type of the edge iterators.
    174 
    175       /// The base type of the edge iterators.
    176       ///
     184      /// The edge type of the graph
     185
     186      /// This class identifies an edge of the graph. It also serves
     187      /// as a base class of the edge iterators,
     188      /// thus they will convert to this type.
    177189      class Edge {
    178190      public:
    179191        /// Default constructor
    180192
    181         /// @warning The default constructor sets the iterator
    182         /// to an undefined value.
     193        /// Default constructor.
     194        /// \warning It sets the object to an undefined value.
    183195        Edge() { }
    184196        /// Copy constructor.
     
    187199        ///
    188200        Edge(const Edge&) { }
    189         /// Initialize the iterator to be invalid.
    190 
    191         /// Initialize the iterator to be invalid.
    192         ///
     201        /// %Invalid constructor \& conversion.
     202
     203        /// Initializes the object to be invalid.
     204        /// \sa Invalid for more details.
    193205        Edge(Invalid) { }
    194206        /// Equality operator
    195207
     208        /// Equality operator.
     209        ///
    196210        /// Two iterators are equal if and only if they point to the
    197         /// same object or both are invalid.
     211        /// same object or both are \c INVALID.
    198212        bool operator==(Edge) const { return true; }
    199213        /// Inequality operator
    200214
    201         /// \sa operator==(Edge n)
    202         ///
     215        /// Inequality operator.
    203216        bool operator!=(Edge) const { return true; }
    204217
    205218        /// Artificial ordering operator.
    206219
    207         /// To allow the use of graph descriptors as key type in std::map or
    208         /// similar associative container we require this.
    209         ///
    210         /// \note This operator only have to define some strict ordering of
    211         /// the items; this order has nothing to do with the iteration
    212         /// ordering of the items.
     220        /// Artificial ordering operator.
     221        ///
     222        /// \note This operator only has to define some strict ordering of
     223        /// the edges; this order has nothing to do with the iteration
     224        /// ordering of the edges.
    213225        bool operator<(Edge) const { return false; }
    214226      };
    215227
    216       /// This iterator goes through each edge.
    217 
    218       /// This iterator goes through each edge of a graph.
    219       /// Its usage is quite simple, for example you can count the number
    220       /// of edges in a graph \c g of type \c Graph as follows:
     228      /// Iterator class for the edges.
     229
     230      /// This iterator goes through each edge of the graph.
     231      /// Its usage is quite simple, for example, you can count the number
     232      /// of edges in a graph \c g of type \c %Graph as follows:
    221233      ///\code
    222234      /// int count=0;
     
    227239        /// Default constructor
    228240
    229         /// @warning The default constructor sets the iterator
    230         /// to an undefined value.
     241        /// Default constructor.
     242        /// \warning It sets the iterator to an undefined value.
    231243        EdgeIt() { }
    232244        /// Copy constructor.
     
    235247        ///
    236248        EdgeIt(const EdgeIt& e) : Edge(e) { }
    237         /// Initialize the iterator to be invalid.
    238 
    239         /// Initialize the iterator to be invalid.
    240         ///
     249        /// %Invalid constructor \& conversion.
     250
     251        /// Initializes the iterator to be invalid.
     252        /// \sa Invalid for more details.
    241253        EdgeIt(Invalid) { }
    242         /// This constructor sets the iterator to the first edge.
    243 
    244         /// This constructor sets the iterator to the first edge.
    245         EdgeIt(const Graph&) { }
    246         /// Edge -> EdgeIt conversion
    247 
    248         /// Sets the iterator to the value of the trivial iterator.
    249         /// This feature necessitates that each time we
    250         /// iterate the edge-set, the iteration order is the
    251         /// same.
     254        /// Sets the iterator to the first edge.
     255
     256        /// Sets the iterator to the first edge of the given graph.
     257        ///
     258        explicit EdgeIt(const Graph&) { }
     259        /// Sets the iterator to the given edge.
     260
     261        /// Sets the iterator to the given edge of the given graph.
     262        ///
    252263        EdgeIt(const Graph&, const Edge&) { }
    253264        /// Next edge
    254265
    255266        /// Assign the iterator to the next edge.
     267        ///
    256268        EdgeIt& operator++() { return *this; }
    257269      };
    258270
    259       /// \brief This iterator goes trough the incident undirected
    260       /// arcs of a node.
    261       ///
    262       /// This iterator goes trough the incident edges
    263       /// of a certain node of a graph. You should assume that the
    264       /// loop arcs will be iterated twice.
    265       ///
    266       /// Its usage is quite simple, for example you can compute the
    267       /// degree (i.e. count the number of incident arcs of a node \c n
    268       /// in graph \c g of type \c Graph as follows.
     271      /// Iterator class for the incident edges of a node.
     272
     273      /// This iterator goes trough the incident undirected edges
     274      /// of a certain node of a graph.
     275      /// Its usage is quite simple, for example, you can compute the
     276      /// degree (i.e. the number of incident edges) of a node \c n
     277      /// in a graph \c g of type \c %Graph as follows.
    269278      ///
    270279      ///\code
     
    272281      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
    273282      ///\endcode
     283      ///
     284      /// \warning Loop edges will be iterated twice.
    274285      class IncEdgeIt : public Edge {
    275286      public:
    276287        /// Default constructor
    277288
    278         /// @warning The default constructor sets the iterator
    279         /// to an undefined value.
     289        /// Default constructor.
     290        /// \warning It sets the iterator to an undefined value.
    280291        IncEdgeIt() { }
    281292        /// Copy constructor.
     
    284295        ///
    285296        IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
    286         /// Initialize the iterator to be invalid.
    287 
    288         /// Initialize the iterator to be invalid.
    289         ///
     297        /// %Invalid constructor \& conversion.
     298
     299        /// Initializes the iterator to be invalid.
     300        /// \sa Invalid for more details.
    290301        IncEdgeIt(Invalid) { }
    291         /// This constructor sets the iterator to first incident arc.
    292 
    293         /// This constructor set the iterator to the first incident arc of
    294         /// the node.
     302        /// Sets the iterator to the first incident edge.
     303
     304        /// Sets the iterator to the first incident edge of the given node.
     305        ///
    295306        IncEdgeIt(const Graph&, const Node&) { }
    296         /// Edge -> IncEdgeIt conversion
    297 
    298         /// Sets the iterator to the value of the trivial iterator \c e.
    299         /// This feature necessitates that each time we
    300         /// iterate the arc-set, the iteration order is the same.
     307        /// Sets the iterator to the given edge.
     308
     309        /// Sets the iterator to the given edge of the given graph.
     310        ///
    301311        IncEdgeIt(const Graph&, const Edge&) { }
    302         /// Next incident arc
    303 
    304         /// Assign the iterator to the next incident arc
     312        /// Next incident edge
     313
     314        /// Assign the iterator to the next incident edge
    305315        /// of the corresponding node.
    306316        IncEdgeIt& operator++() { return *this; }
    307317      };
    308318
    309       /// The directed arc type.
    310 
    311       /// The directed arc type. It can be converted to the
    312       /// edge or it should be inherited from the undirected
    313       /// edge.
     319      /// The arc type of the graph
     320
     321      /// This class identifies a directed arc of the graph. It also serves
     322      /// as a base class of the arc iterators,
     323      /// thus they will convert to this type.
    314324      class Arc {
    315325      public:
    316326        /// Default constructor
    317327
    318         /// @warning The default constructor sets the iterator
    319         /// to an undefined value.
     328        /// Default constructor.
     329        /// \warning It sets the object to an undefined value.
    320330        Arc() { }
    321331        /// Copy constructor.
     
    324334        ///
    325335        Arc(const Arc&) { }
    326         /// Initialize the iterator to be invalid.
    327 
    328         /// Initialize the iterator to be invalid.
    329         ///
     336        /// %Invalid constructor \& conversion.
     337
     338        /// Initializes the object to be invalid.
     339        /// \sa Invalid for more details.
    330340        Arc(Invalid) { }
    331341        /// Equality operator
    332342
     343        /// Equality operator.
     344        ///
    333345        /// Two iterators are equal if and only if they point to the
    334         /// same object or both are invalid.
     346        /// same object or both are \c INVALID.
    335347        bool operator==(Arc) const { return true; }
    336348        /// Inequality operator
    337349
    338         /// \sa operator==(Arc n)
    339         ///
     350        /// Inequality operator.
    340351        bool operator!=(Arc) const { return true; }
    341352
    342353        /// Artificial ordering operator.
    343354
    344         /// To allow the use of graph descriptors as key type in std::map or
    345         /// similar associative container we require this.
    346         ///
    347         /// \note This operator only have to define some strict ordering of
    348         /// the items; this order has nothing to do with the iteration
    349         /// ordering of the items.
     355        /// Artificial ordering operator.
     356        ///
     357        /// \note This operator only has to define some strict ordering of
     358        /// the arcs; this order has nothing to do with the iteration
     359        /// ordering of the arcs.
    350360        bool operator<(Arc) const { return false; }
    351361
    352         /// Converison to Edge
     362        /// Converison to \c Edge
     363
     364        /// Converison to \c Edge.
     365        ///
    353366        operator Edge() const { return Edge(); }
    354367      };
    355       /// This iterator goes through each directed arc.
    356 
    357       /// This iterator goes through each arc of a graph.
    358       /// Its usage is quite simple, for example you can count the number
    359       /// of arcs in a graph \c g of type \c Graph as follows:
     368
     369      /// Iterator class for the arcs.
     370
     371      /// This iterator goes through each directed arc of the graph.
     372      /// Its usage is quite simple, for example, you can count the number
     373      /// of arcs in a graph \c g of type \c %Graph as follows:
    360374      ///\code
    361375      /// int count=0;
    362       /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
     376      /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;
    363377      ///\endcode
    364378      class ArcIt : public Arc {
     
    366380        /// Default constructor
    367381
    368         /// @warning The default constructor sets the iterator
    369         /// to an undefined value.
     382        /// Default constructor.
     383        /// \warning It sets the iterator to an undefined value.
    370384        ArcIt() { }
    371385        /// Copy constructor.
     
    374388        ///
    375389        ArcIt(const ArcIt& e) : Arc(e) { }
    376         /// Initialize the iterator to be invalid.
    377 
    378         /// Initialize the iterator to be invalid.
    379         ///
     390        /// %Invalid constructor \& conversion.
     391
     392        /// Initializes the iterator to be invalid.
     393        /// \sa Invalid for more details.
    380394        ArcIt(Invalid) { }
    381         /// This constructor sets the iterator to the first arc.
    382 
    383         /// This constructor sets the iterator to the first arc of \c g.
    384         ///@param g the graph
    385         ArcIt(const Graph &g) { ::lemon::ignore_unused_variable_warning(g); }
    386         /// Arc -> ArcIt conversion
    387 
    388         /// Sets the iterator to the value of the trivial iterator \c e.
    389         /// This feature necessitates that each time we
    390         /// iterate the arc-set, the iteration order is the same.
     395        /// Sets the iterator to the first arc.
     396
     397        /// Sets the iterator to the first arc of the given graph.
     398        ///
     399        explicit ArcIt(const Graph &g) { ::lemon::ignore_unused_variable_warning(g); }
     400        /// Sets the iterator to the given arc.
     401
     402        /// Sets the iterator to the given arc of the given graph.
     403        ///
    391404        ArcIt(const Graph&, const Arc&) { }
    392         ///Next arc
     405        /// Next arc
    393406
    394407        /// Assign the iterator to the next arc.
     408        ///
    395409        ArcIt& operator++() { return *this; }
    396410      };
    397411
    398       /// This iterator goes trough the outgoing directed arcs of a node.
    399 
    400       /// This iterator goes trough the \e outgoing arcs of a certain node
    401       /// of a graph.
    402       /// Its usage is quite simple, for example you can count the number
     412      /// Iterator class for the outgoing arcs of a node.
     413
     414      /// This iterator goes trough the \e outgoing directed arcs of a
     415      /// certain node of a graph.
     416      /// Its usage is quite simple, for example, you can count the number
    403417      /// of outgoing arcs of a node \c n
    404       /// in graph \c g of type \c Graph as follows.
     418      /// in a graph \c g of type \c %Graph as follows.
    405419      ///\code
    406420      /// int count=0;
    407       /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
     421      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
    408422      ///\endcode
    409 
    410423      class OutArcIt : public Arc {
    411424      public:
    412425        /// Default constructor
    413426
    414         /// @warning The default constructor sets the iterator
    415         /// to an undefined value.
     427        /// Default constructor.
     428        /// \warning It sets the iterator to an undefined value.
    416429        OutArcIt() { }
    417430        /// Copy constructor.
     
    420433        ///
    421434        OutArcIt(const OutArcIt& e) : Arc(e) { }
    422         /// Initialize the iterator to be invalid.
    423 
    424         /// Initialize the iterator to be invalid.
    425         ///
     435        /// %Invalid constructor \& conversion.
     436
     437        /// Initializes the iterator to be invalid.
     438        /// \sa Invalid for more details.
    426439        OutArcIt(Invalid) { }
    427         /// This constructor sets the iterator to the first outgoing arc.
    428 
    429         /// This constructor sets the iterator to the first outgoing arc of
    430         /// the node.
    431         ///@param n the node
    432         ///@param g the graph
     440        /// Sets the iterator to the first outgoing arc.
     441
     442        /// Sets the iterator to the first outgoing arc of the given node.
     443        ///
    433444        OutArcIt(const Graph& n, const Node& g) {
    434445          ::lemon::ignore_unused_variable_warning(n);
    435446          ::lemon::ignore_unused_variable_warning(g);
    436447        }
    437         /// Arc -> OutArcIt conversion
    438 
    439         /// Sets the iterator to the value of the trivial iterator.
    440         /// This feature necessitates that each time we
    441         /// iterate the arc-set, the iteration order is the same.
     448        /// Sets the iterator to the given arc.
     449
     450        /// Sets the iterator to the given arc of the given graph.
     451        ///
    442452        OutArcIt(const Graph&, const Arc&) { }
    443         ///Next outgoing arc
     453        /// Next outgoing arc
    444454
    445455        /// Assign the iterator to the next
     
    448458      };
    449459
    450       /// This iterator goes trough the incoming directed arcs of a node.
    451 
    452       /// This iterator goes trough the \e incoming arcs of a certain node
    453       /// of a graph.
    454       /// Its usage is quite simple, for example you can count the number
    455       /// of outgoing arcs of a node \c n
    456       /// in graph \c g of type \c Graph as follows.
     460      /// Iterator class for the incoming arcs of a node.
     461
     462      /// This iterator goes trough the \e incoming directed arcs of a
     463      /// certain node of a graph.
     464      /// Its usage is quite simple, for example, you can count the number
     465      /// of incoming arcs of a node \c n
     466      /// in a graph \c g of type \c %Graph as follows.
    457467      ///\code
    458468      /// int count=0;
    459       /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
     469      /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
    460470      ///\endcode
    461 
    462471      class InArcIt : public Arc {
    463472      public:
    464473        /// Default constructor
    465474
    466         /// @warning The default constructor sets the iterator
    467         /// to an undefined value.
     475        /// Default constructor.
     476        /// \warning It sets the iterator to an undefined value.
    468477        InArcIt() { }
    469478        /// Copy constructor.
     
    472481        ///
    473482        InArcIt(const InArcIt& e) : Arc(e) { }
    474         /// Initialize the iterator to be invalid.
    475 
    476         /// Initialize the iterator to be invalid.
    477         ///
     483        /// %Invalid constructor \& conversion.
     484
     485        /// Initializes the iterator to be invalid.
     486        /// \sa Invalid for more details.
    478487        InArcIt(Invalid) { }
    479         /// This constructor sets the iterator to first incoming arc.
    480 
    481         /// This constructor set the iterator to the first incoming arc of
    482         /// the node.
    483         ///@param n the node
    484         ///@param g the graph
     488        /// Sets the iterator to the first incoming arc.
     489
     490        /// Sets the iterator to the first incoming arc of the given node.
     491        ///
    485492        InArcIt(const Graph& g, const Node& n) {
    486493          ::lemon::ignore_unused_variable_warning(n);
    487494          ::lemon::ignore_unused_variable_warning(g);
    488495        }
    489         /// Arc -> InArcIt conversion
    490 
    491         /// Sets the iterator to the value of the trivial iterator \c e.
    492         /// This feature necessitates that each time we
    493         /// iterate the arc-set, the iteration order is the same.
     496        /// Sets the iterator to the given arc.
     497
     498        /// Sets the iterator to the given arc of the given graph.
     499        ///
    494500        InArcIt(const Graph&, const Arc&) { }
    495501        /// Next incoming arc
    496502
    497         /// Assign the iterator to the next inarc of the corresponding node.
    498         ///
     503        /// Assign the iterator to the next
     504        /// incoming arc of the corresponding node.
    499505        InArcIt& operator++() { return *this; }
    500506      };
    501507
    502       /// \brief Reference map of the nodes to type \c T.
    503       ///
    504       /// Reference map of the nodes to type \c T.
     508      /// \brief Standard graph map type for the nodes.
     509      ///
     510      /// Standard graph map type for the nodes.
     511      /// It conforms to the ReferenceMap concept.
    505512      template<class T>
    506513      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
     
    508515      public:
    509516
    510         ///\e
    511         NodeMap(const Graph&) { }
    512         ///\e
     517        /// Constructor
     518        explicit NodeMap(const Graph&) { }
     519        /// Constructor with given initial value
    513520        NodeMap(const Graph&, T) { }
    514521
     
    525532      };
    526533
    527       /// \brief Reference map of the arcs to type \c T.
    528       ///
    529       /// Reference map of the arcs to type \c T.
     534      /// \brief Standard graph map type for the arcs.
     535      ///
     536      /// Standard graph map type for the arcs.
     537      /// It conforms to the ReferenceMap concept.
    530538      template<class T>
    531539      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
     
    533541      public:
    534542
    535         ///\e
    536         ArcMap(const Graph&) { }
    537         ///\e
     543        /// Constructor
     544        explicit ArcMap(const Graph&) { }
     545        /// Constructor with given initial value
    538546        ArcMap(const Graph&, T) { }
     547
    539548      private:
    540549        ///Copy constructor
     
    549558      };
    550559
    551       /// Reference map of the edges to type \c T.
    552 
    553       /// Reference map of the edges to type \c T.
     560      /// \brief Standard graph map type for the edges.
     561      ///
     562      /// Standard graph map type for the edges.
     563      /// It conforms to the ReferenceMap concept.
    554564      template<class T>
    555565      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
     
    557567      public:
    558568
    559         ///\e
    560         EdgeMap(const Graph&) { }
    561         ///\e
     569        /// Constructor
     570        explicit EdgeMap(const Graph&) { }
     571        /// Constructor with given initial value
    562572        EdgeMap(const Graph&, T) { }
     573
    563574      private:
    564575        ///Copy constructor
     
    573584      };
    574585
    575       /// \brief Direct the given edge.
    576       ///
    577       /// Direct the given edge. The returned arc source
    578       /// will be the given node.
    579       Arc direct(const Edge&, const Node&) const {
    580         return INVALID;
    581       }
    582 
    583       /// \brief Direct the given edge.
    584       ///
    585       /// Direct the given edge. The returned arc
    586       /// represents the given edge and the direction comes
    587       /// from the bool parameter. The source of the edge and
    588       /// the directed arc is the same when the given bool is true.
    589       Arc direct(const Edge&, bool) const {
    590         return INVALID;
    591       }
    592 
    593       /// \brief Returns true if the arc has default orientation.
    594       ///
    595       /// Returns whether the given directed arc is same orientation as
    596       /// the corresponding edge's default orientation.
    597       bool direction(Arc) const { return true; }
    598 
    599       /// \brief Returns the opposite directed arc.
    600       ///
    601       /// Returns the opposite directed arc.
    602       Arc oppositeArc(Arc) const { return INVALID; }
    603 
    604       /// \brief Opposite node on an arc
    605       ///
    606       /// \return The opposite of the given node on the given edge.
    607       Node oppositeNode(Node, Edge) const { return INVALID; }
    608 
    609       /// \brief First node of the edge.
    610       ///
    611       /// \return The first node of the given edge.
    612       ///
    613       /// Naturally edges don't have direction and thus
    614       /// don't have source and target node. However we use \c u() and \c v()
    615       /// methods to query the two nodes of the arc. The direction of the
    616       /// arc which arises this way is called the inherent direction of the
    617       /// edge, and is used to define the "default" direction
    618       /// of the directed versions of the arcs.
     586      /// \brief The first node of the edge.
     587      ///
     588      /// Returns the first node of the given edge.
     589      ///
     590      /// Edges don't have source and target nodes, however, methods
     591      /// u() and v() are used to query the two end-nodes of an edge.
     592      /// The orientation of an edge that arises this way is called
     593      /// the inherent direction, it is used to define the default
     594      /// direction for the corresponding arcs.
    619595      /// \sa v()
    620596      /// \sa direction()
    621597      Node u(Edge) const { return INVALID; }
    622598
    623       /// \brief Second node of the edge.
    624       ///
    625       /// \return The second node of the given edge.
    626       ///
    627       /// Naturally edges don't have direction and thus
    628       /// don't have source and target node. However we use \c u() and \c v()
    629       /// methods to query the two nodes of the arc. The direction of the
    630       /// arc which arises this way is called the inherent direction of the
    631       /// edge, and is used to define the "default" direction
    632       /// of the directed versions of the arcs.
     599      /// \brief The second node of the edge.
     600      ///
     601      /// Returns the second node of the given edge.
     602      ///
     603      /// Edges don't have source and target nodes, however, methods
     604      /// u() and v() are used to query the two end-nodes of an edge.
     605      /// The orientation of an edge that arises this way is called
     606      /// the inherent direction, it is used to define the default
     607      /// direction for the corresponding arcs.
    633608      /// \sa u()
    634609      /// \sa direction()
    635610      Node v(Edge) const { return INVALID; }
    636611
    637       /// \brief Source node of the directed arc.
     612      /// \brief The source node of the arc.
     613      ///
     614      /// Returns the source node of the given arc.
    638615      Node source(Arc) const { return INVALID; }
    639616
    640       /// \brief Target node of the directed arc.
     617      /// \brief The target node of the arc.
     618      ///
     619      /// Returns the target node of the given arc.
    641620      Node target(Arc) const { return INVALID; }
    642621
    643       /// \brief Returns the id of the node.
     622      /// \brief The ID of the node.
     623      ///
     624      /// Returns the ID of the given node.
    644625      int id(Node) const { return -1; }
    645626
    646       /// \brief Returns the id of the edge.
     627      /// \brief The ID of the edge.
     628      ///
     629      /// Returns the ID of the given edge.
    647630      int id(Edge) const { return -1; }
    648631
    649       /// \brief Returns the id of the arc.
     632      /// \brief The ID of the arc.
     633      ///
     634      /// Returns the ID of the given arc.
    650635      int id(Arc) const { return -1; }
    651636
    652       /// \brief Returns the node with the given id.
    653       ///
    654       /// \pre The argument should be a valid node id in the graph.
     637      /// \brief The node with the given ID.
     638      ///
     639      /// Returns the node with the given ID.
     640      /// \pre The argument should be a valid node ID in the graph.
    655641      Node nodeFromId(int) const { return INVALID; }
    656642
    657       /// \brief Returns the edge with the given id.
    658       ///
    659       /// \pre The argument should be a valid edge id in the graph.
     643      /// \brief The edge with the given ID.
     644      ///
     645      /// Returns the edge with the given ID.
     646      /// \pre The argument should be a valid edge ID in the graph.
    660647      Edge edgeFromId(int) const { return INVALID; }
    661648
    662       /// \brief Returns the arc with the given id.
    663       ///
    664       /// \pre The argument should be a valid arc id in the graph.
     649      /// \brief The arc with the given ID.
     650      ///
     651      /// Returns the arc with the given ID.
     652      /// \pre The argument should be a valid arc ID in the graph.
    665653      Arc arcFromId(int) const { return INVALID; }
    666654
    667       /// \brief Returns an upper bound on the node IDs.
     655      /// \brief An upper bound on the node IDs.
     656      ///
     657      /// Returns an upper bound on the node IDs.
    668658      int maxNodeId() const { return -1; }
    669659
    670       /// \brief Returns an upper bound on the edge IDs.
     660      /// \brief An upper bound on the edge IDs.
     661      ///
     662      /// Returns an upper bound on the edge IDs.
    671663      int maxEdgeId() const { return -1; }
    672664
    673       /// \brief Returns an upper bound on the arc IDs.
     665      /// \brief An upper bound on the arc IDs.
     666      ///
     667      /// Returns an upper bound on the arc IDs.
    674668      int maxArcId() const { return -1; }
     669
     670      /// \brief The direction of the arc.
     671      ///
     672      /// Returns \c true if the direction of the given arc is the same as
     673      /// the inherent orientation of the represented edge.
     674      bool direction(Arc) const { return true; }
     675
     676      /// \brief Direct the edge.
     677      ///
     678      /// Direct the given edge. The returned arc
     679      /// represents the given edge and its direction comes
     680      /// from the bool parameter. If it is \c true, then the direction
     681      /// of the arc is the same as the inherent orientation of the edge.
     682      Arc direct(Edge, bool) const {
     683        return INVALID;
     684      }
     685
     686      /// \brief Direct the edge.
     687      ///
     688      /// Direct the given edge. The returned arc represents the given
     689      /// edge and its source node is the given node.
     690      Arc direct(Edge, Node) const {
     691        return INVALID;
     692      }
     693
     694      /// \brief The oppositely directed arc.
     695      ///
     696      /// Returns the oppositely directed arc representing the same edge.
     697      Arc oppositeArc(Arc) const { return INVALID; }
     698
     699      /// \brief The opposite node on the edge.
     700      ///
     701      /// Returns the opposite node on the given edge.
     702      Node oppositeNode(Node, Edge) const { return INVALID; }
    675703
    676704      void first(Node&) const {}
     
    706734      int maxId(Arc) const { return -1; }
    707735
    708       /// \brief Base node of the iterator
    709       ///
    710       /// Returns the base node (the source in this case) of the iterator
    711       Node baseNode(OutArcIt e) const {
    712         return source(e);
    713       }
    714       /// \brief Running node of the iterator
    715       ///
    716       /// Returns the running node (the target in this case) of the
    717       /// iterator
    718       Node runningNode(OutArcIt e) const {
    719         return target(e);
    720       }
    721 
    722       /// \brief Base node of the iterator
    723       ///
    724       /// Returns the base node (the target in this case) of the iterator
    725       Node baseNode(InArcIt e) const {
    726         return target(e);
    727       }
    728       /// \brief Running node of the iterator
    729       ///
    730       /// Returns the running node (the source in this case) of the
    731       /// iterator
    732       Node runningNode(InArcIt e) const {
    733         return source(e);
    734       }
    735 
    736       /// \brief Base node of the iterator
    737       ///
    738       /// Returns the base node of the iterator
    739       Node baseNode(IncEdgeIt) const {
    740         return INVALID;
    741       }
    742 
    743       /// \brief Running node of the iterator
    744       ///
    745       /// Returns the running node of the iterator
    746       Node runningNode(IncEdgeIt) const {
    747         return INVALID;
    748       }
     736      /// \brief The base node of the iterator.
     737      ///
     738      /// Returns the base node of the given incident edge iterator.
     739      Node baseNode(IncEdgeIt) const { return INVALID; }
     740
     741      /// \brief The running node of the iterator.
     742      ///
     743      /// Returns the running node of the given incident edge iterator.
     744      Node runningNode(IncEdgeIt) const { return INVALID; }
     745
     746      /// \brief The base node of the iterator.
     747      ///
     748      /// Returns the base node of the given outgoing arc iterator
     749      /// (i.e. the source node of the corresponding arc).
     750      Node baseNode(OutArcIt) const { return INVALID; }
     751
     752      /// \brief The running node of the iterator.
     753      ///
     754      /// Returns the running node of the given outgoing arc iterator
     755      /// (i.e. the target node of the corresponding arc).
     756      Node runningNode(OutArcIt) const { return INVALID; }
     757
     758      /// \brief The base node of the iterator.
     759      ///
     760      /// Returns the base node of the given incomming arc iterator
     761      /// (i.e. the target node of the corresponding arc).
     762      Node baseNode(InArcIt) const { return INVALID; }
     763
     764      /// \brief The running node of the iterator.
     765      ///
     766      /// Returns the running node of the given incomming arc iterator
     767      /// (i.e. the source node of the corresponding arc).
     768      Node runningNode(InArcIt) const { return INVALID; }
    749769
    750770      template <typename _Graph>
  • lemon/concepts/graph_components.h

    r970 r983  
    109109
    110110          bool b;
    111           ignore_unused_variable_warning(b);
     111          ::lemon::ignore_unused_variable_warning(b);
    112112
    113113          b = (ia == ib) && (ia != ib);
     
    290290            ue = e;
    291291            bool d = graph.direction(e);
    292             ignore_unused_variable_warning(d);
     292            ::lemon::ignore_unused_variable_warning(d);
    293293          }
    294294        }
     
    369369
    370370          nid = digraph.maxNodeId();
    371           ignore_unused_variable_warning(nid);
     371          ::lemon::ignore_unused_variable_warning(nid);
    372372          eid = digraph.maxArcId();
    373           ignore_unused_variable_warning(eid);
     373          ::lemon::ignore_unused_variable_warning(eid);
    374374        }
    375375
     
    424424          edge = graph.edgeFromId(ueid);
    425425          ueid = graph.maxEdgeId();
    426           ignore_unused_variable_warning(ueid);
     426          ::lemon::ignore_unused_variable_warning(ueid);
    427427        }
    428428
     
    497497          _GraphItemIt it3 = it1;
    498498          _GraphItemIt it4 = INVALID;
    499           ignore_unused_variable_warning(it3);
    500           ignore_unused_variable_warning(it4);
     499          ::lemon::ignore_unused_variable_warning(it3);
     500          ::lemon::ignore_unused_variable_warning(it4);
    501501
    502502          it2 = ++it1;
     
    588588          _GraphIncIt it3 = it1;
    589589          _GraphIncIt it4 = INVALID;
    590           ignore_unused_variable_warning(it3);
    591           ignore_unused_variable_warning(it4);
     590          ::lemon::ignore_unused_variable_warning(it3);
     591          ::lemon::ignore_unused_variable_warning(it4);
    592592
    593593          it2 = ++it1;
     
    771771            n = digraph.baseNode(oait);
    772772            n = digraph.runningNode(oait);
    773             ignore_unused_variable_warning(n);
     773            ::lemon::ignore_unused_variable_warning(n);
    774774          }
    775775        }
     
    954954            = digraph.notifier(typename _Digraph::Arc());
    955955
    956           ignore_unused_variable_warning(nn);
    957           ignore_unused_variable_warning(en);
     956          ::lemon::ignore_unused_variable_warning(nn);
     957          ::lemon::ignore_unused_variable_warning(en);
    958958        }
    959959
     
    997997          typename _Graph::EdgeNotifier& uen
    998998            = graph.notifier(typename _Graph::Edge());
    999           ignore_unused_variable_warning(uen);
     999          ::lemon::ignore_unused_variable_warning(uen);
    10001000        }
    10011001
     
    10711071          // m3 = cmap;
    10721072
    1073           ignore_unused_variable_warning(m1);
    1074           ignore_unused_variable_warning(m2);
    1075           // ignore_unused_variable_warning(m3);
     1073          ::lemon::ignore_unused_variable_warning(m1);
     1074          ::lemon::ignore_unused_variable_warning(m2);
     1075          // ::lemon::ignore_unused_variable_warning(m3);
    10761076        }
    10771077
  • lemon/concepts/graph_components.h

    r982 r983  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    1919///\ingroup graph_concepts
    2020///\file
    21 ///\brief The concept of graph components.
     21///\brief The concepts of graph components.
    2222
    2323#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
     
    3939    /// \note This class is a template class so that we can use it to
    4040    /// create graph skeleton classes. The reason for this is that \c Node
    41     /// and \c Arc (or \c Edge) types should \e not derive from the same 
     41    /// and \c Arc (or \c Edge) types should \e not derive from the same
    4242    /// base class. For \c Node you should instantiate it with character
    4343    /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
     
    9090      ///
    9191      /// This operator defines an ordering of the items.
    92       /// It makes possible to use graph item types as key types in 
     92      /// It makes possible to use graph item types as key types in
    9393      /// associative containers (e.g. \c std::map).
    9494      ///
    95       /// \note This operator only have to define some strict ordering of
     95      /// \note This operator only has to define some strict ordering of
    9696      /// the items; this order has nothing to do with the iteration
    9797      /// ordering of the items.
     
    126126    /// This class describes the base interface of directed graph types.
    127127    /// All digraph %concepts have to conform to this class.
    128     /// It just provides types for nodes and arcs and functions 
     128    /// It just provides types for nodes and arcs and functions
    129129    /// to get the source and the target nodes of arcs.
    130130    class BaseDigraphComponent {
     
    434434    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
    435435    ///
    436     /// This class describes the concept of \c NodeIt, \c ArcIt and 
     436    /// This class describes the concept of \c NodeIt, \c ArcIt and
    437437    /// \c EdgeIt subtypes of digraph and graph types.
    438438    template <typename GR, typename Item>
     
    474474      /// next item.
    475475      GraphItemIt& operator++() { return *this; }
    476  
     476
    477477      /// \brief Equality operator
    478478      ///
     
    512512    };
    513513
    514     /// \brief Concept class for \c InArcIt, \c OutArcIt and 
     514    /// \brief Concept class for \c InArcIt, \c OutArcIt and
    515515    /// \c IncEdgeIt types.
    516516    ///
    517     /// This class describes the concept of \c InArcIt, \c OutArcIt 
     517    /// This class describes the concept of \c InArcIt, \c OutArcIt
    518518    /// and \c IncEdgeIt subtypes of digraph and graph types.
    519519    ///
    520520    /// \note Since these iterator classes do not inherit from the same
    521521    /// base class, there is an additional template parameter (selector)
    522     /// \c sel. For \c InArcIt you should instantiate it with character 
     522    /// \c sel. For \c InArcIt you should instantiate it with character
    523523    /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
    524524    template <typename GR,
     
    541541      GraphIncIt(const GraphIncIt& it) : Item(it) {}
    542542
    543       /// \brief Constructor that sets the iterator to the first 
     543      /// \brief Constructor that sets the iterator to the first
    544544      /// incoming or outgoing arc.
    545545      ///
    546       /// Constructor that sets the iterator to the first arc 
     546      /// Constructor that sets the iterator to the first arc
    547547      /// incoming to or outgoing from the given node.
    548548      explicit GraphIncIt(const GR&, const Base&) {}
     
    819819      /// \brief Return the first edge incident to the given node.
    820820      ///
    821       /// This function gives back the first edge incident to the given 
     821      /// This function gives back the first edge incident to the given
    822822      /// node. The bool parameter gives back the direction for which the
    823       /// source node of the directed arc representing the edge is the 
     823      /// source node of the directed arc representing the edge is the
    824824      /// given node.
    825825      void firstInc(Edge&, bool&, const Node&) const {}
     
    828828      /// given node.
    829829      ///
    830       /// This function gives back the next edge incident to the given 
     830      /// This function gives back the next edge incident to the given
    831831      /// node. The bool parameter should be used as \c firstInc() use it.
    832832      void nextInc(Edge&, bool&) const {}
     
    10081008    ///
    10091009    /// This class describes the concept of standard graph maps, i.e.
    1010     /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and 
     1010    /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
    10111011    /// graph types, which can be used for associating data to graph items.
    10121012    /// The standard graph maps must conform to the ReferenceMap concept.
     
    10631063          _Map m1(g);
    10641064          _Map m2(g,t);
    1065          
     1065
    10661066          // Copy constructor
    10671067          // _Map m3(m);
     
    10871087    ///
    10881088    /// This class describes the interface of mappable directed graphs.
    1089     /// It extends \ref BaseDigraphComponent with the standard digraph 
     1089    /// It extends \ref BaseDigraphComponent with the standard digraph
    10901090    /// map classes, namely \c NodeMap and \c ArcMap.
    10911091    /// This concept is part of the Digraph concept.
     
    12251225    ///
    12261226    /// This class describes the interface of mappable undirected graphs.
    1227     /// It extends \ref MappableDigraphComponent with the standard graph 
     1227    /// It extends \ref MappableDigraphComponent with the standard graph
    12281228    /// map class for edges (\c EdgeMap).
    12291229    /// This concept is part of the Graph concept.
     
    13111311    ///
    13121312    /// This class describes the interface of extendable directed graphs.
    1313     /// It extends \ref BaseDigraphComponent with functions for adding 
     1313    /// It extends \ref BaseDigraphComponent with functions for adding
    13141314    /// nodes and arcs to the digraph.
    13151315    /// This concept requires \ref AlterableDigraphComponent.
     
    13561356    ///
    13571357    /// This class describes the interface of extendable undirected graphs.
    1358     /// It extends \ref BaseGraphComponent with functions for adding 
     1358    /// It extends \ref BaseGraphComponent with functions for adding
    13591359    /// nodes and edges to the graph.
    13601360    /// This concept requires \ref AlterableGraphComponent.
     
    14011401    ///
    14021402    /// This class describes the interface of erasable directed graphs.
    1403     /// It extends \ref BaseDigraphComponent with functions for removing 
     1403    /// It extends \ref BaseDigraphComponent with functions for removing
    14041404    /// nodes and arcs from the digraph.
    14051405    /// This concept requires \ref AlterableDigraphComponent.
     
    14141414      /// \brief Erase a node from the digraph.
    14151415      ///
    1416       /// This function erases the given node from the digraph and all arcs 
     1416      /// This function erases the given node from the digraph and all arcs
    14171417      /// connected to the node.
    14181418      void erase(const Node&) {}
     
    14411441    ///
    14421442    /// This class describes the interface of erasable undirected graphs.
    1443     /// It extends \ref BaseGraphComponent with functions for removing 
     1443    /// It extends \ref BaseGraphComponent with functions for removing
    14441444    /// nodes and edges from the graph.
    14451445    /// This concept requires \ref AlterableGraphComponent.
  • lemon/concepts/heap.h

    r954 r983  
    261261          item=Item();
    262262          prio=Prio();
    263           ignore_unused_variable_warning(item);
    264           ignore_unused_variable_warning(prio);
     263          ::lemon::ignore_unused_variable_warning(item);
     264          ::lemon::ignore_unused_variable_warning(prio);
    265265
    266266          OwnItem own_item;
     
    269269          own_item=Item();
    270270          own_prio=Prio();
    271           ignore_unused_variable_warning(own_item);
    272           ignore_unused_variable_warning(own_prio);
    273           ignore_unused_variable_warning(own_state);
     271          ::lemon::ignore_unused_variable_warning(own_item);
     272          ::lemon::ignore_unused_variable_warning(own_prio);
     273          ::lemon::ignore_unused_variable_warning(own_state);
    274274
    275275          _Heap heap1(map);
    276276          _Heap heap2 = heap1;
    277           ignore_unused_variable_warning(heap1);
    278           ignore_unused_variable_warning(heap2);
     277          ::lemon::ignore_unused_variable_warning(heap1);
     278          ::lemon::ignore_unused_variable_warning(heap2);
    279279
    280280          int s = heap.size();
    281           ignore_unused_variable_warning(s);
     281          ::lemon::ignore_unused_variable_warning(s);
    282282          bool e = heap.empty();
    283           ignore_unused_variable_warning(e);
     283          ::lemon::ignore_unused_variable_warning(e);
    284284
    285285          prio = heap.prio();
  • lemon/concepts/heap.h

    r982 r983  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    1717 */
    1818
     19#ifndef LEMON_CONCEPTS_HEAP_H
     20#define LEMON_CONCEPTS_HEAP_H
     21
    1922///\ingroup concept
    2023///\file
    2124///\brief The concept of heaps.
    2225
    23 #ifndef LEMON_CONCEPTS_HEAP_H
    24 #define LEMON_CONCEPTS_HEAP_H
    25 
    2626#include <lemon/core.h>
    2727#include <lemon/concept_check.h>
     
    3636    /// \brief The heap concept.
    3737    ///
    38     /// Concept class describing the main interface of heaps. A \e heap
    39     /// is a data structure for storing items with specified values called
    40     /// \e priorities in such a way that finding the item with minimum
    41     /// priority is efficient. In a heap one can change the priority of an
    42     /// item, add or erase an item, etc.
     38    /// This concept class describes the main interface of heaps.
     39    /// The various \ref heaps "heap structures" are efficient
     40    /// implementations of the abstract data type \e priority \e queue.
     41    /// They store items with specified values called \e priorities
     42    /// in such a way that finding and removing the item with minimum
     43    /// priority are efficient. The basic operations are adding and
     44    /// erasing items, changing the priority of an item, etc.
    4345    ///
    44     /// \tparam PR Type of the priority of the items.
    45     /// \tparam IM A read and writable item map with int values, used
     46    /// Heaps are crucial in several algorithms, such as Dijkstra and Prim.
     47    /// Any class that conforms to this concept can be used easily in such
     48    /// algorithms.
     49    ///
     50    /// \tparam PR Type of the priorities of the items.
     51    /// \tparam IM A read-writable item map with \c int values, used
    4652    /// internally to handle the cross references.
    47     /// \tparam Comp A functor class for the ordering of the priorities.
     53    /// \tparam CMP A functor class for comparing the priorities.
    4854    /// The default is \c std::less<PR>.
    4955#ifdef DOXYGEN
    50     template <typename PR, typename IM, typename Comp = std::less<PR> >
    51 #else
    52     template <typename PR, typename IM>
     56    template <typename PR, typename IM, typename CMP>
     57#else
     58    template <typename PR, typename IM, typename CMP = std::less<PR> >
    5359#endif
    5460    class Heap {
     
    6571      ///
    6672      /// Each item has a state associated to it. It can be "in heap",
    67       /// "pre heap" or "post heap". The later two are indifferent
    68       /// from the point of view of the heap, but may be useful for
    69       /// the user.
     73      /// "pre-heap" or "post-heap". The latter two are indifferent from the
     74      /// heap's point of view, but may be useful to the user.
    7075      ///
    7176      /// The item-int map must be initialized in such way that it assigns
     
    7378      enum State {
    7479        IN_HEAP = 0,    ///< = 0. The "in heap" state constant.
    75         PRE_HEAP = -1,  ///< = -1. The "pre heap" state constant.
    76         POST_HEAP = -2  ///< = -2. The "post heap" state constant.
     80        PRE_HEAP = -1,  ///< = -1. The "pre-heap" state constant.
     81        POST_HEAP = -2  ///< = -2. The "post-heap" state constant.
    7782      };
    7883
    79       /// \brief The constructor.
    80       ///
    81       /// The constructor.
     84      /// \brief Constructor.
     85      ///
     86      /// Constructor.
    8287      /// \param map A map that assigns \c int values to keys of type
    8388      /// \c Item. It is used internally by the heap implementations to
    8489      /// handle the cross references. The assigned value must be
    85       /// \c PRE_HEAP (<tt>-1</tt>) for every item.
     90      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
     91#ifdef DOXYGEN
    8692      explicit Heap(ItemIntMap &map) {}
     93#else
     94      explicit Heap(ItemIntMap&) {}
     95#endif
     96
     97      /// \brief Constructor.
     98      ///
     99      /// Constructor.
     100      /// \param map A map that assigns \c int values to keys of type
     101      /// \c Item. It is used internally by the heap implementations to
     102      /// handle the cross references. The assigned value must be
     103      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
     104      /// \param comp The function object used for comparing the priorities.
     105#ifdef DOXYGEN
     106      explicit Heap(ItemIntMap &map, const CMP &comp) {}
     107#else
     108      explicit Heap(ItemIntMap&, const CMP&) {}
     109#endif
    87110
    88111      /// \brief The number of items stored in the heap.
    89112      ///
    90       /// Returns the number of items stored in the heap.
     113      /// This function returns the number of items stored in the heap.
    91114      int size() const { return 0; }
    92115
    93       /// \brief Checks if the heap is empty.
    94       ///
    95       /// Returns \c true if the heap is empty.
     116      /// \brief Check if the heap is empty.
     117      ///
     118      /// This function returns \c true if the heap is empty.
    96119      bool empty() const { return false; }
    97120
    98       /// \brief Makes the heap empty.
    99       ///
    100       /// Makes the heap empty.
    101       void clear();
    102 
    103       /// \brief Inserts an item into the heap with the given priority.
    104       ///
    105       /// Inserts the given item into the heap with the given priority.
     121      /// \brief Make the heap empty.
     122      ///
     123      /// This functon makes the heap empty.
     124      /// It does not change the cross reference map. If you want to reuse
     125      /// a heap that is not surely empty, you should first clear it and
     126      /// then you should set the cross reference map to \c PRE_HEAP
     127      /// for each item.
     128      void clear() {}
     129
     130      /// \brief Insert an item into the heap with the given priority.
     131      ///
     132      /// This function inserts the given item into the heap with the
     133      /// given priority.
    106134      /// \param i The item to insert.
    107135      /// \param p The priority of the item.
     136      /// \pre \e i must not be stored in the heap.
     137#ifdef DOXYGEN
    108138      void push(const Item &i, const Prio &p) {}
    109 
    110       /// \brief Returns the item having minimum priority.
    111       ///
    112       /// Returns the item having minimum priority.
     139#else
     140      void push(const Item&, const Prio&) {}
     141#endif
     142
     143      /// \brief Return the item having minimum priority.
     144      ///
     145      /// This function returns the item having minimum priority.
    113146      /// \pre The heap must be non-empty.
    114       Item top() const {}
     147      Item top() const { return Item(); }
    115148
    116149      /// \brief The minimum priority.
    117150      ///
    118       /// Returns the minimum priority.
     151      /// This function returns the minimum priority.
    119152      /// \pre The heap must be non-empty.
    120       Prio prio() const {}
    121 
    122       /// \brief Removes the item having minimum priority.
    123       ///
    124       /// Removes the item having minimum priority.
     153      Prio prio() const { return Prio(); }
     154
     155      /// \brief Remove the item having minimum priority.
     156      ///
     157      /// This function removes the item having minimum priority.
    125158      /// \pre The heap must be non-empty.
    126159      void pop() {}
    127160
    128       /// \brief Removes an item from the heap.
    129       ///
    130       /// Removes the given item from the heap if it is already stored.
     161      /// \brief Remove the given item from the heap.
     162      ///
     163      /// This function removes the given item from the heap if it is
     164      /// already stored.
    131165      /// \param i The item to delete.
     166      /// \pre \e i must be in the heap.
     167#ifdef DOXYGEN
    132168      void erase(const Item &i) {}
    133 
    134       /// \brief The priority of an item.
    135       ///
    136       /// Returns the priority of the given item.
    137       /// \param i The item.
    138       /// \pre \c i must be in the heap.
     169#else
     170      void erase(const Item&) {}
     171#endif
     172
     173      /// \brief The priority of the given item.
     174      ///
     175      /// This function returns the priority of the given item.
     176      /// \param i The item.
     177      /// \pre \e i must be in the heap.
     178#ifdef DOXYGEN
    139179      Prio operator[](const Item &i) const {}
    140 
    141       /// \brief Sets the priority of an item or inserts it, if it is
     180#else
     181      Prio operator[](const Item&) const { return Prio(); }
     182#endif
     183
     184      /// \brief Set the priority of an item or insert it, if it is
    142185      /// not stored in the heap.
    143186      ///
    144187      /// This method sets the priority of the given item if it is
    145       /// already stored in the heap.
    146       /// Otherwise it inserts the given item with the given priority.
     188      /// already stored in the heap. Otherwise it inserts the given
     189      /// item into the heap with the given priority.
    147190      ///
    148191      /// \param i The item.
    149192      /// \param p The priority.
     193#ifdef DOXYGEN
    150194      void set(const Item &i, const Prio &p) {}
    151 
    152       /// \brief Decreases the priority of an item to the given value.
    153       ///
    154       /// Decreases the priority of an item to the given value.
     195#else
     196      void set(const Item&, const Prio&) {}
     197#endif
     198
     199      /// \brief Decrease the priority of an item to the given value.
     200      ///
     201      /// This function decreases the priority of an item to the given value.
    155202      /// \param i The item.
    156203      /// \param p The priority.
    157       /// \pre \c i must be stored in the heap with priority at least \c p.
     204      /// \pre \e i must be stored in the heap with priority at least \e p.
     205#ifdef DOXYGEN
    158206      void decrease(const Item &i, const Prio &p) {}
    159 
    160       /// \brief Increases the priority of an item to the given value.
    161       ///
    162       /// Increases the priority of an item to the given value.
     207#else
     208      void decrease(const Item&, const Prio&) {}
     209#endif
     210
     211      /// \brief Increase the priority of an item to the given value.
     212      ///
     213      /// This function increases the priority of an item to the given value.
    163214      /// \param i The item.
    164215      /// \param p The priority.
    165       /// \pre \c i must be stored in the heap with priority at most \c p.
     216      /// \pre \e i must be stored in the heap with priority at most \e p.
     217#ifdef DOXYGEN
    166218      void increase(const Item &i, const Prio &p) {}
    167 
    168       /// \brief Returns if an item is in, has already been in, or has
    169       /// never been in the heap.
     219#else
     220      void increase(const Item&, const Prio&) {}
     221#endif
     222
     223      /// \brief Return the state of an item.
    170224      ///
    171225      /// This method returns \c PRE_HEAP if the given item has never
     
    175229      /// to the heap again.
    176230      /// \param i The item.
     231#ifdef DOXYGEN
    177232      State state(const Item &i) const {}
    178 
    179       /// \brief Sets the state of an item in the heap.
    180       ///
    181       /// Sets the state of the given item in the heap. It can be used
    182       /// to manually clear the heap when it is important to achive the
    183       /// better time complexity.
     233#else
     234      State state(const Item&) const { return PRE_HEAP; }
     235#endif
     236
     237      /// \brief Set the state of an item in the heap.
     238      ///
     239      /// This function sets the state of the given item in the heap.
     240      /// It can be used to manually clear the heap when it is important
     241      /// to achive better time complexity.
    184242      /// \param i The item.
    185243      /// \param st The state. It should not be \c IN_HEAP.
     244#ifdef DOXYGEN
    186245      void state(const Item& i, State st) {}
     246#else
     247      void state(const Item&, State) {}
     248#endif
    187249
    188250
  • lemon/concepts/path.h

    r954 r983  
    7676      template <typename CPath>
    7777      Path& operator=(const CPath& cpath) {
    78         ignore_unused_variable_warning(cpath);
     78        ::lemon::ignore_unused_variable_warning(cpath);
    7979        return *this;
    8080      }
     
    136136          e = (i < ii);
    137137
    138           ignore_unused_variable_warning(l);
    139           ignore_unused_variable_warning(pp);
    140           ignore_unused_variable_warning(e);
    141           ignore_unused_variable_warning(id);
    142           ignore_unused_variable_warning(ii);
    143           ignore_unused_variable_warning(ed);
     138          ::lemon::ignore_unused_variable_warning(l);
     139          ::lemon::ignore_unused_variable_warning(pp);
     140          ::lemon::ignore_unused_variable_warning(e);
     141          ::lemon::ignore_unused_variable_warning(id);
     142          ::lemon::ignore_unused_variable_warning(ii);
     143          ::lemon::ignore_unused_variable_warning(ed);
    144144        }
    145145      };
     
    163163          e = (i != INVALID);
    164164
    165           ignore_unused_variable_warning(l);
    166           ignore_unused_variable_warning(e);
    167           ignore_unused_variable_warning(id);
    168           ignore_unused_variable_warning(ed);
     165          ::lemon::ignore_unused_variable_warning(l);
     166          ::lemon::ignore_unused_variable_warning(e);
     167          ::lemon::ignore_unused_variable_warning(id);
     168          ::lemon::ignore_unused_variable_warning(ed);
    169169        }
    170170        _Path& p;
     
    189189          e = (i != INVALID);
    190190
    191           ignore_unused_variable_warning(l);
    192           ignore_unused_variable_warning(e);
    193           ignore_unused_variable_warning(id);
    194           ignore_unused_variable_warning(ed);
     191          ::lemon::ignore_unused_variable_warning(l);
     192          ::lemon::ignore_unused_variable_warning(e);
     193          ::lemon::ignore_unused_variable_warning(id);
     194          ::lemon::ignore_unused_variable_warning(ed);
    195195        }
    196196        _Path& p;
  • lemon/concepts/path.h

    r982 r983  
    1919///\ingroup concept
    2020///\file
    21 ///\brief Classes for representing paths in digraphs.
     21///\brief The concept of paths
    2222///
    2323
     
    3939    /// A skeleton structure for representing directed paths in a
    4040    /// digraph.
     41    /// In a sense, a path can be treated as a list of arcs.
     42    /// LEMON path types just store this list. As a consequence, they cannot
     43    /// enumerate the nodes on the path directly and a zero length path
     44    /// cannot store its source node.
     45    ///
     46    /// The arcs of a path should be stored in the order of their directions,
     47    /// i.e. the target node of each arc should be the same as the source
     48    /// node of the next arc. This consistency could be checked using
     49    /// \ref checkPath().
     50    /// The source and target nodes of a (consistent) path can be obtained
     51    /// using \ref pathSource() and \ref pathTarget().
     52    ///
     53    /// A path can be constructed from another path of any type using the
     54    /// copy constructor or the assignment operator.
     55    ///
    4156    /// \tparam GR The digraph type in which the path is.
    42     ///
    43     /// In a sense, the path can be treated as a list of arcs. The
    44     /// lemon path type stores just this list. As a consequence it
    45     /// cannot enumerate the nodes in the path and the zero length
    46     /// paths cannot store the source.
    47     ///
    4857    template <typename GR>
    4958    class Path {
     
    6069      Path() {}
    6170
    62       /// \brief Template constructor
     71      /// \brief Template copy constructor
    6372      template <typename CPath>
    6473      Path(const CPath& cpath) {}
    6574
    66       /// \brief Template assigment
     75      /// \brief Template assigment operator
    6776      template <typename CPath>
    6877      Path& operator=(const CPath& cpath) {
     
    7180      }
    7281
    73       /// Length of the path ie. the number of arcs in the path.
     82      /// Length of the path, i.e. the number of arcs on the path.
    7483      int length() const { return 0;}
    7584
     
    8089      void clear() {}
    8190
    82       /// \brief LEMON style iterator for path arcs
     91      /// \brief LEMON style iterator for enumerating the arcs of a path.
    8392      ///
    84       /// This class is used to iterate on the arcs of the paths.
     93      /// LEMON style iterator class for enumerating the arcs of a path.
    8594      class ArcIt {
    8695      public:
     
    8998        /// Invalid constructor
    9099        ArcIt(Invalid) {}
    91         /// Constructor for first arc
     100        /// Sets the iterator to the first arc of the given path
    92101        ArcIt(const Path &) {}
    93102
    94         /// Conversion to Arc
     103        /// Conversion to \c Arc
    95104        operator Arc() const { return INVALID; }
    96105
     
    195204    ///
    196205    /// A skeleton structure for path dumpers. The path dumpers are
    197     /// the generalization of the paths. The path dumpers can
    198     /// enumerate the arcs of the path wheter in forward or in
    199     /// backward order.  In most time these classes are not used
    200     /// directly rather it used to assign a dumped class to a real
    201     /// path type.
     206    /// the generalization of the paths, they can enumerate the arcs
     207    /// of the path either in forward or in backward order.
     208    /// These classes are typically not used directly, they are rather
     209    /// used to be assigned to a real path type.
    202210    ///
    203211    /// The main purpose of this concept is that the shortest path
    204     /// algorithms can enumerate easily the arcs in reverse order.
    205     /// If we would like to give back a real path from these
    206     /// algorithms then we should create a temporarly path object. In
    207     /// LEMON such algorithms gives back a path dumper what can
    208     /// assigned to a real path and the dumpers can be implemented as
     212    /// algorithms can enumerate the arcs easily in reverse order.
     213    /// In LEMON, such algorithms give back a (reverse) path dumper that
     214    /// can be assigned to a real path. The dumpers can be implemented as
    209215    /// an adaptor class to the predecessor map.
    210216    ///
    211217    /// \tparam GR The digraph type in which the path is.
    212     ///
    213     /// The paths can be constructed from any path type by a
    214     /// template constructor or a template assignment operator.
    215218    template <typename GR>
    216219    class PathDumper {
     
    222225      typedef typename Digraph::Arc Arc;
    223226
    224       /// Length of the path ie. the number of arcs in the path.
     227      /// Length of the path, i.e. the number of arcs on the path.
    225228      int length() const { return 0;}
    226229
     
    230233      /// \brief Forward or reverse dumping
    231234      ///
    232       /// If the RevPathTag is defined and true then reverse dumping
    233       /// is provided in the path dumper. In this case instead of the
    234       /// ArcIt the RevArcIt iterator should be implemented in the
    235       /// dumper.
     235      /// If this tag is defined to be \c True, then reverse dumping
     236      /// is provided in the path dumper. In this case, \c RevArcIt
     237      /// iterator should be implemented instead of \c ArcIt iterator.
    236238      typedef False RevPathTag;
    237239
    238       /// \brief LEMON style iterator for path arcs
     240      /// \brief LEMON style iterator for enumerating the arcs of a path.
    239241      ///
    240       /// This class is used to iterate on the arcs of the paths.
     242      /// LEMON style iterator class for enumerating the arcs of a path.
    241243      class ArcIt {
    242244      public:
     
    245247        /// Invalid constructor
    246248        ArcIt(Invalid) {}
    247         /// Constructor for first arc
     249        /// Sets the iterator to the first arc of the given path
    248250        ArcIt(const PathDumper&) {}
    249251
    250         /// Conversion to Arc
     252        /// Conversion to \c Arc
    251253        operator Arc() const { return INVALID; }
    252254
     
    263265      };
    264266
    265       /// \brief LEMON style iterator for path arcs
     267      /// \brief LEMON style iterator for enumerating the arcs of a path
     268      /// in reverse direction.
    266269      ///
    267       /// This class is used to iterate on the arcs of the paths in
    268       /// reverse direction.
     270      /// LEMON style iterator class for enumerating the arcs of a path
     271      /// in reverse direction.
    269272      class RevArcIt {
    270273      public:
     
    273276        /// Invalid constructor
    274277        RevArcIt(Invalid) {}
    275         /// Constructor for first arc
     278        /// Sets the iterator to the last arc of the given path
    276279        RevArcIt(const PathDumper &) {}
    277280
    278         /// Conversion to Arc
     281        /// Conversion to \c Arc
    279282        operator Arc() const { return INVALID; }
    280283
  • lemon/core.h

    r964 r983  
    3636#ifdef _MSC_VER
    3737#pragma warning( disable : 4250 4355 4503 4800 4996 )
     38#endif
     39
     40#ifdef __GNUC__
     41#define GCC_VERSION (__GNUC__ * 10000                   \
     42                     + __GNUC_MINOR__ * 100             \
     43                     + __GNUC_PATCHLEVEL__)
     44#endif
     45
     46#if GCC_VERSION >= 40800
     47// Needed by the [DI]GRAPH_TYPEDEFS marcos for gcc 4.8
     48#pragma GCC diagnostic ignored "-Wunused-local-typedefs"
    3849#endif
    3950
  • lemon/core.h

    r979 r983  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    12531253  protected:
    12541254
    1255     class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
     1255    class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type
     1256    {
    12561257      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
    12571258
     
    12921293    };
    12931294
    1294   protected: 
     1295  protected:
    12951296
    12961297    const Digraph &_g;
  • lemon/cplex.cc

    r956 r974  
    4141    int status;
    4242    _cnt = new int;
     43    (*_cnt) = 1;
    4344    _env = CPXopenCPLEX(&status);
    4445    if (_env == 0) {
  • lemon/cplex.cc

    r973 r974  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    113113  }
    114114
     115  int CplexBase::_addRow(Value lb, ExprIterator b,
     116                         ExprIterator e, Value ub) {
     117    int i = CPXgetnumrows(cplexEnv(), _prob);
     118    if (lb == -INF) {
     119      const char s = 'L';
     120      CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0);
     121    } else if (ub == INF) {
     122      const char s = 'G';
     123      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
     124    } else if (lb == ub){
     125      const char s = 'E';
     126      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
     127    } else {
     128      const char s = 'R';
     129      double len = ub - lb;
     130      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, &len, 0);
     131    }
     132
     133    std::vector<int> indices;
     134    std::vector<int> rowlist;
     135    std::vector<Value> values;
     136
     137    for(ExprIterator it=b; it!=e; ++it) {
     138      indices.push_back(it->first);
     139      values.push_back(it->second);
     140      rowlist.push_back(i);
     141    }
     142
     143    CPXchgcoeflist(cplexEnv(), _prob, values.size(),
     144                   &rowlist.front(), &indices.front(), &values.front());
     145
     146    return i;
     147  }
    115148
    116149  void CplexBase::_eraseCol(int i) {
     
    456489
    457490  void CplexBase::_applyMessageLevel() {
    458     CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND, 
     491    CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND,
    459492                   _message_enabled ? CPX_ON : CPX_OFF);
    460493  }
  • lemon/graph_to_eps.h

    r964 r981  
    223223  using T::_copyright;
    224224
    225   using typename T::NodeTextColorType;
     225  using T::NodeTextColorType;
    226226  using T::CUST_COL;
    227227  using T::DIST_COL;
  • lemon/graph_to_eps.h

    r980 r981  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    143143  ///\param gr  Reference to the graph to be printed.
    144144  ///\param ost Reference to the output stream.
    145   ///By default it is <tt>std::cout</tt>.
     145  ///By default, it is <tt>std::cout</tt>.
    146146  ///\param pros If it is \c true, then the \c ostream referenced by \c os
    147147  ///will be explicitly deallocated by the destructor.
     
    513513  ///Turn on/off pre-scaling
    514514
    515   ///By default graphToEps() rescales the whole image in order to avoid
     515  ///By default, graphToEps() rescales the whole image in order to avoid
    516516  ///very big or very small bounding boxes.
    517517  ///
     
    11151115///\param g Reference to the graph to be printed.
    11161116///\param os Reference to the output stream.
    1117 ///By default it is <tt>std::cout</tt>.
     1117///By default, it is <tt>std::cout</tt>.
    11181118///
    11191119///This function also has a lot of
     
    11271127///\endcode
    11281128///
    1129 ///For more detailed examples see the \ref graph_to_eps_demo.cc demo file.
     1129///For more detailed examples, see the \ref graph_to_eps_demo.cc demo file.
    11301130///
    11311131///\warning Don't forget to put the \ref GraphToEps::run() "run()"
  • test/adaptors_test.cc

    r964 r983  
    6666  Digraph::Arc a2 = digraph.addArc(n1, n3);
    6767  Digraph::Arc a3 = digraph.addArc(n2, n3);
    68   ignore_unused_variable_warning(a3);
     68  ::lemon::ignore_unused_variable_warning(a3);
    6969
    7070  // Check the adaptor
     
    101101  Adaptor::Arc a7 = adaptor.addArc(n1, n4);
    102102  Adaptor::Arc a8 = adaptor.addArc(n1, n2);
    103   ignore_unused_variable_warning(a6,a7,a8);
     103  ::lemon::ignore_unused_variable_warning(a6,a7,a8);
    104104
    105105  adaptor.erase(a1);
     
    761761  Digraph::Arc a2 = digraph.addArc(n1, n3);
    762762  Digraph::Arc a3 = digraph.addArc(n2, n3);
    763   ignore_unused_variable_warning(a1,a2,a3);
     763  ::lemon::ignore_unused_variable_warning(a1,a2,a3);
    764764
    765765  checkGraphNodeList(adaptor, 6);
  • test/adaptors_test.cc

    r982 r983  
    13751375
    13761376  GridGraph::EdgeMap<bool> dir_map(graph);
    1377   dir_map[graph.right(n1)] = graph.u(graph.right(n1)) == n1;
    1378   dir_map[graph.up(n1)] = graph.u(graph.up(n1)) != n1;
    1379   dir_map[graph.left(n4)] = graph.u(graph.left(n4)) != n4;
    1380   dir_map[graph.down(n4)] = graph.u(graph.down(n4)) != n4;
     1377  dir_map[graph.right(n1)] = graph.u(graph.right(n1)) != n1;
     1378  dir_map[graph.up(n1)] = graph.u(graph.up(n1)) == n1;
     1379  dir_map[graph.left(n4)] = graph.u(graph.left(n4)) == n4;
     1380  dir_map[graph.down(n4)] = graph.u(graph.down(n4)) == n4;
    13811381
    13821382  // Apply several adaptors on the grid graph
    1383   typedef SplitNodes< ReverseDigraph< const Orienter<
    1384             const GridGraph, GridGraph::EdgeMap<bool> > > >
    1385     RevSplitGridGraph;
    1386   typedef ReverseDigraph<const RevSplitGridGraph> SplitGridGraph;
     1383  typedef Orienter< const GridGraph, GridGraph::EdgeMap<bool> >
     1384    OrientedGridGraph;
     1385  typedef SplitNodes<OrientedGridGraph> SplitGridGraph;
    13871386  typedef Undirector<const SplitGridGraph> USplitGridGraph;
    1388   typedef Undirector<const USplitGridGraph> UUSplitGridGraph;
    1389   checkConcept<concepts::Digraph, RevSplitGridGraph>();
    13901387  checkConcept<concepts::Digraph, SplitGridGraph>();
    13911388  checkConcept<concepts::Graph, USplitGridGraph>();
    1392   checkConcept<concepts::Graph, UUSplitGridGraph>();
    1393 
    1394   RevSplitGridGraph rev_adaptor =
    1395     splitNodes(reverseDigraph(orienter(graph, dir_map)));
    1396   SplitGridGraph adaptor = reverseDigraph(rev_adaptor);
     1389
     1390  OrientedGridGraph oadaptor = orienter(graph, dir_map);
     1391  SplitGridGraph adaptor = splitNodes(oadaptor);
    13971392  USplitGridGraph uadaptor = undirector(adaptor);
    1398   UUSplitGridGraph uuadaptor = undirector(uadaptor);
    13991393
    14001394  // Check adaptor
     
    14031397  checkGraphConArcList(adaptor, 8);
    14041398
    1405   checkGraphOutArcList(adaptor, rev_adaptor.inNode(n1), 1);
    1406   checkGraphOutArcList(adaptor, rev_adaptor.outNode(n1), 1);
    1407   checkGraphOutArcList(adaptor, rev_adaptor.inNode(n2), 2);
    1408   checkGraphOutArcList(adaptor, rev_adaptor.outNode(n2), 1);
    1409   checkGraphOutArcList(adaptor, rev_adaptor.inNode(n3), 1);
    1410   checkGraphOutArcList(adaptor, rev_adaptor.outNode(n3), 1);
    1411   checkGraphOutArcList(adaptor, rev_adaptor.inNode(n4), 0);
    1412   checkGraphOutArcList(adaptor, rev_adaptor.outNode(n4), 1);
    1413 
    1414   checkGraphInArcList(adaptor, rev_adaptor.inNode(n1), 1);
    1415   checkGraphInArcList(adaptor, rev_adaptor.outNode(n1), 1);
    1416   checkGraphInArcList(adaptor, rev_adaptor.inNode(n2), 1);
    1417   checkGraphInArcList(adaptor, rev_adaptor.outNode(n2), 0);
    1418   checkGraphInArcList(adaptor, rev_adaptor.inNode(n3), 1);
    1419   checkGraphInArcList(adaptor, rev_adaptor.outNode(n3), 1);
    1420   checkGraphInArcList(adaptor, rev_adaptor.inNode(n4), 1);
    1421   checkGraphInArcList(adaptor, rev_adaptor.outNode(n4), 2);
     1399  checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
     1400  checkGraphOutArcList(adaptor, adaptor.outNode(n1), 1);
     1401  checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
     1402  checkGraphOutArcList(adaptor, adaptor.outNode(n2), 0);
     1403  checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
     1404  checkGraphOutArcList(adaptor, adaptor.outNode(n3), 1);
     1405  checkGraphOutArcList(adaptor, adaptor.inNode(n4), 1);
     1406  checkGraphOutArcList(adaptor, adaptor.outNode(n4), 2);
     1407
     1408  checkGraphInArcList(adaptor, adaptor.inNode(n1), 1);
     1409  checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
     1410  checkGraphInArcList(adaptor, adaptor.inNode(n2), 2);
     1411  checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
     1412  checkGraphInArcList(adaptor, adaptor.inNode(n3), 1);
     1413  checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
     1414  checkGraphInArcList(adaptor, adaptor.inNode(n4), 0);
     1415  checkGraphInArcList(adaptor, adaptor.outNode(n4), 1);
    14221416
    14231417  checkNodeIds(adaptor);
     
    14421436  checkGraphArcMap(uadaptor);
    14431437
    1444   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n1), 2);
    1445   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n1), 2);
    1446   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n2), 3);
    1447   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n2), 1);
    1448   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n3), 2);
    1449   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n3), 2);
    1450   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n4), 1);
    1451   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n4), 3);
    1452 
    1453   // Check uuadaptor
    1454   checkGraphNodeList(uuadaptor, 8);
    1455   checkGraphEdgeList(uuadaptor, 16);
    1456   checkGraphArcList(uuadaptor, 32);
    1457   checkGraphConEdgeList(uuadaptor, 16);
    1458   checkGraphConArcList(uuadaptor, 32);
    1459 
    1460   checkNodeIds(uuadaptor);
    1461   checkEdgeIds(uuadaptor);
    1462   checkArcIds(uuadaptor);
    1463 
    1464   checkGraphNodeMap(uuadaptor);
    1465   checkGraphEdgeMap(uuadaptor);
    1466   checkGraphArcMap(uuadaptor);
     1438  checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n1), 2);
     1439  checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n1), 2);
     1440  checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n2), 3);
     1441  checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n2), 1);
     1442  checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n3), 2);
     1443  checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n3), 2);
     1444  checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n4), 1);
     1445  checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n4), 3);
    14671446}
    14681447
  • test/bfs_test.cc

    r970 r983  
    6262  Arc e;
    6363  int l, i;
    64   ignore_unused_variable_warning(l,i);
     64  ::lemon::ignore_unused_variable_warning(l,i);
    6565  bool b;
    6666  BType::DistMap d(G);
     
    152152  Digraph g;
    153153  bool b;
    154   ignore_unused_variable_warning(b);
     154  ::lemon::ignore_unused_variable_warning(b);
    155155
    156156  bfs(g).run(Node());
  • test/bfs_test.cc

    r982 r983  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8585    b = const_bfs_test.emptyQueue();
    8686    i = const_bfs_test.queueSize();
    87    
     87
    8888    bfs_test.start();
    8989    bfs_test.start(t);
     
    106106      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
    107107      ::Create bfs_test(G);
    108      
     108
    109109    concepts::ReadWriteMap<Node,Arc> pred_map;
    110110    concepts::ReadWriteMap<Node,int> dist_map;
    111111    concepts::ReadWriteMap<Node,bool> reached_map;
    112112    concepts::WriteMap<Node,bool> processed_map;
    113    
     113
    114114    bfs_test
    115115      .predMap(pred_map)
     
    121121    bfs_test.run(s,t);
    122122    bfs_test.run();
    123    
     123
    124124    bfs_test.init();
    125125    bfs_test.addSource(s);
     
    130130    b = bfs_test.emptyQueue();
    131131    i = bfs_test.queueSize();
    132    
     132
    133133    bfs_test.start();
    134134    bfs_test.start(t);
  • test/circulation_test.cc

    r970 r983  
    7474  VType v;
    7575  bool b;
    76   ignore_unused_variable_warning(v,b);
     76  ::lemon::ignore_unused_variable_warning(v,b);
    7777
    7878  typedef Circulation<Digraph, CapMap, CapMap, SupplyMap>
     
    105105  const_circ_test.barrierMap(bar);
    106106
    107   ignore_unused_variable_warning(fm);
     107  ::lemon::ignore_unused_variable_warning(fm);
    108108}
    109109
  • test/circulation_test.cc

    r982 r983  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8383  CirculationType circ_test(g, lcap, ucap, supply);
    8484  const CirculationType& const_circ_test = circ_test;
    85    
     85
    8686  circ_test
    8787    .lowerMap(lcap)
     
    8989    .supplyMap(supply)
    9090    .flowMap(flow);
     91
     92  const CirculationType::Elevator& elev = const_circ_test.elevator();
     93  circ_test.elevator(const_cast<CirculationType::Elevator&>(elev));
     94  CirculationType::Tolerance tol = const_circ_test.tolerance();
     95  circ_test.tolerance(tol);
    9196
    9297  circ_test.init();
     
    99104  b = const_circ_test.barrier(n);
    100105  const_circ_test.barrierMap(bar);
    101  
     106
    102107  ::lemon::ignore_unused_variable_warning(fm);
    103108}
  • test/connectivity_test.cc

    r964 r983  
    6969    Graph g(d);
    7070    Digraph::Node n = d.addNode();
    71     ignore_unused_variable_warning(n);
     71    ::lemon::ignore_unused_variable_warning(n);
    7272
    7373    check(stronglyConnected(d), "This digraph is strongly connected");
     
    247247    Digraph::Node watch = d.addNode();
    248248    Digraph::Node pants = d.addNode();
    249     ignore_unused_variable_warning(watch);
     249    ::lemon::ignore_unused_variable_warning(watch);
    250250
    251251    d.addArc(socks, shoe);
  • test/connectivity_test.cc

    r982 r983  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3030  typedef ListDigraph Digraph;
    3131  typedef Undirector<Digraph> Graph;
    32  
    33   {
    34     Digraph d;
    35     Digraph::NodeMap<int> order(d);
    36     Graph g(d);
    37    
     32
     33  {
     34    Digraph d;
     35    Digraph::NodeMap<int> order(d);
     36    Graph g(d);
     37
    3838    check(stronglyConnected(d), "The empty digraph is strongly connected");
    3939    check(countStronglyConnectedComponents(d) == 0,
     
    4949    check(countBiEdgeConnectedComponents(g) == 0,
    5050          "The empty graph has 0 bi-edge-connected component");
    51          
     51
    5252    check(dag(d), "The empty digraph is DAG.");
    5353    check(checkedTopologicalSort(d, order), "The empty digraph is DAG.");
     
    8484    check(countBiEdgeConnectedComponents(g) == 1,
    8585          "This graph has 1 bi-edge-connected component");
    86          
     86
    8787    check(dag(d), "This digraph is DAG.");
    8888    check(checkedTopologicalSort(d, order), "This digraph is DAG.");
     
    103103    Digraph::NodeMap<int> order(d);
    104104    Graph g(d);
    105    
     105
    106106    Digraph::Node n1 = d.addNode();
    107107    Digraph::Node n2 = d.addNode();
     
    110110    Digraph::Node n5 = d.addNode();
    111111    Digraph::Node n6 = d.addNode();
    112    
     112
    113113    d.addArc(n1, n3);
    114114    d.addArc(n3, n2);
     
    138138    check(!parallelFree(g), "This graph is not parallel-free.");
    139139    check(!simpleGraph(g), "This graph is not simple.");
    140    
     140
    141141    d.addArc(n3, n3);
    142    
     142
    143143    check(!loopFree(d), "This digraph is not loop-free.");
    144144    check(!loopFree(g), "This graph is not loop-free.");
    145145    check(!simpleGraph(d), "This digraph is not simple.");
    146    
     146
    147147    d.addArc(n3, n2);
    148    
     148
    149149    check(!parallelFree(d), "This digraph is not parallel-free.");
    150150  }
    151  
     151
    152152  {
    153153    Digraph d;
    154154    Digraph::ArcMap<bool> cutarcs(d, false);
    155155    Graph g(d);
    156    
     156
    157157    Digraph::Node n1 = d.addNode();
    158158    Digraph::Node n2 = d.addNode();
     
    174174    d.addArc(n6, n7);
    175175    d.addArc(n7, n6);
    176    
     176
    177177    check(!stronglyConnected(d), "This digraph is not strongly connected");
    178178    check(countStronglyConnectedComponents(d) == 3,
     
    237237    Digraph d;
    238238    Digraph::NodeMap<int> order(d);
    239    
     239
    240240    Digraph::Node belt = d.addNode();
    241241    Digraph::Node trousers = d.addNode();
     
    258258    d.addArc(shirt, necktie);
    259259    d.addArc(necktie, coat);
    260    
     260
    261261    check(dag(d), "This digraph is DAG.");
    262262    topologicalSort(d, order);
     
    270270    ListGraph g;
    271271    ListGraph::NodeMap<bool> map(g);
    272    
     272
    273273    ListGraph::Node n1 = g.addNode();
    274274    ListGraph::Node n2 = g.addNode();
     
    286286    g.addEdge(n4, n7);
    287287    g.addEdge(n5, n7);
    288    
     288
    289289    check(bipartite(g), "This graph is bipartite");
    290290    check(bipartitePartitions(g, map), "This graph is bipartite");
    291    
     291
    292292    check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
    293293          "Wrong bipartitePartitions()");
  • test/dfs_test.cc

    r970 r983  
    6868  int l, i;
    6969  bool b;
    70   ignore_unused_variable_warning(l,i,b);
     70  ::lemon::ignore_unused_variable_warning(l,i,b);
    7171
    7272  DType::DistMap d(G);
     
    154154  Digraph g;
    155155  bool b;
    156   ignore_unused_variable_warning(b);
     156  ::lemon::ignore_unused_variable_warning(b);
    157157
    158158  dfs(g).run(Node());
  • test/dfs_test.cc

    r982 r983  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8989    b = const_dfs_test.emptyQueue();
    9090    i = const_dfs_test.queueSize();
    91    
     91
    9292    dfs_test.start();
    9393    dfs_test.start(t);
     
    115115    concepts::ReadWriteMap<Node,bool> reached_map;
    116116    concepts::WriteMap<Node,bool> processed_map;
    117    
     117
    118118    dfs_test
    119119      .predMap(pred_map)
     
    132132    b = dfs_test.emptyQueue();
    133133    i = dfs_test.queueSize();
    134    
     134
    135135    dfs_test.start();
    136136    dfs_test.start(t);
  • test/digraph_test.cc

    r965 r983  
    6565      a3 = G.addArc(n2, n3),
    6666      a4 = G.addArc(n2, n3);
    67   ignore_unused_variable_warning(a2,a3,a4);
     67  ::lemon::ignore_unused_variable_warning(a2,a3,a4);
    6868
    6969  checkGraphNodeList(G, 3);
     
    9494  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
    9595      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
    96   ignore_unused_variable_warning(a1,a2,a3,a4);
     96  ::lemon::ignore_unused_variable_warning(a1,a2,a3,a4);
    9797
    9898  Node n4 = G.split(n2);
     
    128128      a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),
    129129      a5 = G.addArc(n2, n4);
    130   ignore_unused_variable_warning(a1,a2,a3,a5);
     130  ::lemon::ignore_unused_variable_warning(a1,a2,a3,a5);
    131131
    132132  checkGraphNodeList(G, 4);
     
    208208      a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1),
    209209      a5 = G.addArc(n2, n4);
    210   ignore_unused_variable_warning(a2,a3,a4,a5);
     210  ::lemon::ignore_unused_variable_warning(a2,a3,a4,a5);
    211211
    212212  // Check arc deletion
     
    256256  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
    257257      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
    258   ignore_unused_variable_warning(a1,a2,a3,a4);
     258  ::lemon::ignore_unused_variable_warning(a1,a2,a3,a4);
    259259
    260260  typename Digraph::Snapshot snapshot(G);
     
    357357    e1 = g.addArc(n1, n2),
    358358    e2 = g.addArc(n2, n3);
    359   ignore_unused_variable_warning(e2);
     359  ::lemon::ignore_unused_variable_warning(e2);
    360360
    361361  check(g.valid(n1), "Wrong validity check");
  • test/digraph_test.cc

    r982 r983  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2020#include <lemon/list_graph.h>
    2121#include <lemon/smart_graph.h>
     22#include <lemon/static_graph.h>
    2223#include <lemon/full_graph.h>
    2324
     
    3536  checkGraphNodeList(G, 0);
    3637  checkGraphArcList(G, 0);
     38
     39  G.reserveNode(3);
     40  G.reserveArc(4);
    3741
    3842  Node
     
    289293
    290294  snapshot.restore();
     295  snapshot.save(G);
     296
     297  checkGraphNodeList(G, 4);
     298  checkGraphArcList(G, 4);
     299
     300  G.addArc(G.addNode(), G.addNode());
     301
     302  snapshot.restore();
    291303
    292304  checkGraphNodeList(G, 4);
     
    323335    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
    324336  }
     337  { // Checking StaticDigraph
     338    checkConcept<Digraph, StaticDigraph>();
     339    checkConcept<ClearableDigraphComponent<>, StaticDigraph>();
     340  }
    325341  { // Checking FullDigraph
    326342    checkConcept<Digraph, FullDigraph>();
     
    379395}
    380396
     397void checkStaticDigraph() {
     398  SmartDigraph g;
     399  SmartDigraph::NodeMap<StaticDigraph::Node> nref(g);
     400  SmartDigraph::ArcMap<StaticDigraph::Arc> aref(g);
     401
     402  StaticDigraph G;
     403
     404  checkGraphNodeList(G, 0);
     405  checkGraphArcList(G, 0);
     406
     407  G.build(g, nref, aref);
     408
     409  checkGraphNodeList(G, 0);
     410  checkGraphArcList(G, 0);
     411
     412  SmartDigraph::Node
     413    n1 = g.addNode(),
     414    n2 = g.addNode(),
     415    n3 = g.addNode();
     416
     417  G.build(g, nref, aref);
     418
     419  checkGraphNodeList(G, 3);
     420  checkGraphArcList(G, 0);
     421
     422  SmartDigraph::Arc a1 = g.addArc(n1, n2);
     423
     424  G.build(g, nref, aref);
     425
     426  check(G.source(aref[a1]) == nref[n1] && G.target(aref[a1]) == nref[n2],
     427        "Wrong arc or wrong references");
     428  checkGraphNodeList(G, 3);
     429  checkGraphArcList(G, 1);
     430
     431  checkGraphOutArcList(G, nref[n1], 1);
     432  checkGraphOutArcList(G, nref[n2], 0);
     433  checkGraphOutArcList(G, nref[n3], 0);
     434
     435  checkGraphInArcList(G, nref[n1], 0);
     436  checkGraphInArcList(G, nref[n2], 1);
     437  checkGraphInArcList(G, nref[n3], 0);
     438
     439  checkGraphConArcList(G, 1);
     440
     441  SmartDigraph::Arc
     442    a2 = g.addArc(n2, n1),
     443    a3 = g.addArc(n2, n3),
     444    a4 = g.addArc(n2, n3);
     445  ignore_unused_variable_warning(a2,a3,a4);
     446
     447  digraphCopy(g, G).nodeRef(nref).run();
     448
     449  checkGraphNodeList(G, 3);
     450  checkGraphArcList(G, 4);
     451
     452  checkGraphOutArcList(G, nref[n1], 1);
     453  checkGraphOutArcList(G, nref[n2], 3);
     454  checkGraphOutArcList(G, nref[n3], 0);
     455
     456  checkGraphInArcList(G, nref[n1], 1);
     457  checkGraphInArcList(G, nref[n2], 1);
     458  checkGraphInArcList(G, nref[n3], 2);
     459
     460  checkGraphConArcList(G, 4);
     461
     462  std::vector<std::pair<int,int> > arcs;
     463  arcs.push_back(std::make_pair(0,1));
     464  arcs.push_back(std::make_pair(0,2));
     465  arcs.push_back(std::make_pair(1,3));
     466  arcs.push_back(std::make_pair(1,2));
     467  arcs.push_back(std::make_pair(3,0));
     468  arcs.push_back(std::make_pair(3,3));
     469  arcs.push_back(std::make_pair(4,2));
     470  arcs.push_back(std::make_pair(4,3));
     471  arcs.push_back(std::make_pair(4,1));
     472
     473  G.build(6, arcs.begin(), arcs.end());
     474
     475  checkGraphNodeList(G, 6);
     476  checkGraphArcList(G, 9);
     477
     478  checkGraphOutArcList(G, G.node(0), 2);
     479  checkGraphOutArcList(G, G.node(1), 2);
     480  checkGraphOutArcList(G, G.node(2), 0);
     481  checkGraphOutArcList(G, G.node(3), 2);
     482  checkGraphOutArcList(G, G.node(4), 3);
     483  checkGraphOutArcList(G, G.node(5), 0);
     484
     485  checkGraphInArcList(G, G.node(0), 1);
     486  checkGraphInArcList(G, G.node(1), 2);
     487  checkGraphInArcList(G, G.node(2), 3);
     488  checkGraphInArcList(G, G.node(3), 3);
     489  checkGraphInArcList(G, G.node(4), 0);
     490  checkGraphInArcList(G, G.node(5), 0);
     491
     492  checkGraphConArcList(G, 9);
     493
     494  checkNodeIds(G);
     495  checkArcIds(G);
     496  checkGraphNodeMap(G);
     497  checkGraphArcMap(G);
     498
     499  int n = G.nodeNum();
     500  int m = G.arcNum();
     501  check(G.index(G.node(n-1)) == n-1, "Wrong index.");
     502  check(G.index(G.arc(m-1)) == m-1, "Wrong index.");
     503}
     504
    381505void checkFullDigraph(int num) {
    382506  typedef FullDigraph Digraph;
    383507  DIGRAPH_TYPEDEFS(Digraph);
     508
    384509  Digraph G(num);
     510  check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
     511
     512  G.resize(num);
     513  check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
    385514
    386515  checkGraphNodeList(G, num);
     
    426555    checkDigraphValidity<SmartDigraph>();
    427556  }
     557  { // Checking StaticDigraph
     558    checkStaticDigraph();
     559  }
    428560  { // Checking FullDigraph
    429561    checkFullDigraph(8);
  • test/dijkstra_test.cc

    r970 r983  
    6666  int i;
    6767  bool b;
    68   ignore_unused_variable_warning(l,i,b);
     68  ::lemon::ignore_unused_variable_warning(l,i,b);
    6969
    7070  DType::DistMap d(G);
     
    165165  Digraph g;
    166166  bool b;
    167   ignore_unused_variable_warning(b);
     167  ::lemon::ignore_unused_variable_warning(b);
    168168
    169169  dijkstra(g,LengthMap()).run(Node());
  • test/dijkstra_test.cc

    r982 r983  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8888    b = const_dijkstra_test.emptyQueue();
    8989    i = const_dijkstra_test.queueSize();
    90    
     90
    9191    dijkstra_test.start();
    9292    dijkstra_test.start(t);
     
    112112      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
    113113      ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
    114       ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> >, 
     114      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> >,
    115115                concepts::ReadWriteMap<Node,int> >
    116116      ::Create dijkstra_test(G,length);
     
    122122    concepts::ReadWriteMap<Node,int> heap_cross_ref;
    123123    BinHeap<VType, concepts::ReadWriteMap<Node,int> > heap(heap_cross_ref);
    124    
     124
    125125    dijkstra_test
    126126      .lengthMap(length_map)
     
    139139    b = dijkstra_test.emptyQueue();
    140140    i = dijkstra_test.queueSize();
    141    
     141
    142142    dijkstra_test.start();
    143143    dijkstra_test.start(t);
  • test/edge_set_test.cc

    r964 r983  
    4545
    4646  Digraph::Arc ga1 = digraph.addArc(n1, n2);
    47   ignore_unused_variable_warning(ga1);
     47  ::lemon::ignore_unused_variable_warning(ga1);
    4848
    4949  ArcSet arc_set(digraph);
    5050
    5151  Digraph::Arc ga2 = digraph.addArc(n2, n1);
    52   ignore_unused_variable_warning(ga2);
     52  ::lemon::ignore_unused_variable_warning(ga2);
    5353
    5454  checkGraphNodeList(arc_set, 2);
     
    7878    a3 = arc_set.addArc(n2, n3),
    7979    a4 = arc_set.addArc(n2, n3);
    80   ignore_unused_variable_warning(a2,a3,a4);
     80  ::lemon::ignore_unused_variable_warning(a2,a3,a4);
    8181
    8282  checkGraphNodeList(arc_set, 3);
     
    115115
    116116  Digraph::Arc ga1 = digraph.addArc(n1, n2);
    117   ignore_unused_variable_warning(ga1);
     117  ::lemon::ignore_unused_variable_warning(ga1);
    118118
    119119  ArcSet arc_set(digraph);
    120120
    121121  Digraph::Arc ga2 = digraph.addArc(n2, n1);
    122   ignore_unused_variable_warning(ga2);
     122  ::lemon::ignore_unused_variable_warning(ga2);
    123123
    124124  checkGraphNodeList(arc_set, 2);
     
    148148    a3 = arc_set.addArc(n2, n3),
    149149    a4 = arc_set.addArc(n2, n3);
    150   ignore_unused_variable_warning(a2,a3,a4);
     150  ::lemon::ignore_unused_variable_warning(a2,a3,a4);
    151151
    152152  checkGraphNodeList(arc_set, 3);
     
    199199
    200200  Digraph::Arc ga1 = digraph.addArc(n1, n2);
    201   ignore_unused_variable_warning(ga1);
     201  ::lemon::ignore_unused_variable_warning(ga1);
    202202
    203203  EdgeSet edge_set(digraph);
    204204
    205205  Digraph::Arc ga2 = digraph.addArc(n2, n1);
    206   ignore_unused_variable_warning(ga2);
     206  ::lemon::ignore_unused_variable_warning(ga2);
    207207
    208208  checkGraphNodeList(edge_set, 2);
     
    241241    e3 = edge_set.addEdge(n2, n3),
    242242    e4 = edge_set.addEdge(n2, n3);
    243   ignore_unused_variable_warning(e2,e3,e4);
     243  ::lemon::ignore_unused_variable_warning(e2,e3,e4);
    244244
    245245  checkGraphNodeList(edge_set, 3);
     
    287287
    288288  Digraph::Arc ga1 = digraph.addArc(n1, n2);
    289   ignore_unused_variable_warning(ga1);
     289  ::lemon::ignore_unused_variable_warning(ga1);
    290290
    291291  EdgeSet edge_set(digraph);
    292292
    293293  Digraph::Arc ga2 = digraph.addArc(n2, n1);
    294   ignore_unused_variable_warning(ga2);
     294  ::lemon::ignore_unused_variable_warning(ga2);
    295295
    296296  checkGraphNodeList(edge_set, 2);
     
    329329    e3 = edge_set.addEdge(n2, n3),
    330330    e4 = edge_set.addEdge(n2, n3);
    331   ignore_unused_variable_warning(e2,e3,e4);
     331  ::lemon::ignore_unused_variable_warning(e2,e3,e4);
    332332
    333333  checkGraphNodeList(edge_set, 3);
  • test/edge_set_test.cc

    r982 r983  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • test/euler_test.cc

    r964 r983  
    102102    Graph g(d);
    103103    Digraph::Node n = d.addNode();
    104     ignore_unused_variable_warning(n);
     104    ::lemon::ignore_unused_variable_warning(n);
    105105 
    106106    checkDiEulerIt(d);
     
    191191    Digraph::Node n4 = d.addNode();
    192192    Digraph::Node n5 = d.addNode();
    193     ignore_unused_variable_warning(n0,n4,n5);
     193    ::lemon::ignore_unused_variable_warning(n0,n4,n5);
    194194
    195195    d.addArc(n1, n2);
  • test/euler_test.cc

    r982 r983  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8686  typedef ListDigraph Digraph;
    8787  typedef Undirector<Digraph> Graph;
    88  
    89   {
    90     Digraph d;
    91     Graph g(d);
    92    
     88
     89  {
     90    Digraph d;
     91    Graph g(d);
     92
    9393    checkDiEulerIt(d);
    9494    checkDiEulerIt(g);
     
    130130    Digraph::Node n2 = d.addNode();
    131131    Digraph::Node n3 = d.addNode();
    132    
     132
    133133    d.addArc(n1, n2);
    134134    d.addArc(n2, n1);
     
    155155    Digraph::Node n5 = d.addNode();
    156156    Digraph::Node n6 = d.addNode();
    157    
     157
    158158    d.addArc(n1, n2);
    159159    d.addArc(n2, n4);
     
    214214    Digraph::Node n2 = d.addNode();
    215215    Digraph::Node n3 = d.addNode();
    216    
     216
    217217    d.addArc(n1, n2);
    218218    d.addArc(n2, n3);
  • test/gomory_hu_test.cc

    r970 r983  
    6969  Value v;
    7070  int d;
    71   ignore_unused_variable_warning(v,d);
     71  ::lemon::ignore_unused_variable_warning(v,d);
    7272
    7373  GomoryHu<Graph, CapMap> gh_test(g, cap);
  • test/gomory_hu_test.cc

    r982 r983  
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
     4 *
     5 * Copyright (C) 2003-2010
     6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8 *
     9 * Permission to use, modify and distribute this software is granted
     10 * provided that this copyright notice appears in all copies. For
     11 * precise terms see the accompanying LICENSE file.
     12 *
     13 * This software is provided "AS IS" with no warranty of any kind,
     14 * express or implied, and with no claim as to its suitability for any
     15 * purpose.
     16 *
     17 */
     18
    119#include <iostream>
    220
     
    3452  "source 0\n"
    3553  "target 3\n";
    36  
     54
    3755void checkGomoryHuCompile()
    3856{
     
    7189
    7290int cutValue(const Graph& graph, const BoolNodeMap& cut,
    73              const IntEdgeMap& capacity) {
     91             const IntEdgeMap& capacity) {
    7492
    7593  int sum = 0;
     
    109127      int sum=0;
    110128      for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
    111         sum+=capacity[a]; 
     129        sum+=capacity[a];
    112130      check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
    113131
     
    120138    }
    121139  }
    122  
     140
    123141  return 0;
    124142}
  • test/graph_test.cc

    r964 r983  
    6767  Edge e2 = G.addEdge(n2, n1),
    6868       e3 = G.addEdge(n2, n3);
    69   ignore_unused_variable_warning(e2,e3);
     69  ::lemon::ignore_unused_variable_warning(e2,e3);
    7070
    7171  checkGraphNodeList(G, 3);
     
    100100       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
    101101       e5 = G.addEdge(n4, n3);
    102   ignore_unused_variable_warning(e1,e3,e4,e5);
     102  ::lemon::ignore_unused_variable_warning(e1,e3,e4,e5);
    103103
    104104  checkGraphNodeList(G, 4);
     
    180180       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
    181181       e5 = G.addEdge(n4, n3);
    182   ignore_unused_variable_warning(e1,e3,e4,e5);
     182  ::lemon::ignore_unused_variable_warning(e1,e3,e4,e5);
    183183
    184184  // Check edge deletion
     
    221221  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
    222222       e3 = G.addEdge(n2, n3);
    223   ignore_unused_variable_warning(e1,e2,e3);
     223  ::lemon::ignore_unused_variable_warning(e1,e2,e3);
    224224
    225225  checkGraphNodeList(G, 3);
     
    386386    e1 = g.addEdge(n1, n2),
    387387    e2 = g.addEdge(n2, n3);
    388   ignore_unused_variable_warning(e2);
     388  ::lemon::ignore_unused_variable_warning(e2);
    389389
    390390  check(g.valid(n1), "Wrong validity check");
     
    525525
    526526  Node n = G.nodeFromId(dim);
    527   ignore_unused_variable_warning(n);
     527  ::lemon::ignore_unused_variable_warning(n);
    528528
    529529  for (NodeIt n(G); n != INVALID; ++n) {
  • test/graph_test.cc

    r982 r983  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3939  checkGraphArcList(G, 0);
    4040
     41  G.reserveNode(3);
     42  G.reserveEdge(3);
     43
    4144  Node
    4245    n1 = G.addNode(),
     
    261264
    262265  snapshot.restore();
     266  snapshot.save(G);
    263267
    264268  checkGraphNodeList(G, 4);
    265269  checkGraphEdgeList(G, 3);
    266270  checkGraphArcList(G, 6);
     271
     272  G.addEdge(G.addNode(), G.addNode());
     273
     274  snapshot.restore();
     275
     276  checkGraphNodeList(G, 4);
     277  checkGraphEdgeList(G, 3);
     278  checkGraphArcList(G, 6);
    267279}
    268280
     
    272284
    273285  Graph G(num);
     286  check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
     287        "Wrong size");
     288
     289  G.resize(num);
     290  check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
     291        "Wrong size");
     292
    274293  checkGraphNodeList(G, num);
    275294  checkGraphEdgeList(G, num * (num - 1) / 2);
     
    417436  check(G.height() == height, "Wrong row number");
    418437
     438  G.resize(width, height);
     439  check(G.width() == width, "Wrong column number");
     440  check(G.height() == height, "Wrong row number");
     441
    419442  for (int i = 0; i < width; ++i) {
    420443    for (int j = 0; j < height; ++j) {
     
    492515
    493516  HypercubeGraph G(dim);
     517  check(G.dimension() == dim, "Wrong dimension");
     518
     519  G.resize(dim);
     520  check(G.dimension() == dim, "Wrong dimension");
     521
    494522  checkGraphNodeList(G, 1 << dim);
    495523  checkGraphEdgeList(G, dim * (1 << (dim-1)));
  • test/hao_orlin_test.cc

    r970 r983  
    6767  CutMap cut;
    6868  Value v;
    69   ignore_unused_variable_warning(v);
     69  ::lemon::ignore_unused_variable_warning(v);
    7070
    7171  HaoOrlin<Digraph, CapMap> ho_test(g, cap);
  • test/hao_orlin_test.cc

    r982 r983  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8585
    8686template <typename Graph, typename CapMap, typename CutMap>
    87 typename CapMap::Value 
     87typename CapMap::Value
    8888  cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut)
    8989{
     
    112112    ho.run();
    113113    ho.minCutMap(cut);
    114    
     114
    115115    check(ho.minCutValue() == 1, "Wrong cut value");
    116116    check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");
     
    128128    ho.run();
    129129    ho.minCutMap(cut);
    130    
     130
    131131    check(ho.minCutValue() == 1, "Wrong cut value");
    132132    check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value");
    133133  }
    134  
     134
    135135  typedef Undirector<SmartDigraph> UGraph;
    136136  UGraph ugraph(graph);
    137  
     137
    138138  {
    139139    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap1);
    140140    ho.run();
    141141    ho.minCutMap(cut);
    142    
     142
    143143    check(ho.minCutValue() == 2, "Wrong cut value");
    144144    check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value");
     
    148148    ho.run();
    149149    ho.minCutMap(cut);
    150    
     150
    151151    check(ho.minCutValue() == 5, "Wrong cut value");
    152152    check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value");
     
    156156    ho.run();
    157157    ho.minCutMap(cut);
    158    
     158
    159159    check(ho.minCutValue() == 5, "Wrong cut value");
    160160    check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value");
  • test/maps_test.cc

    r964 r983  
    104104    NullMap<A,B> map1;
    105105    NullMap<A,B> map2 = map1;
    106     ignore_unused_variable_warning(map2);
     106    ::lemon::ignore_unused_variable_warning(map2);
    107107    map1 = nullMap<A,B>();
    108108  }
     
    115115    ConstMap<A,B> map2 = B();
    116116    ConstMap<A,B> map3 = map1;
    117     ignore_unused_variable_warning(map2,map3);
     117    ::lemon::ignore_unused_variable_warning(map2,map3);
    118118
    119119    map1 = constMap<A>(B());
     
    122122    ConstMap<A,C> map4(C(1));
    123123    ConstMap<A,C> map5 = map4;
    124     ignore_unused_variable_warning(map5);
     124    ::lemon::ignore_unused_variable_warning(map5);
    125125
    126126    map4 = constMap<A>(C(2));
     
    144144    IdentityMap<A> map1;
    145145    IdentityMap<A> map2 = map1;
    146     ignore_unused_variable_warning(map2);
     146    ::lemon::ignore_unused_variable_warning(map2);
    147147
    148148    map1 = identityMap<A>();
     
    205205    checkConcept<ReadMap<B,double>, CompMap>();
    206206    CompMap map1 = CompMap(DoubleMap(),ReadMap<B,A>());
    207     ignore_unused_variable_warning(map1);
     207    ::lemon::ignore_unused_variable_warning(map1);
    208208    CompMap map2 = composeMap(DoubleMap(), ReadMap<B,A>());
    209     ignore_unused_variable_warning(map2);
     209    ::lemon::ignore_unused_variable_warning(map2);
    210210
    211211    SparseMap<double, bool> m1(false); m1[3.14] = true;
     
    220220    checkConcept<ReadMap<A,double>, CombMap>();
    221221    CombMap map1 = CombMap(DoubleMap(), DoubleMap());
    222     ignore_unused_variable_warning(map1);
     222    ::lemon::ignore_unused_variable_warning(map1);
    223223    CombMap map2 = combineMap(DoubleMap(), DoubleMap(), std::plus<double>());
    224     ignore_unused_variable_warning(map2);
     224    ::lemon::ignore_unused_variable_warning(map2);
    225225
    226226    check(combineMap(constMap<B,int,2>(), identityMap<B>(), &binc)[B()] == 3,
     
    234234    FunctorToMap<F> map1;
    235235    FunctorToMap<F> map2 = FunctorToMap<F>(F());
    236     ignore_unused_variable_warning(map2);
     236    ::lemon::ignore_unused_variable_warning(map2);
    237237
    238238    B b = functorToMap(F())[A()];
    239     ignore_unused_variable_warning(b);
     239    ::lemon::ignore_unused_variable_warning(b);
    240240
    241241    checkConcept<ReadMap<A,B>, MapToFunctor<ReadMap<A,B> > >();
    242242    MapToFunctor<ReadMap<A,B> > map =
    243243      MapToFunctor<ReadMap<A,B> >(ReadMap<A,B>());
    244     ignore_unused_variable_warning(map);
     244    ::lemon::ignore_unused_variable_warning(map);
    245245
    246246    check(functorToMap(&func)[A()] == 3,
     
    260260      ConvertMap<ReadMap<double, int>, double> >();
    261261    ConvertMap<RangeMap<bool>, int> map1(rangeMap(1, true));
    262     ignore_unused_variable_warning(map1);
     262    ::lemon::ignore_unused_variable_warning(map1);
    263263    ConvertMap<RangeMap<bool>, int> map2 = convertMap<int>(rangeMap(2, false));
    264     ignore_unused_variable_warning(map2);
     264    ::lemon::ignore_unused_variable_warning(map2);
    265265
    266266  }
  • test/maps_test.cc

    r982 r983  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2424#include <lemon/maps.h>
    2525#include <lemon/list_graph.h>
     26#include <lemon/smart_graph.h>
     27#include <lemon/adaptors.h>
     28#include <lemon/dfs.h>
     29#include <algorithm>
    2630
    2731#include "test_tools.h"
     
    3539
    3640class C {
    37   int x;
     41  int _x;
    3842public:
    39   C(int _x) : x(_x) {}
     43  C(int x) : _x(x) {}
     44  int get() const { return _x; }
     45};
     46inline bool operator<(C c1, C c2) { return c1.get() < c2.get(); }
     47inline bool operator==(C c1, C c2) { return c1.get() == c2.get(); }
     48
     49C createC(int x) { return C(x); }
     50
     51template <typename T>
     52class Less {
     53  T _t;
     54public:
     55  Less(T t): _t(t) {}
     56  bool operator()(const T& t) const { return t < _t; }
    4057};
    4158
     
    5370
    5471int binc(int a, B) { return a+1; }
     72
     73template <typename T>
     74class Sum {
     75  T& _sum;
     76public:
     77  Sum(T& sum) : _sum(sum) {}
     78  void operator()(const T& t) { _sum += t; }
     79};
    5580
    5681typedef ReadMap<A, double> DoubleMap;
     
    349374  {
    350375    typedef std::vector<int> vec;
     376    checkConcept<WriteMap<int, bool>, LoggerBoolMap<vec::iterator> >();
     377    checkConcept<WriteMap<int, bool>,
     378                 LoggerBoolMap<std::back_insert_iterator<vec> > >();
     379
    351380    vec v1;
    352381    vec v2(10);
     
    368397          it != map2.end(); ++it )
    369398      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
    370   }
    371  
    372   // CrossRefMap
    373   {
     399
    374400    typedef ListDigraph Graph;
    375401    DIGRAPH_TYPEDEFS(Graph);
     402    Graph gr;
     403
     404    Node n0 = gr.addNode();
     405    Node n1 = gr.addNode();
     406    Node n2 = gr.addNode();
     407    Node n3 = gr.addNode();
     408
     409    gr.addArc(n3, n0);
     410    gr.addArc(n3, n2);
     411    gr.addArc(n0, n2);
     412    gr.addArc(n2, n1);
     413    gr.addArc(n0, n1);
     414
     415    {
     416      std::vector<Node> v;
     417      dfs(gr).processedMap(loggerBoolMap(std::back_inserter(v))).run();
     418
     419      check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3,
     420            "Something is wrong with LoggerBoolMap");
     421    }
     422    {
     423      std::vector<Node> v(countNodes(gr));
     424      dfs(gr).processedMap(loggerBoolMap(v.begin())).run();
     425
     426      check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3,
     427            "Something is wrong with LoggerBoolMap");
     428    }
     429  }
     430
     431  // IdMap, RangeIdMap
     432  {
     433    typedef ListDigraph Graph;
     434    DIGRAPH_TYPEDEFS(Graph);
     435
     436    checkConcept<ReadMap<Node, int>, IdMap<Graph, Node> >();
     437    checkConcept<ReadMap<Arc, int>, IdMap<Graph, Arc> >();
     438    checkConcept<ReadMap<Node, int>, RangeIdMap<Graph, Node> >();
     439    checkConcept<ReadMap<Arc, int>, RangeIdMap<Graph, Arc> >();
     440
     441    Graph gr;
     442    IdMap<Graph, Node> nmap(gr);
     443    IdMap<Graph, Arc> amap(gr);
     444    RangeIdMap<Graph, Node> nrmap(gr);
     445    RangeIdMap<Graph, Arc> armap(gr);
     446
     447    Node n0 = gr.addNode();
     448    Node n1 = gr.addNode();
     449    Node n2 = gr.addNode();
     450
     451    Arc a0 = gr.addArc(n0, n1);
     452    Arc a1 = gr.addArc(n0, n2);
     453    Arc a2 = gr.addArc(n2, n1);
     454    Arc a3 = gr.addArc(n2, n0);
     455
     456    check(nmap[n0] == gr.id(n0) && nmap(gr.id(n0)) == n0, "Wrong IdMap");
     457    check(nmap[n1] == gr.id(n1) && nmap(gr.id(n1)) == n1, "Wrong IdMap");
     458    check(nmap[n2] == gr.id(n2) && nmap(gr.id(n2)) == n2, "Wrong IdMap");
     459
     460    check(amap[a0] == gr.id(a0) && amap(gr.id(a0)) == a0, "Wrong IdMap");
     461    check(amap[a1] == gr.id(a1) && amap(gr.id(a1)) == a1, "Wrong IdMap");
     462    check(amap[a2] == gr.id(a2) && amap(gr.id(a2)) == a2, "Wrong IdMap");
     463    check(amap[a3] == gr.id(a3) && amap(gr.id(a3)) == a3, "Wrong IdMap");
     464
     465    check(nmap.inverse()[gr.id(n0)] == n0, "Wrong IdMap::InverseMap");
     466    check(amap.inverse()[gr.id(a0)] == a0, "Wrong IdMap::InverseMap");
     467
     468    check(nrmap.size() == 3 && armap.size() == 4,
     469          "Wrong RangeIdMap::size()");
     470
     471    check(nrmap[n0] == 0 && nrmap(0) == n0, "Wrong RangeIdMap");
     472    check(nrmap[n1] == 1 && nrmap(1) == n1, "Wrong RangeIdMap");
     473    check(nrmap[n2] == 2 && nrmap(2) == n2, "Wrong RangeIdMap");
     474
     475    check(armap[a0] == 0 && armap(0) == a0, "Wrong RangeIdMap");
     476    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");
     477    check(armap[a2] == 2 && armap(2) == a2, "Wrong RangeIdMap");
     478    check(armap[a3] == 3 && armap(3) == a3, "Wrong RangeIdMap");
     479
     480    check(nrmap.inverse()[0] == n0, "Wrong RangeIdMap::InverseMap");
     481    check(armap.inverse()[0] == a0, "Wrong RangeIdMap::InverseMap");
     482
     483    gr.erase(n1);
     484
     485    if (nrmap[n0] == 1) nrmap.swap(n0, n2);
     486    nrmap.swap(n2, n0);
     487    if (armap[a1] == 1) armap.swap(a1, a3);
     488    armap.swap(a3, a1);
     489
     490    check(nrmap.size() == 2 && armap.size() == 2,
     491          "Wrong RangeIdMap::size()");
     492
     493    check(nrmap[n0] == 1 && nrmap(1) == n0, "Wrong RangeIdMap");
     494    check(nrmap[n2] == 0 && nrmap(0) == n2, "Wrong RangeIdMap");
     495
     496    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");
     497    check(armap[a3] == 0 && armap(0) == a3, "Wrong RangeIdMap");
     498
     499    check(nrmap.inverse()[0] == n2, "Wrong RangeIdMap::InverseMap");
     500    check(armap.inverse()[0] == a3, "Wrong RangeIdMap::InverseMap");
     501  }
     502
     503  // SourceMap, TargetMap, ForwardMap, BackwardMap, InDegMap, OutDegMap
     504  {
     505    typedef ListGraph Graph;
     506    GRAPH_TYPEDEFS(Graph);
     507
     508    checkConcept<ReadMap<Arc, Node>, SourceMap<Graph> >();
     509    checkConcept<ReadMap<Arc, Node>, TargetMap<Graph> >();
     510    checkConcept<ReadMap<Edge, Arc>, ForwardMap<Graph> >();
     511    checkConcept<ReadMap<Edge, Arc>, BackwardMap<Graph> >();
     512    checkConcept<ReadMap<Node, int>, InDegMap<Graph> >();
     513    checkConcept<ReadMap<Node, int>, OutDegMap<Graph> >();
     514
     515    Graph gr;
     516    Node n0 = gr.addNode();
     517    Node n1 = gr.addNode();
     518    Node n2 = gr.addNode();
     519
     520    gr.addEdge(n0,n1);
     521    gr.addEdge(n1,n2);
     522    gr.addEdge(n0,n2);
     523    gr.addEdge(n2,n1);
     524    gr.addEdge(n1,n2);
     525    gr.addEdge(n0,n1);
     526
     527    for (EdgeIt e(gr); e != INVALID; ++e) {
     528      check(forwardMap(gr)[e] == gr.direct(e, true), "Wrong ForwardMap");
     529      check(backwardMap(gr)[e] == gr.direct(e, false), "Wrong BackwardMap");
     530    }
     531
     532    check(mapCompare(gr,
     533          sourceMap(orienter(gr, constMap<Edge, bool>(true))),
     534          targetMap(orienter(gr, constMap<Edge, bool>(false)))),
     535          "Wrong SourceMap or TargetMap");
     536
     537    typedef Orienter<Graph, const ConstMap<Edge, bool> > Digraph;
     538    Digraph dgr(gr, constMap<Edge, bool>(true));
     539    OutDegMap<Digraph> odm(dgr);
     540    InDegMap<Digraph> idm(dgr);
     541
     542    check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 1, "Wrong OutDegMap");
     543    check(idm[n0] == 0 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");
     544
     545    gr.addEdge(n2, n0);
     546
     547    check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 2, "Wrong OutDegMap");
     548    check(idm[n0] == 1 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");
     549  }
     550
     551  // CrossRefMap
     552  {
     553    typedef ListDigraph Graph;
     554    DIGRAPH_TYPEDEFS(Graph);
    376555
    377556    checkConcept<ReadWriteMap<Node, int>,
    378557                 CrossRefMap<Graph, Node, int> >();
    379    
     558    checkConcept<ReadWriteMap<Node, bool>,
     559                 CrossRefMap<Graph, Node, bool> >();
     560    checkConcept<ReadWriteMap<Node, double>,
     561                 CrossRefMap<Graph, Node, double> >();
     562
     563    Graph gr;
     564    typedef CrossRefMap<Graph, Node, char> CRMap;
     565    CRMap map(gr);
     566
     567    Node n0 = gr.addNode();
     568    Node n1 = gr.addNode();
     569    Node n2 = gr.addNode();
     570
     571    map.set(n0, 'A');
     572    map.set(n1, 'B');
     573    map.set(n2, 'C');
     574
     575    check(map[n0] == 'A' && map('A') == n0 && map.inverse()['A'] == n0,
     576          "Wrong CrossRefMap");
     577    check(map[n1] == 'B' && map('B') == n1 && map.inverse()['B'] == n1,
     578          "Wrong CrossRefMap");
     579    check(map[n2] == 'C' && map('C') == n2 && map.inverse()['C'] == n2,
     580          "Wrong CrossRefMap");
     581    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,
     582          "Wrong CrossRefMap::count()");
     583
     584    CRMap::ValueIt it = map.beginValue();
     585    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
     586          it == map.endValue(), "Wrong value iterator");
     587
     588    map.set(n2, 'A');
     589
     590    check(map[n0] == 'A' && map[n1] == 'B' && map[n2] == 'A',
     591          "Wrong CrossRefMap");
     592    check(map('A') == n0 && map.inverse()['A'] == n0, "Wrong CrossRefMap");
     593    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
     594    check(map('C') == INVALID && map.inverse()['C'] == INVALID,
     595          "Wrong CrossRefMap");
     596    check(map.count('A') == 2 && map.count('B') == 1 && map.count('C') == 0,
     597          "Wrong CrossRefMap::count()");
     598
     599    it = map.beginValue();
     600    check(*it++ == 'A' && *it++ == 'A' && *it++ == 'B' &&
     601          it == map.endValue(), "Wrong value iterator");
     602
     603    map.set(n0, 'C');
     604
     605    check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',
     606          "Wrong CrossRefMap");
     607    check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");
     608    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
     609    check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");
     610    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,
     611          "Wrong CrossRefMap::count()");
     612
     613    it = map.beginValue();
     614    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
     615          it == map.endValue(), "Wrong value iterator");
     616  }
     617
     618  // CrossRefMap
     619  {
     620    typedef SmartDigraph Graph;
     621    DIGRAPH_TYPEDEFS(Graph);
     622
     623    checkConcept<ReadWriteMap<Node, int>,
     624                 CrossRefMap<Graph, Node, int> >();
     625
    380626    Graph gr;
    381627    typedef CrossRefMap<Graph, Node, char> CRMap;
    382628    typedef CRMap::ValueIterator ValueIt;
    383629    CRMap map(gr);
    384    
     630
    385631    Node n0 = gr.addNode();
    386632    Node n1 = gr.addNode();
    387633    Node n2 = gr.addNode();
    388    
     634
    389635    map.set(n0, 'A');
    390636    map.set(n1, 'B');
     
    404650  }
    405651
     652  // Iterable bool map
     653  {
     654    typedef SmartGraph Graph;
     655    typedef SmartGraph::Node Item;
     656
     657    typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm;
     658    checkConcept<ReferenceMap<Item, bool, bool&, const bool&>, Ibm>();
     659
     660    const int num = 10;
     661    Graph g;
     662    Ibm map0(g, true);
     663    std::vector<Item> items;
     664    for (int i = 0; i < num; ++i) {
     665      items.push_back(g.addNode());
     666    }
     667
     668    Ibm map1(g, true);
     669    int n = 0;
     670    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
     671      check(map1[static_cast<Item>(it)], "Wrong TrueIt");
     672      ++n;
     673    }
     674    check(n == num, "Wrong number");
     675
     676    n = 0;
     677    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
     678        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
     679        ++n;
     680    }
     681    check(n == num, "Wrong number");
     682    check(Ibm::FalseIt(map1) == INVALID, "Wrong FalseIt");
     683    check(Ibm::ItemIt(map1, false) == INVALID, "Wrong ItemIt for false");
     684
     685    map1[items[5]] = true;
     686
     687    n = 0;
     688    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
     689        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
     690        ++n;
     691    }
     692    check(n == num, "Wrong number");
     693
     694    map1[items[num / 2]] = false;
     695    check(map1[items[num / 2]] == false, "Wrong map value");
     696
     697    n = 0;
     698    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
     699        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
     700        ++n;
     701    }
     702    check(n == num - 1, "Wrong number");
     703
     704    n = 0;
     705    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
     706        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
     707        ++n;
     708    }
     709    check(n == 1, "Wrong number");
     710
     711    map1[items[0]] = false;
     712    check(map1[items[0]] == false, "Wrong map value");
     713
     714    map1[items[num - 1]] = false;
     715    check(map1[items[num - 1]] == false, "Wrong map value");
     716
     717    n = 0;
     718    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
     719        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
     720        ++n;
     721    }
     722    check(n == num - 3, "Wrong number");
     723    check(map1.trueNum() == num - 3, "Wrong number");
     724
     725    n = 0;
     726    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
     727        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
     728        ++n;
     729    }
     730    check(n == 3, "Wrong number");
     731    check(map1.falseNum() == 3, "Wrong number");
     732  }
     733
     734  // Iterable int map
     735  {
     736    typedef SmartGraph Graph;
     737    typedef SmartGraph::Node Item;
     738    typedef IterableIntMap<SmartGraph, SmartGraph::Node> Iim;
     739
     740    checkConcept<ReferenceMap<Item, int, int&, const int&>, Iim>();
     741
     742    const int num = 10;
     743    Graph g;
     744    Iim map0(g, 0);
     745    std::vector<Item> items;
     746    for (int i = 0; i < num; ++i) {
     747      items.push_back(g.addNode());
     748    }
     749
     750    Iim map1(g);
     751    check(map1.size() == 0, "Wrong size");
     752
     753    for (int i = 0; i < num; ++i) {
     754      map1[items[i]] = i;
     755    }
     756    check(map1.size() == num, "Wrong size");
     757
     758    for (int i = 0; i < num; ++i) {
     759      Iim::ItemIt it(map1, i);
     760      check(static_cast<Item>(it) == items[i], "Wrong value");
     761      ++it;
     762      check(static_cast<Item>(it) == INVALID, "Wrong value");
     763    }
     764
     765    for (int i = 0; i < num; ++i) {
     766      map1[items[i]] = i % 2;
     767    }
     768    check(map1.size() == 2, "Wrong size");
     769
     770    int n = 0;
     771    for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) {
     772      check(map1[static_cast<Item>(it)] == 0, "Wrong value");
     773      ++n;
     774    }
     775    check(n == (num + 1) / 2, "Wrong number");
     776
     777    for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) {
     778      check(map1[static_cast<Item>(it)] == 1, "Wrong value");
     779      ++n;
     780    }
     781    check(n == num, "Wrong number");
     782
     783  }
     784
     785  // Iterable value map
     786  {
     787    typedef SmartGraph Graph;
     788    typedef SmartGraph::Node Item;
     789    typedef IterableValueMap<SmartGraph, SmartGraph::Node, double> Ivm;
     790
     791    checkConcept<ReadWriteMap<Item, double>, Ivm>();
     792
     793    const int num = 10;
     794    Graph g;
     795    Ivm map0(g, 0.0);
     796    std::vector<Item> items;
     797    for (int i = 0; i < num; ++i) {
     798      items.push_back(g.addNode());
     799    }
     800
     801    Ivm map1(g, 0.0);
     802    check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size");
     803    check(*map1.beginValue() == 0.0, "Wrong value");
     804
     805    for (int i = 0; i < num; ++i) {
     806      map1.set(items[i], static_cast<double>(i));
     807    }
     808    check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size");
     809
     810    for (int i = 0; i < num; ++i) {
     811      Ivm::ItemIt it(map1, static_cast<double>(i));
     812      check(static_cast<Item>(it) == items[i], "Wrong value");
     813      ++it;
     814      check(static_cast<Item>(it) == INVALID, "Wrong value");
     815    }
     816
     817    for (Ivm::ValueIt vit = map1.beginValue();
     818         vit != map1.endValue(); ++vit) {
     819      check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,
     820            "Wrong ValueIt");
     821    }
     822
     823    for (int i = 0; i < num; ++i) {
     824      map1.set(items[i], static_cast<double>(i % 2));
     825    }
     826    check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size");
     827
     828    int n = 0;
     829    for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) {
     830      check(map1[static_cast<Item>(it)] == 0.0, "Wrong value");
     831      ++n;
     832    }
     833    check(n == (num + 1) / 2, "Wrong number");
     834
     835    for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) {
     836      check(map1[static_cast<Item>(it)] == 1.0, "Wrong value");
     837      ++n;
     838    }
     839    check(n == num, "Wrong number");
     840
     841  }
     842
     843  // Graph map utilities:
     844  // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
     845  // mapFind(), mapFindIf(), mapCount(), mapCountIf()
     846  // mapCopy(), mapCompare(), mapFill()
     847  {
     848    DIGRAPH_TYPEDEFS(SmartDigraph);
     849
     850    SmartDigraph g;
     851    Node n1 = g.addNode();
     852    Node n2 = g.addNode();
     853    Node n3 = g.addNode();
     854
     855    SmartDigraph::NodeMap<int> map1(g);
     856    SmartDigraph::ArcMap<char> map2(g);
     857    ConstMap<Node, A> cmap1 = A();
     858    ConstMap<Arc, C> cmap2 = C(0);
     859
     860    map1[n1] = 10;
     861    map1[n2] = 5;
     862    map1[n3] = 12;
     863
     864    // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
     865    check(mapMin(g, map1) == n2, "Wrong mapMin()");
     866    check(mapMax(g, map1) == n3, "Wrong mapMax()");
     867    check(mapMin(g, map1, std::greater<int>()) == n3, "Wrong mapMin()");
     868    check(mapMax(g, map1, std::greater<int>()) == n2, "Wrong mapMax()");
     869    check(mapMinValue(g, map1) == 5, "Wrong mapMinValue()");
     870    check(mapMaxValue(g, map1) == 12, "Wrong mapMaxValue()");
     871
     872    check(mapMin(g, map2) == INVALID, "Wrong mapMin()");
     873    check(mapMax(g, map2) == INVALID, "Wrong mapMax()");
     874
     875    check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()");
     876    check(mapMax(g, cmap2) == INVALID, "Wrong mapMax()");
     877
     878    Arc a1 = g.addArc(n1, n2);
     879    Arc a2 = g.addArc(n1, n3);
     880    Arc a3 = g.addArc(n2, n3);
     881    Arc a4 = g.addArc(n3, n1);
     882
     883    map2[a1] = 'b';
     884    map2[a2] = 'a';
     885    map2[a3] = 'b';
     886    map2[a4] = 'c';
     887
     888    // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
     889    check(mapMin(g, map2) == a2, "Wrong mapMin()");
     890    check(mapMax(g, map2) == a4, "Wrong mapMax()");
     891    check(mapMin(g, map2, std::greater<int>()) == a4, "Wrong mapMin()");
     892    check(mapMax(g, map2, std::greater<int>()) == a2, "Wrong mapMax()");
     893    check(mapMinValue(g, map2, std::greater<int>()) == 'c',
     894          "Wrong mapMinValue()");
     895    check(mapMaxValue(g, map2, std::greater<int>()) == 'a',
     896          "Wrong mapMaxValue()");
     897
     898    check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()");
     899    check(mapMax(g, cmap2) != INVALID, "Wrong mapMax()");
     900    check(mapMaxValue(g, cmap2) == C(0), "Wrong mapMaxValue()");
     901
     902    check(mapMin(g, composeMap(functorToMap(&createC), map2)) == a2,
     903          "Wrong mapMin()");
     904    check(mapMax(g, composeMap(functorToMap(&createC), map2)) == a4,
     905          "Wrong mapMax()");
     906    check(mapMinValue(g, composeMap(functorToMap(&createC), map2)) == C('a'),
     907          "Wrong mapMinValue()");
     908    check(mapMaxValue(g, composeMap(functorToMap(&createC), map2)) == C('c'),
     909          "Wrong mapMaxValue()");
     910
     911    // mapFind(), mapFindIf()
     912    check(mapFind(g, map1, 5) == n2, "Wrong mapFind()");
     913    check(mapFind(g, map1, 6) == INVALID, "Wrong mapFind()");
     914    check(mapFind(g, map2, 'a') == a2, "Wrong mapFind()");
     915    check(mapFind(g, map2, 'e') == INVALID, "Wrong mapFind()");
     916    check(mapFind(g, cmap2, C(0)) == ArcIt(g), "Wrong mapFind()");
     917    check(mapFind(g, cmap2, C(1)) == INVALID, "Wrong mapFind()");
     918
     919    check(mapFindIf(g, map1, Less<int>(7)) == n2,
     920          "Wrong mapFindIf()");
     921    check(mapFindIf(g, map1, Less<int>(5)) == INVALID,
     922          "Wrong mapFindIf()");
     923    check(mapFindIf(g, map2, Less<char>('d')) == ArcIt(g),
     924          "Wrong mapFindIf()");
     925    check(mapFindIf(g, map2, Less<char>('a')) == INVALID,
     926          "Wrong mapFindIf()");
     927
     928    // mapCount(), mapCountIf()
     929    check(mapCount(g, map1, 5) == 1, "Wrong mapCount()");
     930    check(mapCount(g, map1, 6) == 0, "Wrong mapCount()");
     931    check(mapCount(g, map2, 'a') == 1, "Wrong mapCount()");
     932    check(mapCount(g, map2, 'b') == 2, "Wrong mapCount()");
     933    check(mapCount(g, map2, 'e') == 0, "Wrong mapCount()");
     934    check(mapCount(g, cmap2, C(0)) == 4, "Wrong mapCount()");
     935    check(mapCount(g, cmap2, C(1)) == 0, "Wrong mapCount()");
     936
     937    check(mapCountIf(g, map1, Less<int>(11)) == 2,
     938          "Wrong mapCountIf()");
     939    check(mapCountIf(g, map1, Less<int>(13)) == 3,
     940          "Wrong mapCountIf()");
     941    check(mapCountIf(g, map1, Less<int>(5)) == 0,
     942          "Wrong mapCountIf()");
     943    check(mapCountIf(g, map2, Less<char>('d')) == 4,
     944          "Wrong mapCountIf()");
     945    check(mapCountIf(g, map2, Less<char>('c')) == 3,
     946          "Wrong mapCountIf()");
     947    check(mapCountIf(g, map2, Less<char>('a')) == 0,
     948          "Wrong mapCountIf()");
     949
     950    // MapIt, ConstMapIt
     951/*
     952These tests can be used after applying bugfix #330
     953    typedef SmartDigraph::NodeMap<int>::MapIt MapIt;
     954    typedef SmartDigraph::NodeMap<int>::ConstMapIt ConstMapIt;
     955    check(*std::min_element(MapIt(map1), MapIt(INVALID)) == 5,
     956          "Wrong NodeMap<>::MapIt");
     957    check(*std::max_element(ConstMapIt(map1), ConstMapIt(INVALID)) == 12,
     958          "Wrong NodeMap<>::MapIt");
     959
     960    int sum = 0;
     961    std::for_each(MapIt(map1), MapIt(INVALID), Sum<int>(sum));
     962    check(sum == 27, "Wrong NodeMap<>::MapIt");
     963    std::for_each(ConstMapIt(map1), ConstMapIt(INVALID), Sum<int>(sum));
     964    check(sum == 54, "Wrong NodeMap<>::ConstMapIt");
     965*/
     966
     967    // mapCopy(), mapCompare(), mapFill()
     968    check(mapCompare(g, map1, map1), "Wrong mapCompare()");
     969    check(mapCompare(g, cmap2, cmap2), "Wrong mapCompare()");
     970    check(mapCompare(g, map1, shiftMap(map1, 0)), "Wrong mapCompare()");
     971    check(mapCompare(g, map2, scaleMap(map2, 1)), "Wrong mapCompare()");
     972    check(!mapCompare(g, map1, shiftMap(map1, 1)), "Wrong mapCompare()");
     973
     974    SmartDigraph::NodeMap<int> map3(g, 0);
     975    SmartDigraph::ArcMap<char> map4(g, 'a');
     976
     977    check(!mapCompare(g, map1, map3), "Wrong mapCompare()");
     978    check(!mapCompare(g, map2, map4), "Wrong mapCompare()");
     979
     980    mapCopy(g, map1, map3);
     981    mapCopy(g, map2, map4);
     982
     983    check(mapCompare(g, map1, map3), "Wrong mapCompare() or mapCopy()");
     984    check(mapCompare(g, map2, map4), "Wrong mapCompare() or mapCopy()");
     985
     986    Undirector<SmartDigraph> ug(g);
     987    Undirector<SmartDigraph>::EdgeMap<char> umap1(ug, 'x');
     988    Undirector<SmartDigraph>::ArcMap<double> umap2(ug, 3.14);
     989
     990    check(!mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()");
     991    check(!mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()");
     992    check(!mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");
     993    check(!mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");
     994
     995    mapCopy(g, map2, umap1);
     996
     997    check(mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()");
     998    check(mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()");
     999    check(mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");
     1000    check(mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");
     1001
     1002    mapCopy(g, map2, umap1);
     1003    mapCopy(g, umap1, map2);
     1004    mapCopy(ug, map2, umap1);
     1005    mapCopy(ug, umap1, map2);
     1006
     1007    check(!mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()");
     1008    mapCopy(ug, umap1, umap2);
     1009    check(mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()");
     1010
     1011    check(!mapCompare(g, map1, constMap<Node>(2)), "Wrong mapCompare()");
     1012    mapFill(g, map1, 2);
     1013    check(mapCompare(g, constMap<Node>(2), map1), "Wrong mapFill()");
     1014
     1015    check(!mapCompare(g, map2, constMap<Arc>('z')), "Wrong mapCompare()");
     1016    mapCopy(g, constMap<Arc>('z'), map2);
     1017    check(mapCompare(g, constMap<Arc>('z'), map2), "Wrong mapCopy()");
     1018  }
     1019
    4061020  return 0;
    4071021}
  • test/matching_test.cc

    r970 r983  
    146146  MaxMatching<Graph>::Status stat =
    147147    const_mat_test.status(n);
    148   ignore_unused_variable_warning(stat);
     148  ::lemon::ignore_unused_variable_warning(stat);
    149149  const MaxMatching<Graph>::StatusMap& smap =
    150150    const_mat_test.statusMap();
  • test/matching_test.cc

    r982 r983  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    135135  mat_test.startDense();
    136136  mat_test.run();
    137  
     137
    138138  const_mat_test.matchingSize();
    139139  const_mat_test.matching(e);
     
    144144  const_mat_test.mate(n);
    145145
    146   MaxMatching<Graph>::Status stat = 
     146  MaxMatching<Graph>::Status stat =
    147147    const_mat_test.status(n);
    148148  ::lemon::ignore_unused_variable_warning(stat);
     
    172172  mat_test.start();
    173173  mat_test.run();
    174  
     174
    175175  const_mat_test.matchingWeight();
    176176  const_mat_test.matchingSize();
     
    181181  e = mmap[n];
    182182  const_mat_test.mate(n);
    183  
     183
    184184  int k = 0;
    185185  const_mat_test.dualValue();
     
    209209  mat_test.start();
    210210  mat_test.run();
    211  
     211
    212212  const_mat_test.matchingWeight();
    213213  const_mat_test.matching(e);
     
    217217  e = mmap[n];
    218218  const_mat_test.mate(n);
    219  
     219
    220220  int k = 0;
    221221  const_mat_test.dualValue();
     
    403403      edgeMap("weight", weight).run();
    404404
    405     MaxMatching<SmartGraph> mm(graph);
    406     mm.run();
    407     checkMatching(graph, mm);
    408 
    409     MaxWeightedMatching<SmartGraph> mwm(graph, weight);
    410     mwm.run();
    411     checkWeightedMatching(graph, weight, mwm);
    412 
    413     MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight);
    414     bool perfect = mwpm.run();
    415 
    416     check(perfect == (mm.matchingSize() * 2 == countNodes(graph)),
    417           "Perfect matching found");
    418 
    419     if (perfect) {
    420       checkWeightedPerfectMatching(graph, weight, mwpm);
     405    bool perfect;
     406    {
     407      MaxMatching<SmartGraph> mm(graph);
     408      mm.run();
     409      checkMatching(graph, mm);
     410      perfect = 2 * mm.matchingSize() == countNodes(graph);
     411    }
     412
     413    {
     414      MaxWeightedMatching<SmartGraph> mwm(graph, weight);
     415      mwm.run();
     416      checkWeightedMatching(graph, weight, mwm);
     417    }
     418
     419    {
     420      MaxWeightedMatching<SmartGraph> mwm(graph, weight);
     421      mwm.init();
     422      mwm.start();
     423      checkWeightedMatching(graph, weight, mwm);
     424    }
     425
     426    {
     427      MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight);
     428      bool result = mwpm.run();
     429
     430      check(result == perfect, "Perfect matching found");
     431      if (perfect) {
     432        checkWeightedPerfectMatching(graph, weight, mwpm);
     433      }
     434    }
     435
     436    {
     437      MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight);
     438      mwpm.init();
     439      bool result = mwpm.start();
     440
     441      check(result == perfect, "Perfect matching found");
     442      if (perfect) {
     443        checkWeightedPerfectMatching(graph, weight, mwpm);
     444      }
    421445    }
    422446  }
  • test/min_cost_arborescence_test.cc

    r970 r983  
    9292  VType c;
    9393  bool b;
    94   ignore_unused_variable_warning(c,b);
     94  ::lemon::ignore_unused_variable_warning(c,b);
    9595  int i;
    9696  CostMap cost;
     
    128128  c = const_mcarb_test.dualValue(i);
    129129
    130   ignore_unused_variable_warning(am);
    131   ignore_unused_variable_warning(pm);
     130  ::lemon::ignore_unused_variable_warning(am);
     131  ::lemon::ignore_unused_variable_warning(pm);
    132132}
    133133
  • test/min_cost_arborescence_test.cc

    r982 r983  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    112112  b = const_mcarb_test.emptyQueue();
    113113  i = const_mcarb_test.queueSize();
    114  
     114
    115115  c = const_mcarb_test.arborescenceCost();
    116116  b = const_mcarb_test.arborescence(e);
     
    122122  b = const_mcarb_test.reached(n);
    123123  b = const_mcarb_test.processed(n);
    124  
     124
    125125  i = const_mcarb_test.dualNum();
    126126  c = const_mcarb_test.dualValue();
    127127  i = const_mcarb_test.dualSize(i);
    128128  c = const_mcarb_test.dualValue(i);
    129  
     129
    130130  ::lemon::ignore_unused_variable_warning(am);
    131131  ::lemon::ignore_unused_variable_warning(pm);
  • test/preflow_test.cc

    r970 r983  
    8787  VType v;
    8888  bool b;
    89   ignore_unused_variable_warning(v,b);
     89  ::lemon::ignore_unused_variable_warning(v,b);
    9090
    9191  typedef Preflow<Digraph, CapMap>
     
    121121  const_preflow_test.minCutMap(cut);
    122122
    123   ignore_unused_variable_warning(fm);
     123  ::lemon::ignore_unused_variable_warning(fm);
    124124}
    125125
  • test/preflow_test.cc

    r982 r983  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9797  const PreflowType& const_preflow_test = preflow_test;
    9898
     99  const PreflowType::Elevator& elev = const_preflow_test.elevator();
     100  preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
     101  PreflowType::Tolerance tol = const_preflow_test.tolerance();
     102  preflow_test.tolerance(tol);
     103
    99104  preflow_test
    100105    .capacityMap(cap)
     
    115120  b = const_preflow_test.minCut(n);
    116121  const_preflow_test.minCutMap(cut);
    117  
     122
    118123  ::lemon::ignore_unused_variable_warning(fm);
    119124}
  • test/suurballe_test.cc

    r970 r983  
    118118  int f;
    119119  VType c;
    120   ignore_unused_variable_warning(f,c);
     120  ::lemon::ignore_unused_variable_warning(f,c);
    121121
    122122  c = const_suurb_test.totalLength();
     
    130130  Path<Digraph> p = const_suurb_test.path(k);
    131131
    132   ignore_unused_variable_warning(fm);
    133   ignore_unused_variable_warning(pm);
     132  ::lemon::ignore_unused_variable_warning(fm);
     133  ::lemon::ignore_unused_variable_warning(pm);
    134134}
    135135
  • test/suurballe_test.cc

    r982 r983  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2424#include <lemon/suurballe.h>
    2525#include <lemon/concepts/digraph.h>
     26#include <lemon/concepts/heap.h>
    2627
    2728#include "test_tools.h"
     
    8182  typedef Digraph::Arc Arc;
    8283  typedef concepts::ReadMap<Arc, VType> LengthMap;
    83  
    84   typedef Suurballe<Digraph, LengthMap> SuurballeType;
     84
     85  typedef Suurballe<Digraph, LengthMap> ST;
     86  typedef Suurballe<Digraph, LengthMap>
     87    ::SetFlowMap<ST::FlowMap>
     88    ::SetPotentialMap<ST::PotentialMap>
     89    ::SetPath<SimplePath<Digraph> >
     90    ::SetHeap<concepts::Heap<VType, Digraph::NodeMap<int> > >
     91    ::Create SuurballeType;
    8592
    8693  Digraph g;
     
    102109  k = suurb_test.run(n, n, k);
    103110  suurb_test.init(n);
     111  suurb_test.fullInit(n);
     112  suurb_test.start(n);
     113  suurb_test.start(n, k);
    104114  k = suurb_test.findFlow(n);
    105115  k = suurb_test.findFlow(n, k);
    106116  suurb_test.findPaths();
    107  
     117
    108118  int f;
    109119  VType c;
     
    119129  k = const_suurb_test.pathNum();
    120130  Path<Digraph> p = const_suurb_test.path(k);
    121  
     131
    122132  ::lemon::ignore_unused_variable_warning(fm);
    123133  ::lemon::ignore_unused_variable_warning(pm);
     
    198208    run();
    199209
    200   // Find 2 paths
     210  // Check run()
    201211  {
    202212    Suurballe<ListDigraph> suurballe(digraph, length);
     213
     214    // Find 2 paths
    203215    check(suurballe.run(s, t) == 2, "Wrong number of paths");
    204216    check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
     
    210222    for (int i = 0; i < suurballe.pathNum(); ++i)
    211223      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    212   }
    213 
    214   // Find 3 paths
    215   {
    216     Suurballe<ListDigraph> suurballe(digraph, length);
     224
     225    // Find 3 paths
    217226    check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
    218227    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
     
    224233    for (int i = 0; i < suurballe.pathNum(); ++i)
    225234      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    226   }
    227 
    228   // Find 5 paths (only 3 can be found)
    229   {
    230     Suurballe<ListDigraph> suurballe(digraph, length);
     235
     236    // Find 5 paths (only 3 can be found)
    231237    check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
    232238    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
     
    240246  }
    241247
     248  // Check fullInit() + start()
     249  {
     250    Suurballe<ListDigraph> suurballe(digraph, length);
     251    suurballe.fullInit(s);
     252
     253    // Find 2 paths
     254    check(suurballe.start(t) == 2, "Wrong number of paths");
     255    check(suurballe.totalLength() == 510, "The flow is not optimal");
     256
     257    // Find 3 paths
     258    check(suurballe.start(t, 3) == 3, "Wrong number of paths");
     259    check(suurballe.totalLength() == 1040, "The flow is not optimal");
     260
     261    // Find 5 paths (only 3 can be found)
     262    check(suurballe.start(t, 5) == 3, "Wrong number of paths");
     263    check(suurballe.totalLength() == 1040, "The flow is not optimal");
     264  }
     265
    242266  return 0;
    243267}
Note: See TracChangeset for help on using the changeset viewer.