COIN-OR::LEMON - Graph Library

Ignore:
Files:
1 added
13 edited

Legend:

Unmodified
Added
Removed
  • NEWS

    r712 r853  
     12009-10-03 Version 1.1.1 released
     2
     3        Bugfix release.
     4
     5        #295: Suppress MSVC warnings using pragmas
     6        ----: Various CMAKE related improvements
     7              * Remove duplications from doc/CMakeLists.txt
     8              * Rename documentation install folder from 'docs' to 'html'
     9              * Add tools/CMakeLists.txt to the tarball
     10              * Generate and install LEMONConfig.cmake
     11              * Change the label of the html project in Visual Studio
     12              * Fix the check for the 'long long' type
     13              * Put the version string into config.h
     14              * Minor CMake improvements
     15              * Set the version to 'hg-tip' if everything fails
     16        #311: Add missing 'explicit' keywords
     17        #302: Fix the implementation and doc of CrossRefMap
     18        #308: Remove duplicate list_graph.h entry from source list
     19        #307: Bug fix in Preflow and Circulation
     20
    1212009-05-13 Version 1.1 released
    222
  • doc/groups.dox

    r710 r844  
    227227
    228228/**
    229 @defgroup matrices Matrices
    230 @ingroup datas
    231 \brief Two dimensional data storages implemented in LEMON.
    232 
    233 This group contains two dimensional data storages implemented in LEMON.
    234 */
    235 
    236 /**
    237229@defgroup paths Path Structures
    238230@ingroup datas
     
    284276This group contains the algorithms for finding shortest paths in digraphs.
    285277
    286  - \ref Dijkstra algorithm for finding shortest paths from a source node
    287    when all arc lengths are non-negative.
    288  - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
    289    from a source node when arc lenghts can be either positive or negative,
    290    but the digraph should not contain directed cycles with negative total
    291    length.
    292  - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
    293    for solving the \e all-pairs \e shortest \e paths \e problem when arc
    294    lenghts can be either positive or negative, but the digraph should
    295    not contain directed cycles with negative total length.
     278 - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a
     279   source node when all arc lengths are non-negative.
    296280 - \ref Suurballe A successive shortest path algorithm for finding
    297281   arc-disjoint paths between two nodes having minimum total length.
     
    318302\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    319303
    320 LEMON contains several algorithms for solving maximum flow problems:
    321 - \ref EdmondsKarp Edmonds-Karp algorithm.
    322 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
    323 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
    324 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
    325 
    326 In most cases the \ref Preflow "Preflow" algorithm provides the
    327 fastest method for computing a maximum flow. All implementations
    328 also provide functions to query the minimum cut, which is the dual
    329 problem of maximum flow.
     304\ref Preflow implements the preflow push-relabel algorithm of Goldberg and
     305Tarjan for solving this problem. It also provides functions to query the
     306minimum cut, which is the dual problem of maximum flow.
     307
    330308
    331309\ref Circulation is a preflow push-relabel algorithm implemented directly
     
    345323solution see \ref min_cost_flow "Minimum Cost Flow Problem".
    346324
    347 LEMON contains several algorithms for this problem.
    348  - \ref NetworkSimplex Primal Network Simplex algorithm with various
    349    pivot strategies.
    350  - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
    351    cost scaling.
    352  - \ref CapacityScaling Successive Shortest %Path algorithm with optional
    353    capacity scaling.
    354  - \ref CancelAndTighten The Cancel and Tighten algorithm.
    355  - \ref CycleCanceling Cycle-Canceling algorithms.
    356 
    357 In general NetworkSimplex is the most efficient implementation,
    358 but in special cases other algorithms could be faster.
    359 For example, if the total supply and/or capacities are rather small,
    360 CapacityScaling is usually the fastest algorithm (without effective scaling).
     325\ref NetworkSimplex is an efficient implementation of the primal Network
     326Simplex algorithm for finding minimum cost flows. It also provides dual
     327solution (node potentials), if an optimal flow is found.
    361328*/
    362329
     
    382349- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
    383350  in directed graphs.
    384 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
    385   calculating minimum cut in undirected graphs.
    386351- \ref GomoryHu "Gomory-Hu tree computation" for calculating
    387352  all-pairs minimum cut in undirected graphs.
     
    404369
    405370/**
    406 @defgroup planar Planarity Embedding and Drawing
    407 @ingroup algs
    408 \brief Algorithms for planarity checking, embedding and drawing
    409 
    410 This group contains the algorithms for planarity checking,
    411 embedding and drawing.
    412 
    413 \image html planar.png
    414 \image latex planar.eps "Plane graph" width=\textwidth
    415 */
    416 
    417 /**
    418371@defgroup matching Matching Algorithms
    419372@ingroup algs
    420373\brief Algorithms for finding matchings in graphs and bipartite graphs.
    421374
    422 This group contains the algorithms for calculating
    423 matchings in graphs and bipartite graphs. The general matching problem is
    424 finding a subset of the edges for which each node has at most one incident
    425 edge.
     375This group contains the algorithms for calculating matchings in graphs.
     376The general matching problem is finding a subset of the edges for which
     377each node has at most one incident edge.
    426378
    427379There are several different algorithms for calculate matchings in
    428 graphs.  The matching problems in bipartite graphs are generally
    429 easier than in general graphs. The goal of the matching optimization
     380graphs. The goal of the matching optimization
    430381can be finding maximum cardinality, maximum weight or minimum cost
    431382matching. The search can be constrained to find perfect or
     
    433384
    434385The matching algorithms implemented in LEMON:
    435 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
    436   for calculating maximum cardinality matching in bipartite graphs.
    437 - \ref PrBipartiteMatching Push-relabel algorithm
    438   for calculating maximum cardinality matching in bipartite graphs.
    439 - \ref MaxWeightedBipartiteMatching
    440   Successive shortest path algorithm for calculating maximum weighted
    441   matching and maximum weighted bipartite matching in bipartite graphs.
    442 - \ref MinCostMaxBipartiteMatching
    443   Successive shortest path algorithm for calculating minimum cost maximum
    444   matching in bipartite graphs.
    445386- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    446387  maximum cardinality matching in general graphs.
     
    474415
    475416/**
    476 @defgroup approx Approximation Algorithms
    477 @ingroup algs
    478 \brief Approximation algorithms.
    479 
    480 This group contains the approximation and heuristic algorithms
    481 implemented in LEMON.
    482 */
    483 
    484 /**
    485417@defgroup gen_opt_group General Optimization Tools
    486418\brief This group contains some general optimization frameworks
     
    499431various LP solvers could be used in the same manner with this
    500432interface.
    501 */
    502 
    503 /**
    504 @defgroup lp_utils Tools for Lp and Mip Solvers
    505 @ingroup lp_group
    506 \brief Helper tools to the Lp and Mip solvers.
    507 
    508 This group adds some helper tools to general optimization framework
    509 implemented in LEMON.
    510 */
    511 
    512 /**
    513 @defgroup metah Metaheuristics
    514 @ingroup gen_opt_group
    515 \brief Metaheuristics for LEMON library.
    516 
    517 This group contains some metaheuristic optimization tools.
    518433*/
    519434
  • lemon/Makefile.am

    r714 r913  
    9191        lemon/lp_base.h \
    9292        lemon/lp_skeleton.h \
    93         lemon/list_graph.h \
    9493        lemon/maps.h \
    9594        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/bits/map_extender.h

    r664 r913  
    8383      typedef typename Map::Value Value;
    8484
    85       MapIt() {}
    86 
    87       MapIt(Invalid i) : Parent(i) { }
    88 
    89       explicit MapIt(Map& _map) : map(_map) {
    90         map.notifier()->first(*this);
     85      MapIt() : map(NULL) {}
     86
     87      MapIt(Invalid i) : Parent(i), map(NULL) {}
     88
     89      explicit MapIt(Map& _map) : map(&_map) {
     90        map->notifier()->first(*this);
    9191      }
    9292
    9393      MapIt(const Map& _map, const Item& item)
     94        : Parent(item), map(&_map) {}
     95
     96      MapIt& operator++() {
     97        map->notifier()->next(*this);
     98        return *this;
     99      }
     100
     101      typename MapTraits<Map>::ConstReturnValue operator*() const {
     102        return (*map)[*this];
     103      }
     104
     105      typename MapTraits<Map>::ReturnValue operator*() {
     106        return (*map)[*this];
     107      }
     108
     109      void set(const Value& value) {
     110        map->set(*this, value);
     111      }
     112
     113    protected:
     114      Map* map;
     115
     116    };
     117
     118    class ConstMapIt : public Item {
     119      typedef Item Parent;
     120
     121    public:
     122
     123      typedef typename Map::Value Value;
     124
     125      ConstMapIt() : map(NULL) {}
     126
     127      ConstMapIt(Invalid i) : Parent(i), map(NULL) {}
     128
     129      explicit ConstMapIt(Map& _map) : map(&_map) {
     130        map->notifier()->first(*this);
     131      }
     132
     133      ConstMapIt(const Map& _map, const Item& item)
    94134        : Parent(item), map(_map) {}
    95135
    96       MapIt& operator++() {
    97         map.notifier()->next(*this);
     136      ConstMapIt& operator++() {
     137        map->notifier()->next(*this);
    98138        return *this;
    99139      }
     
    103143      }
    104144
    105       typename MapTraits<Map>::ReturnValue operator*() {
    106         return map[*this];
    107       }
    108 
    109       void set(const Value& value) {
    110         map.set(*this, value);
    111       }
    112 
    113     protected:
    114       Map& map;
    115 
    116     };
    117 
    118     class ConstMapIt : public Item {
    119       typedef Item Parent;
    120 
    121     public:
    122 
    123       typedef typename Map::Value Value;
    124 
    125       ConstMapIt() {}
    126 
    127       ConstMapIt(Invalid i) : Parent(i) { }
    128 
    129       explicit ConstMapIt(Map& _map) : map(_map) {
    130         map.notifier()->first(*this);
    131       }
    132 
    133       ConstMapIt(const Map& _map, const Item& item)
    134         : Parent(item), map(_map) {}
    135 
    136       ConstMapIt& operator++() {
    137         map.notifier()->next(*this);
    138         return *this;
    139       }
    140 
    141       typename MapTraits<Map>::ConstReturnValue operator*() const {
    142         return map[*this];
    143       }
    144 
    145     protected:
    146       const Map& map;
     145    protected:
     146      const Map* map;
    147147    };
    148148
     
    151151
    152152    public:
    153 
    154       ItemIt() {}
    155 
    156       ItemIt(Invalid i) : Parent(i) { }
    157 
    158       explicit ItemIt(Map& _map) : map(_map) {
    159         map.notifier()->first(*this);
     153      ItemIt() : map(NULL) {}
     154
     155
     156      ItemIt(Invalid i) : Parent(i), map(NULL) {}
     157
     158      explicit ItemIt(Map& _map) : map(&_map) {
     159        map->notifier()->first(*this);
    160160      }
    161161
    162162      ItemIt(const Map& _map, const Item& item)
    163         : Parent(item), map(_map) {}
     163        : Parent(item), map(&_map) {}
    164164
    165165      ItemIt& operator++() {
    166         map.notifier()->next(*this);
    167         return *this;
    168       }
    169 
    170     protected:
    171       const Map& map;
     166        map->notifier()->next(*this);
     167        return *this;
     168      }
     169
     170    protected:
     171      const Map* map;
    172172
    173173    };
     
    228228      typedef typename Map::Value Value;
    229229
    230       MapIt() {}
    231 
    232       MapIt(Invalid i) : Parent(i) { }
    233 
    234       explicit MapIt(Map& _map) : map(_map) {
    235         map.graph.first(*this);
     230      MapIt() : map(NULL) {}
     231
     232      MapIt(Invalid i) : Parent(i), map(NULL) { }
     233
     234      explicit MapIt(Map& _map) : map(&_map) {
     235        map->graph.first(*this);
    236236      }
    237237
    238238      MapIt(const Map& _map, const Item& item)
    239         : Parent(item), map(_map) {}
     239        : Parent(item), map(&_map) {}
    240240
    241241      MapIt& operator++() {
    242         map.graph.next(*this);
     242        map->graph.next(*this);
    243243        return *this;
    244244      }
    245245
    246246      typename MapTraits<Map>::ConstReturnValue operator*() const {
    247         return map[*this];
     247        return (*map)[*this];
    248248      }
    249249
    250250      typename MapTraits<Map>::ReturnValue operator*() {
    251         return map[*this];
     251        return (*map)[*this];
    252252      }
    253253
    254254      void set(const Value& value) {
    255         map.set(*this, value);
    256       }
    257 
    258     protected:
    259       Map& map;
     255        map->set(*this, value);
     256      }
     257
     258    protected:
     259      Map* map;
    260260
    261261    };
     
    268268      typedef typename Map::Value Value;
    269269
    270       ConstMapIt() {}
    271 
    272       ConstMapIt(Invalid i) : Parent(i) { }
    273 
    274       explicit ConstMapIt(Map& _map) : map(_map) {
    275         map.graph.first(*this);
     270      ConstMapIt() : map(NULL) {}
     271
     272      ConstMapIt(Invalid i) : Parent(i), map(NULL) { }
     273
     274      explicit ConstMapIt(Map& _map) : map(&_map) {
     275        map->graph.first(*this);
    276276      }
    277277
    278278      ConstMapIt(const Map& _map, const Item& item)
    279         : Parent(item), map(_map) {}
     279        : Parent(item), map(&_map) {}
    280280
    281281      ConstMapIt& operator++() {
    282         map.graph.next(*this);
     282        map->graph.next(*this);
    283283        return *this;
    284284      }
    285285
    286286      typename MapTraits<Map>::ConstReturnValue operator*() const {
    287         return map[*this];
    288       }
    289 
    290     protected:
    291       const Map& map;
     287        return (*map)[*this];
     288      }
     289
     290    protected:
     291      const Map* map;
    292292    };
    293293
     
    296296
    297297    public:
    298 
    299       ItemIt() {}
    300 
    301       ItemIt(Invalid i) : Parent(i) { }
    302 
    303       explicit ItemIt(Map& _map) : map(_map) {
    304         map.graph.first(*this);
     298      ItemIt() : map(NULL) {}
     299
     300
     301      ItemIt(Invalid i) : Parent(i), map(NULL) { }
     302
     303      explicit ItemIt(Map& _map) : map(&_map) {
     304        map->graph.first(*this);
    305305      }
    306306
    307307      ItemIt(const Map& _map, const Item& item)
    308         : Parent(item), map(_map) {}
     308        : Parent(item), map(&_map) {}
    309309
    310310      ItemIt& operator++() {
    311         map.graph.next(*this);
    312         return *this;
    313       }
    314 
    315     protected:
    316       const Map& map;
     311        map->graph.next(*this);
     312        return *this;
     313      }
     314
     315    protected:
     316      const Map* map;
    317317
    318318    };
  • lemon/glpk.h

    r697 r900  
    2626#include <lemon/lp_base.h>
    2727
    28 // forward declaration
    29 #if !defined _GLP_PROB && !defined GLP_PROB
    30 #define _GLP_PROB
    31 #define GLP_PROB
    32 typedef struct { double _opaque_prob; } glp_prob;
    33 /* LP/MIP problem object */
    34 #endif
    35 
    3628namespace lemon {
    3729
     30  namespace _solver_bits {
     31    class VoidPtr {
     32    private:
     33      void *_ptr;     
     34    public:
     35      VoidPtr() : _ptr(0) {}
     36
     37      template <typename T>
     38      VoidPtr(T* ptr) : _ptr(reinterpret_cast<void*>(ptr)) {}
     39
     40      template <typename T>
     41      VoidPtr& operator=(T* ptr) {
     42        _ptr = reinterpret_cast<void*>(ptr);
     43        return *this;
     44      }
     45
     46      template <typename T>
     47      operator T*() const { return reinterpret_cast<T*>(_ptr); }
     48    };
     49  }
    3850
    3951  /// \brief Base interface for the GLPK LP and MIP solver
     
    4456  protected:
    4557
    46     typedef glp_prob LPX;
    47     glp_prob* lp;
     58    _solver_bits::VoidPtr lp;
    4859
    4960    GlpkBase();
     
    123134
    124135    ///Pointer to the underlying GLPK data structure.
    125     LPX *lpx() {return lp;}
     136    _solver_bits::VoidPtr lpx() {return lp;}
    126137    ///Const pointer to the underlying GLPK data structure.
    127     const LPX *lpx() const {return lp;}
     138    _solver_bits::VoidPtr lpx() const {return lp;}
    128139
    129140    ///Returns the constraint identifier understood by GLPK.
  • lemon/graph_to_eps.h

    r664 r908  
    685685#else
    686686      os << bits::getWinFormattedDate();
     687      os << std::endl;
    687688#endif
    688689    }
    689     os << std::endl;
    690690
    691691    if (_autoArcWidthScale) {
  • 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/path.h

    r606 r868  
    7171    template <typename CPath>
    7272    Path(const CPath& cpath) {
    73       copyPath(*this, cpath);
     73      pathCopy(cpath, *this);
    7474    }
    7575
     
    7979    template <typename CPath>
    8080    Path& operator=(const CPath& cpath) {
    81       copyPath(*this, cpath);
     81      pathCopy(cpath, *this);
    8282      return *this;
    8383    }
     
    259259    template <typename CPath>
    260260    SimplePath(const CPath& cpath) {
    261       copyPath(*this, cpath);
     261      pathCopy(cpath, *this);
    262262    }
    263263
     
    268268    template <typename CPath>
    269269    SimplePath& operator=(const CPath& cpath) {
    270       copyPath(*this, cpath);
     270      pathCopy(cpath, *this);
    271271      return *this;
    272272    }
     
    438438    template <typename CPath>
    439439    ListPath(const CPath& cpath) : first(0), last(0) {
    440       copyPath(*this, cpath);
     440      pathCopy(cpath, *this);
    441441    }
    442442
     
    454454    template <typename CPath>
    455455    ListPath& operator=(const CPath& cpath) {
    456       copyPath(*this, cpath);
     456      pathCopy(cpath, *this);
    457457      return *this;
    458458    }
     
    764764    template <typename CPath>
    765765    StaticPath(const CPath& cpath) : arcs(0) {
    766       copyPath(*this, cpath);
     766      pathCopy(cpath, *this);
    767767    }
    768768
     
    780780    template <typename CPath>
    781781    StaticPath& operator=(const CPath& cpath) {
    782       copyPath(*this, cpath);
     782      pathCopy(cpath, *this);
    783783      return *this;
    784784    }
     
    929929    };
    930930
    931     template <typename Target, typename Source,
    932               bool buildEnable = BuildTagIndicator<Target>::value>
     931    template <typename From, typename To,
     932              bool buildEnable = BuildTagIndicator<To>::value>
    933933    struct PathCopySelectorForward {
    934       static void copy(Target& target, const Source& source) {
    935         target.clear();
    936         for (typename Source::ArcIt it(source); it != INVALID; ++it) {
    937           target.addBack(it);
     934      static void copy(const From& from, To& to) {
     935        to.clear();
     936        for (typename From::ArcIt it(from); it != INVALID; ++it) {
     937          to.addBack(it);
    938938        }
    939939      }
    940940    };
    941941
    942     template <typename Target, typename Source>
    943     struct PathCopySelectorForward<Target, Source, true> {
    944       static void copy(Target& target, const Source& source) {
    945         target.clear();
    946         target.build(source);
    947       }
    948     };
    949 
    950     template <typename Target, typename Source,
    951               bool buildEnable = BuildTagIndicator<Target>::value>
     942    template <typename From, typename To>
     943    struct PathCopySelectorForward<From, To, true> {
     944      static void copy(const From& from, To& to) {
     945        to.clear();
     946        to.build(from);
     947      }
     948    };
     949
     950    template <typename From, typename To,
     951              bool buildEnable = BuildTagIndicator<To>::value>
    952952    struct PathCopySelectorBackward {
    953       static void copy(Target& target, const Source& source) {
    954         target.clear();
    955         for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
    956           target.addFront(it);
     953      static void copy(const From& from, To& to) {
     954        to.clear();
     955        for (typename From::RevArcIt it(from); it != INVALID; ++it) {
     956          to.addFront(it);
    957957        }
    958958      }
    959959    };
    960960
    961     template <typename Target, typename Source>
    962     struct PathCopySelectorBackward<Target, Source, true> {
    963       static void copy(Target& target, const Source& source) {
    964         target.clear();
    965         target.buildRev(source);
     961    template <typename From, typename To>
     962    struct PathCopySelectorBackward<From, To, true> {
     963      static void copy(const From& from, To& to) {
     964        to.clear();
     965        to.buildRev(from);
    966966      }
    967967    };
    968968
    969969   
    970     template <typename Target, typename Source,
    971               bool revEnable = RevPathTagIndicator<Source>::value>
     970    template <typename From, typename To,
     971              bool revEnable = RevPathTagIndicator<From>::value>
    972972    struct PathCopySelector {
    973       static void copy(Target& target, const Source& source) {
    974         PathCopySelectorForward<Target, Source>::copy(target, source);
     973      static void copy(const From& from, To& to) {
     974        PathCopySelectorForward<From, To>::copy(from, to);
    975975      }     
    976976    };
    977977
    978     template <typename Target, typename Source>
    979     struct PathCopySelector<Target, Source, true> {
    980       static void copy(Target& target, const Source& source) {
    981         PathCopySelectorBackward<Target, Source>::copy(target, source);
     978    template <typename From, typename To>
     979    struct PathCopySelector<From, To, true> {
     980      static void copy(const From& from, To& to) {
     981        PathCopySelectorBackward<From, To>::copy(from, to);
    982982      }     
    983983    };
     
    988988  /// \brief Make a copy of a path.
    989989  ///
    990   ///  This function makes a copy of a path.
    991   template <typename Target, typename Source>
    992   void copyPath(Target& target, const Source& source) {
    993     checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
    994     _path_bits::PathCopySelector<Target, Source>::copy(target, source);
     990  /// This function makes a copy of a path.
     991  template <typename From, typename To>
     992  void pathCopy(const From& from, To& to) {
     993    checkConcept<concepts::PathDumper<typename From::Digraph>, From>();
     994    _path_bits::PathCopySelector<From, To>::copy(from, to);
     995  }
     996
     997  /// \brief Deprecated version of \ref pathCopy().
     998  ///
     999  /// Deprecated version of \ref pathCopy() (only for reverse compatibility).
     1000  template <typename To, typename From>
     1001  void copyPath(To& to, const From& from) {
     1002    pathCopy(from, to);
    9951003  }
    9961004
     
    10161024  /// \brief The source of a path
    10171025  ///
    1018   /// This function returns the source of the given path.
     1026  /// This function returns the source node of the given path.
     1027  /// If the path is empty, then it returns \c INVALID.
    10191028  template <typename Digraph, typename Path>
    10201029  typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
    1021     return digraph.source(path.front());
     1030    return path.empty() ? INVALID : digraph.source(path.front());
    10221031  }
    10231032
    10241033  /// \brief The target of a path
    10251034  ///
    1026   /// This function returns the target of the given path.
     1035  /// This function returns the target node of the given path.
     1036  /// If the path is empty, then it returns \c INVALID.
    10271037  template <typename Digraph, typename Path>
    10281038  typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
    1029     return digraph.target(path.back());
     1039    return path.empty() ? INVALID : digraph.target(path.back());
    10301040  }
    10311041
  • lemon/suurballe.h

    r925 r928  
    4646  /// Note that this problem is a special case of the \ref min_cost_flow
    4747  /// "minimum cost flow problem". This implementation is actually an
    48   /// efficient specialized version of the \ref CapacityScaling
    49   /// "Successive Shortest Path" algorithm directly for this problem.
     48  /// efficient specialized version of the Successive Shortest Path
     49  /// algorithm directly for this problem.
    5050  /// Therefore this class provides query functions for flow values and
    5151  /// node potentials (the dual solution) just like the minimum cost flow
  • lemon/unionfind.h

    r606 r894  
    740740    void clear() {
    741741      items.clear();
    742       classes.clear;
     742      classes.clear();
    743743      firstClass = firstFreeClass = firstFreeItem = -1;
    744744    }
  • 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;
Note: See TracChangeset for help on using the changeset viewer.