COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [707:3887d6f994d7:708:5d313b76f323] in lemon-main


Ignore:
Files:
2 added
12 edited

Legend:

Unmodified
Added
Removed

  • lemon/Makefile.am

    r701 r708  
    5858        lemon/arg_parser.h \
    5959        lemon/assert.h \
     60        lemon/bellman_ford.h \
    6061        lemon/bfs.h \
    6162        lemon/bin_heap.h \
    … …  
    9697        lemon/lp_base.h \
    9798        lemon/lp_skeleton.h \
    98         lemon/list_graph.h \
    9999        lemon/maps.h \
    100100        lemon/matching.h \

  • lemon/bits/edge_set_extender.h

    r617 r685  
    538538
    539539    public:
    540       ArcMap(const Graph& _g)
     540      explicit ArcMap(const Graph& _g)
    541541        : Parent(_g) {}
    542542      ArcMap(const Graph& _g, const _Value& _v)
    … …  
    562562
    563563    public:
    564       EdgeMap(const Graph& _g)
     564      explicit EdgeMap(const Graph& _g)
    565565        : Parent(_g) {}
    566566

  • lemon/bits/graph_extender.h

    r617 r685  
    605605
    606606    public:
    607       NodeMap(const Graph& graph)
     607      explicit NodeMap(const Graph& graph)
    608608        : Parent(graph) {}
    609609      NodeMap(const Graph& graph, const _Value& value)
    … …  
    629629
    630630    public:
    631       ArcMap(const Graph& graph)
     631      explicit ArcMap(const Graph& graph)
    632632        : Parent(graph) {}
    633633      ArcMap(const Graph& graph, const _Value& value)
    … …  
    653653
    654654    public:
    655       EdgeMap(const Graph& graph)
     655      explicit EdgeMap(const Graph& graph)
    656656        : Parent(graph) {}
    657657

  • lemon/circulation.h

    r641 r689  
    451451    }
    452452
    453     /// \brief Sets the tolerance used by algorithm.
    454     ///
    455     /// Sets the tolerance used by algorithm.
    456     Circulation& tolerance(const Tolerance& tolerance) const {
     453    /// \brief Sets the tolerance used by the algorithm.
     454    ///
     455    /// Sets the tolerance object used by the algorithm.
     456    /// \return <tt>(*this)</tt>
     457    Circulation& tolerance(const Tolerance& tolerance) {
    457458      _tol = tolerance;
    458459      return *this;
    … …  
    461462    /// \brief Returns a const reference to the tolerance.
    462463    ///
    463     /// Returns a const reference to the tolerance.
     464    /// Returns a const reference to the tolerance object used by
     465    /// the algorithm.
    464466    const Tolerance& tolerance() const {
    465       return tolerance;
     467      return _tol;
    466468    }
    467469

  • lemon/maps.h

    r617 r695  
    2323#include <functional>
    2424#include <vector>
     25#include <map>
    2526
    2627#include <lemon/core.h>
    … …  
    2930///\ingroup maps
    3031///\brief Miscellaneous property maps
    31 
    32 #include <map>
    3332
    3433namespace lemon {
    … …  
    18191818  ///
    18201819  /// 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 
     1820  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
    18221821  ///  - \b unique: different items get different ids,
    18231822  ///  - \b immutable: the id of an item does not change (even if you
    … …  
    19031902
    19041903  /// This class provides simple invertable graph maps.
    1905   /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"
    1906   /// and if a key is set to a new value then store it
    1907   /// in the inverse map.
    1908   ///
     1904  /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
     1905  /// and if a key is set to a new value, then stores it in the inverse map.
    19091906  /// The values of the map can be accessed
    19101907  /// with stl compatible forward iterator.
     1908  ///
     1909  /// This type is not reference map, so it cannot be modified with
     1910  /// the subscript operator.
    19111911  ///
    19121912  /// \tparam GR The graph type.
    … …  
    19241924      template Map<V>::Type Map;
    19251925
    1926     typedef std::map<V, K> Container;
     1926    typedef std::multimap<V, K> Container;
    19271927    Container _inv_map;
    19281928
    … …  
    19491949    /// iterator on the values of the map. The values can
    19501950    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
     1951    /// They are considered with multiplicity, so each value is
     1952    /// traversed for each item it is assigned to.
    19511953    class ValueIterator
    19521954      : public std::iterator<std::forward_iterator_tag, Value> {
    … …  
    20012003    void set(const Key& key, const Value& val) {
    20022004      Value oldval = Map::operator[](key);
    2003       typename Container::iterator it = _inv_map.find(oldval);
    2004       if (it != _inv_map.end() && it->second == key) {
    2005         _inv_map.erase(it);
    2006       }
    2007       _inv_map.insert(make_pair(val, key));
     2005      typename Container::iterator it;
     2006      for (it = _inv_map.equal_range(oldval).first;
     2007           it != _inv_map.equal_range(oldval).second; ++it) {
     2008        if (it->second == key) {
     2009          _inv_map.erase(it);
     2010          break;
     2011        }
     2012      }
     2013      _inv_map.insert(std::make_pair(val, key));
    20082014      Map::set(key, val);
    20092015    }
    … …  
    20172023    }
    20182024
    2019     /// \brief Gives back the item by its value.
    2020     ///
    2021     /// Gives back the item by its value.
    2022     Key operator()(const Value& key) const {
    2023       typename Container::const_iterator it = _inv_map.find(key);
     2025    /// \brief Gives back an item by its value.
     2026    ///
     2027    /// This function gives back an item that is assigned to
     2028    /// the given value or \c INVALID if no such item exists.
     2029    /// If there are more items with the same associated value,
     2030    /// only one of them is returned.
     2031    Key operator()(const Value& val) const {
     2032      typename Container::const_iterator it = _inv_map.find(val);
    20242033      return it != _inv_map.end() ? it->second : INVALID;
    20252034    }
    … …  
    20332042    virtual void erase(const Key& key) {
    20342043      Value val = Map::operator[](key);
    2035       typename Container::iterator it = _inv_map.find(val);
    2036       if (it != _inv_map.end() && it->second == key) {
    2037         _inv_map.erase(it);
     2044      typename Container::iterator it;
     2045      for (it = _inv_map.equal_range(val).first;
     2046           it != _inv_map.equal_range(val).second; ++it) {
     2047        if (it->second == key) {
     2048          _inv_map.erase(it);
     2049          break;
     2050        }
    20382051      }
    20392052      Map::erase(key);
    … …  
    20472060      for (int i = 0; i < int(keys.size()); ++i) {
    20482061        Value val = Map::operator[](keys[i]);
    2049         typename Container::iterator it = _inv_map.find(val);
    2050         if (it != _inv_map.end() && it->second == keys[i]) {
    2051           _inv_map.erase(it);
     2062        typename Container::iterator it;
     2063        for (it = _inv_map.equal_range(val).first;
     2064             it != _inv_map.equal_range(val).second; ++it) {
     2065          if (it->second == keys[i]) {
     2066            _inv_map.erase(it);
     2067            break;
     2068          }
    20522069        }
    20532070      }
    … …  
    20852102      /// \brief Subscript operator.
    20862103      ///
    2087       /// Subscript operator. It gives back the item
    2088       /// that was last assigned to the given value.
     2104      /// Subscript operator. It gives back an item
     2105      /// that is assigned to the given value or \c INVALID
     2106      /// if no such item exists.
    20892107      Value operator[](const Key& key) const {
    20902108        return _inverted(key);
    … …  
    22552273
    22562274    /// \brief Gives back the item belonging to a \e RangeId
    2257     /// 
     2275    ///
    22582276    /// Gives back the item belonging to a \e RangeId.
    22592277    Item operator()(int id) const {
    … …  
    23122330  };
    23132331
     2332  /// \brief Dynamic iterable \c bool map.
     2333  ///
     2334  /// This class provides a special graph map type which can store a
     2335  /// \c bool value for graph items (\c Node, \c Arc or \c Edge).
     2336  /// For both \c true and \c false values it is possible to iterate on
     2337  /// the keys.
     2338  ///
     2339  /// This type is a reference map, so it can be modified with the
     2340  /// subscript operator.
     2341  ///
     2342  /// \tparam GR The graph type.
     2343  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
     2344  /// \c GR::Edge).
     2345  ///
     2346  /// \see IterableIntMap, IterableValueMap
     2347  /// \see CrossRefMap
     2348  template <typename GR, typename K>
     2349  class IterableBoolMap
     2350    : protected ItemSetTraits<GR, K>::template Map<int>::Type {
     2351  private:
     2352    typedef GR Graph;
     2353
     2354    typedef typename ItemSetTraits<GR, K>::ItemIt KeyIt;
     2355    typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Parent;
     2356
     2357    std::vector<K> _array;
     2358    int _sep;
     2359
     2360  public:
     2361
     2362    /// Indicates that the map is reference map.
     2363    typedef True ReferenceMapTag;
     2364
     2365    /// The key type
     2366    typedef K Key;
     2367    /// The value type
     2368    typedef bool Value;
     2369    /// The const reference type.
     2370    typedef const Value& ConstReference;
     2371
     2372  private:
     2373
     2374    int position(const Key& key) const {
     2375      return Parent::operator[](key);
     2376    }
     2377
     2378  public:
     2379
     2380    /// \brief Reference to the value of the map.
     2381    ///
     2382    /// This class is similar to the \c bool type. It can be converted to
     2383    /// \c bool and it provides the same operators.
     2384    class Reference {
     2385      friend class IterableBoolMap;
     2386    private:
     2387      Reference(IterableBoolMap& map, const Key& key)
     2388        : _key(key), _map(map) {}
     2389    public:
     2390
     2391      Reference& operator=(const Reference& value) {
     2392        _map.set(_key, static_cast<bool>(value));
     2393         return *this;
     2394      }
     2395
     2396      operator bool() const {
     2397        return static_cast<const IterableBoolMap&>(_map)[_key];
     2398      }
     2399
     2400      Reference& operator=(bool value) {
     2401        _map.set(_key, value);
     2402        return *this;
     2403      }
     2404      Reference& operator&=(bool value) {
     2405        _map.set(_key, _map[_key] & value);
     2406        return *this;
     2407      }
     2408      Reference& operator|=(bool value) {
     2409        _map.set(_key, _map[_key] | value);
     2410        return *this;
     2411      }
     2412      Reference& operator^=(bool value) {
     2413        _map.set(_key, _map[_key] ^ value);
     2414        return *this;
     2415      }
     2416    private:
     2417      Key _key;
     2418      IterableBoolMap& _map;
     2419    };
     2420
     2421    /// \brief Constructor of the map with a default value.
     2422    ///
     2423    /// Constructor of the map with a default value.
     2424    explicit IterableBoolMap(const Graph& graph, bool def = false)
     2425      : Parent(graph) {
     2426      typename Parent::Notifier* nf = Parent::notifier();
     2427      Key it;
     2428      for (nf->first(it); it != INVALID; nf->next(it)) {
     2429        Parent::set(it, _array.size());
     2430        _array.push_back(it);
     2431      }
     2432      _sep = (def ? _array.size() : 0);
     2433    }
     2434
     2435    /// \brief Const subscript operator of the map.
     2436    ///
     2437    /// Const subscript operator of the map.
     2438    bool operator[](const Key& key) const {
     2439      return position(key) < _sep;
     2440    }
     2441
     2442    /// \brief Subscript operator of the map.
     2443    ///
     2444    /// Subscript operator of the map.
     2445    Reference operator[](const Key& key) {
     2446      return Reference(*this, key);
     2447    }
     2448
     2449    /// \brief Set operation of the map.
     2450    ///
     2451    /// Set operation of the map.
     2452    void set(const Key& key, bool value) {
     2453      int pos = position(key);
     2454      if (value) {
     2455        if (pos < _sep) return;
     2456        Key tmp = _array[_sep];
     2457        _array[_sep] = key;
     2458        Parent::set(key, _sep);
     2459        _array[pos] = tmp;
     2460        Parent::set(tmp, pos);
     2461        ++_sep;
     2462      } else {
     2463        if (pos >= _sep) return;
     2464        --_sep;
     2465        Key tmp = _array[_sep];
     2466        _array[_sep] = key;
     2467        Parent::set(key, _sep);
     2468        _array[pos] = tmp;
     2469        Parent::set(tmp, pos);
     2470      }
     2471    }
     2472
     2473    /// \brief Set all items.
     2474    ///
     2475    /// Set all items in the map.
     2476    /// \note Constant time operation.
     2477    void setAll(bool value) {
     2478      _sep = (value ? _array.size() : 0);
     2479    }
     2480
     2481    /// \brief Returns the number of the keys mapped to \c true.
     2482    ///
     2483    /// Returns the number of the keys mapped to \c true.
     2484    int trueNum() const {
     2485      return _sep;
     2486    }
     2487
     2488    /// \brief Returns the number of the keys mapped to \c false.
     2489    ///
     2490    /// Returns the number of the keys mapped to \c false.
     2491    int falseNum() const {
     2492      return _array.size() - _sep;
     2493    }
     2494
     2495    /// \brief Iterator for the keys mapped to \c true.
     2496    ///
     2497    /// Iterator for the keys mapped to \c true. It works
     2498    /// like a graph item iterator, it can be converted to
     2499    /// the key type of the map, incremented with \c ++ operator, and
     2500    /// if the iterator leaves the last valid key, it will be equal to
     2501    /// \c INVALID.
     2502    class TrueIt : public Key {
     2503    public:
     2504      typedef Key Parent;
     2505
     2506      /// \brief Creates an iterator.
     2507      ///
     2508      /// Creates an iterator. It iterates on the
     2509      /// keys mapped to \c true.
     2510      /// \param map The IterableBoolMap.
     2511      explicit TrueIt(const IterableBoolMap& map)
     2512        : Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID),
     2513          _map(&map) {}
     2514
     2515      /// \brief Invalid constructor \& conversion.
     2516      ///
     2517      /// This constructor initializes the iterator to be invalid.
     2518      /// \sa Invalid for more details.
     2519      TrueIt(Invalid) : Parent(INVALID), _map(0) {}
     2520
     2521      /// \brief Increment operator.
     2522      ///
     2523      /// Increment operator.
     2524      TrueIt& operator++() {
     2525        int pos = _map->position(*this);
     2526        Parent::operator=(pos > 0 ? _map->_array[pos - 1] : INVALID);
     2527        return *this;
     2528      }
     2529
     2530    private:
     2531      const IterableBoolMap* _map;
     2532    };
     2533
     2534    /// \brief Iterator for the keys mapped to \c false.
     2535    ///
     2536    /// Iterator for the keys mapped to \c false. It works
     2537    /// like a graph item iterator, it can be converted to
     2538    /// the key type of the map, incremented with \c ++ operator, and
     2539    /// if the iterator leaves the last valid key, it will be equal to
     2540    /// \c INVALID.
     2541    class FalseIt : public Key {
     2542    public:
     2543      typedef Key Parent;
     2544
     2545      /// \brief Creates an iterator.
     2546      ///
     2547      /// Creates an iterator. It iterates on the
     2548      /// keys mapped to \c false.
     2549      /// \param map The IterableBoolMap.
     2550      explicit FalseIt(const IterableBoolMap& map)
     2551        : Parent(map._sep < int(map._array.size()) ?
     2552                 map._array.back() : INVALID), _map(&map) {}
     2553
     2554      /// \brief Invalid constructor \& conversion.
     2555      ///
     2556      /// This constructor initializes the iterator to be invalid.
     2557      /// \sa Invalid for more details.
     2558      FalseIt(Invalid) : Parent(INVALID), _map(0) {}
     2559
     2560      /// \brief Increment operator.
     2561      ///
     2562      /// Increment operator.
     2563      FalseIt& operator++() {
     2564        int pos = _map->position(*this);
     2565        Parent::operator=(pos > _map->_sep ? _map->_array[pos - 1] : INVALID);
     2566        return *this;
     2567      }
     2568
     2569    private:
     2570      const IterableBoolMap* _map;
     2571    };
     2572
     2573    /// \brief Iterator for the keys mapped to a given value.
     2574    ///
     2575    /// Iterator for the keys mapped to a given value. It works
     2576    /// like a graph item iterator, it can be converted to
     2577    /// the key type of the map, incremented with \c ++ operator, and
     2578    /// if the iterator leaves the last valid key, it will be equal to
     2579    /// \c INVALID.
     2580    class ItemIt : public Key {
     2581    public:
     2582      typedef Key Parent;
     2583
     2584      /// \brief Creates an iterator with a value.
     2585      ///
     2586      /// Creates an iterator with a value. It iterates on the
     2587      /// keys mapped to the given value.
     2588      /// \param map The IterableBoolMap.
     2589      /// \param value The value.
     2590      ItemIt(const IterableBoolMap& map, bool value)
     2591        : Parent(value ?
     2592                 (map._sep > 0 ?
     2593                  map._array[map._sep - 1] : INVALID) :
     2594                 (map._sep < int(map._array.size()) ?
     2595                  map._array.back() : INVALID)), _map(&map) {}
     2596
     2597      /// \brief Invalid constructor \& conversion.
     2598      ///
     2599      /// This constructor initializes the iterator to be invalid.
     2600      /// \sa Invalid for more details.
     2601      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
     2602
     2603      /// \brief Increment operator.
     2604      ///
     2605      /// Increment operator.
     2606      ItemIt& operator++() {
     2607        int pos = _map->position(*this);
     2608        int _sep = pos >= _map->_sep ? _map->_sep : 0;
     2609        Parent::operator=(pos > _sep ? _map->_array[pos - 1] : INVALID);
     2610        return *this;
     2611      }
     2612
     2613    private:
     2614      const IterableBoolMap* _map;
     2615    };
     2616
     2617  protected:
     2618
     2619    virtual void add(const Key& key) {
     2620      Parent::add(key);
     2621      Parent::set(key, _array.size());
     2622      _array.push_back(key);
     2623    }
     2624
     2625    virtual void add(const std::vector<Key>& keys) {
     2626      Parent::add(keys);
     2627      for (int i = 0; i < int(keys.size()); ++i) {
     2628        Parent::set(keys[i], _array.size());
     2629        _array.push_back(keys[i]);
     2630      }
     2631    }
     2632
     2633    virtual void erase(const Key& key) {
     2634      int pos = position(key);
     2635      if (pos < _sep) {
     2636        --_sep;
     2637        Parent::set(_array[_sep], pos);
     2638        _array[pos] = _array[_sep];
     2639        Parent::set(_array.back(), _sep);
     2640        _array[_sep] = _array.back();
     2641        _array.pop_back();
     2642      } else {
     2643        Parent::set(_array.back(), pos);
     2644        _array[pos] = _array.back();
     2645        _array.pop_back();
     2646      }
     2647      Parent::erase(key);
     2648    }
     2649
     2650    virtual void erase(const std::vector<Key>& keys) {
     2651      for (int i = 0; i < int(keys.size()); ++i) {
     2652        int pos = position(keys[i]);
     2653        if (pos < _sep) {
     2654          --_sep;
     2655          Parent::set(_array[_sep], pos);
     2656          _array[pos] = _array[_sep];
     2657          Parent::set(_array.back(), _sep);
     2658          _array[_sep] = _array.back();
     2659          _array.pop_back();
     2660        } else {
     2661          Parent::set(_array.back(), pos);
     2662          _array[pos] = _array.back();
     2663          _array.pop_back();
     2664        }
     2665      }
     2666      Parent::erase(keys);
     2667    }
     2668
     2669    virtual void build() {
     2670      Parent::build();
     2671      typename Parent::Notifier* nf = Parent::notifier();
     2672      Key it;
     2673      for (nf->first(it); it != INVALID; nf->next(it)) {
     2674        Parent::set(it, _array.size());
     2675        _array.push_back(it);
     2676      }
     2677      _sep = 0;
     2678    }
     2679
     2680    virtual void clear() {
     2681      _array.clear();
     2682      _sep = 0;
     2683      Parent::clear();
     2684    }
     2685
     2686  };
     2687
     2688
     2689  namespace _maps_bits {
     2690    template <typename Item>
     2691    struct IterableIntMapNode {
     2692      IterableIntMapNode() : value(-1) {}
     2693      IterableIntMapNode(int _value) : value(_value) {}
     2694      Item prev, next;
     2695      int value;
     2696    };
     2697  }
     2698
     2699  /// \brief Dynamic iterable integer map.
     2700  ///
     2701  /// This class provides a special graph map type which can store an
     2702  /// integer value for graph items (\c Node, \c Arc or \c Edge).
     2703  /// For each non-negative value it is possible to iterate on the keys
     2704  /// mapped to the value.
     2705  ///
     2706  /// This type is a reference map, so it can be modified with the
     2707  /// subscript operator.
     2708  ///
     2709  /// \note The size of the data structure depends on the largest
     2710  /// value in the map.
     2711  ///
     2712  /// \tparam GR The graph type.
     2713  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
     2714  /// \c GR::Edge).
     2715  ///
     2716  /// \see IterableBoolMap, IterableValueMap
     2717  /// \see CrossRefMap
     2718  template <typename GR, typename K>
     2719  class IterableIntMap
     2720    : protected ItemSetTraits<GR, K>::
     2721        template Map<_maps_bits::IterableIntMapNode<K> >::Type {
     2722  public:
     2723    typedef typename ItemSetTraits<GR, K>::
     2724      template Map<_maps_bits::IterableIntMapNode<K> >::Type Parent;
     2725
     2726    /// The key type
     2727    typedef K Key;
     2728    /// The value type
     2729    typedef int Value;
     2730    /// The graph type
     2731    typedef GR Graph;
     2732
     2733    /// \brief Constructor of the map.
     2734    ///
     2735    /// Constructor of the map. It sets all values to -1.
     2736    explicit IterableIntMap(const Graph& graph)
     2737      : Parent(graph) {}
     2738
     2739    /// \brief Constructor of the map with a given value.
     2740    ///
     2741    /// Constructor of the map with a given value.
     2742    explicit IterableIntMap(const Graph& graph, int value)
     2743      : Parent(graph, _maps_bits::IterableIntMapNode<K>(value)) {
     2744      if (value >= 0) {
     2745        for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
     2746          lace(it);
     2747        }
     2748      }
     2749    }
     2750
     2751  private:
     2752
     2753    void unlace(const Key& key) {
     2754      typename Parent::Value& node = Parent::operator[](key);
     2755      if (node.value < 0) return;
     2756      if (node.prev != INVALID) {
     2757        Parent::operator[](node.prev).next = node.next;
     2758      } else {
     2759        _first[node.value] = node.next;
     2760      }
     2761      if (node.next != INVALID) {
     2762        Parent::operator[](node.next).prev = node.prev;
     2763      }
     2764      while (!_first.empty() && _first.back() == INVALID) {
     2765        _first.pop_back();
     2766      }
     2767    }
     2768
     2769    void lace(const Key& key) {
     2770      typename Parent::Value& node = Parent::operator[](key);
     2771      if (node.value < 0) return;
     2772      if (node.value >= int(_first.size())) {
     2773        _first.resize(node.value + 1, INVALID);
     2774      }
     2775      node.prev = INVALID;
     2776      node.next = _first[node.value];
     2777      if (node.next != INVALID) {
     2778        Parent::operator[](node.next).prev = key;
     2779      }
     2780      _first[node.value] = key;
     2781    }
     2782
     2783  public:
     2784
     2785    /// Indicates that the map is reference map.
     2786    typedef True ReferenceMapTag;
     2787
     2788    /// \brief Reference to the value of the map.
     2789    ///
     2790    /// This class is similar to the \c int type. It can
     2791    /// be converted to \c int and it has the same operators.
     2792    class Reference {
     2793      friend class IterableIntMap;
     2794    private:
     2795      Reference(IterableIntMap& map, const Key& key)
     2796        : _key(key), _map(map) {}
     2797    public:
     2798
     2799      Reference& operator=(const Reference& value) {
     2800        _map.set(_key, static_cast<const int&>(value));
     2801         return *this;
     2802      }
     2803
     2804      operator const int&() const {
     2805        return static_cast<const IterableIntMap&>(_map)[_key];
     2806      }
     2807
     2808      Reference& operator=(int value) {
     2809        _map.set(_key, value);
     2810        return *this;
     2811      }
     2812      Reference& operator++() {
     2813        _map.set(_key, _map[_key] + 1);
     2814        return *this;
     2815      }
     2816      int operator++(int) {
     2817        int value = _map[_key];
     2818        _map.set(_key, value + 1);
     2819        return value;
     2820      }
     2821      Reference& operator--() {
     2822        _map.set(_key, _map[_key] - 1);
     2823        return *this;
     2824      }
     2825      int operator--(int) {
     2826        int value = _map[_key];
     2827        _map.set(_key, value - 1);
     2828        return value;
     2829      }
     2830      Reference& operator+=(int value) {
     2831        _map.set(_key, _map[_key] + value);
     2832        return *this;
     2833      }
     2834      Reference& operator-=(int value) {
     2835        _map.set(_key, _map[_key] - value);
     2836        return *this;
     2837      }
     2838      Reference& operator*=(int value) {
     2839        _map.set(_key, _map[_key] * value);
     2840        return *this;
     2841      }
     2842      Reference& operator/=(int value) {
     2843        _map.set(_key, _map[_key] / value);
     2844        return *this;
     2845      }
     2846      Reference& operator%=(int value) {
     2847        _map.set(_key, _map[_key] % value);
     2848        return *this;
     2849      }
     2850      Reference& operator&=(int value) {
     2851        _map.set(_key, _map[_key] & value);
     2852        return *this;
     2853      }
     2854      Reference& operator|=(int value) {
     2855        _map.set(_key, _map[_key] | value);
     2856        return *this;
     2857      }
     2858      Reference& operator^=(int value) {
     2859        _map.set(_key, _map[_key] ^ value);
     2860        return *this;
     2861      }
     2862      Reference& operator<<=(int value) {
     2863        _map.set(_key, _map[_key] << value);
     2864        return *this;
     2865      }
     2866      Reference& operator>>=(int value) {
     2867        _map.set(_key, _map[_key] >> value);
     2868        return *this;
     2869      }
     2870
     2871    private:
     2872      Key _key;
     2873      IterableIntMap& _map;
     2874    };
     2875
     2876    /// The const reference type.
     2877    typedef const Value& ConstReference;
     2878
     2879    /// \brief Gives back the maximal value plus one.
     2880    ///
     2881    /// Gives back the maximal value plus one.
     2882    int size() const {
     2883      return _first.size();
     2884    }
     2885
     2886    /// \brief Set operation of the map.
     2887    ///
     2888    /// Set operation of the map.
     2889    void set(const Key& key, const Value& value) {
     2890      unlace(key);
     2891      Parent::operator[](key).value = value;
     2892      lace(key);
     2893    }
     2894
     2895    /// \brief Const subscript operator of the map.
     2896    ///
     2897    /// Const subscript operator of the map.
     2898    const Value& operator[](const Key& key) const {
     2899      return Parent::operator[](key).value;
     2900    }
     2901
     2902    /// \brief Subscript operator of the map.
     2903    ///
     2904    /// Subscript operator of the map.
     2905    Reference operator[](const Key& key) {
     2906      return Reference(*this, key);
     2907    }
     2908
     2909    /// \brief Iterator for the keys with the same value.
     2910    ///
     2911    /// Iterator for the keys with the same value. It works
     2912    /// like a graph item iterator, it can be converted to
     2913    /// the item type of the map, incremented with \c ++ operator, and
     2914    /// if the iterator leaves the last valid item, it will be equal to
     2915    /// \c INVALID.
     2916    class ItemIt : public Key {
     2917    public:
     2918      typedef Key Parent;
     2919
     2920      /// \brief Invalid constructor \& conversion.
     2921      ///
     2922      /// This constructor initializes the iterator to be invalid.
     2923      /// \sa Invalid for more details.
     2924      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
     2925
     2926      /// \brief Creates an iterator with a value.
     2927      ///
     2928      /// Creates an iterator with a value. It iterates on the
     2929      /// keys mapped to the given value.
     2930      /// \param map The IterableIntMap.
     2931      /// \param value The value.
     2932      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
     2933        if (value < 0 || value >= int(_map->_first.size())) {
     2934          Parent::operator=(INVALID);
     2935        } else {
     2936          Parent::operator=(_map->_first[value]);
     2937        }
     2938      }
     2939
     2940      /// \brief Increment operator.
     2941      ///
     2942      /// Increment operator.
     2943      ItemIt& operator++() {
     2944        Parent::operator=(_map->IterableIntMap::Parent::
     2945                          operator[](static_cast<Parent&>(*this)).next);
     2946        return *this;
     2947      }
     2948
     2949    private:
     2950      const IterableIntMap* _map;
     2951    };
     2952
     2953  protected:
     2954
     2955    virtual void erase(const Key& key) {
     2956      unlace(key);
     2957      Parent::erase(key);
     2958    }
     2959
     2960    virtual void erase(const std::vector<Key>& keys) {
     2961      for (int i = 0; i < int(keys.size()); ++i) {
     2962        unlace(keys[i]);
     2963      }
     2964      Parent::erase(keys);
     2965    }
     2966
     2967    virtual void clear() {
     2968      _first.clear();
     2969      Parent::clear();
     2970    }
     2971
     2972  private:
     2973    std::vector<Key> _first;
     2974  };
     2975
     2976  namespace _maps_bits {
     2977    template <typename Item, typename Value>
     2978    struct IterableValueMapNode {
     2979      IterableValueMapNode(Value _value = Value()) : value(_value) {}
     2980      Item prev, next;
     2981      Value value;
     2982    };
     2983  }
     2984
     2985  /// \brief Dynamic iterable map for comparable values.
     2986  ///
     2987  /// This class provides a special graph map type which can store an
     2988  /// comparable value for graph items (\c Node, \c Arc or \c Edge).
     2989  /// For each value it is possible to iterate on the keys mapped to
     2990  /// the value.
     2991  ///
     2992  /// The map stores for each value a linked list with
     2993  /// the items which mapped to the value, and the values are stored
     2994  /// in balanced binary tree. The values of the map can be accessed
     2995  /// with stl compatible forward iterator.
     2996  ///
     2997  /// This type is not reference map, so it cannot be modified with
     2998  /// the subscript operator.
     2999  ///
     3000  /// \tparam GR The graph type.
     3001  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
     3002  /// \c GR::Edge).
     3003  /// \tparam V The value type of the map. It can be any comparable
     3004  /// value type.
     3005  ///
     3006  /// \see IterableBoolMap, IterableIntMap
     3007  /// \see CrossRefMap
     3008  template <typename GR, typename K, typename V>
     3009  class IterableValueMap
     3010    : protected ItemSetTraits<GR, K>::
     3011        template Map<_maps_bits::IterableValueMapNode<K, V> >::Type {
     3012  public:
     3013    typedef typename ItemSetTraits<GR, K>::
     3014      template Map<_maps_bits::IterableValueMapNode<K, V> >::Type Parent;
     3015
     3016    /// The key type
     3017    typedef K Key;
     3018    /// The value type
     3019    typedef V Value;
     3020    /// The graph type
     3021    typedef GR Graph;
     3022
     3023  public:
     3024
     3025    /// \brief Constructor of the map with a given value.
     3026    ///
     3027    /// Constructor of the map with a given value.
     3028    explicit IterableValueMap(const Graph& graph,
     3029                              const Value& value = Value())
     3030      : Parent(graph, _maps_bits::IterableValueMapNode<K, V>(value)) {
     3031      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
     3032        lace(it);
     3033      }
     3034    }
     3035
     3036  protected:
     3037
     3038    void unlace(const Key& key) {
     3039      typename Parent::Value& node = Parent::operator[](key);
     3040      if (node.prev != INVALID) {
     3041        Parent::operator[](node.prev).next = node.next;
     3042      } else {
     3043        if (node.next != INVALID) {
     3044          _first[node.value] = node.next;
     3045        } else {
     3046          _first.erase(node.value);
     3047        }
     3048      }
     3049      if (node.next != INVALID) {
     3050        Parent::operator[](node.next).prev = node.prev;
     3051      }
     3052    }
     3053
     3054    void lace(const Key& key) {
     3055      typename Parent::Value& node = Parent::operator[](key);
     3056      typename std::map<Value, Key>::iterator it = _first.find(node.value);
     3057      if (it == _first.end()) {
     3058        node.prev = node.next = INVALID;
     3059        _first.insert(std::make_pair(node.value, key));
     3060      } else {
     3061        node.prev = INVALID;
     3062        node.next = it->second;
     3063        if (node.next != INVALID) {
     3064          Parent::operator[](node.next).prev = key;
     3065        }
     3066        it->second = key;
     3067      }
     3068    }
     3069
     3070  public:
     3071
     3072    /// \brief Forward iterator for values.
     3073    ///
     3074    /// This iterator is an stl compatible forward
     3075    /// iterator on the values of the map. The values can
     3076    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
     3077    class ValueIterator
     3078      : public std::iterator<std::forward_iterator_tag, Value> {
     3079      friend class IterableValueMap;
     3080    private:
     3081      ValueIterator(typename std::map<Value, Key>::const_iterator _it)
     3082        : it(_it) {}
     3083    public:
     3084
     3085      ValueIterator() {}
     3086
     3087      ValueIterator& operator++() { ++it; return *this; }
     3088      ValueIterator operator++(int) {
     3089        ValueIterator tmp(*this);
     3090        operator++();
     3091        return tmp;
     3092      }
     3093
     3094      const Value& operator*() const { return it->first; }
     3095      const Value* operator->() const { return &(it->first); }
     3096
     3097      bool operator==(ValueIterator jt) const { return it == jt.it; }
     3098      bool operator!=(ValueIterator jt) const { return it != jt.it; }
     3099
     3100    private:
     3101      typename std::map<Value, Key>::const_iterator it;
     3102    };
     3103
     3104    /// \brief Returns an iterator to the first value.
     3105    ///
     3106    /// Returns an stl compatible iterator to the
     3107    /// first value of the map. The values of the
     3108    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
     3109    /// range.
     3110    ValueIterator beginValue() const {
     3111      return ValueIterator(_first.begin());
     3112    }
     3113
     3114    /// \brief Returns an iterator after the last value.
     3115    ///
     3116    /// Returns an stl compatible iterator after the
     3117    /// last value of the map. The values of the
     3118    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
     3119    /// range.
     3120    ValueIterator endValue() const {
     3121      return ValueIterator(_first.end());
     3122    }
     3123
     3124    /// \brief Set operation of the map.
     3125    ///
     3126    /// Set operation of the map.
     3127    void set(const Key& key, const Value& value) {
     3128      unlace(key);
     3129      Parent::operator[](key).value = value;
     3130      lace(key);
     3131    }
     3132
     3133    /// \brief Const subscript operator of the map.
     3134    ///
     3135    /// Const subscript operator of the map.
     3136    const Value& operator[](const Key& key) const {
     3137      return Parent::operator[](key).value;
     3138    }
     3139
     3140    /// \brief Iterator for the keys with the same value.
     3141    ///
     3142    /// Iterator for the keys with the same value. It works
     3143    /// like a graph item iterator, it can be converted to
     3144    /// the item type of the map, incremented with \c ++ operator, and
     3145    /// if the iterator leaves the last valid item, it will be equal to
     3146    /// \c INVALID.
     3147    class ItemIt : public Key {
     3148    public:
     3149      typedef Key Parent;
     3150
     3151      /// \brief Invalid constructor \& conversion.
     3152      ///
     3153      /// This constructor initializes the iterator to be invalid.
     3154      /// \sa Invalid for more details.
     3155      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
     3156
     3157      /// \brief Creates an iterator with a value.
     3158      ///
     3159      /// Creates an iterator with a value. It iterates on the
     3160      /// keys which have the given value.
     3161      /// \param map The IterableValueMap
     3162      /// \param value The value
     3163      ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
     3164        typename std::map<Value, Key>::const_iterator it =
     3165          map._first.find(value);
     3166        if (it == map._first.end()) {
     3167          Parent::operator=(INVALID);
     3168        } else {
     3169          Parent::operator=(it->second);
     3170        }
     3171      }
     3172
     3173      /// \brief Increment operator.
     3174      ///
     3175      /// Increment Operator.
     3176      ItemIt& operator++() {
     3177        Parent::operator=(_map->IterableValueMap::Parent::
     3178                          operator[](static_cast<Parent&>(*this)).next);
     3179        return *this;
     3180      }
     3181
     3182
     3183    private:
     3184      const IterableValueMap* _map;
     3185    };
     3186
     3187  protected:
     3188
     3189    virtual void add(const Key& key) {
     3190      Parent::add(key);
     3191      unlace(key);
     3192    }
     3193
     3194    virtual void add(const std::vector<Key>& keys) {
     3195      Parent::add(keys);
     3196      for (int i = 0; i < int(keys.size()); ++i) {
     3197        lace(keys[i]);
     3198      }
     3199    }
     3200
     3201    virtual void erase(const Key& key) {
     3202      unlace(key);
     3203      Parent::erase(key);
     3204    }
     3205
     3206    virtual void erase(const std::vector<Key>& keys) {
     3207      for (int i = 0; i < int(keys.size()); ++i) {
     3208        unlace(keys[i]);
     3209      }
     3210      Parent::erase(keys);
     3211    }
     3212
     3213    virtual void build() {
     3214      Parent::build();
     3215      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
     3216        lace(it);
     3217      }
     3218    }
     3219
     3220    virtual void clear() {
     3221      _first.clear();
     3222      Parent::clear();
     3223    }
     3224
     3225  private:
     3226    std::map<Value, Key> _first;
     3227  };
     3228
    23143229  /// \brief Map of the source nodes of arcs in a digraph.
    23153230  ///
    … …  
    24813396  /// whenever the digraph changes.
    24823397  ///
    2483   /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
     3398  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
    24843399  /// may provide alternative ways to modify the digraph.
    24853400  /// The correct behavior of InDegMap is not guarantied if these additional
    … …  
    24973412
    24983413  public:
    2499    
     3414
    25003415    /// The graph type of InDegMap
    25013416    typedef GR Graph;
    … …  
    26113526  /// whenever the digraph changes.
    26123527  ///
    2613   /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
     3528  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
    26143529  /// may provide alternative ways to modify the digraph.
    26153530  /// The correct behavior of OutDegMap is not guarantied if these additional

  • lemon/preflow.h

    r641 r689  
    9898  /// "flow of maximum value" in a digraph.
    9999  /// The preflow algorithms are the fastest known maximum
    100   /// flow algorithms. The current implementation use a mixture of the
     100  /// flow algorithms. The current implementation uses a mixture of the
    101101  /// \e "highest label" and the \e "bound decrease" heuristics.
    102102  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
    … …  
    372372    }
    373373
    374     /// \brief Sets the tolerance used by algorithm.
    375     ///
    376     /// Sets the tolerance used by algorithm.
    377     Preflow& tolerance(const Tolerance& tolerance) const {
     374    /// \brief Sets the tolerance used by the algorithm.
     375    ///
     376    /// Sets the tolerance object used by the algorithm.
     377    /// \return <tt>(*this)</tt>
     378    Preflow& tolerance(const Tolerance& tolerance) {
    378379      _tolerance = tolerance;
    379380      return *this;
    … …  
    382383    /// \brief Returns a const reference to the tolerance.
    383384    ///
    384     /// Returns a const reference to the tolerance.
     385    /// Returns a const reference to the tolerance object used by
     386    /// the algorithm.
    385387    const Tolerance& tolerance() const {
    386       return tolerance;
     388      return _tolerance;
    387389    }
    388390

  • test/CMakeLists.txt

    r679 r698  
    1010SET(TESTS
    1111  adaptors_test
     12  bellman_ford_test
    1213  bfs_test
    1314  circulation_test

  • test/Makefile.am

    r649 r698  
    88check_PROGRAMS += \
    99        test/adaptors_test \
     10        test/bellman_ford_test \
    1011        test/bfs_test \
    1112        test/circulation_test \
    … …  
    5354
    5455test_adaptors_test_SOURCES = test/adaptors_test.cc
     56test_bellman_ford_test_SOURCES = test/bellman_ford_test.cc
    5557test_bfs_test_SOURCES = test/bfs_test.cc
    5658test_circulation_test_SOURCES = test/circulation_test.cc

  • test/circulation_test.cc

    r611 r689  
    8888    .supplyMap(supply)
    8989    .flowMap(flow);
     90 
     91  const CirculationType::Elevator& elev = const_circ_test.elevator();
     92  circ_test.elevator(const_cast<CirculationType::Elevator&>(elev));
     93  CirculationType::Tolerance tol = const_circ_test.tolerance();
     94  circ_test.tolerance(tol);
    9095
    9196  circ_test.init();

  • test/maps_test.cc

    r477 r695  
    2323#include <lemon/concepts/maps.h>
    2424#include <lemon/maps.h>
     25#include <lemon/smart_graph.h>
    2526
    2627#include "test_tools.h"
    … …  
    350351  }
    351352
     353  // CrossRefMap
     354  {
     355    typedef SmartDigraph Graph;
     356    DIGRAPH_TYPEDEFS(Graph);
     357
     358    checkConcept<ReadWriteMap<Node, int>,
     359                 CrossRefMap<Graph, Node, int> >();
     360   
     361    Graph gr;
     362    typedef CrossRefMap<Graph, Node, char> CRMap;
     363    typedef CRMap::ValueIterator ValueIt;
     364    CRMap map(gr);
     365   
     366    Node n0 = gr.addNode();
     367    Node n1 = gr.addNode();
     368    Node n2 = gr.addNode();
     369   
     370    map.set(n0, 'A');
     371    map.set(n1, 'B');
     372    map.set(n2, 'C');
     373    map.set(n2, 'A');
     374    map.set(n0, 'C');
     375
     376    check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',
     377          "Wrong CrossRefMap");
     378    check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");
     379    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
     380    check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");
     381
     382    ValueIt it = map.beginValue();
     383    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
     384          it == map.endValue(), "Wrong value iterator");
     385  }
     386 
     387  // Iterable bool map
     388  {
     389    typedef SmartGraph Graph;
     390    typedef SmartGraph::Node Item;
     391
     392    typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm;
     393    checkConcept<ReferenceMap<Item, bool, bool&, const bool&>, Ibm>();
     394
     395    const int num = 10;
     396    Graph g;
     397    std::vector<Item> items;
     398    for (int i = 0; i < num; ++i) {
     399      items.push_back(g.addNode());
     400    }
     401
     402    Ibm map1(g, true);
     403    int n = 0;
     404    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
     405      check(map1[static_cast<Item>(it)], "Wrong TrueIt");
     406      ++n;
     407    }
     408    check(n == num, "Wrong number");
     409
     410    n = 0;
     411    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
     412        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
     413        ++n;
     414    }
     415    check(n == num, "Wrong number");
     416    check(Ibm::FalseIt(map1) == INVALID, "Wrong FalseIt");
     417    check(Ibm::ItemIt(map1, false) == INVALID, "Wrong ItemIt for false");
     418
     419    map1[items[5]] = true;
     420
     421    n = 0;
     422    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
     423        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
     424        ++n;
     425    }
     426    check(n == num, "Wrong number");
     427
     428    map1[items[num / 2]] = false;
     429    check(map1[items[num / 2]] == false, "Wrong map value");
     430
     431    n = 0;
     432    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
     433        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
     434        ++n;
     435    }
     436    check(n == num - 1, "Wrong number");
     437
     438    n = 0;
     439    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
     440        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
     441        ++n;
     442    }
     443    check(n == 1, "Wrong number");
     444
     445    map1[items[0]] = false;
     446    check(map1[items[0]] == false, "Wrong map value");
     447
     448    map1[items[num - 1]] = false;
     449    check(map1[items[num - 1]] == false, "Wrong map value");
     450
     451    n = 0;
     452    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
     453        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
     454        ++n;
     455    }
     456    check(n == num - 3, "Wrong number");
     457    check(map1.trueNum() == num - 3, "Wrong number");
     458
     459    n = 0;
     460    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
     461        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
     462        ++n;
     463    }
     464    check(n == 3, "Wrong number");
     465    check(map1.falseNum() == 3, "Wrong number");
     466  }
     467
     468  // Iterable int map
     469  {
     470    typedef SmartGraph Graph;
     471    typedef SmartGraph::Node Item;
     472    typedef IterableIntMap<SmartGraph, SmartGraph::Node> Iim;
     473
     474    checkConcept<ReferenceMap<Item, int, int&, const int&>, Iim>();
     475
     476    const int num = 10;
     477    Graph g;
     478    std::vector<Item> items;
     479    for (int i = 0; i < num; ++i) {
     480      items.push_back(g.addNode());
     481    }
     482
     483    Iim map1(g);
     484    check(map1.size() == 0, "Wrong size");
     485
     486    for (int i = 0; i < num; ++i) {
     487      map1[items[i]] = i;
     488    }
     489    check(map1.size() == num, "Wrong size");
     490
     491    for (int i = 0; i < num; ++i) {
     492      Iim::ItemIt it(map1, i);
     493      check(static_cast<Item>(it) == items[i], "Wrong value");
     494      ++it;
     495      check(static_cast<Item>(it) == INVALID, "Wrong value");
     496    }
     497
     498    for (int i = 0; i < num; ++i) {
     499      map1[items[i]] = i % 2;
     500    }
     501    check(map1.size() == 2, "Wrong size");
     502
     503    int n = 0;
     504    for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) {
     505      check(map1[static_cast<Item>(it)] == 0, "Wrong value");
     506      ++n;
     507    }
     508    check(n == (num + 1) / 2, "Wrong number");
     509
     510    for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) {
     511      check(map1[static_cast<Item>(it)] == 1, "Wrong value");
     512      ++n;
     513    }
     514    check(n == num, "Wrong number");
     515
     516  }
     517
     518  // Iterable value map
     519  {
     520    typedef SmartGraph Graph;
     521    typedef SmartGraph::Node Item;
     522    typedef IterableValueMap<SmartGraph, SmartGraph::Node, double> Ivm;
     523
     524    checkConcept<ReadWriteMap<Item, double>, Ivm>();
     525
     526    const int num = 10;
     527    Graph g;
     528    std::vector<Item> items;
     529    for (int i = 0; i < num; ++i) {
     530      items.push_back(g.addNode());
     531    }
     532
     533    Ivm map1(g, 0.0);
     534    check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size");
     535    check(*map1.beginValue() == 0.0, "Wrong value");
     536
     537    for (int i = 0; i < num; ++i) {
     538      map1.set(items[i], static_cast<double>(i));
     539    }
     540    check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size");
     541
     542    for (int i = 0; i < num; ++i) {
     543      Ivm::ItemIt it(map1, static_cast<double>(i));
     544      check(static_cast<Item>(it) == items[i], "Wrong value");
     545      ++it;
     546      check(static_cast<Item>(it) == INVALID, "Wrong value");
     547    }
     548
     549    for (Ivm::ValueIterator vit = map1.beginValue();
     550         vit != map1.endValue(); ++vit) {
     551      check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,
     552            "Wrong ValueIterator");
     553    }
     554
     555    for (int i = 0; i < num; ++i) {
     556      map1.set(items[i], static_cast<double>(i % 2));
     557    }
     558    check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size");
     559
     560    int n = 0;
     561    for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) {
     562      check(map1[static_cast<Item>(it)] == 0.0, "Wrong value");
     563      ++n;
     564    }
     565    check(n == (num + 1) / 2, "Wrong number");
     566
     567    for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) {
     568      check(map1[static_cast<Item>(it)] == 1.0, "Wrong value");
     569      ++n;
     570    }
     571    check(n == num, "Wrong number");
     572
     573  }
    352574  return 0;
    353575}

  • test/preflow_test.cc

    r585 r689  
    9595  PreflowType preflow_test(g, cap, n, n);
    9696  const PreflowType& const_preflow_test = preflow_test;
     97 
     98  const PreflowType::Elevator& elev = const_preflow_test.elevator();
     99  preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
     100  PreflowType::Tolerance tol = const_preflow_test.tolerance();
     101  preflow_test.tolerance(tol);
    97102
    98103  preflow_test

  • tools/lemon-0.x-to-1.x.sh

    r574 r691  
    3636        -e "s/Edge\>/_Ar_c_label_/g"\
    3737        -e "s/\<edge\>/_ar_c_label_/g"\
    38         -e "s/_edge\>/_ar_c_label_/g"\
     38        -e "s/_edge\>/__ar_c_label_/g"\
    3939        -e "s/Edges\>/_Ar_c_label_s/g"\
    4040        -e "s/\<edges\>/_ar_c_label_s/g"\
    41         -e "s/_edges\>/_ar_c_label_s/g"\
     41        -e "s/_edges\>/__ar_c_label_s/g"\
    4242        -e "s/\([Ee]\)dge\([a-z]\)/_\1d_ge_label_\2/g"\
    4343        -e "s/\([a-z]\)edge/\1_ed_ge_label_/g"\
    … …  
    6969        -e "s/_GR_APH_TY_PEDE_FS_label_/GRAPH_TYPEDEFS/g"\
    7070        -e "s/_DIGR_APH_TY_PEDE_FS_label_/DIGRAPH_TYPEDEFS/g"\
     71        -e "s/\<digraph_adaptor\.h\>/adaptors.h/g"\
     72        -e "s/\<digraph_utils\.h\>/core.h/g"\
     73        -e "s/\<digraph_reader\.h\>/lgf_reader.h/g"\
     74        -e "s/\<digraph_writer\.h\>/lgf_writer.h/g"\
     75        -e "s/\<topology\.h\>/connectivity.h/g"\
    7176        -e "s/DigraphToEps/GraphToEps/g"\
    7277        -e "s/digraphToEps/graphToEps/g"\
Note: See TracChangeset for help on using the changeset viewer.