COIN-OR::LEMON - Graph Library

Changeset 559:c5fd2d996909 in lemon-1.2 for lemon


Ignore:
Timestamp:
03/29/09 23:08:20 (15 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.
Location:
lemon
Files:
31 edited

Legend:

Unmodified
Added
Removed
  • lemon/adaptors.h

    r519 r559  
    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

    r440 r559  
    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

    r519 r559  
    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

    r492 r559  
    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

    r529 r559  
    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

    r534 r559  
    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

    r529 r559  
    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

    r529 r559  
    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

    r440 r559  
    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

    r535 r559  
    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

    r492 r559  
    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

    r512 r559  
    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

    r519 r559  
    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

    r522 r559  
    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

    r515 r559  
    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

    r440 r559  
    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

    r440 r559  
    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

    r440 r559  
    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

    r517 r559  
    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

    r517 r559  
    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

    r440 r559  
    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

    r440 r559  
    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

    r440 r559  
    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

    r490 r559  
    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

    r517 r559  
    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

    r492 r559  
    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

    r444 r559  
    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

    r517 r559  
    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

    r440 r559  
    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

    r519 r559  
    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

    r440 r559  
    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.