COIN-OR::LEMON - Graph Library

Ignore:
Files:
9 edited

Legend:

Unmodified
Added
Removed
  • lemon/Makefile.am

    r728 r733  
    9393        lemon/lp_base.h \
    9494        lemon/lp_skeleton.h \
    95         lemon/list_graph.h \
    9695        lemon/maps.h \
    9796        lemon/matching.h \
  • lemon/bits/edge_set_extender.h

    r664 r732  
    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

    r664 r732  
    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

    r688 r736  
    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

    r664 r731  
    19031903
    19041904  /// 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   ///
     1905  /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
     1906  /// and if a key is set to a new value, then stores it in the inverse map.
    19091907  /// The values of the map can be accessed
    19101908  /// with stl compatible forward iterator.
     1909  ///
     1910  /// This type is not reference map, so it cannot be modified with
     1911  /// the subscript operator.
    19111912  ///
    19121913  /// \tparam GR The graph type.
     
    19241925      template Map<V>::Type Map;
    19251926
    1926     typedef std::map<V, K> Container;
     1927    typedef std::multimap<V, K> Container;
    19271928    Container _inv_map;
    19281929
     
    19491950    /// iterator on the values of the map. The values can
    19501951    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
     1952    /// They are considered with multiplicity, so each value is
     1953    /// traversed for each item it is assigned to.
    19511954    class ValueIterator
    19521955      : public std::iterator<std::forward_iterator_tag, Value> {
     
    20012004    void set(const Key& key, const Value& val) {
    20022005      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      typename Container::iterator it;
     2007      for (it = _inv_map.equal_range(oldval).first;
     2008           it != _inv_map.equal_range(oldval).second; ++it) {
     2009        if (it->second == key) {
     2010          _inv_map.erase(it);
     2011          break;
     2012        }
    20062013      }
    2007       _inv_map.insert(make_pair(val, key));
     2014      _inv_map.insert(std::make_pair(val, key));
    20082015      Map::set(key, val);
    20092016    }
     
    20172024    }
    20182025
    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);
     2026    /// \brief Gives back an item by its value.
     2027    ///
     2028    /// This function gives back an item that is assigned to
     2029    /// the given value or \c INVALID if no such item exists.
     2030    /// If there are more items with the same associated value,
     2031    /// only one of them is returned.
     2032    Key operator()(const Value& val) const {
     2033      typename Container::const_iterator it = _inv_map.find(val);
    20242034      return it != _inv_map.end() ? it->second : INVALID;
    20252035    }
     
    20332043    virtual void erase(const Key& key) {
    20342044      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);
     2045      typename Container::iterator it;
     2046      for (it = _inv_map.equal_range(val).first;
     2047           it != _inv_map.equal_range(val).second; ++it) {
     2048        if (it->second == key) {
     2049          _inv_map.erase(it);
     2050          break;
     2051        }
    20382052      }
    20392053      Map::erase(key);
     
    20472061      for (int i = 0; i < int(keys.size()); ++i) {
    20482062        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);
     2063        typename Container::iterator it;
     2064        for (it = _inv_map.equal_range(val).first;
     2065             it != _inv_map.equal_range(val).second; ++it) {
     2066          if (it->second == keys[i]) {
     2067            _inv_map.erase(it);
     2068            break;
     2069          }
    20522070        }
    20532071      }
     
    20852103      /// \brief Subscript operator.
    20862104      ///
    2087       /// Subscript operator. It gives back the item
    2088       /// that was last assigned to the given value.
     2105      /// Subscript operator. It gives back an item
     2106      /// that is assigned to the given value or \c INVALID
     2107      /// if no such item exists.
    20892108      Value operator[](const Key& key) const {
    20902109        return _inverted(key);
  • lemon/preflow.h

    r688 r736  
    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/circulation_test.cc

    r658 r736  
    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

    r554 r731  
    2323#include <lemon/concepts/maps.h>
    2424#include <lemon/maps.h>
     25#include <lemon/list_graph.h>
    2526
    2627#include "test_tools.h"
     
    349350      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
    350351  }
     352 
     353  // CrossRefMap
     354  {
     355    typedef ListDigraph 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  }
    351386
    352387  return 0;
  • test/preflow_test.cc

    r632 r736  
    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
Note: See TracChangeset for help on using the changeset viewer.