COIN-OR::LEMON - Graph Library

Ignore:
Files:
1 deleted
12 edited

Legend:

Unmodified
Added
Removed
  • NEWS

    r939 r712  
    1 2010-03-08 Version 1.1.2 released
    2 
    3         Bugfix release.
    4 
    5         #317: Fix (and improve) error message in mip_test.cc
    6               Remove unnecessary OsiCbc dependency
    7         #250: Fix in pathSource() and pathTarget()
    8         #322: Distribute LEMONConfig.cmake.in
    9         #321: Use pathCopy(from,to) instead of copyPath(to,from)
    10         #330: Bug fix in map_extender.h
    11         #335: Fix clear() function in ExtendFindEnum
    12         #337: Use void* as LPX object pointer
    13         #336: Fix the date field comment of graphToEps() output
    14         #323: Bug fix in Suurballe
    15 
    16 2009-10-03 Version 1.1.1 released
    17 
    18         Bugfix release.
    19 
    20         #295: Suppress MSVC warnings using pragmas
    21         ----: Various CMAKE related improvements
    22               * Remove duplications from doc/CMakeLists.txt
    23               * Rename documentation install folder from 'docs' to 'html'
    24               * Add tools/CMakeLists.txt to the tarball
    25               * Generate and install LEMONConfig.cmake
    26               * Change the label of the html project in Visual Studio
    27               * Fix the check for the 'long long' type
    28               * Put the version string into config.h
    29               * Minor CMake improvements
    30               * Set the version to 'hg-tip' if everything fails
    31         #311: Add missing 'explicit' keywords
    32         #302: Fix the implementation and doc of CrossRefMap
    33         #308: Remove duplicate list_graph.h entry from source list
    34         #307: Bug fix in Preflow and Circulation
    35 
    3612009-05-13 Version 1.1 released
    372
  • doc/groups.dox

    r844 r710  
    227227
    228228/**
     229@defgroup matrices Matrices
     230@ingroup datas
     231\brief Two dimensional data storages implemented in LEMON.
     232
     233This group contains two dimensional data storages implemented in LEMON.
     234*/
     235
     236/**
    229237@defgroup paths Path Structures
    230238@ingroup datas
     
    276284This group contains the algorithms for finding shortest paths in digraphs.
    277285
    278  - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a
    279    source node when all arc lengths are non-negative.
     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.
    280296 - \ref Suurballe A successive shortest path algorithm for finding
    281297   arc-disjoint paths between two nodes having minimum total length.
     
    302318\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    303319
    304 \ref Preflow implements the preflow push-relabel algorithm of Goldberg and
    305 Tarjan for solving this problem. It also provides functions to query the
    306 minimum cut, which is the dual problem of maximum flow.
    307 
     320LEMON 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
     326In most cases the \ref Preflow "Preflow" algorithm provides the
     327fastest method for computing a maximum flow. All implementations
     328also provide functions to query the minimum cut, which is the dual
     329problem of maximum flow.
    308330
    309331\ref Circulation is a preflow push-relabel algorithm implemented directly
     
    323345solution see \ref min_cost_flow "Minimum Cost Flow Problem".
    324346
    325 \ref NetworkSimplex is an efficient implementation of the primal Network
    326 Simplex algorithm for finding minimum cost flows. It also provides dual
    327 solution (node potentials), if an optimal flow is found.
     347LEMON 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
     357In general NetworkSimplex is the most efficient implementation,
     358but in special cases other algorithms could be faster.
     359For example, if the total supply and/or capacities are rather small,
     360CapacityScaling is usually the fastest algorithm (without effective scaling).
    328361*/
    329362
     
    349382- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
    350383  in directed graphs.
     384- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
     385  calculating minimum cut in undirected graphs.
    351386- \ref GomoryHu "Gomory-Hu tree computation" for calculating
    352387  all-pairs minimum cut in undirected graphs.
     
    369404
    370405/**
     406@defgroup planar Planarity Embedding and Drawing
     407@ingroup algs
     408\brief Algorithms for planarity checking, embedding and drawing
     409
     410This group contains the algorithms for planarity checking,
     411embedding and drawing.
     412
     413\image html planar.png
     414\image latex planar.eps "Plane graph" width=\textwidth
     415*/
     416
     417/**
    371418@defgroup matching Matching Algorithms
    372419@ingroup algs
    373420\brief Algorithms for finding matchings in graphs and bipartite graphs.
    374421
    375 This group contains the algorithms for calculating matchings in graphs.
    376 The general matching problem is finding a subset of the edges for which
    377 each node has at most one incident edge.
     422This group contains the algorithms for calculating
     423matchings in graphs and bipartite graphs. The general matching problem is
     424finding a subset of the edges for which each node has at most one incident
     425edge.
    378426
    379427There are several different algorithms for calculate matchings in
    380 graphs. The goal of the matching optimization
     428graphs.  The matching problems in bipartite graphs are generally
     429easier than in general graphs. The goal of the matching optimization
    381430can be finding maximum cardinality, maximum weight or minimum cost
    382431matching. The search can be constrained to find perfect or
     
    384433
    385434The 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.
    386445- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    387446  maximum cardinality matching in general graphs.
     
    415474
    416475/**
     476@defgroup approx Approximation Algorithms
     477@ingroup algs
     478\brief Approximation algorithms.
     479
     480This group contains the approximation and heuristic algorithms
     481implemented in LEMON.
     482*/
     483
     484/**
    417485@defgroup gen_opt_group General Optimization Tools
    418486\brief This group contains some general optimization frameworks
     
    431499various LP solvers could be used in the same manner with this
    432500interface.
     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
     508This group adds some helper tools to general optimization framework
     509implemented in LEMON.
     510*/
     511
     512/**
     513@defgroup metah Metaheuristics
     514@ingroup gen_opt_group
     515\brief Metaheuristics for LEMON library.
     516
     517This group contains some metaheuristic optimization tools.
    433518*/
    434519
  • lemon/Makefile.am

    r913 r714  
    9191        lemon/lp_base.h \
    9292        lemon/lp_skeleton.h \
     93        lemon/list_graph.h \
    9394        lemon/maps.h \
    9495        lemon/matching.h \
  • lemon/bits/edge_set_extender.h

    r967 r965  
    540540
    541541    public:
    542       explicit ArcMap(const Graph& _g)
     542      ArcMap(const Graph& _g)
    543543        : Parent(_g) {}
    544544      ArcMap(const Graph& _g, const _Value& _v)
     
    564564
    565565    public:
    566       explicit EdgeMap(const Graph& _g)
     566      EdgeMap(const Graph& _g)
    567567        : Parent(_g) {}
    568568
  • lemon/bits/graph_extender.h

    r732 r664  
    605605
    606606    public:
    607       explicit NodeMap(const Graph& graph)
     607      NodeMap(const Graph& graph)
    608608        : Parent(graph) {}
    609609      NodeMap(const Graph& graph, const _Value& value)
     
    629629
    630630    public:
    631       explicit ArcMap(const Graph& graph)
     631      ArcMap(const Graph& graph)
    632632        : Parent(graph) {}
    633633      ArcMap(const Graph& graph, const _Value& value)
     
    653653
    654654    public:
    655       explicit EdgeMap(const Graph& graph)
     655      EdgeMap(const Graph& graph)
    656656        : Parent(graph) {}
    657657
  • lemon/bits/map_extender.h

    r913 r664  
    8383      typedef typename Map::Value Value;
    8484
    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);
     85      MapIt() {}
     86
     87      MapIt(Invalid i) : Parent(i) { }
     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) {}
     94        : Parent(item), map(_map) {}
    9595
    9696      MapIt& operator++() {
    97         map->notifier()->next(*this);
     97        map.notifier()->next(*this);
    9898        return *this;
    9999      }
    100100
    101101      typename MapTraits<Map>::ConstReturnValue operator*() const {
    102         return (*map)[*this];
     102        return map[*this];
    103103      }
    104104
    105105      typename MapTraits<Map>::ReturnValue operator*() {
    106         return (*map)[*this];
     106        return map[*this];
    107107      }
    108108
    109109      void set(const Value& value) {
    110         map->set(*this, value);
    111       }
    112 
    113     protected:
    114       Map* map;
     110        map.set(*this, value);
     111      }
     112
     113    protected:
     114      Map& map;
    115115
    116116    };
     
    123123      typedef typename Map::Value Value;
    124124
    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);
     125      ConstMapIt() {}
     126
     127      ConstMapIt(Invalid i) : Parent(i) { }
     128
     129      explicit ConstMapIt(Map& _map) : map(_map) {
     130        map.notifier()->first(*this);
    131131      }
    132132
     
    135135
    136136      ConstMapIt& operator++() {
    137         map->notifier()->next(*this);
     137        map.notifier()->next(*this);
    138138        return *this;
    139139      }
     
    144144
    145145    protected:
    146       const Map* map;
     146      const Map& map;
    147147    };
    148148
     
    151151
    152152    public:
    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);
     153
     154      ItemIt() {}
     155
     156      ItemIt(Invalid i) : Parent(i) { }
     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() : map(NULL) {}
    231 
    232       MapIt(Invalid i) : Parent(i), map(NULL) { }
    233 
    234       explicit MapIt(Map& _map) : map(&_map) {
    235         map->graph.first(*this);
     230      MapIt() {}
     231
     232      MapIt(Invalid i) : Parent(i) { }
     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() : map(NULL) {}
    271 
    272       ConstMapIt(Invalid i) : Parent(i), map(NULL) { }
    273 
    274       explicit ConstMapIt(Map& _map) : map(&_map) {
    275         map->graph.first(*this);
     270      ConstMapIt() {}
     271
     272      ConstMapIt(Invalid i) : Parent(i) { }
     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       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);
     298
     299      ItemIt() {}
     300
     301      ItemIt(Invalid i) : Parent(i) { }
     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

    r900 r697  
    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
     32typedef struct { double _opaque_prob; } glp_prob;
     33/* LP/MIP problem object */
     34#endif
     35
    2836namespace lemon {
    2937
    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   }
    5038
    5139  /// \brief Base interface for the GLPK LP and MIP solver
     
    5644  protected:
    5745
    58     _solver_bits::VoidPtr lp;
     46    typedef glp_prob LPX;
     47    glp_prob* lp;
    5948
    6049    GlpkBase();
     
    134123
    135124    ///Pointer to the underlying GLPK data structure.
    136     _solver_bits::VoidPtr lpx() {return lp;}
     125    LPX *lpx() {return lp;}
    137126    ///Const pointer to the underlying GLPK data structure.
    138     _solver_bits::VoidPtr lpx() const {return lp;}
     127    const LPX *lpx() const {return lp;}
    139128
    140129    ///Returns the constraint identifier understood by GLPK.
  • lemon/graph_to_eps.h

    r908 r664  
    685685#else
    686686      os << bits::getWinFormattedDate();
    687       os << std::endl;
    688687#endif
    689688    }
     689    os << std::endl;
    690690
    691691    if (_autoArcWidthScale) {
  • lemon/maps.h

    r731 r664  
    19031903
    19041904  /// This class provides simple invertable graph maps.
    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.
     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  ///
    19071909  /// The values of the map can be accessed
    19081910  /// with stl compatible forward iterator.
    1909   ///
    1910   /// This type is not reference map, so it cannot be modified with
    1911   /// the subscript operator.
    19121911  ///
    19131912  /// \tparam GR The graph type.
     
    19251924      template Map<V>::Type Map;
    19261925
    1927     typedef std::multimap<V, K> Container;
     1926    typedef std::map<V, K> Container;
    19281927    Container _inv_map;
    19291928
     
    19501949    /// iterator on the values of the map. The values can
    19511950    /// 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.
    19541951    class ValueIterator
    19551952      : public std::iterator<std::forward_iterator_tag, Value> {
     
    20042001    void set(const Key& key, const Value& val) {
    20052002      Value oldval = Map::operator[](key);
    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         }
     2003      typename Container::iterator it = _inv_map.find(oldval);
     2004      if (it != _inv_map.end() && it->second == key) {
     2005        _inv_map.erase(it);
    20132006      }
    2014       _inv_map.insert(std::make_pair(val, key));
     2007      _inv_map.insert(make_pair(val, key));
    20152008      Map::set(key, val);
    20162009    }
     
    20242017    }
    20252018
    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);
     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);
    20342024      return it != _inv_map.end() ? it->second : INVALID;
    20352025    }
     
    20432033    virtual void erase(const Key& key) {
    20442034      Value val = Map::operator[](key);
    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         }
     2035      typename Container::iterator it = _inv_map.find(val);
     2036      if (it != _inv_map.end() && it->second == key) {
     2037        _inv_map.erase(it);
    20522038      }
    20532039      Map::erase(key);
     
    20612047      for (int i = 0; i < int(keys.size()); ++i) {
    20622048        Value val = Map::operator[](keys[i]);
    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           }
     2049        typename Container::iterator it = _inv_map.find(val);
     2050        if (it != _inv_map.end() && it->second == keys[i]) {
     2051          _inv_map.erase(it);
    20702052        }
    20712053      }
     
    21032085      /// \brief Subscript operator.
    21042086      ///
    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.
     2087      /// Subscript operator. It gives back the item
     2088      /// that was last assigned to the given value.
    21082089      Value operator[](const Key& key) const {
    21092090        return _inverted(key);
  • lemon/path.h

    r868 r606  
    7171    template <typename CPath>
    7272    Path(const CPath& cpath) {
    73       pathCopy(cpath, *this);
     73      copyPath(*this, cpath);
    7474    }
    7575
     
    7979    template <typename CPath>
    8080    Path& operator=(const CPath& cpath) {
    81       pathCopy(cpath, *this);
     81      copyPath(*this, cpath);
    8282      return *this;
    8383    }
     
    259259    template <typename CPath>
    260260    SimplePath(const CPath& cpath) {
    261       pathCopy(cpath, *this);
     261      copyPath(*this, cpath);
    262262    }
    263263
     
    268268    template <typename CPath>
    269269    SimplePath& operator=(const CPath& cpath) {
    270       pathCopy(cpath, *this);
     270      copyPath(*this, cpath);
    271271      return *this;
    272272    }
     
    438438    template <typename CPath>
    439439    ListPath(const CPath& cpath) : first(0), last(0) {
    440       pathCopy(cpath, *this);
     440      copyPath(*this, cpath);
    441441    }
    442442
     
    454454    template <typename CPath>
    455455    ListPath& operator=(const CPath& cpath) {
    456       pathCopy(cpath, *this);
     456      copyPath(*this, cpath);
    457457      return *this;
    458458    }
     
    764764    template <typename CPath>
    765765    StaticPath(const CPath& cpath) : arcs(0) {
    766       pathCopy(cpath, *this);
     766      copyPath(*this, cpath);
    767767    }
    768768
     
    780780    template <typename CPath>
    781781    StaticPath& operator=(const CPath& cpath) {
    782       pathCopy(cpath, *this);
     782      copyPath(*this, cpath);
    783783      return *this;
    784784    }
     
    929929    };
    930930
    931     template <typename From, typename To,
    932               bool buildEnable = BuildTagIndicator<To>::value>
     931    template <typename Target, typename Source,
     932              bool buildEnable = BuildTagIndicator<Target>::value>
    933933    struct PathCopySelectorForward {
    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);
     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);
    938938        }
    939939      }
    940940    };
    941941
    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>
     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>
    952952    struct PathCopySelectorBackward {
    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);
     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);
    957957        }
    958958      }
    959959    };
    960960
    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);
     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);
    966966      }
    967967    };
    968968
    969969   
    970     template <typename From, typename To,
    971               bool revEnable = RevPathTagIndicator<From>::value>
     970    template <typename Target, typename Source,
     971              bool revEnable = RevPathTagIndicator<Source>::value>
    972972    struct PathCopySelector {
    973       static void copy(const From& from, To& to) {
    974         PathCopySelectorForward<From, To>::copy(from, to);
     973      static void copy(Target& target, const Source& source) {
     974        PathCopySelectorForward<Target, Source>::copy(target, source);
    975975      }     
    976976    };
    977977
    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);
     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);
    982982      }     
    983983    };
     
    988988  /// \brief Make a copy of a path.
    989989  ///
    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);
     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);
    1003995  }
    1004996
     
    10241016  /// \brief The source of a path
    10251017  ///
    1026   /// This function returns the source node of the given path.
    1027   /// If the path is empty, then it returns \c INVALID.
     1018  /// This function returns the source of the given path.
    10281019  template <typename Digraph, typename Path>
    10291020  typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
    1030     return path.empty() ? INVALID : digraph.source(path.front());
     1021    return digraph.source(path.front());
    10311022  }
    10321023
    10331024  /// \brief The target of a path
    10341025  ///
    1035   /// This function returns the target node of the given path.
    1036   /// If the path is empty, then it returns \c INVALID.
     1026  /// This function returns the target of the given path.
    10371027  template <typename Digraph, typename Path>
    10381028  typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
    1039     return path.empty() ? INVALID : digraph.target(path.back());
     1029    return digraph.target(path.back());
    10401030  }
    10411031
  • lemon/suurballe.h

    r928 r925  
    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 Successive Shortest Path
    49   /// algorithm directly for this problem.
     48  /// efficient specialized version of the \ref CapacityScaling
     49  /// "Successive Shortest Path" 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
  • test/maps_test.cc

    r731 r554  
    2323#include <lemon/concepts/maps.h>
    2424#include <lemon/maps.h>
    25 #include <lemon/list_graph.h>
    2625
    2726#include "test_tools.h"
     
    350349      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
    351350  }
    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   }
    386351
    387352  return 0;
Note: See TracChangeset for help on using the changeset viewer.