COIN-OR::LEMON - Graph Library

Changeset 606:c5fd2d996909 in lemon


Ignore:
Timestamp:
03/29/09 23:08:20 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Various doc improvements (#248)

  • Rename all the ugly template parameters (too long and/or starting with an underscore).
  • Rename function parameters starting with an underscore.
  • Extend the doc for many classes.
  • Use LaTeX-style O(...) expressions only for the complicated ones.
  • A lot of small unification changes.
  • Small fixes.
  • Some other improvements.
Files:
33 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r478 r606  
    2121/**
    2222@defgroup datas Data Structures
    23 This group describes the several data structures implemented in LEMON.
     23This group contains the several data structures implemented in LEMON.
    2424*/
    2525
     
    143143\brief Graph types between real graphs and graph adaptors.
    144144
    145 This group describes some graph types between real graphs and graph adaptors.
     145This group contains some graph types between real graphs and graph adaptors.
    146146These classes wrap graphs to give new functionality as the adaptors do it.
    147147On the other hand they are not light-weight structures as the adaptors.
     
    153153\brief Map structures implemented in LEMON.
    154154
    155 This group describes the map structures implemented in LEMON.
     155This group contains the map structures implemented in LEMON.
    156156
    157157LEMON provides several special purpose maps and map adaptors that e.g. combine
     
    166166\brief Special graph-related maps.
    167167
    168 This group describes maps that are specifically designed to assign
     168This group contains maps that are specifically designed to assign
    169169values to the nodes and arcs/edges of graphs.
    170170
     
    178178\brief Tools to create new maps from existing ones
    179179
    180 This group describes map adaptors that are used to create "implicit"
     180This group contains map adaptors that are used to create "implicit"
    181181maps from other maps.
    182182
     
    241241\brief Two dimensional data storages implemented in LEMON.
    242242
    243 This group describes two dimensional data storages implemented in LEMON.
     243This group contains two dimensional data storages implemented in LEMON.
    244244*/
    245245
     
    249249\brief %Path structures implemented in LEMON.
    250250
    251 This group describes the path structures implemented in LEMON.
     251This group contains the path structures implemented in LEMON.
    252252
    253253LEMON provides flexible data structures to work with paths.
     
    265265\brief Auxiliary data structures implemented in LEMON.
    266266
    267 This group describes some data structures implemented in LEMON in
     267This group contains some data structures implemented in LEMON in
    268268order to make it easier to implement combinatorial algorithms.
    269269*/
     
    271271/**
    272272@defgroup algs Algorithms
    273 \brief This group describes the several algorithms
     273\brief This group contains the several algorithms
    274274implemented in LEMON.
    275275
    276 This group describes the several algorithms
     276This group contains the several algorithms
    277277implemented in LEMON.
    278278*/
     
    283283\brief Common graph search algorithms.
    284284
    285 This group describes the common graph search algorithms, namely
     285This group contains the common graph search algorithms, namely
    286286\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
    287287*/
     
    292292\brief Algorithms for finding shortest paths.
    293293
    294 This group describes the algorithms for finding shortest paths in digraphs.
     294This group contains the algorithms for finding shortest paths in digraphs.
    295295
    296296 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    313313\brief Algorithms for finding maximum flows.
    314314
    315 This group describes the algorithms for finding maximum flows and
     315This group contains the algorithms for finding maximum flows and
    316316feasible circulations.
    317317
     
    346346\brief Algorithms for finding minimum cost flows and circulations.
    347347
    348 This group describes the algorithms for finding minimum cost flows and
     348This group contains the algorithms for finding minimum cost flows and
    349349circulations.
    350350
     
    383383\brief Algorithms for finding minimum cut in graphs.
    384384
    385 This group describes the algorithms for finding minimum cut in graphs.
     385This group contains the algorithms for finding minimum cut in graphs.
    386386
    387387The \e minimum \e cut \e problem is to find a non-empty and non-complete
     
    400400- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
    401401  calculating minimum cut in undirected graphs.
    402 - \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
     402- \ref GomoryHu "Gomory-Hu tree computation" for calculating
    403403  all-pairs minimum cut in undirected graphs.
    404404
     
    412412\brief Algorithms for discovering the graph properties
    413413
    414 This group describes the algorithms for discovering the graph properties
     414This group contains the algorithms for discovering the graph properties
    415415like connectivity, bipartiteness, euler property, simplicity etc.
    416416
     
    424424\brief Algorithms for planarity checking, embedding and drawing
    425425
    426 This group describes the algorithms for planarity checking,
     426This group contains the algorithms for planarity checking,
    427427embedding and drawing.
    428428
     
    475475\brief Algorithms for finding a minimum cost spanning tree in a graph.
    476476
    477 This group describes the algorithms for finding a minimum cost spanning
     477This group contains the algorithms for finding a minimum cost spanning
    478478tree in a graph.
    479479*/
     
    484484\brief Auxiliary algorithms implemented in LEMON.
    485485
    486 This group describes some algorithms implemented in LEMON
     486This group contains some algorithms implemented in LEMON
    487487in order to make it easier to implement complex algorithms.
    488488*/
     
    493493\brief Approximation algorithms.
    494494
    495 This group describes the approximation and heuristic algorithms
     495This group contains the approximation and heuristic algorithms
    496496implemented in LEMON.
    497497*/
     
    499499/**
    500500@defgroup gen_opt_group General Optimization Tools
    501 \brief This group describes some general optimization frameworks
     501\brief This group contains some general optimization frameworks
    502502implemented in LEMON.
    503503
    504 This group describes some general optimization frameworks
     504This group contains some general optimization frameworks
    505505implemented in LEMON.
    506506*/
     
    511511\brief Lp and Mip solver interfaces for LEMON.
    512512
    513 This group describes Lp and Mip solver interfaces for LEMON. The
     513This group contains Lp and Mip solver interfaces for LEMON. The
    514514various LP solvers could be used in the same manner with this
    515515interface.
     
    530530\brief Metaheuristics for LEMON library.
    531531
    532 This group describes some metaheuristic optimization tools.
     532This group contains some metaheuristic optimization tools.
    533533*/
    534534
     
    545545\brief Simple basic graph utilities.
    546546
    547 This group describes some simple basic graph utilities.
     547This group contains some simple basic graph utilities.
    548548*/
    549549
     
    553553\brief Tools for development, debugging and testing.
    554554
    555 This group describes several useful tools for development,
     555This group contains several useful tools for development,
    556556debugging and testing.
    557557*/
     
    562562\brief Simple tools for measuring the performance of algorithms.
    563563
    564 This group describes simple tools for measuring the performance
     564This group contains simple tools for measuring the performance
    565565of algorithms.
    566566*/
     
    571571\brief Exceptions defined in LEMON.
    572572
    573 This group describes the exceptions defined in LEMON.
     573This group contains the exceptions defined in LEMON.
    574574*/
    575575
     
    578578\brief Graph Input-Output methods
    579579
    580 This group describes the tools for importing and exporting graphs
     580This group contains the tools for importing and exporting graphs
    581581and graph related data. Now it supports the \ref lgf-format
    582582"LEMON Graph Format", the \c DIMACS format and the encapsulated
     
    589589\brief Reading and writing LEMON Graph Format.
    590590
    591 This group describes methods for reading and writing
     591This group contains methods for reading and writing
    592592\ref lgf-format "LEMON Graph Format".
    593593*/
     
    598598\brief General \c EPS drawer and graph exporter
    599599
    600 This group describes general \c EPS drawing methods and special
     600This group contains general \c EPS drawing methods and special
    601601graph exporting tools.
    602602*/
     
    622622\brief Skeleton classes and concept checking classes
    623623
    624 This group describes the data/algorithm skeletons and concept checking
     624This group contains the data/algorithm skeletons and concept checking
    625625classes implemented in LEMON.
    626626
     
    652652\brief Skeleton and concept checking classes for graph structures
    653653
    654 This group describes the skeletons and concept checking classes of LEMON's
     654This group contains the skeletons and concept checking classes of LEMON's
    655655graph structures and helper classes used to implement these.
    656656*/
     
    661661\brief Skeleton and concept checking classes for maps
    662662
    663 This group describes the skeletons and concept checking classes of maps.
     663This group contains the skeletons and concept checking classes of maps.
    664664*/
    665665
  • doc/mainpage.dox

    r463 r606  
    4646"Quick Tour to LEMON" which will guide you along.
    4747
    48 If you already feel like using our library, see the page that tells you
    49 \ref getstart "How to start using LEMON".
    50 
    51 If you
    52 want to see how LEMON works, see
    53 some \ref demoprograms "demo programs".
     48If you already feel like using our library, see the
     49<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
    5450
    5551If you know what you are looking for then try to find it under the
    56 <a class="el" href="modules.html">Modules</a>
    57 section.
     52<a class="el" href="modules.html">Modules</a> section.
    5853
    5954If you are a user of the old (0.x) series of LEMON, please check out the
  • lemon/adaptors.h

    r566 r606  
    22552255    /// This map adaptor class adapts two arc maps of the underlying
    22562256    /// digraph to get an arc map of the undirected graph.
    2257     /// Its value type is inherited from the first arc map type
    2258     /// (\c %ForwardMap).
    2259     template <typename ForwardMap, typename BackwardMap>
     2257    /// Its value type is inherited from the first arc map type (\c FW).
     2258    /// \tparam FW The type of the "foward" arc map.
     2259    /// \tparam BK The type of the "backward" arc map.
     2260    template <typename FW, typename BK>
    22602261    class CombinedArcMap {
    22612262    public:
     
    22642265      typedef typename Parent::Arc Key;
    22652266      /// The value type of the map
    2266       typedef typename ForwardMap::Value Value;
    2267 
    2268       typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
    2269 
    2270       typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;
    2271       typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue;
    2272       typedef typename MapTraits<ForwardMap>::ReturnValue Reference;
    2273       typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;
     2267      typedef typename FW::Value Value;
     2268
     2269      typedef typename MapTraits<FW>::ReferenceMapTag ReferenceMapTag;
     2270
     2271      typedef typename MapTraits<FW>::ReturnValue ReturnValue;
     2272      typedef typename MapTraits<FW>::ConstReturnValue ConstReturnValue;
     2273      typedef typename MapTraits<FW>::ReturnValue Reference;
     2274      typedef typename MapTraits<FW>::ConstReturnValue ConstReference;
    22742275
    22752276      /// Constructor
    2276       CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
     2277      CombinedArcMap(FW& forward, BK& backward)
    22772278        : _forward(&forward), _backward(&backward) {}
    22782279
     
    23062307    protected:
    23072308
    2308       ForwardMap* _forward;
    2309       BackwardMap* _backward;
     2309      FW* _forward;
     2310      BK* _backward;
    23102311
    23112312    };
     
    23142315    ///
    23152316    /// This function just returns a combined arc map.
    2316     template <typename ForwardMap, typename BackwardMap>
    2317     static CombinedArcMap<ForwardMap, BackwardMap>
    2318     combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
    2319       return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
    2320     }
    2321 
    2322     template <typename ForwardMap, typename BackwardMap>
    2323     static CombinedArcMap<const ForwardMap, BackwardMap>
    2324     combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {
    2325       return CombinedArcMap<const ForwardMap,
    2326         BackwardMap>(forward, backward);
    2327     }
    2328 
    2329     template <typename ForwardMap, typename BackwardMap>
    2330     static CombinedArcMap<ForwardMap, const BackwardMap>
    2331     combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {
    2332       return CombinedArcMap<ForwardMap,
    2333         const BackwardMap>(forward, backward);
    2334     }
    2335 
    2336     template <typename ForwardMap, typename BackwardMap>
    2337     static CombinedArcMap<const ForwardMap, const BackwardMap>
    2338     combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {
    2339       return CombinedArcMap<const ForwardMap,
    2340         const BackwardMap>(forward, backward);
     2317    template <typename FW, typename BK>
     2318    static CombinedArcMap<FW, BK>
     2319    combinedArcMap(FW& forward, BK& backward) {
     2320      return CombinedArcMap<FW, BK>(forward, backward);
     2321    }
     2322
     2323    template <typename FW, typename BK>
     2324    static CombinedArcMap<const FW, BK>
     2325    combinedArcMap(const FW& forward, BK& backward) {
     2326      return CombinedArcMap<const FW, BK>(forward, backward);
     2327    }
     2328
     2329    template <typename FW, typename BK>
     2330    static CombinedArcMap<FW, const BK>
     2331    combinedArcMap(FW& forward, const BK& backward) {
     2332      return CombinedArcMap<FW, const BK>(forward, backward);
     2333    }
     2334
     2335    template <typename FW, typename BK>
     2336    static CombinedArcMap<const FW, const BK>
     2337    combinedArcMap(const FW& forward, const BK& backward) {
     2338      return CombinedArcMap<const FW, const BK>(forward, backward);
    23412339    }
    23422340
     
    34073405    /// This map adaptor class adapts two node maps of the original digraph
    34083406    /// to get a node map of the split digraph.
    3409     /// Its value type is inherited from the first node map type
    3410     /// (\c InNodeMap).
    3411     template <typename InNodeMap, typename OutNodeMap>
     3407    /// Its value type is inherited from the first node map type (\c IN).
     3408    /// \tparam IN The type of the node map for the in-nodes.
     3409    /// \tparam OUT The type of the node map for the out-nodes.
     3410    template <typename IN, typename OUT>
    34123411    class CombinedNodeMap {
    34133412    public:
     
    34163415      typedef Node Key;
    34173416      /// The value type of the map
    3418       typedef typename InNodeMap::Value Value;
    3419 
    3420       typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;
    3421       typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;
    3422       typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;
    3423       typedef typename MapTraits<InNodeMap>::ReturnValue Reference;
    3424       typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;
     3417      typedef typename IN::Value Value;
     3418
     3419      typedef typename MapTraits<IN>::ReferenceMapTag ReferenceMapTag;
     3420      typedef typename MapTraits<IN>::ReturnValue ReturnValue;
     3421      typedef typename MapTraits<IN>::ConstReturnValue ConstReturnValue;
     3422      typedef typename MapTraits<IN>::ReturnValue Reference;
     3423      typedef typename MapTraits<IN>::ConstReturnValue ConstReference;
    34253424
    34263425      /// Constructor
    3427       CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
     3426      CombinedNodeMap(IN& in_map, OUT& out_map)
    34283427        : _in_map(in_map), _out_map(out_map) {}
    34293428
     
    34573456    private:
    34583457
    3459       InNodeMap& _in_map;
    3460       OutNodeMap& _out_map;
     3458      IN& _in_map;
     3459      OUT& _out_map;
    34613460
    34623461    };
     
    34663465    ///
    34673466    /// This function just returns a combined node map.
    3468     template <typename InNodeMap, typename OutNodeMap>
    3469     static CombinedNodeMap<InNodeMap, OutNodeMap>
    3470     combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
    3471       return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
    3472     }
    3473 
    3474     template <typename InNodeMap, typename OutNodeMap>
    3475     static CombinedNodeMap<const InNodeMap, OutNodeMap>
    3476     combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
    3477       return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
    3478     }
    3479 
    3480     template <typename InNodeMap, typename OutNodeMap>
    3481     static CombinedNodeMap<InNodeMap, const OutNodeMap>
    3482     combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
    3483       return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
    3484     }
    3485 
    3486     template <typename InNodeMap, typename OutNodeMap>
    3487     static CombinedNodeMap<const InNodeMap, const OutNodeMap>
    3488     combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
    3489       return CombinedNodeMap<const InNodeMap,
    3490         const OutNodeMap>(in_map, out_map);
     3467    template <typename IN, typename OUT>
     3468    static CombinedNodeMap<IN, OUT>
     3469    combinedNodeMap(IN& in_map, OUT& out_map) {
     3470      return CombinedNodeMap<IN, OUT>(in_map, out_map);
     3471    }
     3472
     3473    template <typename IN, typename OUT>
     3474    static CombinedNodeMap<const IN, OUT>
     3475    combinedNodeMap(const IN& in_map, OUT& out_map) {
     3476      return CombinedNodeMap<const IN, OUT>(in_map, out_map);
     3477    }
     3478
     3479    template <typename IN, typename OUT>
     3480    static CombinedNodeMap<IN, const OUT>
     3481    combinedNodeMap(IN& in_map, const OUT& out_map) {
     3482      return CombinedNodeMap<IN, const OUT>(in_map, out_map);
     3483    }
     3484
     3485    template <typename IN, typename OUT>
     3486    static CombinedNodeMap<const IN, const OUT>
     3487    combinedNodeMap(const IN& in_map, const OUT& out_map) {
     3488      return CombinedNodeMap<const IN, const OUT>(in_map, out_map);
    34913489    }
    34923490
     
    34963494    /// This map adaptor class adapts an arc map and a node map of the
    34973495    /// original digraph to get an arc map of the split digraph.
    3498     /// Its value type is inherited from the original arc map type
    3499     /// (\c ArcMap).
    3500     template <typename ArcMap, typename NodeMap>
     3496    /// Its value type is inherited from the original arc map type (\c AM).
     3497    /// \tparam AM The type of the arc map.
     3498    /// \tparam NM the type of the node map.
     3499    template <typename AM, typename NM>
    35013500    class CombinedArcMap {
    35023501    public:
     
    35053504      typedef Arc Key;
    35063505      /// The value type of the map
    3507       typedef typename ArcMap::Value Value;
    3508 
    3509       typedef typename MapTraits<ArcMap>::ReferenceMapTag ReferenceMapTag;
    3510       typedef typename MapTraits<ArcMap>::ReturnValue ReturnValue;
    3511       typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReturnValue;
    3512       typedef typename MapTraits<ArcMap>::ReturnValue Reference;
    3513       typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReference;
     3506      typedef typename AM::Value Value;
     3507
     3508      typedef typename MapTraits<AM>::ReferenceMapTag ReferenceMapTag;
     3509      typedef typename MapTraits<AM>::ReturnValue ReturnValue;
     3510      typedef typename MapTraits<AM>::ConstReturnValue ConstReturnValue;
     3511      typedef typename MapTraits<AM>::ReturnValue Reference;
     3512      typedef typename MapTraits<AM>::ConstReturnValue ConstReference;
    35143513
    35153514      /// Constructor
    3516       CombinedArcMap(ArcMap& arc_map, NodeMap& node_map)
     3515      CombinedArcMap(AM& arc_map, NM& node_map)
    35173516        : _arc_map(arc_map), _node_map(node_map) {}
    35183517
     
    35453544
    35463545    private:
    3547       ArcMap& _arc_map;
    3548       NodeMap& _node_map;
     3546
     3547      AM& _arc_map;
     3548      NM& _node_map;
     3549
    35493550    };
    35503551
  • lemon/bin_heap.h

    r463 r606  
    3434  ///\brief A Binary Heap implementation.
    3535  ///
    36   ///This class implements the \e binary \e heap data structure. A \e heap
    37   ///is a data structure for storing items with specified values called \e
    38   ///priorities in such a way that finding the item with minimum priority is
    39   ///efficient. \c Compare specifies the ordering of the priorities. In a heap
    40   ///one can change the priority of an item, add or erase an item, etc.
     36  ///This class implements the \e binary \e heap data structure.
     37  ///
     38  ///A \e heap is a data structure for storing items with specified values
     39  ///called \e priorities in such a way that finding the item with minimum
     40  ///priority is efficient. \c Comp specifies the ordering of the priorities.
     41  ///In a heap one can change the priority of an item, add or erase an
     42  ///item, etc.
    4143  ///
    42   ///\tparam _Prio Type of the priority of the items.
    43   ///\tparam _ItemIntMap A read and writable Item int map, used internally
     44  ///\tparam PR Type of the priority of the items.
     45  ///\tparam IM A read and writable item map with int values, used internally
    4446  ///to handle the cross references.
    45   ///\tparam _Compare A class for the ordering of the priorities. The
    46   ///default is \c std::less<_Prio>.
     47  ///\tparam Comp A functor class for the ordering of the priorities.
     48  ///The default is \c std::less<PR>.
    4749  ///
    4850  ///\sa FibHeap
    4951  ///\sa Dijkstra
    50   template <typename _Prio, typename _ItemIntMap,
    51             typename _Compare = std::less<_Prio> >
     52  template <typename PR, typename IM, typename Comp = std::less<PR> >
    5253  class BinHeap {
    5354
    5455  public:
    5556    ///\e
    56     typedef _ItemIntMap ItemIntMap;
    57     ///\e
    58     typedef _Prio Prio;
     57    typedef IM ItemIntMap;
     58    ///\e
     59    typedef PR Prio;
    5960    ///\e
    6061    typedef typename ItemIntMap::Key Item;
     
    6263    typedef std::pair<Item,Prio> Pair;
    6364    ///\e
    64     typedef _Compare Compare;
     65    typedef Comp Compare;
    6566
    6667    /// \brief Type to represent the items states.
     
    7071    /// heap's point of view, but may be useful to the user.
    7172    ///
    72     /// The ItemIntMap \e should be initialized in such way that it maps
    73     /// PRE_HEAP (-1) to any element to be put in the heap...
     73    /// The item-int map must be initialized in such way that it assigns
     74    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    7475    enum State {
    75       IN_HEAP = 0,
    76       PRE_HEAP = -1,
    77       POST_HEAP = -2
     76      IN_HEAP = 0,    ///< \e
     77      PRE_HEAP = -1,  ///< \e
     78      POST_HEAP = -2  ///< \e
    7879    };
    7980
    8081  private:
    81     std::vector<Pair> data;
    82     Compare comp;
    83     ItemIntMap &iim;
     82    std::vector<Pair> _data;
     83    Compare _comp;
     84    ItemIntMap &_iim;
    8485
    8586  public:
     
    8788    ///
    8889    /// The constructor.
    89     /// \param _iim should be given to the constructor, since it is used
     90    /// \param map should be given to the constructor, since it is used
     91    /// internally to handle the cross references. The value of the map
     92    /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
     93    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
     94
     95    /// \brief The constructor.
     96    ///
     97    /// The constructor.
     98    /// \param map should be given to the constructor, since it is used
    9099    /// internally to handle the cross references. The value of the map
    91100    /// should be PRE_HEAP (-1) for each element.
    92     explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
    93 
    94     /// \brief The constructor.
    95     ///
    96     /// The constructor.
    97     /// \param _iim should be given to the constructor, since it is used
    98     /// internally to handle the cross references. The value of the map
    99     /// should be PRE_HEAP (-1) for each element.
    100     ///
    101     /// \param _comp The comparator function object.
    102     BinHeap(ItemIntMap &_iim, const Compare &_comp)
    103       : iim(_iim), comp(_comp) {}
     101    ///
     102    /// \param comp The comparator function object.
     103    BinHeap(ItemIntMap &map, const Compare &comp)
     104      : _iim(map), _comp(comp) {}
    104105
    105106
     
    107108    ///
    108109    /// \brief Returns the number of items stored in the heap.
    109     int size() const { return data.size(); }
     110    int size() const { return _data.size(); }
    110111
    111112    /// \brief Checks if the heap stores no items.
    112113    ///
    113114    /// Returns \c true if and only if the heap stores no items.
    114     bool empty() const { return data.empty(); }
     115    bool empty() const { return _data.empty(); }
    115116
    116117    /// \brief Make empty this heap.
     
    121122    /// each item to \c PRE_HEAP.
    122123    void clear() {
    123       data.clear();
     124      _data.clear();
    124125    }
    125126
     
    129130    static int second_child(int i) { return 2*i+2; }
    130131    bool less(const Pair &p1, const Pair &p2) const {
    131       return comp(p1.second, p2.second);
     132      return _comp(p1.second, p2.second);
    132133    }
    133134
    134135    int bubble_up(int hole, Pair p) {
    135136      int par = parent(hole);
    136       while( hole>0 && less(p,data[par]) ) {
    137         move(data[par],hole);
     137      while( hole>0 && less(p,_data[par]) ) {
     138        move(_data[par],hole);
    138139        hole = par;
    139140        par = parent(hole);
     
    146147      int child = second_child(hole);
    147148      while(child < length) {
    148         if( less(data[child-1], data[child]) ) {
     149        if( less(_data[child-1], _data[child]) ) {
    149150          --child;
    150151        }
    151         if( !less(data[child], p) )
     152        if( !less(_data[child], p) )
    152153          goto ok;
    153         move(data[child], hole);
     154        move(_data[child], hole);
    154155        hole = child;
    155156        child = second_child(hole);
    156157      }
    157158      child--;
    158       if( child<length && less(data[child], p) ) {
    159         move(data[child], hole);
     159      if( child<length && less(_data[child], p) ) {
     160        move(_data[child], hole);
    160161        hole=child;
    161162      }
     
    166167
    167168    void move(const Pair &p, int i) {
    168       data[i] = p;
    169       iim.set(p.first, i);
     169      _data[i] = p;
     170      _iim.set(p.first, i);
    170171    }
    171172
     
    176177    /// \param p The pair to insert.
    177178    void push(const Pair &p) {
    178       int n = data.size();
    179       data.resize(n+1);
     179      int n = _data.size();
     180      _data.resize(n+1);
    180181      bubble_up(n, p);
    181182    }
     
    194195    /// \pre The heap must be nonempty.
    195196    Item top() const {
    196       return data[0].first;
     197      return _data[0].first;
    197198    }
    198199
     
    202203    /// \pre The heap must be nonempty.
    203204    Prio prio() const {
    204       return data[0].second;
     205      return _data[0].second;
    205206    }
    206207
     
    211212    /// \pre The heap must be non-empty.
    212213    void pop() {
    213       int n = data.size()-1;
    214       iim.set(data[0].first, POST_HEAP);
     214      int n = _data.size()-1;
     215      _iim.set(_data[0].first, POST_HEAP);
    215216      if (n > 0) {
    216         bubble_down(0, data[n], n);
    217       }
    218       data.pop_back();
     217        bubble_down(0, _data[n], n);
     218      }
     219      _data.pop_back();
    219220    }
    220221
     
    225226    /// \pre The item should be in the heap.
    226227    void erase(const Item &i) {
    227       int h = iim[i];
    228       int n = data.size()-1;
    229       iim.set(data[h].first, POST_HEAP);
     228      int h = _iim[i];
     229      int n = _data.size()-1;
     230      _iim.set(_data[h].first, POST_HEAP);
    230231      if( h < n ) {
    231         if ( bubble_up(h, data[n]) == h) {
    232           bubble_down(h, data[n], n);
     232        if ( bubble_up(h, _data[n]) == h) {
     233          bubble_down(h, _data[n], n);
    233234        }
    234235      }
    235       data.pop_back();
     236      _data.pop_back();
    236237    }
    237238
     
    240241    ///
    241242    /// This function returns the priority of item \c i.
     243    /// \param i The item.
    242244    /// \pre \c i must be in the heap.
    243     /// \param i The item.
    244245    Prio operator[](const Item &i) const {
    245       int idx = iim[i];
    246       return data[idx].second;
     246      int idx = _iim[i];
     247      return _data[idx].second;
    247248    }
    248249
     
    255256    /// \param p The priority.
    256257    void set(const Item &i, const Prio &p) {
    257       int idx = iim[i];
     258      int idx = _iim[i];
    258259      if( idx < 0 ) {
    259260        push(i,p);
    260261      }
    261       else if( comp(p, data[idx].second) ) {
     262      else if( _comp(p, _data[idx].second) ) {
    262263        bubble_up(idx, Pair(i,p));
    263264      }
    264265      else {
    265         bubble_down(idx, Pair(i,p), data.size());
     266        bubble_down(idx, Pair(i,p), _data.size());
    266267      }
    267268    }
     
    270271    ///
    271272    /// This method decreases the priority of item \c i to \c p.
     273    /// \param i The item.
     274    /// \param p The priority.
    272275    /// \pre \c i must be stored in the heap with priority at least \c
    273276    /// p relative to \c Compare.
     277    void decrease(const Item &i, const Prio &p) {
     278      int idx = _iim[i];
     279      bubble_up(idx, Pair(i,p));
     280    }
     281
     282    /// \brief Increases the priority of \c i to \c p.
     283    ///
     284    /// This method sets the priority of item \c i to \c p.
    274285    /// \param i The item.
    275286    /// \param p The priority.
    276     void decrease(const Item &i, const Prio &p) {
    277       int idx = iim[i];
    278       bubble_up(idx, Pair(i,p));
    279     }
    280 
    281     /// \brief Increases the priority of \c i to \c p.
    282     ///
    283     /// This method sets the priority of item \c i to \c p.
    284287    /// \pre \c i must be stored in the heap with priority at most \c
    285288    /// p relative to \c Compare.
    286     /// \param i The item.
    287     /// \param p The priority.
    288289    void increase(const Item &i, const Prio &p) {
    289       int idx = iim[i];
    290       bubble_down(idx, Pair(i,p), data.size());
     290      int idx = _iim[i];
     291      bubble_down(idx, Pair(i,p), _data.size());
    291292    }
    292293
     
    300301    /// \param i The item.
    301302    State state(const Item &i) const {
    302       int s = iim[i];
     303      int s = _iim[i];
    303304      if( s>=0 )
    304305        s=0;
     
    320321          erase(i);
    321322        }
    322         iim[i] = st;
     323        _iim[i] = st;
    323324        break;
    324325      case IN_HEAP:
     
    334335    /// with the same prioriority as prevoiusly the \c i item.
    335336    void replace(const Item& i, const Item& j) {
    336       int idx = iim[i];
    337       iim.set(i, iim[j]);
    338       iim.set(j, idx);
    339       data[idx].first = j;
     337      int idx = _iim[i];
     338      _iim.set(i, _iim[j]);
     339      _iim.set(j, idx);
     340      _data[idx].first = j;
    340341    }
    341342
  • lemon/bits/edge_set_extender.h

    r566 r606  
    2525#include <lemon/bits/map_extender.h>
    2626
    27 ///\ingroup digraphbits
    28 ///\file
    29 ///\brief Extenders for the arc set types
     27//\ingroup digraphbits
     28//\file
     29//\brief Extenders for the arc set types
    3030namespace lemon {
    3131
    32   /// \ingroup digraphbits
    33   ///
    34   /// \brief Extender for the ArcSets
     32  // \ingroup digraphbits
     33  //
     34  // \brief Extender for the ArcSets
    3535  template <typename Base>
    3636  class ArcSetExtender : public Base {
     
    7373    // Alteration notifier extensions
    7474
    75     /// The arc observer registry.
     75    // The arc observer registry.
    7676    typedef AlterationNotifier<ArcSetExtender, Arc> ArcNotifier;
    7777
     
    8484    using Parent::notifier;
    8585
    86     /// \brief Gives back the arc alteration notifier.
    87     ///
    88     /// Gives back the arc alteration notifier.
     86    // Gives back the arc alteration notifier.
    8987    ArcNotifier& notifier(Arc) const {
    9088      return arc_notifier;
     
    186184    };
    187185
    188     /// \brief Base node of the iterator
    189     ///
    190     /// Returns the base node (ie. the source in this case) of the iterator
     186    // \brief Base node of the iterator
     187    //
     188    // Returns the base node (ie. the source in this case) of the iterator
    191189    Node baseNode(const OutArcIt &e) const {
    192190      return Parent::source(static_cast<const Arc&>(e));
    193191    }
    194     /// \brief Running node of the iterator
    195     ///
    196     /// Returns the running node (ie. the target in this case) of the
    197     /// iterator
     192    // \brief Running node of the iterator
     193    //
     194    // Returns the running node (ie. the target in this case) of the
     195    // iterator
    198196    Node runningNode(const OutArcIt &e) const {
    199197      return Parent::target(static_cast<const Arc&>(e));
    200198    }
    201199
    202     /// \brief Base node of the iterator
    203     ///
    204     /// Returns the base node (ie. the target in this case) of the iterator
     200    // \brief Base node of the iterator
     201    //
     202    // Returns the base node (ie. the target in this case) of the iterator
    205203    Node baseNode(const InArcIt &e) const {
    206204      return Parent::target(static_cast<const Arc&>(e));
    207205    }
    208     /// \brief Running node of the iterator
    209     ///
    210     /// Returns the running node (ie. the source in this case) of the
    211     /// iterator
     206    // \brief Running node of the iterator
     207    //
     208    // Returns the running node (ie. the source in this case) of the
     209    // iterator
    212210    Node runningNode(const InArcIt &e) const {
    213211      return Parent::source(static_cast<const Arc&>(e));
     
    272270
    273271
    274   /// \ingroup digraphbits
    275   ///
    276   /// \brief Extender for the EdgeSets
     272  // \ingroup digraphbits
     273  //
     274  // \brief Extender for the EdgeSets
    277275  template <typename Base>
    278276  class EdgeSetExtender : public Base {
     
    493491    };
    494492
    495     /// \brief Base node of the iterator
    496     ///
    497     /// Returns the base node (ie. the source in this case) of the iterator
     493    // \brief Base node of the iterator
     494    //
     495    // Returns the base node (ie. the source in this case) of the iterator
    498496    Node baseNode(const OutArcIt &e) const {
    499497      return Parent::source(static_cast<const Arc&>(e));
    500498    }
    501     /// \brief Running node of the iterator
    502     ///
    503     /// Returns the running node (ie. the target in this case) of the
    504     /// iterator
     499    // \brief Running node of the iterator
     500    //
     501    // Returns the running node (ie. the target in this case) of the
     502    // iterator
    505503    Node runningNode(const OutArcIt &e) const {
    506504      return Parent::target(static_cast<const Arc&>(e));
    507505    }
    508506
    509     /// \brief Base node of the iterator
    510     ///
    511     /// Returns the base node (ie. the target in this case) of the iterator
     507    // \brief Base node of the iterator
     508    //
     509    // Returns the base node (ie. the target in this case) of the iterator
    512510    Node baseNode(const InArcIt &e) const {
    513511      return Parent::target(static_cast<const Arc&>(e));
    514512    }
    515     /// \brief Running node of the iterator
    516     ///
    517     /// Returns the running node (ie. the source in this case) of the
    518     /// iterator
     513    // \brief Running node of the iterator
     514    //
     515    // Returns the running node (ie. the source in this case) of the
     516    // iterator
    519517    Node runningNode(const InArcIt &e) const {
    520518      return Parent::source(static_cast<const Arc&>(e));
    521519    }
    522520
    523     /// Base node of the iterator
    524     ///
    525     /// Returns the base node of the iterator
     521    // Base node of the iterator
     522    //
     523    // Returns the base node of the iterator
    526524    Node baseNode(const IncEdgeIt &e) const {
    527525      return e.direction ? u(e) : v(e);
    528526    }
    529     /// Running node of the iterator
    530     ///
    531     /// Returns the running node of the iterator
     527    // Running node of the iterator
     528    //
     529    // Returns the running node of the iterator
    532530    Node runningNode(const IncEdgeIt &e) const {
    533531      return e.direction ? v(e) : u(e);
  • lemon/circulation.h

    r525 r606  
    216216    ///@{
    217217
    218     template <typename _FlowMap>
     218    template <typename T>
    219219    struct SetFlowMapTraits : public Traits {
    220       typedef _FlowMap FlowMap;
     220      typedef T FlowMap;
    221221      static FlowMap *createFlowMap(const Digraph&) {
    222222        LEMON_ASSERT(false, "FlowMap is not initialized");
     
    230230    /// \ref named-templ-param "Named parameter" for setting FlowMap
    231231    /// type.
    232     template <typename _FlowMap>
     232    template <typename T>
    233233    struct SetFlowMap
    234234      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    235                            SetFlowMapTraits<_FlowMap> > {
     235                           SetFlowMapTraits<T> > {
    236236      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    237                           SetFlowMapTraits<_FlowMap> > Create;
     237                          SetFlowMapTraits<T> > Create;
    238238    };
    239239
    240     template <typename _Elevator>
     240    template <typename T>
    241241    struct SetElevatorTraits : public Traits {
    242       typedef _Elevator Elevator;
     242      typedef T Elevator;
    243243      static Elevator *createElevator(const Digraph&, int) {
    244244        LEMON_ASSERT(false, "Elevator is not initialized");
     
    256256    /// \ref run() or \ref init().
    257257    /// \sa SetStandardElevator
    258     template <typename _Elevator>
     258    template <typename T>
    259259    struct SetElevator
    260260      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    261                            SetElevatorTraits<_Elevator> > {
     261                           SetElevatorTraits<T> > {
    262262      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    263                           SetElevatorTraits<_Elevator> > Create;
     263                          SetElevatorTraits<T> > Create;
    264264    };
    265265
    266     template <typename _Elevator>
     266    template <typename T>
    267267    struct SetStandardElevatorTraits : public Traits {
    268       typedef _Elevator Elevator;
     268      typedef T Elevator;
    269269      static Elevator *createElevator(const Digraph& digraph, int max_level) {
    270270        return new Elevator(digraph, max_level);
     
    284284    /// before calling \ref run() or \ref init().
    285285    /// \sa SetElevator
    286     template <typename _Elevator>
     286    template <typename T>
    287287    struct SetStandardElevator
    288288      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    289                        SetStandardElevatorTraits<_Elevator> > {
     289                       SetStandardElevatorTraits<T> > {
    290290      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    291                       SetStandardElevatorTraits<_Elevator> > Create;
     291                      SetStandardElevatorTraits<T> > Create;
    292292    };
    293293
     
    683683    ///
    684684    /// \note This function calls \ref barrier() for each node,
    685     /// so it runs in \f$O(n)\f$ time.
     685    /// so it runs in O(n) time.
    686686    ///
    687687    /// \pre Either \ref run() or \ref init() must be called before
  • lemon/concepts/graph.h

    r576 r606  
    602602      /// \brief Opposite node on an arc
    603603      ///
    604       /// \return the opposite of the given Node on the given Edge
     604      /// \return The opposite of the given node on the given edge.
    605605      Node oppositeNode(Node, Edge) const { return INVALID; }
    606606
    607607      /// \brief First node of the edge.
    608608      ///
    609       /// \return the first node of the given Edge.
     609      /// \return The first node of the given edge.
    610610      ///
    611611      /// Naturally edges don't have direction and thus
    612       /// don't have source and target node. But we use these two methods
    613       /// to query the two nodes of the arc. The direction of the arc
    614       /// which arises this way is called the inherent direction of the
     612      /// don't have source and target node. However we use \c u() and \c v()
     613      /// methods to query the two nodes of the arc. The direction of the
     614      /// arc which arises this way is called the inherent direction of the
    615615      /// edge, and is used to define the "default" direction
    616616      /// of the directed versions of the arcs.
    617       /// \sa direction
     617      /// \sa v()
     618      /// \sa direction()
    618619      Node u(Edge) const { return INVALID; }
    619620
    620621      /// \brief Second node of the edge.
     622      ///
     623      /// \return The second node of the given edge.
     624      ///
     625      /// Naturally edges don't have direction and thus
     626      /// don't have source and target node. However we use \c u() and \c v()
     627      /// methods to query the two nodes of the arc. The direction of the
     628      /// arc which arises this way is called the inherent direction of the
     629      /// edge, and is used to define the "default" direction
     630      /// of the directed versions of the arcs.
     631      /// \sa u()
     632      /// \sa direction()
    621633      Node v(Edge) const { return INVALID; }
    622634
  • lemon/concepts/graph_components.h

    r581 r606  
    2121///\brief The concept of graph components.
    2222
    23 
    2423#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
    2524#define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
     
    4544
    4645#ifndef DOXYGEN
    47     template <char _selector = '0'>
     46    template <char sel = '0'>
    4847#endif
    4948    class GraphItem {
     
    297296    /// The most of the base digraphs should conform to this concept.
    298297    /// The id's are unique and immutable.
    299     template <typename _Base = BaseDigraphComponent>
    300     class IDableDigraphComponent : public _Base {
    301     public:
    302 
    303       typedef _Base Base;
     298    template <typename BAS = BaseDigraphComponent>
     299    class IDableDigraphComponent : public BAS {
     300    public:
     301
     302      typedef BAS Base;
    304303      typedef typename Base::Node Node;
    305304      typedef typename Base::Arc Arc;
     
    375374    /// most of the base undirected graphs should conform to this
    376375    /// concept.  The id's are unique and immutable.
    377     template <typename _Base = BaseGraphComponent>
    378     class IDableGraphComponent : public IDableDigraphComponent<_Base> {
    379     public:
    380 
    381       typedef _Base Base;
     376    template <typename BAS = BaseGraphComponent>
     377    class IDableGraphComponent : public IDableDigraphComponent<BAS> {
     378    public:
     379
     380      typedef BAS Base;
    382381      typedef typename Base::Edge Edge;
    383382
    384       using IDableDigraphComponent<_Base>::id;
     383      using IDableDigraphComponent<Base>::id;
    385384
    386385      /// \brief Gives back an unique integer id for the Edge.
     
    426425    /// Skeleton class for graph NodeIt and ArcIt.
    427426    ///
    428     template <typename _Graph, typename _Item>
    429     class GraphItemIt : public _Item {
     427    template <typename GR, typename Item>
     428    class GraphItemIt : public Item {
    430429    public:
    431430      /// \brief Default constructor.
     
    443442      /// Sets the iterator to the first item of \c the graph.
    444443      ///
    445       explicit GraphItemIt(const _Graph&) {}
     444      explicit GraphItemIt(const GR&) {}
    446445      /// \brief Invalid constructor \& conversion.
    447446      ///
     
    480479          ++(++it1);
    481480
    482           _Item bi = it1;
     481          Item bi = it1;
    483482          bi = it2;
    484483        }
    485         _Graph& g;
     484        GR& g;
    486485      };
    487486    };
     
    490489    ///
    491490    /// \note Because InArcIt and OutArcIt may not inherit from the same
    492     /// base class, the _selector is a additional template parameter. For
    493     /// InArcIt you should instantiate it with character 'i' and for
     491    /// base class, the \c sel is a additional template parameter (selector).
     492    /// For InArcIt you should instantiate it with character 'i' and for
    494493    /// OutArcIt with 'o'.
    495     template <typename _Graph,
    496               typename _Item = typename _Graph::Arc,
    497               typename _Base = typename _Graph::Node,
    498               char _selector = '0'>
    499     class GraphIncIt : public _Item {
     494    template <typename GR,
     495              typename Item = typename GR::Arc,
     496              typename Base = typename GR::Node,
     497              char sel = '0'>
     498    class GraphIncIt : public Item {
    500499    public:
    501500      /// \brief Default constructor.
     
    508507      /// Copy constructor.
    509508      ///
    510       GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}
     509      GraphIncIt(GraphIncIt const& gi) : Item(gi) {}
    511510      /// \brief Sets the iterator to the first arc incoming into or outgoing
    512511      /// from the node.
     
    515514      /// from the node.
    516515      ///
    517       explicit GraphIncIt(const _Graph&, const _Base&) {}
     516      explicit GraphIncIt(const GR&, const Base&) {}
    518517      /// \brief Invalid constructor \& conversion.
    519518      ///
     
    547546      struct Constraints {
    548547        void constraints() {
    549           checkConcept<GraphItem<_selector>, _GraphIncIt>();
     548          checkConcept<GraphItem<sel>, _GraphIncIt>();
    550549          _GraphIncIt it1(graph, node);
    551550          _GraphIncIt it2;
     
    554553          ++it2 = it1;
    555554          ++(++it1);
    556           _Item e = it1;
     555          Item e = it1;
    557556          e = it2;
    558557
    559558        }
    560559
    561         _Item arc;
    562         _Base node;
    563         _Graph graph;
     560        Item arc;
     561        Base node;
     562        GR graph;
    564563        _GraphIncIt it;
    565564      };
     
    572571    /// iterator based iterable interface for the digraph structure.
    573572    /// This concept is part of the Digraph concept.
    574     template <typename _Base = BaseDigraphComponent>
    575     class IterableDigraphComponent : public _Base {
    576 
    577     public:
    578 
    579       typedef _Base Base;
     573    template <typename BAS = BaseDigraphComponent>
     574    class IterableDigraphComponent : public BAS {
     575
     576    public:
     577
     578      typedef BAS Base;
    580579      typedef typename Base::Node Node;
    581580      typedef typename Base::Arc Arc;
     
    757756    /// based iterable interface for the undirected graph structure.
    758757    /// This concept is part of the Graph concept.
    759     template <typename _Base = BaseGraphComponent>
    760     class IterableGraphComponent : public IterableDigraphComponent<_Base> {
    761     public:
    762 
    763       typedef _Base Base;
     758    template <typename BAS = BaseGraphComponent>
     759    class IterableGraphComponent : public IterableDigraphComponent<BAS> {
     760    public:
     761
     762      typedef BAS Base;
    764763      typedef typename Base::Node Node;
    765764      typedef typename Base::Arc Arc;
     
    774773      /// @{
    775774
    776       using IterableDigraphComponent<_Base>::first;
    777       using IterableDigraphComponent<_Base>::next;
     775      using IterableDigraphComponent<Base>::first;
     776      using IterableDigraphComponent<Base>::next;
    778777
    779778      /// \brief Gives back the first edge in the iterating
     
    809808      void nextInc(Edge&, bool&) const {}
    810809
    811       using IterableDigraphComponent<_Base>::baseNode;
    812       using IterableDigraphComponent<_Base>::runningNode;
     810      using IterableDigraphComponent<Base>::baseNode;
     811      using IterableDigraphComponent<Base>::runningNode;
    813812
    814813      /// @}
     
    876875
    877876        const _Graph& graph;
    878 
    879877      };
    880878    };
     
    888886    /// alteration occured in the digraph all the observers will
    889887    /// notified about it.
    890     template <typename _Base = BaseDigraphComponent>
    891     class AlterableDigraphComponent : public _Base {
    892     public:
    893 
    894       typedef _Base Base;
     888    template <typename BAS = BaseDigraphComponent>
     889    class AlterableDigraphComponent : public BAS {
     890    public:
     891
     892      typedef BAS Base;
    895893      typedef typename Base::Node Node;
    896894      typedef typename Base::Arc Arc;
     
    946944    /// alteration occured in the graph all the observers will
    947945    /// notified about it.
    948     template <typename _Base = BaseGraphComponent>
    949     class AlterableGraphComponent : public AlterableDigraphComponent<_Base> {
    950     public:
    951 
    952       typedef _Base Base;
     946    template <typename BAS = BaseGraphComponent>
     947    class AlterableGraphComponent : public AlterableDigraphComponent<BAS> {
     948    public:
     949
     950      typedef BAS Base;
    953951      typedef typename Base::Edge Edge;
    954952
     
    975973
    976974        const _Graph& graph;
    977 
    978       };
    979 
     975      };
    980976    };
    981977
     
    985981    /// (NodeMap, ArcMap), that is maps that can be used to
    986982    /// associate data to graph descriptors (nodes or arcs).
    987     template <typename _Graph, typename _Item, typename _Value>
    988     class GraphMap : public ReadWriteMap<_Item, _Value> {
    989     public:
    990 
    991       typedef ReadWriteMap<_Item, _Value> Parent;
     983    template <typename GR, typename K, typename V>
     984    class GraphMap : public ReadWriteMap<K, V> {
     985    public:
     986
     987      typedef ReadWriteMap<K, V> Parent;
    992988
    993989      /// The graph type of the map.
    994       typedef _Graph Graph;
     990      typedef GR Graph;
    995991      /// The key type of the map.
    996       typedef _Item Key;
     992      typedef K Key;
    997993      /// The value type of the map.
    998       typedef _Value Value;
     994      typedef V Value;
    999995
    1000996      /// \brief Construct a new map.
     
    10561052    /// map interface for the digraph structure.
    10571053    /// This concept is part of the Digraph concept.
    1058     template <typename _Base = BaseDigraphComponent>
    1059     class MappableDigraphComponent : public _Base  {
    1060     public:
    1061 
    1062       typedef _Base Base;
     1054    template <typename BAS = BaseDigraphComponent>
     1055    class MappableDigraphComponent : public BAS  {
     1056    public:
     1057
     1058      typedef BAS Base;
    10631059      typedef typename Base::Node Node;
    10641060      typedef typename Base::Arc Arc;
     
    10701066      /// ReadWrite map of the nodes.
    10711067      ///
    1072       template <typename _Value>
    1073       class NodeMap : public GraphMap<Digraph, Node, _Value> {
     1068      template <typename V>
     1069      class NodeMap : public GraphMap<Digraph, Node, V> {
    10741070      public:
    1075         typedef GraphMap<MappableDigraphComponent, Node, _Value> Parent;
     1071        typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
    10761072
    10771073        /// \brief Construct a new map.
     
    10841080        ///
    10851081        /// Construct a new map for the digraph and initalise the values.
    1086         NodeMap(const MappableDigraphComponent& digraph, const _Value& value)
     1082        NodeMap(const MappableDigraphComponent& digraph, const V& value)
    10871083          : Parent(digraph, value) {}
    10881084
     
    10981094        template <typename CMap>
    10991095        NodeMap& operator=(const CMap&) {
    1100           checkConcept<ReadMap<Node, _Value>, CMap>();
     1096          checkConcept<ReadMap<Node, V>, CMap>();
    11011097          return *this;
    11021098        }
     
    11081104      /// ReadWrite map of the arcs.
    11091105      ///
    1110       template <typename _Value>
    1111       class ArcMap : public GraphMap<Digraph, Arc, _Value> {
     1106      template <typename V>
     1107      class ArcMap : public GraphMap<Digraph, Arc, V> {
    11121108      public:
    1113         typedef GraphMap<MappableDigraphComponent, Arc, _Value> Parent;
     1109        typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;
    11141110
    11151111        /// \brief Construct a new map.
     
    11221118        ///
    11231119        /// Construct a new map for the digraph and initalise the values.
    1124         ArcMap(const MappableDigraphComponent& digraph, const _Value& value)
     1120        ArcMap(const MappableDigraphComponent& digraph, const V& value)
    11251121          : Parent(digraph, value) {}
    11261122
     
    11361132        template <typename CMap>
    11371133        ArcMap& operator=(const CMap&) {
    1138           checkConcept<ReadMap<Arc, _Value>, CMap>();
     1134          checkConcept<ReadMap<Arc, V>, CMap>();
    11391135          return *this;
    11401136        }
     
    11921188    /// map interface for the graph structure.
    11931189    /// This concept is part of the Graph concept.
    1194     template <typename _Base = BaseGraphComponent>
    1195     class MappableGraphComponent : public MappableDigraphComponent<_Base>  {
    1196     public:
    1197 
    1198       typedef _Base Base;
     1190    template <typename BAS = BaseGraphComponent>
     1191    class MappableGraphComponent : public MappableDigraphComponent<BAS>  {
     1192    public:
     1193
     1194      typedef BAS Base;
    11991195      typedef typename Base::Edge Edge;
    12001196
     
    12051201      /// ReadWrite map of the edges.
    12061202      ///
    1207       template <typename _Value>
    1208       class EdgeMap : public GraphMap<Graph, Edge, _Value> {
     1203      template <typename V>
     1204      class EdgeMap : public GraphMap<Graph, Edge, V> {
    12091205      public:
    1210         typedef GraphMap<MappableGraphComponent, Edge, _Value> Parent;
     1206        typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
    12111207
    12121208        /// \brief Construct a new map.
     
    12191215        ///
    12201216        /// Construct a new map for the graph and initalise the values.
    1221         EdgeMap(const MappableGraphComponent& graph, const _Value& value)
     1217        EdgeMap(const MappableGraphComponent& graph, const V& value)
    12221218          : Parent(graph, value) {}
    12231219
     
    12331229        template <typename CMap>
    12341230        EdgeMap& operator=(const CMap&) {
    1235           checkConcept<ReadMap<Edge, _Value>, CMap>();
     1231          checkConcept<ReadMap<Edge, V>, CMap>();
    12361232          return *this;
    12371233        }
     
    12771273    /// difference between the base and this interface is that the
    12781274    /// digraph alterations should handled already on this level.
    1279     template <typename _Base = BaseDigraphComponent>
    1280     class ExtendableDigraphComponent : public _Base {
    1281     public:
    1282       typedef _Base Base;
    1283 
    1284       typedef typename _Base::Node Node;
    1285       typedef typename _Base::Arc Arc;
     1275    template <typename BAS = BaseDigraphComponent>
     1276    class ExtendableDigraphComponent : public BAS {
     1277    public:
     1278      typedef BAS Base;
     1279
     1280      typedef typename Base::Node Node;
     1281      typedef typename Base::Arc Arc;
    12861282
    12871283      /// \brief Adds a new node to the digraph.
     
    13221318    /// that the graph alterations should handled already on this
    13231319    /// level.
    1324     template <typename _Base = BaseGraphComponent>
    1325     class ExtendableGraphComponent : public _Base {
    1326     public:
    1327 
    1328       typedef _Base Base;
    1329       typedef typename _Base::Node Node;
    1330       typedef typename _Base::Edge Edge;
     1320    template <typename BAS = BaseGraphComponent>
     1321    class ExtendableGraphComponent : public BAS {
     1322    public:
     1323
     1324      typedef BAS Base;
     1325      typedef typename Base::Node Node;
     1326      typedef typename Base::Edge Edge;
    13311327
    13321328      /// \brief Adds a new node to the graph.
     
    13661362    /// the base and this interface is that the digraph alterations
    13671363    /// should handled already on this level.
    1368     template <typename _Base = BaseDigraphComponent>
    1369     class ErasableDigraphComponent : public _Base {
    1370     public:
    1371 
    1372       typedef _Base Base;
     1364    template <typename BAS = BaseDigraphComponent>
     1365    class ErasableDigraphComponent : public BAS {
     1366    public:
     1367
     1368      typedef BAS Base;
    13731369      typedef typename Base::Node Node;
    13741370      typedef typename Base::Arc Arc;
     
    14061402    /// main difference between the base and this interface is that
    14071403    /// the graph alterations should handled already on this level.
    1408     template <typename _Base = BaseGraphComponent>
    1409     class ErasableGraphComponent : public _Base {
    1410     public:
    1411 
    1412       typedef _Base Base;
     1404    template <typename BAS = BaseGraphComponent>
     1405    class ErasableGraphComponent : public BAS {
     1406    public:
     1407
     1408      typedef BAS Base;
    14131409      typedef typename Base::Node Node;
    14141410      typedef typename Base::Edge Edge;
     
    14461442    /// the base and this interface is that the digraph alterations
    14471443    /// should handled already on this level.
    1448     template <typename _Base = BaseDigraphComponent>
    1449     class ClearableDigraphComponent : public _Base {
    1450     public:
    1451 
    1452       typedef _Base Base;
     1444    template <typename BAS = BaseDigraphComponent>
     1445    class ClearableDigraphComponent : public BAS {
     1446    public:
     1447
     1448      typedef BAS Base;
    14531449
    14541450      /// \brief Erase all nodes and arcs from the digraph.
     
    14751471    /// main difference between the base and this interface is that
    14761472    /// the graph alterations should handled already on this level.
    1477     template <typename _Base = BaseGraphComponent>
    1478     class ClearableGraphComponent : public ClearableDigraphComponent<_Base> {
    1479     public:
    1480 
    1481       typedef _Base Base;
     1473    template <typename BAS = BaseGraphComponent>
     1474    class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {
     1475    public:
     1476
     1477      typedef BAS Base;
    14821478
    14831479      template <typename _Graph>
  • lemon/concepts/heap.h

    r576 r606  
    3636    /// \brief The heap concept.
    3737    ///
    38     /// Concept class describing the main interface of heaps.
    39     template <typename Priority, typename ItemIntMap>
     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.
     43    ///
     44    /// \tparam PR Type of the priority of the items.
     45    /// \tparam IM A read and writable item map with int values, used
     46    /// internally to handle the cross references.
     47    /// \tparam Comp A functor class for the ordering of the priorities.
     48    /// The default is \c std::less<PR>.
     49#ifdef DOXYGEN
     50    template <typename PR, typename IM, typename Comp = std::less<PR> >
     51#else
     52    template <typename PR, typename IM>
     53#endif
    4054    class Heap {
    4155    public:
    4256
     57      /// Type of the item-int map.
     58      typedef IM ItemIntMap;
     59      /// Type of the priorities.
     60      typedef PR Prio;
    4361      /// Type of the items stored in the heap.
    4462      typedef typename ItemIntMap::Key Item;
    45 
    46       /// Type of the priorities.
    47       typedef Priority Prio;
    4863
    4964      /// \brief Type to represent the states of the items.
     
    5469      /// the user.
    5570      ///
    56       /// The \c ItemIntMap must be initialized in such a way, that it
    57       /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item.
     71      /// The item-int map must be initialized in such way that it assigns
     72      /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    5873      enum State {
    59         IN_HEAP = 0,
    60         PRE_HEAP = -1,
    61         POST_HEAP = -2
     74        IN_HEAP = 0,    ///< The "in heap" state constant.
     75        PRE_HEAP = -1,  ///< The "pre heap" state constant.
     76        POST_HEAP = -2  ///< The "post heap" state constant.
    6277      };
    6378
     
    120135      ///
    121136      /// Returns the priority of the given item.
     137      /// \param i The item.
    122138      /// \pre \c i must be in the heap.
    123       /// \param i The item.
    124139      Prio operator[](const Item &i) const {}
    125140
     
    138153      ///
    139154      /// Decreases the priority of an item to the given value.
     155      /// \param i The item.
     156      /// \param p The priority.
    140157      /// \pre \c i must be stored in the heap with priority at least \c p.
     158      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.
    141163      /// \param i The item.
    142164      /// \param p The priority.
    143       void decrease(const Item &i, const Prio &p) {}
    144 
    145       /// \brief Increases the priority of an item to the given value.
    146       ///
    147       /// Increases the priority of an item to the given value.
    148165      /// \pre \c i must be stored in the heap with priority at most \c p.
    149       /// \param i The item.
    150       /// \param p The priority.
    151166      void increase(const Item &i, const Prio &p) {}
    152167
  • lemon/concepts/path.h

    r576 r606  
    3939    /// A skeleton structure for representing directed paths in a
    4040    /// digraph.
    41     /// \tparam _Digraph The digraph type in which the path is.
     41    /// \tparam GR The digraph type in which the path is.
    4242    ///
    4343    /// In a sense, the path can be treated as a list of arcs. The
     
    4646    /// paths cannot store the source.
    4747    ///
    48     template <typename _Digraph>
     48    template <typename GR>
    4949    class Path {
    5050    public:
    5151
    5252      /// Type of the underlying digraph.
    53       typedef _Digraph Digraph;
     53      typedef GR Digraph;
    5454      /// Arc type of the underlying digraph.
    5555      typedef typename Digraph::Arc Arc;
     
    206206    /// assigned to a real path and the dumpers can be implemented as
    207207    /// an adaptor class to the predecessor map.
    208 
    209     /// \tparam _Digraph The digraph type in which the path is.
     208    ///
     209    /// \tparam GR The digraph type in which the path is.
    210210    ///
    211211    /// The paths can be constructed from any path type by a
    212212    /// template constructor or a template assignment operator.
    213     ///
    214     template <typename _Digraph>
     213    template <typename GR>
    215214    class PathDumper {
    216215    public:
    217216
    218217      /// Type of the underlying digraph.
    219       typedef _Digraph Digraph;
     218      typedef GR Digraph;
    220219      /// Arc type of the underlying digraph.
    221220      typedef typename Digraph::Arc Arc;
  • lemon/connectivity.h

    r463 r606  
    4747  /// Check whether the given undirected graph is connected.
    4848  /// \param graph The undirected graph.
    49   /// \return %True when there is path between any two nodes in the graph.
     49  /// \return \c true when there is path between any two nodes in the graph.
    5050  /// \note By definition, the empty graph is connected.
    5151  template <typename Graph>
     
    235235  /// graph is strongly connected when any two nodes of the graph are
    236236  /// connected with directed paths in both direction.
    237   /// \return %False when the graph is not strongly connected.
     237  /// \return \c false when the graph is not strongly connected.
    238238  /// \see connected
    239239  ///
     
    710710  ///
    711711  /// \param graph The graph.
    712   /// \return %True when the graph bi-node-connected.
     712  /// \return \c true when the graph bi-node-connected.
    713713  template <typename Graph>
    714714  bool biNodeConnected(const Graph& graph) {
     
    12311231  /// of the map will be set exactly once, the values will be set descending
    12321232  /// order.
    1233   /// \return %False when the graph is not DAG.
     1233  /// \return \c false when the graph is not DAG.
    12341234  ///
    12351235  /// \see topologicalSort
     
    12801280  /// Check that the given directed graph is a DAG. The DAG is
    12811281  /// an Directed Acyclic Digraph.
    1282   /// \return %False when the graph is not DAG.
     1282  /// \return \c false when the graph is not DAG.
    12831283  /// \see acyclic
    12841284  template <typename Digraph>
     
    13221322  /// Check that the given undirected graph acyclic.
    13231323  /// \param graph The undirected graph.
    1324   /// \return %True when there is no circle in the graph.
     1324  /// \return \c true when there is no circle in the graph.
    13251325  /// \see dag
    13261326  template <typename Graph>
     
    13561356  /// Check that the given undirected graph is tree.
    13571357  /// \param graph The undirected graph.
    1358   /// \return %True when the graph is acyclic and connected.
     1358  /// \return \c true when the graph is acyclic and connected.
    13591359  template <typename Graph>
    13601360  bool tree(const Graph& graph) {
     
    14491449  /// or not. The \ref Bfs algorithm is used to calculate the result.
    14501450  /// \param graph The undirected graph.
    1451   /// \return %True if \c graph is bipartite, %false otherwise.
     1451  /// \return \c true if \c graph is bipartite, \c false otherwise.
    14521452  /// \sa bipartitePartitions
    14531453  template<typename Graph>
     
    14901490  /// \retval partMap A writable bool map of nodes. It will be set as the
    14911491  /// two partitions of the graph.
    1492   /// \return %True if \c graph is bipartite, %false otherwise.
     1492  /// \return \c true if \c graph is bipartite, \c false otherwise.
    14931493  template<typename Graph, typename NodeMap>
    14941494  inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
  • lemon/core.h

    r582 r606  
    10351035  ///\sa findArc()
    10361036  ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
    1037   template <typename _Graph>
    1038   class ConArcIt : public _Graph::Arc {
     1037  template <typename GR>
     1038  class ConArcIt : public GR::Arc {
    10391039  public:
    10401040
    1041     typedef _Graph Graph;
     1041    typedef GR Graph;
    10421042    typedef typename Graph::Arc Parent;
    10431043
     
    11581158  ///
    11591159  ///\sa findEdge()
    1160   template <typename _Graph>
    1161   class ConEdgeIt : public _Graph::Edge {
     1160  template <typename GR>
     1161  class ConEdgeIt : public GR::Edge {
    11621162  public:
    11631163
    1164     typedef _Graph Graph;
     1164    typedef GR Graph;
    11651165    typedef typename Graph::Edge Parent;
    11661166
     
    12121212  ///queries.
    12131213  ///
    1214   ///\tparam G The type of the underlying digraph.
     1214  ///\tparam GR The type of the underlying digraph.
    12151215  ///
    12161216  ///\sa ArcLookUp
    12171217  ///\sa AllArcLookUp
    1218   template<class G>
     1218  template <typename GR>
    12191219  class DynArcLookUp
    1220     : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
     1220    : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
    12211221  {
    12221222  public:
    1223     typedef typename ItemSetTraits<G, typename G::Arc>
     1223    typedef typename ItemSetTraits<GR, typename GR::Arc>
    12241224    ::ItemNotifier::ObserverBase Parent;
    12251225
    1226     TEMPLATE_DIGRAPH_TYPEDEFS(G);
    1227     typedef G Digraph;
     1226    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1227    typedef GR Digraph;
    12281228
    12291229  protected:
    12301230
    1231     class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type {
     1231    class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
    12321232    public:
    12331233
    1234       typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;
    1235 
    1236       AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
     1234      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
     1235
     1236      AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
    12371237
    12381238      virtual void add(const Node& node) {
     
    16241624  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
    16251625  ///
    1626   ///\tparam G The type of the underlying digraph.
     1626  ///\tparam GR The type of the underlying digraph.
    16271627  ///
    16281628  ///\sa DynArcLookUp
    16291629  ///\sa AllArcLookUp
    1630   template<class G>
     1630  template<class GR>
    16311631  class ArcLookUp
    16321632  {
    16331633  public:
    1634     TEMPLATE_DIGRAPH_TYPEDEFS(G);
    1635     typedef G Digraph;
     1634    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1635    typedef GR Digraph;
    16361636
    16371637  protected:
     
    17341734  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
    17351735  ///
    1736   ///\tparam G The type of the underlying digraph.
     1736  ///\tparam GR The type of the underlying digraph.
    17371737  ///
    17381738  ///\sa DynArcLookUp
    17391739  ///\sa ArcLookUp
    1740   template<class G>
    1741   class AllArcLookUp : public ArcLookUp<G>
     1740  template<class GR>
     1741  class AllArcLookUp : public ArcLookUp<GR>
    17421742  {
    1743     using ArcLookUp<G>::_g;
    1744     using ArcLookUp<G>::_right;
    1745     using ArcLookUp<G>::_left;
    1746     using ArcLookUp<G>::_head;
    1747 
    1748     TEMPLATE_DIGRAPH_TYPEDEFS(G);
    1749     typedef G Digraph;
     1743    using ArcLookUp<GR>::_g;
     1744    using ArcLookUp<GR>::_right;
     1745    using ArcLookUp<GR>::_left;
     1746    using ArcLookUp<GR>::_head;
     1747
     1748    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1749    typedef GR Digraph;
    17501750
    17511751    typename Digraph::template ArcMap<Arc> _next;
     
    17741774    ///It builds up the search database, which remains valid until the digraph
    17751775    ///changes.
    1776     AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
     1776    AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();}
    17771777
    17781778    ///Refresh the data structure at a node.
     
    17841784    void refresh(Node n)
    17851785    {
    1786       ArcLookUp<G>::refresh(n);
     1786      ArcLookUp<GR>::refresh(n);
    17871787      refreshNext(_head[n]);
    17881788    }
     
    18311831    Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
    18321832#else
    1833     using ArcLookUp<G>::operator() ;
     1833    using ArcLookUp<GR>::operator() ;
    18341834    Arc operator()(Node s, Node t, Arc prev) const
    18351835    {
  • lemon/dijkstra.h

    r525 r606  
    3939  /// This operation traits class defines all computational operations and
    4040  /// constants which are used in the Dijkstra algorithm.
    41   template <typename Value>
     41  template <typename V>
    4242  struct DijkstraDefaultOperationTraits {
     43    /// \e
     44    typedef V Value;
    4345    /// \brief Gives back the zero value of the type.
    4446    static Value zero() {
     
    5961  ///Default traits class of Dijkstra class.
    6062  ///\tparam GR The type of the digraph.
    61   ///\tparam LM The type of the length map.
    62   template<class GR, class LM>
     63  ///\tparam LEN The type of the length map.
     64  template<typename GR, typename LEN>
    6365  struct DijkstraDefaultTraits
    6466  {
     
    7072    ///The type of the map that stores the arc lengths.
    7173    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
    72     typedef LM LengthMap;
     74    typedef LEN LengthMap;
    7375    ///The type of the length of the arcs.
    74     typedef typename LM::Value Value;
     76    typedef typename LEN::Value Value;
    7577
    7678    /// Operation traits for %Dijkstra algorithm.
     
    101103    ///\sa BinHeap
    102104    ///\sa Dijkstra
    103     typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
     105    typedef BinHeap<typename LEN::Value, HeapCrossRef, std::less<Value> > Heap;
    104106    ///Instantiates a \c Heap.
    105107
     
    151153    ///The type of the map that stores the distances of the nodes.
    152154    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    153     typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
     155    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
    154156    ///Instantiates a \c DistMap.
    155157
     
    181183  ///\tparam GR The type of the digraph the algorithm runs on.
    182184  ///The default type is \ref ListDigraph.
    183   ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies
     185  ///\tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
    184186  ///the lengths of the arcs.
    185187  ///It is read once for each arc, so the map may involve in
     
    188190  ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
    189191#ifdef DOXYGEN
    190   template <typename GR, typename LM, typename TR>
     192  template <typename GR, typename LEN, typename TR>
    191193#else
    192194  template <typename GR=ListDigraph,
    193             typename LM=typename GR::template ArcMap<int>,
    194             typename TR=DijkstraDefaultTraits<GR,LM> >
     195            typename LEN=typename GR::template ArcMap<int>,
     196            typename TR=DijkstraDefaultTraits<GR,LEN> >
    195197#endif
    196198  class Dijkstra {
     
    914916  ///Default traits class of dijkstra() function.
    915917  ///\tparam GR The type of the digraph.
    916   ///\tparam LM The type of the length map.
    917   template<class GR, class LM>
     918  ///\tparam LEN The type of the length map.
     919  template<class GR, class LEN>
    918920  struct DijkstraWizardDefaultTraits
    919921  {
     
    924926    ///The type of the map that stores the arc lengths.
    925927    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
    926     typedef LM LengthMap;
     928    typedef LEN LengthMap;
    927929    ///The type of the length of the arcs.
    928     typedef typename LM::Value Value;
     930    typedef typename LEN::Value Value;
    929931
    930932    /// Operation traits for Dijkstra algorithm.
     
    10081010    ///The type of the map that stores the distances of the nodes.
    10091011    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1010     typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
     1012    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
    10111013    ///Instantiates a DistMap.
    10121014
     
    10341036  /// The \ref DijkstraWizardBase is a class to be the default traits of the
    10351037  /// \ref DijkstraWizard class.
    1036   template<class GR,class LM>
    1037   class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
     1038  template<typename GR, typename LEN>
     1039  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
    10381040  {
    1039     typedef DijkstraWizardDefaultTraits<GR,LM> Base;
     1041    typedef DijkstraWizardDefaultTraits<GR,LEN> Base;
    10401042  protected:
    10411043    //The type of the nodes in the digraph.
     
    10711073    /// \param g The digraph the algorithm runs on.
    10721074    /// \param l The length map.
    1073     DijkstraWizardBase(const GR &g,const LM &l) :
     1075    DijkstraWizardBase(const GR &g,const LEN &l) :
    10741076      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
    1075       _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
     1077      _length(reinterpret_cast<void*>(const_cast<LEN*>(&l))),
    10761078      _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
    10771079
     
    12821284  ///\sa DijkstraWizard
    12831285  ///\sa Dijkstra
    1284   template<class GR, class LM>
    1285   DijkstraWizard<DijkstraWizardBase<GR,LM> >
    1286   dijkstra(const GR &digraph, const LM &length)
     1286  template<typename GR, typename LEN>
     1287  DijkstraWizard<DijkstraWizardBase<GR,LEN> >
     1288  dijkstra(const GR &digraph, const LEN &length)
    12871289  {
    1288     return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length);
     1290    return DijkstraWizard<DijkstraWizardBase<GR,LEN> >(digraph,length);
    12891291  }
    12901292
  • lemon/edge_set.h

    r559 r606  
    256256  /// concept.
    257257  ///
    258   /// This class is fully conform to the \ref concepts::Digraph
     258  /// This class fully conforms to the \ref concepts::Digraph
    259259  /// "Digraph" concept.
    260260  template <typename GR>
     
    337337    /// Add a new arc to the digraph with source node \c s
    338338    /// and target node \c t.
    339     /// \return the new arc.
     339    /// \return The new arc.
    340340    Arc addArc(const Node& s, const Node& t) {
    341341      return Parent::addArc(s, t);
     
    685685  /// concept.
    686686  ///
    687   /// This class is fully conform to the \ref concepts::Graph "Graph"
     687  /// This class fully conforms to the \ref concepts::Graph "Graph"
    688688  /// concept.
    689689  template <typename GR>
     
    762762    /// Add a new edge to the graph with node \c u
    763763    /// and node \c v endpoints.
    764     /// \return the new edge.
     764    /// \return The new edge.
    765765    Edge addEdge(const Node& u, const Node& v) {
    766766      return Parent::addEdge(u, v);
     
    953953  /// validity can be checked with the \c valid() member function.
    954954  ///
    955   /// This class is fully conform to the \ref concepts::Digraph
     955  /// This class fully conforms to the \ref concepts::Digraph
    956956  /// "Digraph" concept.
    957957  template <typename GR>
     
    10421042    /// Add a new arc to the digraph with source node \c s
    10431043    /// and target node \c t.
    1044     /// \return the new arc.
     1044    /// \return The new arc.
    10451045    Arc addArc(const Node& s, const Node& t) {
    10461046      return Parent::addArc(s, t);
     
    13011301  /// be checked with the \c valid() member function.
    13021302  ///
    1303   /// This class is fully conform to the \ref concepts::Graph
     1303  /// This class fully conforms to the \ref concepts::Graph
    13041304  /// "Graph" concept.
    13051305  template <typename GR>
     
    13901390    /// Add a new edge to the graph with node \c u
    13911391    /// and node \c v endpoints.
    1392     /// \return the new edge.
     1392    /// \return The new edge.
    13931393    Edge addEdge(const Node& u, const Node& v) {
    13941394      return Parent::addEdge(u, v);
  • lemon/elevator.h

    r566 r606  
    4747  ///\sa LinkedElevator
    4848  ///
    49   ///\param Graph Type of the underlying graph.
    50   ///\param Item Type of the items the data is assigned to (Graph::Node,
    51   ///Graph::Arc, Graph::Edge).
    52   template<class Graph, class Item>
     49  ///\param GR Type of the underlying graph.
     50  ///\param Item Type of the items the data is assigned to (\c GR::Node,
     51  ///\c GR::Arc or \c GR::Edge).
     52  template<class GR, class Item>
    5353  class Elevator
    5454  {
     
    6161
    6262    typedef Item *Vit;
    63     typedef typename ItemSetTraits<Graph,Item>::template Map<Vit>::Type VitMap;
    64     typedef typename ItemSetTraits<Graph,Item>::template Map<int>::Type IntMap;
    65 
    66     const Graph &_g;
     63    typedef typename ItemSetTraits<GR,Item>::template Map<Vit>::Type VitMap;
     64    typedef typename ItemSetTraits<GR,Item>::template Map<int>::Type IntMap;
     65
     66    const GR &_g;
    6767    int _max_level;
    6868    int _item_num;
     
    106106    ///\param max_level The maximum allowed level.
    107107    ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
    108     Elevator(const Graph &graph,int max_level) :
     108    Elevator(const GR &graph,int max_level) :
    109109      _g(graph),
    110110      _max_level(max_level),
     
    123123    ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
    124124    ///where \c max_level is equal to the number of labeled items in the graph.
    125     Elevator(const Graph &graph) :
     125    Elevator(const GR &graph) :
    126126      _g(graph),
    127       _max_level(countItems<Graph, Item>(graph)),
     127      _max_level(countItems<GR, Item>(graph)),
    128128      _item_num(_max_level),
    129129      _where(graph),
     
    431431      _last_active[0]=&_items[0]-1;
    432432      Vit n=&_items[0];
    433       for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
     433      for(typename ItemSetTraits<GR,Item>::ItemIt i(_g);i!=INVALID;++i)
    434434        {
    435435          *n=i;
     
    490490  ///\sa Elevator
    491491  ///
    492   ///\param Graph Type of the underlying graph.
    493   ///\param Item Type of the items the data is assigned to (Graph::Node,
    494   ///Graph::Arc, Graph::Edge).
    495   template <class Graph, class Item>
     492  ///\param GR Type of the underlying graph.
     493  ///\param Item Type of the items the data is assigned to (\c GR::Node,
     494  ///\c GR::Arc or \c GR::Edge).
     495  template <class GR, class Item>
    496496  class LinkedElevator {
    497497  public:
     
    502502  private:
    503503
    504     typedef typename ItemSetTraits<Graph,Item>::
     504    typedef typename ItemSetTraits<GR,Item>::
    505505    template Map<Item>::Type ItemMap;
    506     typedef typename ItemSetTraits<Graph,Item>::
     506    typedef typename ItemSetTraits<GR,Item>::
    507507    template Map<int>::Type IntMap;
    508     typedef typename ItemSetTraits<Graph,Item>::
     508    typedef typename ItemSetTraits<GR,Item>::
    509509    template Map<bool>::Type BoolMap;
    510510
    511     const Graph &_graph;
     511    const GR &_graph;
    512512    int _max_level;
    513513    int _item_num;
     
    526526    ///\param max_level The maximum allowed level.
    527527    ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
    528     LinkedElevator(const Graph& graph, int max_level)
     528    LinkedElevator(const GR& graph, int max_level)
    529529      : _graph(graph), _max_level(max_level), _item_num(_max_level),
    530530        _first(_max_level + 1), _last(_max_level + 1),
     
    539539    ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
    540540    ///where \c max_level is equal to the number of labeled items in the graph.
    541     LinkedElevator(const Graph& graph)
    542       : _graph(graph), _max_level(countItems<Graph, Item>(graph)),
     541    LinkedElevator(const GR& graph)
     542      : _graph(graph), _max_level(countItems<GR, Item>(graph)),
    543543        _item_num(_max_level),
    544544        _first(_max_level + 1), _last(_max_level + 1),
     
    936936      }
    937937      _init_level = 0;
    938       for(typename ItemSetTraits<Graph,Item>::ItemIt i(_graph);
     938      for(typename ItemSetTraits<GR,Item>::ItemIt i(_graph);
    939939          i != INVALID; ++i) {
    940940        _level.set(i, _max_level);
  • lemon/euler.h

    r569 r606  
    5555  ///If \c g is not Euler then the resulted tour will not be full or closed.
    5656  ///\sa EulerIt
    57   template<class Digraph>
     57  template<typename GR>
    5858  class DiEulerIt
    5959  {
    60     typedef typename Digraph::Node Node;
    61     typedef typename Digraph::NodeIt NodeIt;
    62     typedef typename Digraph::Arc Arc;
    63     typedef typename Digraph::ArcIt ArcIt;
    64     typedef typename Digraph::OutArcIt OutArcIt;
    65     typedef typename Digraph::InArcIt InArcIt;
    66 
    67     const Digraph &g;
    68     typename Digraph::template NodeMap<OutArcIt> nedge;
     60    typedef typename GR::Node Node;
     61    typedef typename GR::NodeIt NodeIt;
     62    typedef typename GR::Arc Arc;
     63    typedef typename GR::ArcIt ArcIt;
     64    typedef typename GR::OutArcIt OutArcIt;
     65    typedef typename GR::InArcIt InArcIt;
     66
     67    const GR &g;
     68    typename GR::template NodeMap<OutArcIt> nedge;
    6969    std::list<Arc> euler;
    7070
     
    7373    ///Constructor
    7474
    75     ///\param _g A digraph.
     75    ///\param gr A digraph.
    7676    ///\param start The starting point of the tour. If it is not given
    7777    ///       the tour will start from the first node.
    78     DiEulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
    79       : g(_g), nedge(g)
     78    DiEulerIt(const GR &gr, typename GR::Node start = INVALID)
     79      : g(gr), nedge(g)
    8080    {
    8181      if(start==INVALID) start=NodeIt(g);
     
    146146  ///If \c g is not Euler then the resulted tour will not be full or closed.
    147147  ///\sa EulerIt
    148   template<class Digraph>
     148  template<typename GR>
    149149  class EulerIt
    150150  {
    151     typedef typename Digraph::Node Node;
    152     typedef typename Digraph::NodeIt NodeIt;
    153     typedef typename Digraph::Arc Arc;
    154     typedef typename Digraph::Edge Edge;
    155     typedef typename Digraph::ArcIt ArcIt;
    156     typedef typename Digraph::OutArcIt OutArcIt;
    157     typedef typename Digraph::InArcIt InArcIt;
    158 
    159     const Digraph &g;
    160     typename Digraph::template NodeMap<OutArcIt> nedge;
    161     typename Digraph::template EdgeMap<bool> visited;
     151    typedef typename GR::Node Node;
     152    typedef typename GR::NodeIt NodeIt;
     153    typedef typename GR::Arc Arc;
     154    typedef typename GR::Edge Edge;
     155    typedef typename GR::ArcIt ArcIt;
     156    typedef typename GR::OutArcIt OutArcIt;
     157    typedef typename GR::InArcIt InArcIt;
     158
     159    const GR &g;
     160    typename GR::template NodeMap<OutArcIt> nedge;
     161    typename GR::template EdgeMap<bool> visited;
    162162    std::list<Arc> euler;
    163163
     
    166166    ///Constructor
    167167
    168     ///\param _g An graph.
     168    ///\param gr An graph.
    169169    ///\param start The starting point of the tour. If it is not given
    170170    ///       the tour will start from the first node.
    171     EulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
    172       : g(_g), nedge(g), visited(g,false)
     171    EulerIt(const GR &gr, typename GR::Node start = INVALID)
     172      : g(gr), nedge(g), visited(g, false)
    173173    {
    174174      if(start==INVALID) start=NodeIt(g);
     
    239239  ///for each node. <em>Therefore, there are digraphs which are not Eulerian,
    240240  ///but still have an Euler tour</em>.
    241   template<class Digraph>
     241  template<typename GR>
    242242#ifdef DOXYGEN
    243243  bool
    244244#else
    245   typename enable_if<UndirectedTagIndicator<Digraph>,bool>::type
    246   eulerian(const Digraph &g)
    247   {
    248     for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
     245  typename enable_if<UndirectedTagIndicator<GR>,bool>::type
     246  eulerian(const GR &g)
     247  {
     248    for(typename GR::NodeIt n(g);n!=INVALID;++n)
    249249      if(countIncEdges(g,n)%2) return false;
    250250    return connected(g);
    251251  }
    252   template<class Digraph>
    253   typename disable_if<UndirectedTagIndicator<Digraph>,bool>::type
     252  template<class GR>
     253  typename disable_if<UndirectedTagIndicator<GR>,bool>::type
    254254#endif
    255   eulerian(const Digraph &g)
    256   {
    257     for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
     255  eulerian(const GR &g)
     256  {
     257    for(typename GR::NodeIt n(g);n!=INVALID;++n)
    258258      if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
    259     return connected(Undirector<const Digraph>(g));
     259    return connected(Undirector<const GR>(g));
    260260  }
    261261
  • lemon/graph_to_eps.h

    r562 r606  
    6565///Default traits class of \ref GraphToEps.
    6666///
    67 ///\c G is the type of the underlying graph.
    68 template<class G>
     67///\param GR is the type of the underlying graph.
     68template<class GR>
    6969struct DefaultGraphToEpsTraits
    7070{
    71   typedef G Graph;
     71  typedef GR Graph;
    7272  typedef typename Graph::Node Node;
    7373  typedef typename Graph::NodeIt NodeIt;
     
    140140
    141141  ///Constructor
    142   ///\param _g  Reference to the graph to be printed.
    143   ///\param _os Reference to the output stream.
    144   ///\param _os Reference to the output stream.
     142  ///\param gr  Reference to the graph to be printed.
     143  ///\param ost Reference to the output stream.
    145144  ///By default it is <tt>std::cout</tt>.
    146   ///\param _pros If it is \c true, then the \c ostream referenced by \c _os
     145  ///\param pros If it is \c true, then the \c ostream referenced by \c os
    147146  ///will be explicitly deallocated by the destructor.
    148   DefaultGraphToEpsTraits(const G &_g,std::ostream& _os=std::cout,
    149                           bool _pros=false) :
    150     g(_g), os(_os),
     147  DefaultGraphToEpsTraits(const GR &gr, std::ostream& ost = std::cout,
     148                          bool pros = false) :
     149    g(gr), os(ost),
    151150    _coords(dim2::Point<double>(1,1)), _nodeSizes(1), _nodeShapes(0),
    152151    _nodeColors(WHITE), _arcColors(BLACK),
     
    159158    _showNodeText(false), _nodeTexts(false), _nodeTextSize(1),
    160159    _showNodePsText(false), _nodePsTexts(false), _nodePsTextsPreamble(0),
    161     _undirected(lemon::UndirectedTagIndicator<G>::value),
    162     _pleaseRemoveOsStream(_pros), _scaleToA4(false),
     160    _undirected(lemon::UndirectedTagIndicator<GR>::value),
     161    _pleaseRemoveOsStream(pros), _scaleToA4(false),
    163162    _nodeTextColorType(SAME_COL), _nodeTextColors(BLACK),
    164163    _autoNodeScale(false),
     
    11351134///to the end of the parameter list.
    11361135///\sa GraphToEps
    1137 ///\sa graphToEps(G &g, const char *file_name)
    1138 template<class G>
    1139 GraphToEps<DefaultGraphToEpsTraits<G> >
    1140 graphToEps(G &g, std::ostream& os=std::cout)
     1136///\sa graphToEps(GR &g, const char *file_name)
     1137template<class GR>
     1138GraphToEps<DefaultGraphToEpsTraits<GR> >
     1139graphToEps(GR &g, std::ostream& os=std::cout)
    11411140{
    11421141  return
    1143     GraphToEps<DefaultGraphToEpsTraits<G> >(DefaultGraphToEpsTraits<G>(g,os));
     1142    GraphToEps<DefaultGraphToEpsTraits<GR> >(DefaultGraphToEpsTraits<GR>(g,os));
    11441143}
    11451144
     
    11481147///\ingroup eps_io
    11491148///This function does the same as
    1150 ///\ref graphToEps(G &g,std::ostream& os)
     1149///\ref graphToEps(GR &g,std::ostream& os)
    11511150///but it writes its output into the file \c file_name
    11521151///instead of a stream.
    1153 ///\sa graphToEps(G &g, std::ostream& os)
    1154 template<class G>
    1155 GraphToEps<DefaultGraphToEpsTraits<G> >
    1156 graphToEps(G &g,const char *file_name)
     1152///\sa graphToEps(GR &g, std::ostream& os)
     1153template<class GR>
     1154GraphToEps<DefaultGraphToEpsTraits<GR> >
     1155graphToEps(GR &g,const char *file_name)
    11571156{
    11581157  std::ostream* os = new std::ofstream(file_name);
     
    11611160    throw IoError("Cannot write file", file_name);
    11621161  }
    1163   return GraphToEps<DefaultGraphToEpsTraits<G> >
    1164     (DefaultGraphToEpsTraits<G>(g,*os,true));
     1162  return GraphToEps<DefaultGraphToEpsTraits<GR> >
     1163    (DefaultGraphToEpsTraits<GR>(g,*os,true));
    11651164}
    11661165
     
    11691168///\ingroup eps_io
    11701169///This function does the same as
    1171 ///\ref graphToEps(G &g,std::ostream& os)
     1170///\ref graphToEps(GR &g,std::ostream& os)
    11721171///but it writes its output into the file \c file_name
    11731172///instead of a stream.
    1174 ///\sa graphToEps(G &g, std::ostream& os)
    1175 template<class G>
    1176 GraphToEps<DefaultGraphToEpsTraits<G> >
    1177 graphToEps(G &g,const std::string& file_name)
     1173///\sa graphToEps(GR &g, std::ostream& os)
     1174template<class GR>
     1175GraphToEps<DefaultGraphToEpsTraits<GR> >
     1176graphToEps(GR &g,const std::string& file_name)
    11781177{
    11791178  std::ostream* os = new std::ofstream(file_name.c_str());
     
    11821181    throw IoError("Cannot write file", file_name);
    11831182  }
    1184   return GraphToEps<DefaultGraphToEpsTraits<G> >
    1185     (DefaultGraphToEpsTraits<G>(g,*os,true));
     1183  return GraphToEps<DefaultGraphToEpsTraits<GR> >
     1184    (DefaultGraphToEpsTraits<GR>(g,*os,true));
    11861185}
    11871186
  • lemon/grid_graph.h

    r463 r606  
    497497  ///\endcode
    498498  ///
    499   /// This graph type is fully conform to the \ref concepts::Graph
     499  /// This graph type fully conforms to the \ref concepts::Graph
    500500  /// "Graph" concept, and it also has an important extra feature
    501501  /// that its maps are real \ref concepts::ReferenceMap
  • lemon/hao_orlin.h

    r463 r606  
    5858  /// algorithm or you can use the algorithm of Nagamochi and Ibaraki
    5959  /// which solves the undirected problem in
    60   /// \f$ O(nm + n^2 \log(n)) \f$ time: it is implemented in the
     60  /// \f$ O(nm + n^2 \log n) \f$ time: it is implemented in the
    6161  /// NagamochiIbaraki algorithm class.
    6262  ///
    63   /// \param _Digraph is the graph type of the algorithm.
    64   /// \param _CapacityMap is an edge map of capacities which should
    65   /// be any numreric type. The default type is _Digraph::ArcMap<int>.
    66   /// \param _Tolerance is the handler of the inexact computation. The
    67   /// default type for this is Tolerance<CapacityMap::Value>.
     63  /// \param GR The digraph class the algorithm runs on.
     64  /// \param CAP An arc map of capacities which can be any numreric type.
     65  /// The default type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
     66  /// \param TOL Tolerance class for handling inexact computations. The
     67  /// default tolerance type is \ref Tolerance "Tolerance<CAP::Value>".
    6868#ifdef DOXYGEN
    69   template <typename _Digraph, typename _CapacityMap, typename _Tolerance>
     69  template <typename GR, typename CAP, typename TOL>
    7070#else
    71   template <typename _Digraph,
    72             typename _CapacityMap = typename _Digraph::template ArcMap<int>,
    73             typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
     71  template <typename GR,
     72            typename CAP = typename GR::template ArcMap<int>,
     73            typename TOL = Tolerance<typename CAP::Value> >
    7474#endif
    7575  class HaoOrlin {
    7676  private:
    7777
    78     typedef _Digraph Digraph;
    79     typedef _CapacityMap CapacityMap;
    80     typedef _Tolerance Tolerance;
     78    typedef GR Digraph;
     79    typedef CAP CapacityMap;
     80    typedef TOL Tolerance;
    8181
    8282    typedef typename CapacityMap::Value Value;
     
    818818    /// \name Execution control
    819819    /// The simplest way to execute the algorithm is to use
    820     /// one of the member functions called \c run(...).
     820    /// one of the member functions called \ref run().
    821821    /// \n
    822822    /// If you need more control on the execution,
  • lemon/hypercube_graph.h

    r463 r606  
    292292  /// (assuming that the size of \c int is 32 bit).
    293293  ///
    294   /// This graph type is fully conform to the \ref concepts::Graph
     294  /// This graph type fully conforms to the \ref concepts::Graph
    295295  /// "Graph" concept, and it also has an important extra feature
    296296  /// that its maps are real \ref concepts::ReferenceMap
  • lemon/lgf_reader.h

    r564 r606  
    449449  /// a single pass, because the arcs are not constructed when the node
    450450  /// maps are read.
    451   template <typename _Digraph>
     451  template <typename GR>
    452452  class DigraphReader {
    453453  public:
    454454
    455     typedef _Digraph Digraph;
     455    typedef GR Digraph;
     456
     457  private:
     458
    456459    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    457 
    458   private:
    459 
    460460
    461461    std::istream* _is;
     
    12471247  /// arc map.  Similarly, an attribute can be read into an arc, if
    12481248  /// it's value is an edge label prefixed with \c '+' or \c '-'.
    1249   template <typename _Graph>
     1249  template <typename GR>
    12501250  class GraphReader {
    12511251  public:
    12521252
    1253     typedef _Graph Graph;
     1253    typedef GR Graph;
     1254
     1255  private:
     1256
    12541257    TEMPLATE_GRAPH_TYPEDEFS(Graph);
    1255 
    1256   private:
    12571258
    12581259    std::istream* _is;
     
    13571358
    13581359  private:
    1359     template <typename GR>
    1360     friend GraphReader<GR> graphReader(GR& graph, std::istream& is);
    1361     template <typename GR>
    1362     friend GraphReader<GR> graphReader(GR& graph, const std::string& fn);
    1363     template <typename GR>
    1364     friend GraphReader<GR> graphReader(GR& graph, const char *fn);
     1360    template <typename Graph>
     1361    friend GraphReader<Graph> graphReader(Graph& graph, std::istream& is);
     1362    template <typename Graph>
     1363    friend GraphReader<Graph> graphReader(Graph& graph, const std::string& fn);
     1364    template <typename Graph>
     1365    friend GraphReader<Graph> graphReader(Graph& graph, const char *fn);
    13651366
    13661367    GraphReader(GraphReader& other)
  • lemon/lgf_writer.h

    r564 r606  
    407407  /// the \c ostream() function, hence the second pass can append its
    408408  /// output to the output of the first pass.
    409   template <typename _Digraph>
     409  template <typename GR>
    410410  class DigraphWriter {
    411411  public:
    412412
    413     typedef _Digraph Digraph;
     413    typedef GR Digraph;
    414414    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    415415
     
    975975  /// section as a \c '+' or a \c '-' prefix (depends on the direction
    976976  /// of the arc) and the label of corresponding edge.
    977   template <typename _Graph>
     977  template <typename GR>
    978978  class GraphWriter {
    979979  public:
    980980
    981     typedef _Graph Graph;
     981    typedef GR Graph;
    982982    TEMPLATE_GRAPH_TYPEDEFS(Graph);
    983983
     
    10741074  private:
    10751075
    1076     template <typename GR>
    1077     friend GraphWriter<GR> graphWriter(const GR& graph,
    1078                                        std::ostream& os);
    1079     template <typename GR>
    1080     friend GraphWriter<GR> graphWriter(const GR& graph,
    1081                                        const std::string& fn);
    1082     template <typename GR>
    1083     friend GraphWriter<GR> graphWriter(const GR& graph,
    1084                                        const char *fn);
     1076    template <typename Graph>
     1077    friend GraphWriter<Graph> graphWriter(const Graph& graph,
     1078                                          std::ostream& os);
     1079    template <typename Graph>
     1080    friend GraphWriter<Graph> graphWriter(const Graph& graph,
     1081                                          const std::string& fn);
     1082    template <typename Graph>
     1083    friend GraphWriter<Graph> graphWriter(const Graph& graph,
     1084                                          const char *fn);
    10851085   
    10861086    GraphWriter(GraphWriter& other)
  • lemon/list_graph.h

    r463 r606  
    352352
    353353    ///Add a new node to the digraph.
    354     ///\return the new node.
     354    ///\return The new node.
    355355    Node addNode() { return Parent::addNode(); }
    356356
     
    359359    ///Add a new arc to the digraph with source node \c s
    360360    ///and target node \c t.
    361     ///\return the new arc.
     361    ///\return The new arc.
    362362    Arc addArc(const Node& s, const Node& t) {
    363363      return Parent::addArc(s, t);
     
    12091209    ///
    12101210    /// Add a new node to the graph.
    1211     /// \return the new node.
     1211    /// \return The new node.
    12121212    Node addNode() { return Parent::addNode(); }
    12131213
     
    12161216    /// Add a new edge to the graph with source node \c s
    12171217    /// and target node \c t.
    1218     /// \return the new edge.
     1218    /// \return The new edge.
    12191219    Edge addEdge(const Node& s, const Node& t) {
    12201220      return Parent::addEdge(s, t);
  • lemon/maps.h

    r463 r606  
    6464  class NullMap : public MapBase<K, V> {
    6565  public:
    66     typedef MapBase<K, V> Parent;
    67     typedef typename Parent::Key Key;
    68     typedef typename Parent::Value Value;
     66    ///\e
     67    typedef K Key;
     68    ///\e
     69    typedef V Value;
    6970
    7071    /// Gives back a default constructed element.
     
    103104    V _value;
    104105  public:
    105     typedef MapBase<K, V> Parent;
    106     typedef typename Parent::Key Key;
    107     typedef typename Parent::Value Value;
     106    ///\e
     107    typedef K Key;
     108    ///\e
     109    typedef V Value;
    108110
    109111    /// Default constructor
     
    169171  class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
    170172  public:
    171     typedef MapBase<K, V> Parent;
    172     typedef typename Parent::Key Key;
    173     typedef typename Parent::Value Value;
     173    ///\e
     174    typedef K Key;
     175    ///\e
     176    typedef V Value;
    174177
    175178    /// Constructor.
     
    203206  class IdentityMap : public MapBase<T, T> {
    204207  public:
    205     typedef MapBase<T, T> Parent;
    206     typedef typename Parent::Key Key;
    207     typedef typename Parent::Value Value;
     208    ///\e
     209    typedef T Key;
     210    ///\e
     211    typedef T Value;
    208212
    209213    /// Gives back the given value without any modification.
     
    246250  public:
    247251
    248     typedef MapBase<int, V> Parent;
    249252    /// Key type
    250     typedef typename Parent::Key Key;
     253    typedef int Key;
    251254    /// Value type
    252     typedef typename Parent::Value Value;
     255    typedef V Value;
    253256    /// Reference type
    254257    typedef typename Vector::reference Reference;
     
    354357  /// The simplest way of using this map is through the sparseMap()
    355358  /// function.
    356   template <typename K, typename V, typename Compare = std::less<K> >
     359  template <typename K, typename V, typename Comp = std::less<K> >
    357360  class SparseMap : public MapBase<K, V> {
    358361    template <typename K1, typename V1, typename C1>
     
    360363  public:
    361364
    362     typedef MapBase<K, V> Parent;
    363365    /// Key type
    364     typedef typename Parent::Key Key;
     366    typedef K Key;
    365367    /// Value type
    366     typedef typename Parent::Value Value;
     368    typedef V Value;
    367369    /// Reference type
    368370    typedef Value& Reference;
     
    374376  private:
    375377
    376     typedef std::map<K, V, Compare> Map;
     378    typedef std::map<K, V, Comp> Map;
    377379    Map _map;
    378380    Value _value;
     
    490492    const M2 &_m2;
    491493  public:
    492     typedef MapBase<typename M2::Key, typename M1::Value> Parent;
    493     typedef typename Parent::Key Key;
    494     typedef typename Parent::Value Value;
     494    ///\e
     495    typedef typename M2::Key Key;
     496    ///\e
     497    typedef typename M1::Value Value;
    495498
    496499    /// Constructor
    497500    ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
    498501
    499     /// \e
     502    ///\e
    500503    typename MapTraits<M1>::ConstReturnValue
    501504    operator[](const Key &k) const { return _m1[_m2[k]]; }
     
    546549    F _f;
    547550  public:
    548     typedef MapBase<typename M1::Key, V> Parent;
    549     typedef typename Parent::Key Key;
    550     typedef typename Parent::Value Value;
     551    ///\e
     552    typedef typename M1::Key Key;
     553    ///\e
     554    typedef V Value;
    551555
    552556    /// Constructor
    553557    CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
    554558      : _m1(m1), _m2(m2), _f(f) {}
    555     /// \e
     559    ///\e
    556560    Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
    557561  };
     
    616620    F _f;
    617621  public:
    618     typedef MapBase<K, V> Parent;
    619     typedef typename Parent::Key Key;
    620     typedef typename Parent::Value Value;
     622    ///\e
     623    typedef K Key;
     624    ///\e
     625    typedef V Value;
    621626
    622627    /// Constructor
    623628    FunctorToMap(const F &f = F()) : _f(f) {}
    624     /// \e
     629    ///\e
    625630    Value operator[](const Key &k) const { return _f(k); }
    626631  };
     
    670675    const M &_m;
    671676  public:
    672     typedef MapBase<typename M::Key, typename M::Value> Parent;
    673     typedef typename Parent::Key Key;
    674     typedef typename Parent::Value Value;
    675 
    676     typedef typename Parent::Key argument_type;
    677     typedef typename Parent::Value result_type;
     677    ///\e
     678    typedef typename M::Key Key;
     679    ///\e
     680    typedef typename M::Value Value;
     681
     682    typedef typename M::Key argument_type;
     683    typedef typename M::Value result_type;
    678684
    679685    /// Constructor
    680686    MapToFunctor(const M &m) : _m(m) {}
    681     /// \e
     687    ///\e
    682688    Value operator()(const Key &k) const { return _m[k]; }
    683     /// \e
     689    ///\e
    684690    Value operator[](const Key &k) const { return _m[k]; }
    685691  };
     
    710716    const M &_m;
    711717  public:
    712     typedef MapBase<typename M::Key, V> Parent;
    713     typedef typename Parent::Key Key;
    714     typedef typename Parent::Value Value;
     718    ///\e
     719    typedef typename M::Key Key;
     720    ///\e
     721    typedef V Value;
    715722
    716723    /// Constructor
     
    720727    ConvertMap(const M &m) : _m(m) {}
    721728
    722     /// \e
     729    ///\e
    723730    Value operator[](const Key &k) const { return _m[k]; }
    724731  };
     
    752759    M2 &_m2;
    753760  public:
    754     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
    755     typedef typename Parent::Key Key;
    756     typedef typename Parent::Value Value;
     761    ///\e
     762    typedef typename M1::Key Key;
     763    ///\e
     764    typedef typename M1::Value Value;
    757765
    758766    /// Constructor
     
    798806    const M2 &_m2;
    799807  public:
    800     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
    801     typedef typename Parent::Key Key;
    802     typedef typename Parent::Value Value;
     808    ///\e
     809    typedef typename M1::Key Key;
     810    ///\e
     811    typedef typename M1::Value Value;
    803812
    804813    /// Constructor
    805814    AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
    806     /// \e
     815    ///\e
    807816    Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
    808817  };
     
    846855    const M2 &_m2;
    847856  public:
    848     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
    849     typedef typename Parent::Key Key;
    850     typedef typename Parent::Value Value;
     857    ///\e
     858    typedef typename M1::Key Key;
     859    ///\e
     860    typedef typename M1::Value Value;
    851861
    852862    /// Constructor
    853863    SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
    854     /// \e
     864    ///\e
    855865    Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
    856866  };
     
    895905    const M2 &_m2;
    896906  public:
    897     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
    898     typedef typename Parent::Key Key;
    899     typedef typename Parent::Value Value;
     907    ///\e
     908    typedef typename M1::Key Key;
     909    ///\e
     910    typedef typename M1::Value Value;
    900911
    901912    /// Constructor
    902913    MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
    903     /// \e
     914    ///\e
    904915    Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
    905916  };
     
    943954    const M2 &_m2;
    944955  public:
    945     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
    946     typedef typename Parent::Key Key;
    947     typedef typename Parent::Value Value;
     956    ///\e
     957    typedef typename M1::Key Key;
     958    ///\e
     959    typedef typename M1::Value Value;
    948960
    949961    /// Constructor
    950962    DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
    951     /// \e
     963    ///\e
    952964    Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
    953965  };
     
    9931005    C _v;
    9941006  public:
    995     typedef MapBase<typename M::Key, typename M::Value> Parent;
    996     typedef typename Parent::Key Key;
    997     typedef typename Parent::Value Value;
     1007    ///\e
     1008    typedef typename M::Key Key;
     1009    ///\e
     1010    typedef typename M::Value Value;
    9981011
    9991012    /// Constructor
     
    10031016    /// \param v The constant value.
    10041017    ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
    1005     /// \e
     1018    ///\e
    10061019    Value operator[](const Key &k) const { return _m[k]+_v; }
    10071020  };
     
    10231036    C _v;
    10241037  public:
    1025     typedef MapBase<typename M::Key, typename M::Value> Parent;
    1026     typedef typename Parent::Key Key;
    1027     typedef typename Parent::Value Value;
     1038    ///\e
     1039    typedef typename M::Key Key;
     1040    ///\e
     1041    typedef typename M::Value Value;
    10281042
    10291043    /// Constructor
     
    10331047    /// \param v The constant value.
    10341048    ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
    1035     /// \e
     1049    ///\e
    10361050    Value operator[](const Key &k) const { return _m[k]+_v; }
    1037     /// \e
     1051    ///\e
    10381052    void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
    10391053  };
     
    10941108    C _v;
    10951109  public:
    1096     typedef MapBase<typename M::Key, typename M::Value> Parent;
    1097     typedef typename Parent::Key Key;
    1098     typedef typename Parent::Value Value;
     1110    ///\e
     1111    typedef typename M::Key Key;
     1112    ///\e
     1113    typedef typename M::Value Value;
    10991114
    11001115    /// Constructor
     
    11041119    /// \param v The constant value.
    11051120    ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
    1106     /// \e
     1121    ///\e
    11071122    Value operator[](const Key &k) const { return _v*_m[k]; }
    11081123  };
     
    11251140    C _v;
    11261141  public:
    1127     typedef MapBase<typename M::Key, typename M::Value> Parent;
    1128     typedef typename Parent::Key Key;
    1129     typedef typename Parent::Value Value;
     1142    ///\e
     1143    typedef typename M::Key Key;
     1144    ///\e
     1145    typedef typename M::Value Value;
    11301146
    11311147    /// Constructor
     
    11351151    /// \param v The constant value.
    11361152    ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
    1137     /// \e
     1153    ///\e
    11381154    Value operator[](const Key &k) const { return _v*_m[k]; }
    1139     /// \e
     1155    ///\e
    11401156    void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
    11411157  };
     
    11941210    const M& _m;
    11951211  public:
    1196     typedef MapBase<typename M::Key, typename M::Value> Parent;
    1197     typedef typename Parent::Key Key;
    1198     typedef typename Parent::Value Value;
     1212    ///\e
     1213    typedef typename M::Key Key;
     1214    ///\e
     1215    typedef typename M::Value Value;
    11991216
    12001217    /// Constructor
    12011218    NegMap(const M &m) : _m(m) {}
    1202     /// \e
     1219    ///\e
    12031220    Value operator[](const Key &k) const { return -_m[k]; }
    12041221  };
     
    12291246    M &_m;
    12301247  public:
    1231     typedef MapBase<typename M::Key, typename M::Value> Parent;
    1232     typedef typename Parent::Key Key;
    1233     typedef typename Parent::Value Value;
     1248    ///\e
     1249    typedef typename M::Key Key;
     1250    ///\e
     1251    typedef typename M::Value Value;
    12341252
    12351253    /// Constructor
    12361254    NegWriteMap(M &m) : _m(m) {}
    1237     /// \e
     1255    ///\e
    12381256    Value operator[](const Key &k) const { return -_m[k]; }
    1239     /// \e
     1257    ///\e
    12401258    void set(const Key &k, const Value &v) { _m.set(k, -v); }
    12411259  };
     
    12831301    const M &_m;
    12841302  public:
    1285     typedef MapBase<typename M::Key, typename M::Value> Parent;
    1286     typedef typename Parent::Key Key;
    1287     typedef typename Parent::Value Value;
     1303    ///\e
     1304    typedef typename M::Key Key;
     1305    ///\e
     1306    typedef typename M::Value Value;
    12881307
    12891308    /// Constructor
    12901309    AbsMap(const M &m) : _m(m) {}
    1291     /// \e
     1310    ///\e
    12921311    Value operator[](const Key &k) const {
    12931312      Value tmp = _m[k];
     
    13381357  class TrueMap : public MapBase<K, bool> {
    13391358  public:
    1340     typedef MapBase<K, bool> Parent;
    1341     typedef typename Parent::Key Key;
    1342     typedef typename Parent::Value Value;
     1359    ///\e
     1360    typedef K Key;
     1361    ///\e
     1362    typedef bool Value;
    13431363
    13441364    /// Gives back \c true.
     
    13751395  class FalseMap : public MapBase<K, bool> {
    13761396  public:
    1377     typedef MapBase<K, bool> Parent;
    1378     typedef typename Parent::Key Key;
    1379     typedef typename Parent::Value Value;
     1397    ///\e
     1398    typedef K Key;
     1399    ///\e
     1400    typedef bool Value;
    13801401
    13811402    /// Gives back \c false.
     
    14201441    const M2 &_m2;
    14211442  public:
    1422     typedef MapBase<typename M1::Key, bool> Parent;
    1423     typedef typename Parent::Key Key;
    1424     typedef typename Parent::Value Value;
     1443    ///\e
     1444    typedef typename M1::Key Key;
     1445    ///\e
     1446    typedef bool Value;
    14251447
    14261448    /// Constructor
    14271449    AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
    1428     /// \e
     1450    ///\e
    14291451    Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
    14301452  };
     
    14681490    const M2 &_m2;
    14691491  public:
    1470     typedef MapBase<typename M1::Key, bool> Parent;
    1471     typedef typename Parent::Key Key;
    1472     typedef typename Parent::Value Value;
     1492    ///\e
     1493    typedef typename M1::Key Key;
     1494    ///\e
     1495    typedef bool Value;
    14731496
    14741497    /// Constructor
    14751498    OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
    1476     /// \e
     1499    ///\e
    14771500    Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
    14781501  };
     
    15071530    const M &_m;
    15081531  public:
    1509     typedef MapBase<typename M::Key, bool> Parent;
    1510     typedef typename Parent::Key Key;
    1511     typedef typename Parent::Value Value;
     1532    ///\e
     1533    typedef typename M::Key Key;
     1534    ///\e
     1535    typedef bool Value;
    15121536
    15131537    /// Constructor
    15141538    NotMap(const M &m) : _m(m) {}
    1515     /// \e
     1539    ///\e
    15161540    Value operator[](const Key &k) const { return !_m[k]; }
    15171541  };
     
    15331557    M &_m;
    15341558  public:
    1535     typedef MapBase<typename M::Key, bool> Parent;
    1536     typedef typename Parent::Key Key;
    1537     typedef typename Parent::Value Value;
     1559    ///\e
     1560    typedef typename M::Key Key;
     1561    ///\e
     1562    typedef bool Value;
    15381563
    15391564    /// Constructor
    15401565    NotWriteMap(M &m) : _m(m) {}
    1541     /// \e
     1566    ///\e
    15421567    Value operator[](const Key &k) const { return !_m[k]; }
    1543     /// \e
     1568    ///\e
    15441569    void set(const Key &k, bool v) { _m.set(k, !v); }
    15451570  };
     
    15961621    const M2 &_m2;
    15971622  public:
    1598     typedef MapBase<typename M1::Key, bool> Parent;
    1599     typedef typename Parent::Key Key;
    1600     typedef typename Parent::Value Value;
     1623    ///\e
     1624    typedef typename M1::Key Key;
     1625    ///\e
     1626    typedef bool Value;
    16011627
    16021628    /// Constructor
    16031629    EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
    1604     /// \e
     1630    ///\e
    16051631    Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
    16061632  };
     
    16441670    const M2 &_m2;
    16451671  public:
    1646     typedef MapBase<typename M1::Key, bool> Parent;
    1647     typedef typename Parent::Key Key;
    1648     typedef typename Parent::Value Value;
     1672    ///\e
     1673    typedef typename M1::Key Key;
     1674    ///\e
     1675    typedef bool Value;
    16491676
    16501677    /// Constructor
    16511678    LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
    1652     /// \e
     1679    ///\e
    16531680    Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
    16541681  };
     
    17061733  /// function.
    17071734  ///
    1708   /// \tparam It The type of the iterator.
    1709   /// \tparam Ke The key type of the map. The default value set
     1735  /// \tparam IT The type of the iterator.
     1736  /// \tparam KEY The key type of the map. The default value set
    17101737  /// according to the iterator type should work in most cases.
    17111738  ///
     
    17131740  /// for the elements or the iterator should be an inserter iterator.
    17141741#ifdef DOXYGEN
    1715   template <typename It, typename Ke>
     1742  template <typename IT, typename KEY>
    17161743#else
    1717   template <typename It,
    1718             typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
     1744  template <typename IT,
     1745            typename KEY = typename _maps_bits::IteratorTraits<IT>::Value>
    17191746#endif
    1720   class LoggerBoolMap {
    1721   public:
    1722     typedef It Iterator;
    1723 
    1724     typedef Ke Key;
     1747  class LoggerBoolMap : public MapBase<KEY, bool> {
     1748  public:
     1749
     1750    ///\e
     1751    typedef KEY Key;
     1752    ///\e
    17251753    typedef bool Value;
     1754    ///\e
     1755    typedef IT Iterator;
    17261756
    17271757    /// Constructor
     
    17861816  /// @{
    17871817
    1788   /// Provides an immutable and unique id for each item in the graph.
    1789 
    1790   /// The IdMap class provides a unique and immutable id for each item of the
    1791   /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
    1792   /// different items (nodes) get different ids <li>\b immutable: the id of an
    1793   /// item (node) does not change (even if you delete other nodes).  </ul>
    1794   /// Through this map you get access (i.e. can read) the inner id values of
    1795   /// the items stored in the graph. This map can be inverted with its member
     1818  /// \brief Provides an immutable and unique id for each item in a graph.
     1819  ///
     1820  /// IdMap provides a unique and immutable id for each item of the
     1821  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
     1822  ///  - \b unique: different items get different ids,
     1823  ///  - \b immutable: the id of an item does not change (even if you
     1824  ///    delete other nodes).
     1825  ///
     1826  /// Using this map you get access (i.e. can read) the inner id values of
     1827  /// the items stored in the graph, which is returned by the \c id()
     1828  /// function of the graph. This map can be inverted with its member
    17961829  /// class \c InverseMap or with the \c operator() member.
    17971830  ///
    1798   template <typename _Graph, typename _Item>
    1799   class IdMap {
    1800   public:
    1801     typedef _Graph Graph;
     1831  /// \tparam GR The graph type.
     1832  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
     1833  /// \c GR::Edge).
     1834  ///
     1835  /// \see DescriptorMap
     1836  template <typename GR, typename K>
     1837  class IdMap : public MapBase<K, int> {
     1838  public:
     1839    /// The graph type of IdMap.
     1840    typedef GR Graph;
     1841    /// The key type of IdMap (\c Node, \c Arc or \c Edge).
     1842    typedef K Item;
     1843    /// The key type of IdMap (\c Node, \c Arc or \c Edge).
     1844    typedef K Key;
     1845    /// The value type of IdMap.
    18021846    typedef int Value;
    1803     typedef _Item Item;
    1804     typedef _Item Key;
    18051847
    18061848    /// \brief Constructor.
     
    18141856    int operator[](const Item& item) const { return _graph->id(item);}
    18151857
    1816     /// \brief Gives back the item by its id.
    1817     ///
    1818     /// Gives back the item by its id.
     1858    /// \brief Gives back the \e item by its id.
     1859    ///
     1860    /// Gives back the \e item by its id.
    18191861    Item operator()(int id) { return _graph->fromId(id, Item()); }
    18201862
     
    18241866  public:
    18251867
    1826     /// \brief The class represents the inverse of its owner (IdMap).
    1827     ///
    1828     /// The class represents the inverse of its owner (IdMap).
     1868    /// \brief This class represents the inverse of its owner (IdMap).
     1869    ///
     1870    /// This class represents the inverse of its owner (IdMap).
    18291871    /// \see inverse()
    18301872    class InverseMap {
     
    18441886      ///
    18451887      /// Gives back the given item from its id.
    1846       ///
    18471888      Item operator[](int id) const { return _graph->fromId(id, Item());}
    18481889
     
    18551896    /// Gives back the inverse of the IdMap.
    18561897    InverseMap inverse() const { return InverseMap(*_graph);}
    1857 
    1858   };
    1859 
    1860 
    1861   /// \brief General invertable graph-map type.
    1862 
    1863   /// This type provides simple invertable graph-maps.
    1864   /// The InvertableMap wraps an arbitrary ReadWriteMap
     1898  };
     1899
     1900
     1901  /// \brief General invertable graph map type.
     1902
     1903  /// This class provides simple invertable graph maps.
     1904  /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"
    18651905  /// and if a key is set to a new value then store it
    18661906  /// in the inverse map.
     
    18691909  /// with stl compatible forward iterator.
    18701910  ///
    1871   /// \tparam _Graph The graph type.
    1872   /// \tparam _Item The item type of the graph.
    1873   /// \tparam _Value The value type of the map.
     1911  /// \tparam GR The graph type.
     1912  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
     1913  /// \c GR::Edge).
     1914  /// \tparam V The value type of the map.
    18741915  ///
    18751916  /// \see IterableValueMap
    1876   template <typename _Graph, typename _Item, typename _Value>
     1917  template <typename GR, typename K, typename V>
    18771918  class InvertableMap
    1878     : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
     1919    : protected ItemSetTraits<GR, K>::template Map<V>::Type {
    18791920  private:
    18801921
    1881     typedef typename ItemSetTraits<_Graph, _Item>::
    1882     template Map<_Value>::Type Map;
    1883     typedef _Graph Graph;
    1884 
    1885     typedef std::map<_Value, _Item> Container;
     1922    typedef typename ItemSetTraits<GR, K>::
     1923      template Map<V>::Type Map;
     1924
     1925    typedef std::map<V, K> Container;
    18861926    Container _inv_map;
    18871927
    18881928  public:
    18891929
    1890     /// The key type of InvertableMap (Node, Arc, Edge).
    1891     typedef typename Map::Key Key;
    1892     /// The value type of the InvertableMap.
    1893     typedef typename Map::Value Value;
     1930    /// The graph type of InvertableMap.
     1931    typedef GR Graph;
     1932    /// The key type of InvertableMap (\c Node, \c Arc or \c Edge).
     1933    typedef K Item;
     1934    /// The key type of InvertableMap (\c Node, \c Arc or \c Edge).
     1935    typedef K Key;
     1936    /// The value type of InvertableMap.
     1937    typedef V Value;
    18941938
    18951939    /// \brief Constructor.
    18961940    ///
    1897     /// Construct a new InvertableMap for the graph.
    1898     ///
     1941    /// Construct a new InvertableMap for the given graph.
    18991942    explicit InvertableMap(const Graph& graph) : Map(graph) {}
    19001943
     
    19031946    /// This iterator is an stl compatible forward
    19041947    /// iterator on the values of the map. The values can
    1905     /// be accessed in the [beginValue, endValue) range.
    1906     ///
     1948    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
    19071949    class ValueIterator
    19081950      : public std::iterator<std::forward_iterator_tag, Value> {
     
    19361978    /// Returns an stl compatible iterator to the
    19371979    /// first value of the map. The values of the
    1938     /// map can be accessed in the [beginValue, endValue)
     1980    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
    19391981    /// range.
    19401982    ValueIterator beginValue() const {
     
    19461988    /// Returns an stl compatible iterator after the
    19471989    /// last value of the map. The values of the
    1948     /// map can be accessed in the [beginValue, endValue)
     1990    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
    19491991    /// range.
    19501992    ValueIterator endValue() const {
     
    19521994    }
    19531995
    1954     /// \brief The setter function of the map.
    1955     ///
    1956     /// Sets the mapped value.
     1996    /// \brief Sets the value associated with the given key.
     1997    ///
     1998    /// Sets the value associated with the given key.
    19571999    void set(const Key& key, const Value& val) {
    19582000      Value oldval = Map::operator[](key);
     
    19652007    }
    19662008
    1967     /// \brief The getter function of the map.
    1968     ///
    1969     /// It gives back the value associated with the key.
     2009    /// \brief Returns the value associated with the given key.
     2010    ///
     2011    /// Returns the value associated with the given key.
    19702012    typename MapTraits<Map>::ConstReturnValue
    19712013    operator[](const Key& key) const {
     
    19832025  protected:
    19842026
    1985     /// \brief Erase the key from the map.
    1986     ///
    1987     /// Erase the key to the map. It is called by the
     2027    /// \brief Erase the key from the map and the inverse map.
     2028    ///
     2029    /// Erase the key from the map and the inverse map. It is called by the
    19882030    /// \c AlterationNotifier.
    19892031    virtual void erase(const Key& key) {
     
    19962038    }
    19972039
    1998     /// \brief Erase more keys from the map.
    1999     ///
    2000     /// Erase more keys from the map. It is called by the
     2040    /// \brief Erase more keys from the map and the inverse map.
     2041    ///
     2042    /// Erase more keys from the map and the inverse map. It is called by the
    20012043    /// \c AlterationNotifier.
    20022044    virtual void erase(const std::vector<Key>& keys) {
     
    20112053    }
    20122054
    2013     /// \brief Clear the keys from the map and inverse map.
    2014     ///
    2015     /// Clear the keys from the map and inverse map. It is called by the
     2055    /// \brief Clear the keys from the map and the inverse map.
     2056    ///
     2057    /// Clear the keys from the map and the inverse map. It is called by the
    20162058    /// \c AlterationNotifier.
    20172059    virtual void clear() {
     
    20252067    ///
    20262068    /// The inverse of this map. The subscript operator of the map
    2027     /// gives back always the item what was last assigned to the value.
     2069    /// gives back the item that was last assigned to the value.
    20282070    class InverseMap {
    20292071    public:
    2030       /// \brief Constructor of the InverseMap.
     2072      /// \brief Constructor
    20312073      ///
    20322074      /// Constructor of the InverseMap.
     
    20412083      /// \brief Subscript operator.
    20422084      ///
    2043       /// Subscript operator. It gives back always the item
    2044       /// what was last assigned to the value.
     2085      /// Subscript operator. It gives back the item
     2086      /// that was last assigned to the given value.
    20452087      Value operator[](const Key& key) const {
    20462088        return _inverted(key);
     
    20512093    };
    20522094
    2053     /// \brief It gives back the just readable inverse map.
    2054     ///
    2055     /// It gives back the just readable inverse map.
     2095    /// \brief It gives back the read-only inverse map.
     2096    ///
     2097    /// It gives back the read-only inverse map.
    20562098    InverseMap inverse() const {
    20572099      return InverseMap(*this);
     
    20612103
    20622104  /// \brief Provides a mutable, continuous and unique descriptor for each
    2063   /// item in the graph.
    2064   ///
    2065   /// The DescriptorMap class provides a unique and continuous (but mutable)
    2066   /// descriptor (id) for each item of the same type (e.g. node) in the
    2067   /// graph. This id is <ul><li>\b unique: different items (nodes) get
    2068   /// different ids <li>\b continuous: the range of the ids is the set of
    2069   /// integers between 0 and \c n-1, where \c n is the number of the items of
    2070   /// this type (e.g. nodes) (so the id of a node can change if you delete an
    2071   /// other node, i.e. this id is mutable).  </ul> This map can be inverted
    2072   /// with its member class \c InverseMap, or with the \c operator() member.
    2073   ///
    2074   /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
    2075   /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
    2076   /// Edge.
    2077   template <typename _Graph, typename _Item>
     2105  /// item in a graph.
     2106  ///
     2107  /// DescriptorMap provides a unique and continuous (but mutable)
     2108  /// descriptor (id) for each item of the same type (\c Node, \c Arc or
     2109  /// \c Edge) in a graph. This id is
     2110  ///  - \b unique: different items get different ids,
     2111  ///  - \b continuous: the range of the ids is the set of integers
     2112  ///    between 0 and \c n-1, where \c n is the number of the items of
     2113  ///    this type (\c Node, \c Arc or \c Edge). So the id of an item can
     2114  ///    change if you delete an other item of the same type, i.e. this
     2115  ///    id is mutable.
     2116  ///
     2117  /// Thus this id is not (necessarily) the same as what can get using
     2118  /// the \c id() function of the graph or \ref IdMap.
     2119  /// This map can be inverted with its member class \c InverseMap,
     2120  /// or with the \c operator() member.
     2121  ///
     2122  /// \tparam GR The graph type.
     2123  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
     2124  /// \c GR::Edge).
     2125  ///
     2126  /// \see IdMap
     2127  template <typename GR, typename K>
    20782128  class DescriptorMap
    2079     : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
    2080 
    2081     typedef _Item Item;
    2082     typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
    2083 
    2084   public:
    2085     /// The graph class of DescriptorMap.
    2086     typedef _Graph Graph;
    2087 
    2088     /// The key type of DescriptorMap (Node, Arc, Edge).
    2089     typedef typename Map::Key Key;
     2129    : protected ItemSetTraits<GR, K>::template Map<int>::Type {
     2130
     2131    typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Map;
     2132
     2133  public:
     2134    /// The graph type of DescriptorMap.
     2135    typedef GR Graph;
     2136    /// The key type of DescriptorMap (\c Node, \c Arc or \c Edge).
     2137    typedef K Item;
     2138    /// The key type of DescriptorMap (\c Node, \c Arc or \c Edge).
     2139    typedef K Key;
    20902140    /// The value type of DescriptorMap.
    2091     typedef typename Map::Value Value;
     2141    typedef int Value;
    20922142
    20932143    /// \brief Constructor.
    20942144    ///
    20952145    /// Constructor for descriptor map.
    2096     explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
     2146    explicit DescriptorMap(const Graph& gr) : Map(gr) {
    20972147      Item it;
    20982148      const typename Map::Notifier* nf = Map::notifier();
     
    21052155  protected:
    21062156
    2107     /// \brief Add a new key to the map.
     2157    /// \brief Adds a new key to the map.
    21082158    ///
    21092159    /// Add a new key to the map. It is called by the
     
    22152265
    22162266  public:
     2267
    22172268    /// \brief The inverse map type of DescriptorMap.
    22182269    ///
     
    22202271    class InverseMap {
    22212272    public:
    2222       /// \brief Constructor of the InverseMap.
     2273      /// \brief Constructor
    22232274      ///
    22242275      /// Constructor of the InverseMap.
     
    22352286      ///
    22362287      /// Subscript operator. It gives back the item
    2237       /// that the descriptor belongs to currently.
     2288      /// that the descriptor currently belongs to.
    22382289      Value operator[](const Key& key) const {
    22392290        return _inverted(key);
     
    22592310  };
    22602311
    2261   /// \brief Returns the source of the given arc.
    2262   ///
    2263   /// The SourceMap gives back the source Node of the given arc.
     2312  /// \brief Map of the source nodes of arcs in a digraph.
     2313  ///
     2314  /// SourceMap provides access for the source node of each arc in a digraph,
     2315  /// which is returned by the \c source() function of the digraph.
     2316  /// \tparam GR The digraph type.
    22642317  /// \see TargetMap
    2265   template <typename Digraph>
     2318  template <typename GR>
    22662319  class SourceMap {
    22672320  public:
    22682321
    2269     typedef typename Digraph::Node Value;
    2270     typedef typename Digraph::Arc Key;
     2322    ///\e
     2323    typedef typename GR::Arc Key;
     2324    ///\e
     2325    typedef typename GR::Node Value;
    22712326
    22722327    /// \brief Constructor
    22732328    ///
    2274     /// Constructor
     2329    /// Constructor.
    22752330    /// \param digraph The digraph that the map belongs to.
    2276     explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
    2277 
    2278     /// \brief The subscript operator.
    2279     ///
    2280     /// The subscript operator.
    2281     /// \param arc The arc
    2282     /// \return The source of the arc
     2331    explicit SourceMap(const GR& digraph) : _graph(digraph) {}
     2332
     2333    /// \brief Returns the source node of the given arc.
     2334    ///
     2335    /// Returns the source node of the given arc.
    22832336    Value operator[](const Key& arc) const {
    2284       return _digraph.source(arc);
     2337      return _graph.source(arc);
    22852338    }
    22862339
    22872340  private:
    2288     const Digraph& _digraph;
     2341    const GR& _graph;
    22892342  };
    22902343
     
    22932346  /// This function just returns an \c SourceMap class.
    22942347  /// \relates SourceMap
    2295   template <typename Digraph>
    2296   inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
    2297     return SourceMap<Digraph>(digraph);
    2298   }
    2299 
    2300   /// \brief Returns the target of the given arc.
    2301   ///
    2302   /// The TargetMap gives back the target Node of the given arc.
     2348  template <typename GR>
     2349  inline SourceMap<GR> sourceMap(const GR& graph) {
     2350    return SourceMap<GR>(graph);
     2351  }
     2352
     2353  /// \brief Map of the target nodes of arcs in a digraph.
     2354  ///
     2355  /// TargetMap provides access for the target node of each arc in a digraph,
     2356  /// which is returned by the \c target() function of the digraph.
     2357  /// \tparam GR The digraph type.
    23032358  /// \see SourceMap
    2304   template <typename Digraph>
     2359  template <typename GR>
    23052360  class TargetMap {
    23062361  public:
    23072362
    2308     typedef typename Digraph::Node Value;
    2309     typedef typename Digraph::Arc Key;
     2363    ///\e
     2364    typedef typename GR::Arc Key;
     2365    ///\e
     2366    typedef typename GR::Node Value;
    23102367
    23112368    /// \brief Constructor
    23122369    ///
    2313     /// Constructor
     2370    /// Constructor.
    23142371    /// \param digraph The digraph that the map belongs to.
    2315     explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
    2316 
    2317     /// \brief The subscript operator.
    2318     ///
    2319     /// The subscript operator.
    2320     /// \param e The arc
    2321     /// \return The target of the arc
     2372    explicit TargetMap(const GR& digraph) : _graph(digraph) {}
     2373
     2374    /// \brief Returns the target node of the given arc.
     2375    ///
     2376    /// Returns the target node of the given arc.
    23222377    Value operator[](const Key& e) const {
    2323       return _digraph.target(e);
     2378      return _graph.target(e);
    23242379    }
    23252380
    23262381  private:
    2327     const Digraph& _digraph;
     2382    const GR& _graph;
    23282383  };
    23292384
     
    23322387  /// This function just returns a \c TargetMap class.
    23332388  /// \relates TargetMap
    2334   template <typename Digraph>
    2335   inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
    2336     return TargetMap<Digraph>(digraph);
    2337   }
    2338 
    2339   /// \brief Returns the "forward" directed arc view of an edge.
    2340   ///
    2341   /// Returns the "forward" directed arc view of an edge.
     2389  template <typename GR>
     2390  inline TargetMap<GR> targetMap(const GR& graph) {
     2391    return TargetMap<GR>(graph);
     2392  }
     2393
     2394  /// \brief Map of the "forward" directed arc view of edges in a graph.
     2395  ///
     2396  /// ForwardMap provides access for the "forward" directed arc view of
     2397  /// each edge in a graph, which is returned by the \c direct() function
     2398  /// of the graph with \c true parameter.
     2399  /// \tparam GR The graph type.
    23422400  /// \see BackwardMap
    2343   template <typename Graph>
     2401  template <typename GR>
    23442402  class ForwardMap {
    23452403  public:
    23462404
    2347     typedef typename Graph::Arc Value;
    2348     typedef typename Graph::Edge Key;
     2405    typedef typename GR::Arc Value;
     2406    typedef typename GR::Edge Key;
    23492407
    23502408    /// \brief Constructor
    23512409    ///
    2352     /// Constructor
     2410    /// Constructor.
    23532411    /// \param graph The graph that the map belongs to.
    2354     explicit ForwardMap(const Graph& graph) : _graph(graph) {}
    2355 
    2356     /// \brief The subscript operator.
    2357     ///
    2358     /// The subscript operator.
    2359     /// \param key An edge
    2360     /// \return The "forward" directed arc view of edge
     2412    explicit ForwardMap(const GR& graph) : _graph(graph) {}
     2413
     2414    /// \brief Returns the "forward" directed arc view of the given edge.
     2415    ///
     2416    /// Returns the "forward" directed arc view of the given edge.
    23612417    Value operator[](const Key& key) const {
    23622418      return _graph.direct(key, true);
     
    23642420
    23652421  private:
    2366     const Graph& _graph;
     2422    const GR& _graph;
    23672423  };
    23682424
     
    23712427  /// This function just returns an \c ForwardMap class.
    23722428  /// \relates ForwardMap
    2373   template <typename Graph>
    2374   inline ForwardMap<Graph> forwardMap(const Graph& graph) {
    2375     return ForwardMap<Graph>(graph);
    2376   }
    2377 
    2378   /// \brief Returns the "backward" directed arc view of an edge.
    2379   ///
    2380   /// Returns the "backward" directed arc view of an edge.
     2429  template <typename GR>
     2430  inline ForwardMap<GR> forwardMap(const GR& graph) {
     2431    return ForwardMap<GR>(graph);
     2432  }
     2433
     2434  /// \brief Map of the "backward" directed arc view of edges in a graph.
     2435  ///
     2436  /// BackwardMap provides access for the "backward" directed arc view of
     2437  /// each edge in a graph, which is returned by the \c direct() function
     2438  /// of the graph with \c false parameter.
     2439  /// \tparam GR The graph type.
    23812440  /// \see ForwardMap
    2382   template <typename Graph>
     2441  template <typename GR>
    23832442  class BackwardMap {
    23842443  public:
    23852444
    2386     typedef typename Graph::Arc Value;
    2387     typedef typename Graph::Edge Key;
     2445    typedef typename GR::Arc Value;
     2446    typedef typename GR::Edge Key;
    23882447
    23892448    /// \brief Constructor
    23902449    ///
    2391     /// Constructor
     2450    /// Constructor.
    23922451    /// \param graph The graph that the map belongs to.
    2393     explicit BackwardMap(const Graph& graph) : _graph(graph) {}
    2394 
    2395     /// \brief The subscript operator.
    2396     ///
    2397     /// The subscript operator.
    2398     /// \param key An edge
    2399     /// \return The "backward" directed arc view of edge
     2452    explicit BackwardMap(const GR& graph) : _graph(graph) {}
     2453
     2454    /// \brief Returns the "backward" directed arc view of the given edge.
     2455    ///
     2456    /// Returns the "backward" directed arc view of the given edge.
    24002457    Value operator[](const Key& key) const {
    24012458      return _graph.direct(key, false);
     
    24032460
    24042461  private:
    2405     const Graph& _graph;
     2462    const GR& _graph;
    24062463  };
    24072464
     
    24102467  /// This function just returns a \c BackwardMap class.
    24112468  /// \relates BackwardMap
    2412   template <typename Graph>
    2413   inline BackwardMap<Graph> backwardMap(const Graph& graph) {
    2414     return BackwardMap<Graph>(graph);
    2415   }
    2416 
    2417   /// \brief Potential difference map
    2418   ///
    2419   /// If there is an potential map on the nodes then we
    2420   /// can get an arc map as we get the substraction of the
    2421   /// values of the target and source.
    2422   template <typename Digraph, typename NodeMap>
    2423   class PotentialDifferenceMap {
    2424   public:
    2425     typedef typename Digraph::Arc Key;
    2426     typedef typename NodeMap::Value Value;
    2427 
    2428     /// \brief Constructor
    2429     ///
    2430     /// Contructor of the map
    2431     explicit PotentialDifferenceMap(const Digraph& digraph,
    2432                                     const NodeMap& potential)
    2433       : _digraph(digraph), _potential(potential) {}
    2434 
    2435     /// \brief Const subscription operator
    2436     ///
    2437     /// Const subscription operator
    2438     Value operator[](const Key& arc) const {
    2439       return _potential[_digraph.target(arc)] -
    2440         _potential[_digraph.source(arc)];
    2441     }
    2442 
    2443   private:
    2444     const Digraph& _digraph;
    2445     const NodeMap& _potential;
    2446   };
    2447 
    2448   /// \brief Returns a PotentialDifferenceMap.
    2449   ///
    2450   /// This function just returns a PotentialDifferenceMap.
    2451   /// \relates PotentialDifferenceMap
    2452   template <typename Digraph, typename NodeMap>
    2453   PotentialDifferenceMap<Digraph, NodeMap>
    2454   potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
    2455     return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
    2456   }
    2457 
    2458   /// \brief Map of the node in-degrees.
     2469  template <typename GR>
     2470  inline BackwardMap<GR> backwardMap(const GR& graph) {
     2471    return BackwardMap<GR>(graph);
     2472  }
     2473
     2474  /// \brief Map of the in-degrees of nodes in a digraph.
    24592475  ///
    24602476  /// This map returns the in-degree of a node. Once it is constructed,
    2461   /// the degrees are stored in a standard NodeMap, so each query is done
     2477  /// the degrees are stored in a standard \c NodeMap, so each query is done
    24622478  /// in constant time. On the other hand, the values are updated automatically
    24632479  /// whenever the digraph changes.
    24642480  ///
    2465   /// \warning Besides addNode() and addArc(), a digraph structure may provide
    2466   /// alternative ways to modify the digraph. The correct behavior of InDegMap
    2467   /// is not guarantied if these additional features are used. For example
    2468   /// the functions \ref ListDigraph::changeSource() "changeSource()",
     2481  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
     2482  /// may provide alternative ways to modify the digraph.
     2483  /// The correct behavior of InDegMap is not guarantied if these additional
     2484  /// features are used. For example the functions
     2485  /// \ref ListDigraph::changeSource() "changeSource()",
    24692486  /// \ref ListDigraph::changeTarget() "changeTarget()" and
    24702487  /// \ref ListDigraph::reverseArc() "reverseArc()"
     
    24722489  ///
    24732490  /// \sa OutDegMap
    2474 
    2475   template <typename _Digraph>
     2491  template <typename GR>
    24762492  class InDegMap
    2477     : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
     2493    : protected ItemSetTraits<GR, typename GR::Arc>
    24782494      ::ItemNotifier::ObserverBase {
    24792495
    24802496  public:
    2481 
    2482     typedef _Digraph Digraph;
     2497   
     2498    /// The digraph type
     2499    typedef GR Digraph;
     2500    /// The key type
     2501    typedef typename Digraph::Node Key;
     2502    /// The value type
    24832503    typedef int Value;
    2484     typedef typename Digraph::Node Key;
    24852504
    24862505    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
     
    25242543    /// \brief Constructor.
    25252544    ///
    2526     /// Constructor for creating in-degree map.
    2527     explicit InDegMap(const Digraph& digraph)
    2528       : _digraph(digraph), _deg(digraph) {
     2545    /// Constructor for creating an in-degree map.
     2546    explicit InDegMap(const Digraph& graph)
     2547      : _digraph(graph), _deg(graph) {
    25292548      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
    25302549
     
    25342553    }
    25352554
     2555    /// \brief Gives back the in-degree of a Node.
     2556    ///
    25362557    /// Gives back the in-degree of a Node.
    25372558    int operator[](const Key& key) const {
     
    25802601  };
    25812602
    2582   /// \brief Map of the node out-degrees.
     2603  /// \brief Map of the out-degrees of nodes in a digraph.
    25832604  ///
    25842605  /// This map returns the out-degree of a node. Once it is constructed,
    2585   /// the degrees are stored in a standard NodeMap, so each query is done
     2606  /// the degrees are stored in a standard \c NodeMap, so each query is done
    25862607  /// in constant time. On the other hand, the values are updated automatically
    25872608  /// whenever the digraph changes.
    25882609  ///
    2589   /// \warning Besides addNode() and addArc(), a digraph structure may provide
    2590   /// alternative ways to modify the digraph. The correct behavior of OutDegMap
    2591   /// is not guarantied if these additional features are used. For example
    2592   /// the functions \ref ListDigraph::changeSource() "changeSource()",
     2610  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
     2611  /// may provide alternative ways to modify the digraph.
     2612  /// The correct behavior of OutDegMap is not guarantied if these additional
     2613  /// features are used. For example the functions
     2614  /// \ref ListDigraph::changeSource() "changeSource()",
    25932615  /// \ref ListDigraph::changeTarget() "changeTarget()" and
    25942616  /// \ref ListDigraph::reverseArc() "reverseArc()"
     
    25962618  ///
    25972619  /// \sa InDegMap
    2598 
    2599   template <typename _Digraph>
     2620  template <typename GR>
    26002621  class OutDegMap
    2601     : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
     2622    : protected ItemSetTraits<GR, typename GR::Arc>
    26022623      ::ItemNotifier::ObserverBase {
    26032624
    26042625  public:
    26052626
    2606     typedef _Digraph Digraph;
     2627    /// The digraph type
     2628    typedef GR Digraph;
     2629    /// The key type
     2630    typedef typename Digraph::Node Key;
     2631    /// The value type
    26072632    typedef int Value;
    2608     typedef typename Digraph::Node Key;
    26092633
    26102634    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
     
    26462670    /// \brief Constructor.
    26472671    ///
    2648     /// Constructor for creating out-degree map.
    2649     explicit OutDegMap(const Digraph& digraph)
    2650       : _digraph(digraph), _deg(digraph) {
     2672    /// Constructor for creating an out-degree map.
     2673    explicit OutDegMap(const Digraph& graph)
     2674      : _digraph(graph), _deg(graph) {
    26512675      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
    26522676
     
    26562680    }
    26572681
     2682    /// \brief Gives back the out-degree of a Node.
     2683    ///
    26582684    /// Gives back the out-degree of a Node.
    26592685    int operator[](const Key& key) const {
     
    27022728  };
    27032729
     2730  /// \brief Potential difference map
     2731  ///
     2732  /// PotentialMap returns the difference between the potentials of the
     2733  /// source and target nodes of each arc in a digraph, i.e. it returns
     2734  /// \code
     2735  ///   potential[gr.target(arc)] - potential[gr.source(arc)].
     2736  /// \endcode
     2737  /// \tparam GR The digraph type.
     2738  /// \tparam POT A node map storing the potentials.
     2739  template <typename GR, typename POT>
     2740  class PotentialDifferenceMap {
     2741  public:
     2742    /// Key type
     2743    typedef typename GR::Arc Key;
     2744    /// Value type
     2745    typedef typename POT::Value Value;
     2746
     2747    /// \brief Constructor
     2748    ///
     2749    /// Contructor of the map.
     2750    explicit PotentialDifferenceMap(const GR& gr,
     2751                                    const POT& potential)
     2752      : _digraph(gr), _potential(potential) {}
     2753
     2754    /// \brief Returns the potential difference for the given arc.
     2755    ///
     2756    /// Returns the potential difference for the given arc, i.e.
     2757    /// \code
     2758    ///   potential[gr.target(arc)] - potential[gr.source(arc)].
     2759    /// \endcode
     2760    Value operator[](const Key& arc) const {
     2761      return _potential[_digraph.target(arc)] -
     2762        _potential[_digraph.source(arc)];
     2763    }
     2764
     2765  private:
     2766    const GR& _digraph;
     2767    const POT& _potential;
     2768  };
     2769
     2770  /// \brief Returns a PotentialDifferenceMap.
     2771  ///
     2772  /// This function just returns a PotentialDifferenceMap.
     2773  /// \relates PotentialDifferenceMap
     2774  template <typename GR, typename POT>
     2775  PotentialDifferenceMap<GR, POT>
     2776  potentialDifferenceMap(const GR& gr, const POT& potential) {
     2777    return PotentialDifferenceMap<GR, POT>(gr, potential);
     2778  }
     2779
    27042780  /// @}
    27052781}
  • lemon/max_matching.h

    r463 r606  
    5656  /// decomposition() after running the algorithm.
    5757  ///
    58   /// \param _Graph The graph type the algorithm runs on.
    59   template <typename _Graph>
     58  /// \param GR The graph type the algorithm runs on.
     59  template <typename GR>
    6060  class MaxMatching {
    6161  public:
    6262
    63     typedef _Graph Graph;
     63    typedef GR Graph;
    6464    typedef typename Graph::template NodeMap<typename Graph::Arc>
    6565    MatchingMap;
     
    464464    /// map must have the property that there are no two incident edges
    465465    /// with true value, ie. it contains a matching.
    466     /// \return %True if the map contains a matching.
     466    /// \return \c true if the map contains a matching.
    467467    template <typename MatchingMap>
    468468    bool matchingInit(const MatchingMap& matching) {
     
    614614  /// maximum weighted matching algorithm. The implementation is based
    615615  /// on extensive use of priority queues and provides
    616   /// \f$O(nm\log(n))\f$ time complexity.
     616  /// \f$O(nm\log n)\f$ time complexity.
    617617  ///
    618618  /// The maximum weighted matching problem is to find undirected
     
    648648  /// of a blossom. If the value type is integral then the dual
    649649  /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
    650   template <typename _Graph,
    651             typename _WeightMap = typename _Graph::template EdgeMap<int> >
     650  template <typename GR,
     651            typename WM = typename GR::template EdgeMap<int> >
    652652  class MaxWeightedMatching {
    653653  public:
    654654
    655     typedef _Graph Graph;
    656     typedef _WeightMap WeightMap;
     655    ///\e
     656    typedef GR Graph;
     657    ///\e
     658    typedef WM WeightMap;
     659    ///\e
    657660    typedef typename WeightMap::Value Value;
    658661
     
    19581961  /// maximum weighted perfect matching algorithm. The implementation
    19591962  /// is based on extensive use of priority queues and provides
    1960   /// \f$O(nm\log(n))\f$ time complexity.
     1963  /// \f$O(nm\log n)\f$ time complexity.
    19611964  ///
    19621965  /// The maximum weighted matching problem is to find undirected
     
    19911994  /// of a blossom. If the value type is integral then the dual
    19921995  /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
    1993   template <typename _Graph,
    1994             typename _WeightMap = typename _Graph::template EdgeMap<int> >
     1996  template <typename GR,
     1997            typename WM = typename GR::template EdgeMap<int> >
    19951998  class MaxWeightedPerfectMatching {
    19961999  public:
    19972000
    1998     typedef _Graph Graph;
    1999     typedef _WeightMap WeightMap;
     2001    typedef GR Graph;
     2002    typedef WM WeightMap;
    20002003    typedef typename WeightMap::Value Value;
    20012004
  • lemon/min_cost_arborescence.h

    r522 r606  
    3636  ///
    3737  /// Default traits class for MinCostArborescence class.
    38   /// \param _Digraph Digraph type.
    39   /// \param _CostMap Type of cost map.
    40   template <class _Digraph, class _CostMap>
     38  /// \param GR Digraph type.
     39  /// \param CM Type of cost map.
     40  template <class GR, class CM>
    4141  struct MinCostArborescenceDefaultTraits{
    4242
    4343    /// \brief The digraph type the algorithm runs on.
    44     typedef _Digraph Digraph;
     44    typedef GR Digraph;
    4545
    4646    /// \brief The type of the map that stores the arc costs.
     
    4848    /// The type of the map that stores the arc costs.
    4949    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    50     typedef _CostMap CostMap;
     50    typedef CM CostMap;
    5151
    5252    /// \brief The value type of the costs.
     
    6464    typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
    6565
    66     /// \brief Instantiates a ArborescenceMap.
    67     ///
    68     /// This function instantiates a \ref ArborescenceMap.
     66    /// \brief Instantiates a \c ArborescenceMap.
     67    ///
     68    /// This function instantiates a \c ArborescenceMap.
    6969    /// \param digraph is the graph, to which we would like to
    70     /// calculate the ArborescenceMap.
     70    /// calculate the \c ArborescenceMap.
    7171    static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
    7272      return new ArborescenceMap(digraph);
    7373    }
    7474
    75     /// \brief The type of the PredMap
    76     ///
    77     /// The type of the PredMap. It is a node map with an arc value type.
     75    /// \brief The type of the \c PredMap
     76    ///
     77    /// The type of the \c PredMap. It is a node map with an arc value type.
    7878    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    7979
    80     /// \brief Instantiates a PredMap.
    81     ///
    82     /// This function instantiates a \ref PredMap.
    83     /// \param _digraph is the digraph, to which we would like to define the
    84     /// PredMap.
     80    /// \brief Instantiates a \c PredMap.
     81    ///
     82    /// This function instantiates a \c PredMap.
     83    /// \param digraph The digraph to which we would like to define the
     84    /// \c PredMap.
    8585    static PredMap *createPredMap(const Digraph &digraph){
    8686      return new PredMap(digraph);
     
    9999  /// the minimum cost subgraph which are union of arborescences with the
    100100  /// given sources and spans all the nodes which are reachable from the
    101   /// sources. The time complexity of the algorithm is \f$ O(n^2+e) \f$.
     101  /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e).
    102102  ///
    103103  /// The algorithm provides also an optimal dual solution, therefore
    104104  /// the optimality of the solution can be checked.
    105105  ///
    106   /// \param _Digraph The digraph type the algorithm runs on. The default value
     106  /// \param GR The digraph type the algorithm runs on. The default value
    107107  /// is \ref ListDigraph.
    108   /// \param _CostMap This read-only ArcMap determines the costs of the
     108  /// \param CM This read-only ArcMap determines the costs of the
    109109  /// arcs. It is read once for each arc, so the map may involve in
    110110  /// relatively time consuming process to compute the arc cost if
    111111  /// it is necessary. The default map type is \ref
    112112  /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
    113   /// \param _Traits Traits class to set various data types used
     113  /// \param TR Traits class to set various data types used
    114114  /// by the algorithm. The default traits class is
    115115  /// \ref MinCostArborescenceDefaultTraits
    116   /// "MinCostArborescenceDefaultTraits<_Digraph, _CostMap>".  See \ref
     116  /// "MinCostArborescenceDefaultTraits<GR, CM>".  See \ref
    117117  /// MinCostArborescenceDefaultTraits for the documentation of a
    118118  /// MinCostArborescence traits class.
    119   ///
    120   /// \author Balazs Dezso
    121119#ifndef DOXYGEN
    122   template <typename _Digraph = ListDigraph,
    123             typename _CostMap = typename _Digraph::template ArcMap<int>,
    124             typename _Traits =
    125             MinCostArborescenceDefaultTraits<_Digraph, _CostMap> >
     120  template <typename GR = ListDigraph,
     121            typename CM = typename GR::template ArcMap<int>,
     122            typename TR =
     123              MinCostArborescenceDefaultTraits<GR, CM> >
    126124#else
    127   template <typename _Digraph, typename _CostMap, typedef _Traits>
     125  template <typename GR, typename CM, typedef TR>
    128126#endif
    129127  class MinCostArborescence {
     
    131129
    132130    /// The traits.
    133     typedef _Traits Traits;
     131    typedef TR Traits;
    134132    /// The type of the underlying digraph.
    135133    typedef typename Traits::Digraph Digraph;
     
    441439    /// \brief Constructor.
    442440    ///
    443     /// \param _digraph The digraph the algorithm will run on.
    444     /// \param _cost The cost map used by the algorithm.
     441    /// \param digraph The digraph the algorithm will run on.
     442    /// \param cost The cost map used by the algorithm.
    445443    MinCostArborescence(const Digraph& digraph, const CostMap& cost)
    446444      : _digraph(&digraph), _cost(&cost), _pred(0), local_pred(false),
     
    457455    ///
    458456    /// Sets the arborescence map.
    459     /// \return \c (*this)
     457    /// \return <tt>(*this)</tt>
    460458    MinCostArborescence& arborescenceMap(ArborescenceMap& m) {
    461459      if (local_arborescence) {
     
    470468    ///
    471469    /// Sets the arborescence map.
    472     /// \return \c (*this)
     470    /// \return <tt>(*this)</tt>
    473471    MinCostArborescence& predMap(PredMap& m) {
    474472      if (local_pred) {
  • lemon/path.h

    r564 r606  
    4141  ///
    4242  /// A structure for representing directed path in a digraph.
    43   /// \tparam _Digraph The digraph type in which the path is.
     43  /// \tparam GR The digraph type in which the path is.
    4444  ///
    4545  /// In a sense, the path can be treated as a list of arcs. The
     
    5353  /// implementation uses two vectors for storing the front and back
    5454  /// insertions.
    55   template <typename _Digraph>
     55  template <typename GR>
    5656  class Path {
    5757  public:
    5858
    59     typedef _Digraph Digraph;
     59    typedef GR Digraph;
    6060    typedef typename Digraph::Arc Arc;
    6161
     
    138138    /// \brief The nth arc.
    139139    ///
    140     /// \pre n is in the [0..length() - 1] range
     140    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
    141141    const Arc& nth(int n) const {
    142142      return n < int(head.size()) ? *(head.rbegin() + n) :
     
    146146    /// \brief Initialize arc iterator to point to the nth arc
    147147    ///
    148     /// \pre n is in the [0..length() - 1] range
     148    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
    149149    ArcIt nthIt(int n) const {
    150150      return ArcIt(*this, n);
     
    229229  ///
    230230  /// A structure for representing directed path in a digraph.
    231   /// \tparam _Digraph The digraph type in which the path is.
     231  /// \tparam GR The digraph type in which the path is.
    232232  ///
    233233  /// In a sense, the path can be treated as a list of arcs. The
     
    241241  /// then the \c Path type because it use just one vector for the
    242242  /// arcs.
    243   template <typename _Digraph>
     243  template <typename GR>
    244244  class SimplePath {
    245245  public:
    246246
    247     typedef _Digraph Digraph;
     247    typedef GR Digraph;
    248248    typedef typename Digraph::Arc Arc;
    249249
     
    330330    /// \brief The nth arc.
    331331    ///
    332     /// \pre n is in the [0..length() - 1] range
     332    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
    333333    const Arc& nth(int n) const {
    334334      return data[n];
     
    393393  ///
    394394  /// A structure for representing directed path in a digraph.
    395   /// \tparam _Digraph The digraph type in which the path is.
     395  /// \tparam GR The digraph type in which the path is.
    396396  ///
    397397  /// In a sense, the path can be treated as a list of arcs. The
     
    405405  /// time. The front and back insertion and erasure is O(1) time
    406406  /// and it can be splited and spliced in O(1) time.
    407   template <typename _Digraph>
     407  template <typename GR>
    408408  class ListPath {
    409409  public:
    410410
    411     typedef _Digraph Digraph;
     411    typedef GR Digraph;
    412412    typedef typename Digraph::Arc Arc;
    413413
     
    508508    ///
    509509    /// This function looks for the nth arc in O(n) time.
    510     /// \pre n is in the [0..length() - 1] range
     510    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
    511511    const Arc& nth(int n) const {
    512512      Node *node = first;
     
    733733  ///
    734734  /// A structure for representing directed path in a digraph.
    735   /// \tparam _Digraph The digraph type in which the path is.
     735  /// \tparam GR The digraph type in which the path is.
    736736  ///
    737737  /// In a sense, the path can be treated as a list of arcs. The
     
    747747  /// it is intented to be
    748748  /// used when you want to store a large number of paths.
    749   template <typename _Digraph>
     749  template <typename GR>
    750750  class StaticPath {
    751751  public:
    752752
    753     typedef _Digraph Digraph;
     753    typedef GR Digraph;
    754754    typedef typename Digraph::Arc Arc;
    755755
     
    834834    /// \brief The nth arc.
    835835    ///
    836     /// \pre n is in the [0..length() - 1] range
     836    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
    837837    const Arc& nth(int n) const {
    838838      return arcs[n];
  • lemon/preflow.h

    r525 r606  
    3333  /// Default traits class of Preflow class.
    3434  /// \tparam GR Digraph type.
    35   /// \tparam CM Capacity map type.
    36   template <typename GR, typename CM>
     35  /// \tparam CAP Capacity map type.
     36  template <typename GR, typename CAP>
    3737  struct PreflowDefaultTraits {
    3838
     
    4444    /// The type of the map that stores the arc capacities.
    4545    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    46     typedef CM CapacityMap;
     46    typedef CAP CapacityMap;
    4747
    4848    /// \brief The type of the flow values.
     
    9595  ///
    9696  /// This class provides an implementation of Goldberg-Tarjan's \e preflow
    97   /// \e push-relabel algorithm producing a flow of maximum value in a
    98   /// digraph. The preflow algorithms are the fastest known maximum
     97  /// \e push-relabel algorithm producing a \ref max_flow
     98  /// "flow of maximum value" in a digraph.
     99  /// The preflow algorithms are the fastest known maximum
    99100  /// flow algorithms. The current implementation use a mixture of the
    100101  /// \e "highest label" and the \e "bound decrease" heuristics.
     
    106107  ///
    107108  /// \tparam GR The type of the digraph the algorithm runs on.
    108   /// \tparam CM The type of the capacity map. The default map
     109  /// \tparam CAP The type of the capacity map. The default map
    109110  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    110111#ifdef DOXYGEN
    111   template <typename GR, typename CM, typename TR>
     112  template <typename GR, typename CAP, typename TR>
    112113#else
    113114  template <typename GR,
    114             typename CM = typename GR::template ArcMap<int>,
    115             typename TR = PreflowDefaultTraits<GR, CM> >
     115            typename CAP = typename GR::template ArcMap<int>,
     116            typename TR = PreflowDefaultTraits<GR, CAP> >
    116117#endif
    117118  class Preflow {
     
    195196    ///@{
    196197
    197     template <typename _FlowMap>
     198    template <typename T>
    198199    struct SetFlowMapTraits : public Traits {
    199       typedef _FlowMap FlowMap;
     200      typedef T FlowMap;
    200201      static FlowMap *createFlowMap(const Digraph&) {
    201202        LEMON_ASSERT(false, "FlowMap is not initialized");
     
    209210    /// \ref named-templ-param "Named parameter" for setting FlowMap
    210211    /// type.
    211     template <typename _FlowMap>
     212    template <typename T>
    212213    struct SetFlowMap
    213       : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<_FlowMap> > {
     214      : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<T> > {
    214215      typedef Preflow<Digraph, CapacityMap,
    215                       SetFlowMapTraits<_FlowMap> > Create;
     216                      SetFlowMapTraits<T> > Create;
    216217    };
    217218
    218     template <typename _Elevator>
     219    template <typename T>
    219220    struct SetElevatorTraits : public Traits {
    220       typedef _Elevator Elevator;
     221      typedef T Elevator;
    221222      static Elevator *createElevator(const Digraph&, int) {
    222223        LEMON_ASSERT(false, "Elevator is not initialized");
     
    234235    /// \ref run() or \ref init().
    235236    /// \sa SetStandardElevator
    236     template <typename _Elevator>
     237    template <typename T>
    237238    struct SetElevator
    238       : public Preflow<Digraph, CapacityMap, SetElevatorTraits<_Elevator> > {
     239      : public Preflow<Digraph, CapacityMap, SetElevatorTraits<T> > {
    239240      typedef Preflow<Digraph, CapacityMap,
    240                       SetElevatorTraits<_Elevator> > Create;
     241                      SetElevatorTraits<T> > Create;
    241242    };
    242243
    243     template <typename _Elevator>
     244    template <typename T>
    244245    struct SetStandardElevatorTraits : public Traits {
    245       typedef _Elevator Elevator;
     246      typedef T Elevator;
    246247      static Elevator *createElevator(const Digraph& digraph, int max_level) {
    247248        return new Elevator(digraph, max_level);
     
    261262    /// before calling \ref run() or \ref init().
    262263    /// \sa SetElevator
    263     template <typename _Elevator>
     264    template <typename T>
    264265    struct SetStandardElevator
    265266      : public Preflow<Digraph, CapacityMap,
    266                        SetStandardElevatorTraits<_Elevator> > {
     267                       SetStandardElevatorTraits<T> > {
    267268      typedef Preflow<Digraph, CapacityMap,
    268                       SetStandardElevatorTraits<_Elevator> > Create;
     269                      SetStandardElevatorTraits<T> > Create;
    269270    };
    270271
     
    947948    ///
    948949    /// \note This function calls \ref minCut() for each node, so it runs in
    949     /// \f$O(n)\f$ time.
     950    /// O(n) time.
    950951    ///
    951952    /// \pre Either \ref run() or \ref init() must be called before
  • lemon/radix_sort.h

    r467 r606  
    206206  ///
    207207  /// This is a special quick sort algorithm where the pivot
    208   /// values to split the items are choosen to be \f$ 2^k \f$ for each \c k.
    209   /// Therefore, the time complexity of the
    210   /// algorithm is \f$ O(\log(c)n) \f$ and it uses \f$ O(\log(c)) \f$,
    211   /// additional space, where \c c is the maximal value and \c n is the
    212   /// number of the items in the container.
     208  /// values to split the items are choosen to be 2<sup>k</sup>
     209  /// for each \c k.
     210  /// Therefore, the time complexity of the algorithm is O(log(c)*n) and
     211  /// it uses O(log(c)) additional space, where \c c is the maximal value
     212  /// and \c n is the number of the items in the container.
    213213  ///
    214214  /// \param first The begin of the given range.
     
    431431  /// byte-by-byte. First, it counts how many times a byte value occurs
    432432  /// in the container, then it copies the corresponding items to
    433   /// another container in asceding order in \c O(n) time.
    434   ///
    435   /// The time complexity of the algorithm is \f$ O(\log(c)n) \f$ and
    436   /// it uses \f$ O(n) \f$, additional space, where \c c is the
     433  /// another container in asceding order in O(n) time.
     434  ///
     435  /// The time complexity of the algorithm is O(log(c)*n) and
     436  /// it uses O(n) additional space, where \c c is the
    437437  /// maximal value and \c n is the number of the items in the
    438438  /// container.
  • lemon/random.h

    r564 r606  
    604604    /// function with the <tt>/dev/urandom</tt> file. If it does not success,
    605605    /// it uses the \c seedFromTime().
    606     /// \return Currently always true.
     606    /// \return Currently always \c true.
    607607    bool seed() {
    608608#ifndef WIN32
     
    625625    /// \param file The source file
    626626    /// \param offset The offset, from the file read.
    627     /// \return True when the seeding successes.
     627    /// \return \c true when the seeding successes.
    628628#ifndef WIN32
    629629    bool seedFromFile(const std::string& file = "/dev/urandom", int offset = 0)
     
    646646    /// current process id and the current time for initialize the
    647647    /// random sequence.
    648     /// \return Currently always true.
     648    /// \return Currently always \c true.
    649649    bool seedFromTime() {
    650650#ifndef WIN32
  • lemon/smart_graph.h

    r463 r606  
    226226    ///Add a new node to the digraph.
    227227
    228     /// \return the new node.
    229     ///
     228    /// Add a new node to the digraph.
     229    /// \return The new node.
    230230    Node addNode() { return Parent::addNode(); }
    231231
     
    234234    ///Add a new arc to the digraph with source node \c s
    235235    ///and target node \c t.
    236     ///\return the new arc.
     236    ///\return The new arc.
    237237    Arc addArc(const Node& s, const Node& t) {
    238238      return Parent::addArc(s, t);
     
    667667    ///Add a new node to the graph.
    668668
    669     /// \return the new node.
    670     ///
     669    /// Add a new node to the graph.
     670    /// \return The new node.
    671671    Node addNode() { return Parent::addNode(); }
    672672
     
    675675    ///Add a new edge to the graph with node \c s
    676676    ///and \c t.
    677     ///\return the new edge.
     677    ///\return The new edge.
    678678    Edge addEdge(const Node& s, const Node& t) {
    679679      return Parent::addEdge(s, t);
  • lemon/suurballe.h

    r566 r606  
    4646  /// \ref CapacityScaling "successive shortest path" algorithm.
    4747  ///
    48   /// \tparam Digraph The digraph type the algorithm runs on.
     48  /// \tparam GR The digraph type the algorithm runs on.
    4949  /// The default value is \c ListDigraph.
    50   /// \tparam LengthMap The type of the length (cost) map.
     50  /// \tparam LEN The type of the length (cost) map.
    5151  /// The default value is <tt>Digraph::ArcMap<int></tt>.
    5252  ///
     
    5656  /// with \ref SplitNodes.
    5757#ifdef DOXYGEN
    58   template <typename Digraph, typename LengthMap>
     58  template <typename GR, typename LEN>
    5959#else
    60   template < typename Digraph = ListDigraph,
    61              typename LengthMap = typename Digraph::template ArcMap<int> >
     60  template < typename GR = ListDigraph,
     61             typename LEN = typename GR::template ArcMap<int> >
    6262#endif
    6363  class Suurballe
    6464  {
    65     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    66 
     65    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     66
     67    typedef ConstMap<Arc, int> ConstArcMap;
     68    typedef typename GR::template NodeMap<Arc> PredMap;
     69
     70  public:
     71
     72    /// The type of the digraph the algorithm runs on.
     73    typedef GR Digraph;
     74    /// The type of the length map.
     75    typedef LEN LengthMap;
     76    /// The type of the lengths.
    6777    typedef typename LengthMap::Value Length;
    68     typedef ConstMap<Arc, int> ConstArcMap;
    69     typedef typename Digraph::template NodeMap<Arc> PredMap;
    70 
    71   public:
    72 
    7378    /// The type of the flow map.
    7479    typedef typename Digraph::template ArcMap<int> FlowMap;
     
    257262    /// the found arc-disjoint paths.
    258263    ///
    259     /// \return \c (*this)
     264    /// \return <tt>(*this)</tt>
    260265    Suurballe& flowMap(FlowMap &map) {
    261266      if (_local_flow) {
     
    274279    /// minimum cost flow problem.
    275280    ///
    276     /// \return \c (*this)
     281    /// \return <tt>(*this)</tt>
    277282    Suurballe& potentialMap(PotentialMap &map) {
    278283      if (_local_potential) {
     
    459464    ///
    460465    /// This function returns the total length (cost) of the found paths
    461     /// (flow). The complexity of the function is \f$ O(e) \f$.
     466    /// (flow). The complexity of the function is O(e).
    462467    ///
    463468    /// \pre \ref run() or \ref findFlow() must be called before using
  • lemon/unionfind.h

    r463 r606  
    5252  /// \pre You need to add all the elements by the \ref insert()
    5353  /// method.
    54   template <typename _ItemIntMap>
     54  template <typename IM>
    5555  class UnionFind {
    5656  public:
    5757
    58     typedef _ItemIntMap ItemIntMap;
     58    ///\e
     59    typedef IM ItemIntMap;
     60    ///\e
    5961    typedef typename ItemIntMap::Key Item;
    6062
     
    171173  /// method.
    172174  ///
    173   template <typename _ItemIntMap>
     175  template <typename IM>
    174176  class UnionFindEnum {
    175177  public:
    176178
    177     typedef _ItemIntMap ItemIntMap;
     179    ///\e
     180    typedef IM ItemIntMap;
     181    ///\e
    178182    typedef typename ItemIntMap::Key Item;
    179183
     
    628632  /// \pre You need to add all the elements by the \ref insert()
    629633  /// method.
    630   template <typename _ItemIntMap>
     634  template <typename IM>
    631635  class ExtendFindEnum {
    632636  public:
    633637
    634     typedef _ItemIntMap ItemIntMap;
     638    ///\e
     639    typedef IM ItemIntMap;
     640    ///\e
    635641    typedef typename ItemIntMap::Key Item;
    636642
     
    949955  /// \pre You need to add all the elements by the \ref insert()
    950956  /// method.
    951   ///
    952   template <typename _Value, typename _ItemIntMap,
    953             typename _Comp = std::less<_Value> >
     957  template <typename V, typename IM, typename Comp = std::less<V> >
    954958  class HeapUnionFind {
    955959  public:
    956960
    957     typedef _Value Value;
    958     typedef typename _ItemIntMap::Key Item;
    959 
    960     typedef _ItemIntMap ItemIntMap;
    961 
    962     typedef _Comp Comp;
     961    ///\e
     962    typedef V Value;
     963    ///\e
     964    typedef typename IM::Key Item;
     965    ///\e
     966    typedef IM ItemIntMap;
     967    ///\e
     968    typedef Comp Compare;
    963969
    964970  private:
     
    16021608    /// \brief Gives back the priority of the current item.
    16031609    ///
    1604     /// \return Gives back the priority of the current item.
     1610    /// Gives back the priority of the current item.
    16051611    const Value& operator[](const Item& item) const {
    16061612      return nodes[index[item]].prio;
     
    16471653    /// \brief Gives back the minimum priority of the class.
    16481654    ///
    1649     /// \return Gives back the minimum priority of the class.
     1655    /// Gives back the minimum priority of the class.
    16501656    const Value& classPrio(int cls) const {
    16511657      return nodes[~(classes[cls].parent)].prio;
     
    16611667    /// \brief Gives back a representant item of the class.
    16621668    ///
     1669    /// Gives back a representant item of the class.
    16631670    /// The representant is indpendent from the priorities of the
    16641671    /// items.
    1665     /// \return Gives back a representant item of the class.
    16661672    const Item& classRep(int id) const {
    16671673      int parent = classes[id].parent;
Note: See TracChangeset for help on using the changeset viewer.