Changes in / [745:d3b041452dd8:746:27ddc8009ac3] in lemon-1.1
- Files:
-
- 1 added
- 18 edited
Legend:
- Unmodified
- Added
- Removed
-
NEWS
r663 r735 1 2010-10-21 Version 1.1.3 released 2 3 Bugfix release. 4 5 #366: Fix Pred[Matrix]MapPath::empty() 6 #371: Bug fix in (di)graphCopy() 7 The target graph is cleared before adding nodes and arcs/edges. 8 9 #356: Fix multiple execution bug in weighted matchings 10 #364: Add missing UndirectedTags 11 #368: Fix the usage of std::numeric_limits<>::min() in Network Simplex 12 #372: Fix a critical bug in preflow 13 14 2010-03-08 Version 1.1.2 released 15 16 Bugfix release. 17 18 #317: Fix (and improve) error message in mip_test.cc 19 Remove unnecessary OsiCbc dependency 20 #250: Fix in pathSource() and pathTarget() 21 #322: Distribute LEMONConfig.cmake.in 22 #321: Use pathCopy(from,to) instead of copyPath(to,from) 23 #330: Bug fix in map_extender.h 24 #335: Fix clear() function in ExtendFindEnum 25 #337: Use void* as LPX object pointer 26 #336: Fix the date field comment of graphToEps() output 27 #323: Bug fix in Suurballe 28 29 2009-10-03 Version 1.1.1 released 30 31 Bugfix release. 32 33 #295: Suppress MSVC warnings using pragmas 34 ----: Various CMAKE related improvements 35 * Remove duplications from doc/CMakeLists.txt 36 * Rename documentation install folder from 'docs' to 'html' 37 * Add tools/CMakeLists.txt to the tarball 38 * Generate and install LEMONConfig.cmake 39 * Change the label of the html project in Visual Studio 40 * Fix the check for the 'long long' type 41 * Put the version string into config.h 42 * Minor CMake improvements 43 * Set the version to 'hg-tip' if everything fails 44 #311: Add missing 'explicit' keywords 45 #302: Fix the implementation and doc of CrossRefMap 46 #308: Remove duplicate list_graph.h entry from source list 47 #307: Bug fix in Preflow and Circulation 48 1 49 2009-05-13 Version 1.1 released 2 50 -
doc/groups.dox
r661 r664 227 227 228 228 /** 229 @defgroup matrices Matrices230 @ingroup datas231 \brief Two dimensional data storages implemented in LEMON.232 233 This group contains two dimensional data storages implemented in LEMON.234 */235 236 /**237 229 @defgroup paths Path Structures 238 230 @ingroup datas … … 284 276 This group contains the algorithms for finding shortest paths in digraphs. 285 277 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. 296 280 - \ref Suurballe A successive shortest path algorithm for finding 297 281 arc-disjoint paths between two nodes having minimum total length. … … 318 302 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] 319 303 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 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 330 308 331 309 \ref Circulation is a preflow push-relabel algorithm implemented directly … … 345 323 solution see \ref min_cost_flow "Minimum Cost Flow Problem". 346 324 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 326 Simplex algorithm for finding minimum cost flows. It also provides dual 327 solution (node potentials), if an optimal flow is found. 361 328 */ 362 329 … … 382 349 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut 383 350 in directed graphs. 384 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for385 calculating minimum cut in undirected graphs.386 351 - \ref GomoryHu "Gomory-Hu tree computation" for calculating 387 352 all-pairs minimum cut in undirected graphs. … … 404 369 405 370 /** 406 @defgroup planar Planarity Embedding and Drawing407 @ingroup algs408 \brief Algorithms for planarity checking, embedding and drawing409 410 This group contains the algorithms for planarity checking,411 embedding and drawing.412 413 \image html planar.png414 \image latex planar.eps "Plane graph" width=\textwidth415 */416 417 /**418 371 @defgroup matching Matching Algorithms 419 372 @ingroup algs 420 373 \brief Algorithms for finding matchings in graphs and bipartite graphs. 421 374 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. 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. 426 378 427 379 There 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 380 graphs. The goal of the matching optimization 430 381 can be finding maximum cardinality, maximum weight or minimum cost 431 382 matching. The search can be constrained to find perfect or … … 433 384 434 385 The matching algorithms implemented in LEMON: 435 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm436 for calculating maximum cardinality matching in bipartite graphs.437 - \ref PrBipartiteMatching Push-relabel algorithm438 for calculating maximum cardinality matching in bipartite graphs.439 - \ref MaxWeightedBipartiteMatching440 Successive shortest path algorithm for calculating maximum weighted441 matching and maximum weighted bipartite matching in bipartite graphs.442 - \ref MinCostMaxBipartiteMatching443 Successive shortest path algorithm for calculating minimum cost maximum444 matching in bipartite graphs.445 386 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating 446 387 maximum cardinality matching in general graphs. … … 474 415 475 416 /** 476 @defgroup approx Approximation Algorithms477 @ingroup algs478 \brief Approximation algorithms.479 480 This group contains the approximation and heuristic algorithms481 implemented in LEMON.482 */483 484 /**485 417 @defgroup gen_opt_group General Optimization Tools 486 418 \brief This group contains some general optimization frameworks … … 499 431 various LP solvers could be used in the same manner with this 500 432 interface. 501 */502 503 /**504 @defgroup lp_utils Tools for Lp and Mip Solvers505 @ingroup lp_group506 \brief Helper tools to the Lp and Mip solvers.507 508 This group adds some helper tools to general optimization framework509 implemented in LEMON.510 */511 512 /**513 @defgroup metah Metaheuristics514 @ingroup gen_opt_group515 \brief Metaheuristics for LEMON library.516 517 This group contains some metaheuristic optimization tools.518 433 */ 519 434 -
lemon/Makefile.am
r666 r716 91 91 lemon/lp_base.h \ 92 92 lemon/lp_skeleton.h \ 93 lemon/list_graph.h \94 93 lemon/maps.h \ 95 94 lemon/matching.h \ -
lemon/bits/edge_set_extender.h
r609 r725 281 281 typedef EdgeSetExtender Graph; 282 282 283 typedef True UndirectedTag; 284 283 285 typedef typename Parent::Node Node; 284 286 typedef typename Parent::Arc Arc; … … 538 540 539 541 public: 540 ArcMap(const Graph& _g)542 explicit ArcMap(const Graph& _g) 541 543 : Parent(_g) {} 542 544 ArcMap(const Graph& _g, const _Value& _v) … … 562 564 563 565 public: 564 EdgeMap(const Graph& _g)566 explicit EdgeMap(const Graph& _g) 565 567 : Parent(_g) {} 566 568 -
lemon/bits/graph_adaptor_extender.h
r609 r724 182 182 typedef GraphAdaptorExtender Adaptor; 183 183 184 typedef True UndirectedTag; 185 184 186 typedef typename Parent::Node Node; 185 187 typedef typename Parent::Arc Arc; -
lemon/bits/graph_extender.h
r609 r686 605 605 606 606 public: 607 NodeMap(const Graph& graph)607 explicit NodeMap(const Graph& graph) 608 608 : Parent(graph) {} 609 609 NodeMap(const Graph& graph, const _Value& value) … … 629 629 630 630 public: 631 ArcMap(const Graph& graph)631 explicit ArcMap(const Graph& graph) 632 632 : Parent(graph) {} 633 633 ArcMap(const Graph& graph, const _Value& value) … … 653 653 654 654 public: 655 EdgeMap(const Graph& graph)655 explicit EdgeMap(const Graph& graph) 656 656 : Parent(graph) {} 657 657 -
lemon/bits/map_extender.h
r609 r716 83 83 typedef typename Map::Value Value; 84 84 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); 91 91 } 92 92 93 93 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) 94 134 : Parent(item), map(_map) {} 95 135 96 MapIt& operator++() {97 map .notifier()->next(*this);136 ConstMapIt& operator++() { 137 map->notifier()->next(*this); 98 138 return *this; 99 139 } … … 103 143 } 104 144 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; 147 147 }; 148 148 … … 151 151 152 152 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); 160 160 } 161 161 162 162 ItemIt(const Map& _map, const Item& item) 163 : Parent(item), map( _map) {}163 : Parent(item), map(&_map) {} 164 164 165 165 ItemIt& operator++() { 166 map .notifier()->next(*this);167 return *this; 168 } 169 170 protected: 171 const Map ↦166 map->notifier()->next(*this); 167 return *this; 168 } 169 170 protected: 171 const Map* map; 172 172 173 173 }; … … 228 228 typedef typename Map::Value Value; 229 229 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); 236 236 } 237 237 238 238 MapIt(const Map& _map, const Item& item) 239 : Parent(item), map( _map) {}239 : Parent(item), map(&_map) {} 240 240 241 241 MapIt& operator++() { 242 map .graph.next(*this);242 map->graph.next(*this); 243 243 return *this; 244 244 } 245 245 246 246 typename MapTraits<Map>::ConstReturnValue operator*() const { 247 return map[*this];247 return (*map)[*this]; 248 248 } 249 249 250 250 typename MapTraits<Map>::ReturnValue operator*() { 251 return map[*this];251 return (*map)[*this]; 252 252 } 253 253 254 254 void set(const Value& value) { 255 map .set(*this, value);256 } 257 258 protected: 259 Map ↦255 map->set(*this, value); 256 } 257 258 protected: 259 Map* map; 260 260 261 261 }; … … 268 268 typedef typename Map::Value Value; 269 269 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); 276 276 } 277 277 278 278 ConstMapIt(const Map& _map, const Item& item) 279 : Parent(item), map( _map) {}279 : Parent(item), map(&_map) {} 280 280 281 281 ConstMapIt& operator++() { 282 map .graph.next(*this);282 map->graph.next(*this); 283 283 return *this; 284 284 } 285 285 286 286 typename MapTraits<Map>::ConstReturnValue operator*() const { 287 return map[*this];288 } 289 290 protected: 291 const Map ↦287 return (*map)[*this]; 288 } 289 290 protected: 291 const Map* map; 292 292 }; 293 293 … … 296 296 297 297 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); 305 305 } 306 306 307 307 ItemIt(const Map& _map, const Item& item) 308 : Parent(item), map( _map) {}308 : Parent(item), map(&_map) {} 309 309 310 310 ItemIt& operator++() { 311 map .graph.next(*this);312 return *this; 313 } 314 315 protected: 316 const Map ↦311 map->graph.next(*this); 312 return *this; 313 } 314 315 protected: 316 const Map* map; 317 317 318 318 }; -
lemon/bits/path_dump.h
r514 r728 50 50 51 51 bool empty() const { 52 return predMap[target] != INVALID;52 return predMap[target] == INVALID; 53 53 } 54 54 … … 124 124 125 125 bool empty() const { 126 return source != target;126 return predMatrixMap(source, target) == INVALID; 127 127 } 128 128 -
lemon/core.h
r672 r734 395 395 static void copy(const From& from, Digraph &to, 396 396 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { 397 to.clear(); 397 398 for (typename From::NodeIt it(from); it != INVALID; ++it) { 398 399 nodeRefMap[it] = to.addNode(); … … 422 423 static void copy(const From& from, Graph &to, 423 424 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { 425 to.clear(); 424 426 for (typename From::NodeIt it(from); it != INVALID; ++it) { 425 427 nodeRefMap[it] = to.addNode(); -
lemon/dfs.h
r576 r738 558 558 void start(Node t) 559 559 { 560 while ( !emptyQueue() && G->target(_stack[_stack_head])!=t)560 while ( !emptyQueue() && !(*_reached)[t] ) 561 561 processNextArc(); 562 562 } … … 1510 1510 /// with addSource() before using this function. 1511 1511 void start(Node t) { 1512 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t)1512 while ( !emptyQueue() && !(*_reached)[t] ) 1513 1513 processNextArc(); 1514 1514 } -
lemon/glpk.h
r648 r711 26 26 #include <lemon/lp_base.h> 27 27 28 // forward declaration29 #if !defined _GLP_PROB && !defined GLP_PROB30 #define _GLP_PROB31 #define GLP_PROB32 typedef struct { double _opaque_prob; } glp_prob;33 /* LP/MIP problem object */34 #endif35 36 28 namespace lemon { 37 29 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 } 38 50 39 51 /// \brief Base interface for the GLPK LP and MIP solver … … 44 56 protected: 45 57 46 typedef glp_prob LPX; 47 glp_prob* lp; 58 _solver_bits::VoidPtr lp; 48 59 49 60 GlpkBase(); … … 123 134 124 135 ///Pointer to the underlying GLPK data structure. 125 LPX *lpx() {return lp;}136 _solver_bits::VoidPtr lpx() {return lp;} 126 137 ///Const pointer to the underlying GLPK data structure. 127 const LPX *lpx() const {return lp;}138 _solver_bits::VoidPtr lpx() const {return lp;} 128 139 129 140 ///Returns the constraint identifier understood by GLPK. -
lemon/graph_to_eps.h
r609 r714 685 685 #else 686 686 os << bits::getWinFormattedDate(); 687 os << std::endl; 687 688 #endif 688 689 } 689 os << std::endl;690 690 691 691 if (_autoArcWidthScale) { -
lemon/maps.h
r609 r684 1903 1903 1904 1904 /// 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. 1909 1907 /// The values of the map can be accessed 1910 1908 /// with stl compatible forward iterator. 1909 /// 1910 /// This type is not reference map, so it cannot be modified with 1911 /// the subscript operator. 1911 1912 /// 1912 1913 /// \tparam GR The graph type. … … 1924 1925 template Map<V>::Type Map; 1925 1926 1926 typedef std::m ap<V, K> Container;1927 typedef std::multimap<V, K> Container; 1927 1928 Container _inv_map; 1928 1929 … … 1949 1950 /// iterator on the values of the map. The values can 1950 1951 /// 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. 1951 1954 class ValueIterator 1952 1955 : public std::iterator<std::forward_iterator_tag, Value> { … … 2001 2004 void set(const Key& key, const Value& val) { 2002 2005 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 } 2006 2013 } 2007 _inv_map.insert( make_pair(val, key));2014 _inv_map.insert(std::make_pair(val, key)); 2008 2015 Map::set(key, val); 2009 2016 } … … 2017 2024 } 2018 2025 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); 2024 2034 return it != _inv_map.end() ? it->second : INVALID; 2025 2035 } … … 2033 2043 virtual void erase(const Key& key) { 2034 2044 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 } 2038 2052 } 2039 2053 Map::erase(key); … … 2047 2061 for (int i = 0; i < int(keys.size()); ++i) { 2048 2062 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 } 2052 2070 } 2053 2071 } … … 2085 2103 /// \brief Subscript operator. 2086 2104 /// 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. 2089 2108 Value operator[](const Key& key) const { 2090 2109 return _inverted(key); -
lemon/path.h
r550 r709 71 71 template <typename CPath> 72 72 Path(const CPath& cpath) { 73 copyPath(*this, cpath);73 pathCopy(cpath, *this); 74 74 } 75 75 … … 79 79 template <typename CPath> 80 80 Path& operator=(const CPath& cpath) { 81 copyPath(*this, cpath);81 pathCopy(cpath, *this); 82 82 return *this; 83 83 } … … 259 259 template <typename CPath> 260 260 SimplePath(const CPath& cpath) { 261 copyPath(*this, cpath);261 pathCopy(cpath, *this); 262 262 } 263 263 … … 268 268 template <typename CPath> 269 269 SimplePath& operator=(const CPath& cpath) { 270 copyPath(*this, cpath);270 pathCopy(cpath, *this); 271 271 return *this; 272 272 } … … 438 438 template <typename CPath> 439 439 ListPath(const CPath& cpath) : first(0), last(0) { 440 copyPath(*this, cpath);440 pathCopy(cpath, *this); 441 441 } 442 442 … … 454 454 template <typename CPath> 455 455 ListPath& operator=(const CPath& cpath) { 456 copyPath(*this, cpath);456 pathCopy(cpath, *this); 457 457 return *this; 458 458 } … … 764 764 template <typename CPath> 765 765 StaticPath(const CPath& cpath) : arcs(0) { 766 copyPath(*this, cpath);766 pathCopy(cpath, *this); 767 767 } 768 768 … … 780 780 template <typename CPath> 781 781 StaticPath& operator=(const CPath& cpath) { 782 copyPath(*this, cpath);782 pathCopy(cpath, *this); 783 783 return *this; 784 784 } … … 929 929 }; 930 930 931 template <typename Target, typename Source,932 bool buildEnable = BuildTagIndicator<T arget>::value>931 template <typename From, typename To, 932 bool buildEnable = BuildTagIndicator<To>::value> 933 933 struct PathCopySelectorForward { 934 static void copy( Target& target, const Source& source) {935 t arget.clear();936 for (typename Source::ArcIt it(source); it != INVALID; ++it) {937 t arget.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); 938 938 } 939 939 } 940 940 }; 941 941 942 template <typename Target, typename Source>943 struct PathCopySelectorForward< Target, Source, true> {944 static void copy( Target& target, const Source& source) {945 t arget.clear();946 t arget.build(source);947 } 948 }; 949 950 template <typename Target, typename Source,951 bool buildEnable = BuildTagIndicator<T arget>::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> 952 952 struct PathCopySelectorBackward { 953 static void copy( Target& target, const Source& source) {954 t arget.clear();955 for (typename Source::RevArcIt it(source); it != INVALID; ++it) {956 t arget.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); 957 957 } 958 958 } 959 959 }; 960 960 961 template <typename Target, typename Source>962 struct PathCopySelectorBackward< Target, Source, true> {963 static void copy( Target& target, const Source& source) {964 t arget.clear();965 t arget.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); 966 966 } 967 967 }; 968 968 969 969 970 template <typename Target, typename Source,971 bool revEnable = RevPathTagIndicator< Source>::value>970 template <typename From, typename To, 971 bool revEnable = RevPathTagIndicator<From>::value> 972 972 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); 975 975 } 976 976 }; 977 977 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); 982 982 } 983 983 }; … … 988 988 /// \brief Make a copy of a path. 989 989 /// 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); 995 1003 } 996 1004 … … 1016 1024 /// \brief The source of a path 1017 1025 /// 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. 1019 1028 template <typename Digraph, typename Path> 1020 1029 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()); 1022 1031 } 1023 1032 1024 1033 /// \brief The target of a path 1025 1034 /// 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. 1027 1037 template <typename Digraph, typename Path> 1028 1038 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()); 1030 1040 } 1031 1041 -
lemon/suurballe.h
r718 r719 46 46 /// Note that this problem is a special case of the \ref min_cost_flow 47 47 /// "minimum cost flow problem". This implementation is actually an 48 /// efficient specialized version of the \ref CapacityScaling49 /// "Successive Shortest Path"algorithm directly for this problem.48 /// efficient specialized version of the Successive Shortest Path 49 /// algorithm directly for this problem. 50 50 /// Therefore this class provides query functions for flow values and 51 51 /// node potentials (the dual solution) just like the minimum cost flow -
test/dfs_test.cc
r577 r738 51 51 "@attributes\n" 52 52 "source 0\n" 53 "target 5\n"; 53 "target 5\n" 54 "source1 6\n" 55 "target1 3\n"; 56 54 57 55 58 void checkDfsCompile() … … 180 183 Digraph G; 181 184 Node s, t; 185 Node s1, t1; 182 186 183 187 std::istringstream input(test_lgf); … … 185 189 node("source", s). 186 190 node("target", t). 191 node("source1", s1). 192 node("target1", t1). 187 193 run(); 188 194 … … 211 217 212 218 { 219 Dfs<Digraph> dfs(G); 220 check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6."); 221 } 222 223 { 213 224 NullMap<Node,Arc> myPredMap; 214 225 dfs(G).predMap(myPredMap).run(s); -
test/graph_copy_test.cc
r440 r734 30 30 const int nn = 10; 31 31 32 // Build a digraph 32 33 SmartDigraph from; 33 34 SmartDigraph::NodeMap<int> fnm(from); … … 52 53 } 53 54 55 // Test digraph copy 54 56 ListDigraph to; 55 57 ListDigraph::NodeMap<int> tnm(to); … … 69 71 nodeCrossRef(ncr).arcCrossRef(ecr). 70 72 node(fn, tn).arc(fa, ta).run(); 73 74 check(countNodes(from) == countNodes(to), "Wrong copy."); 75 check(countArcs(from) == countArcs(to), "Wrong copy."); 71 76 72 77 for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) { … … 91 96 check(tn == nr[fn], "Wrong copy."); 92 97 check(ta == er[fa], "Wrong copy."); 98 99 // Test repeated copy 100 digraphCopy(from, to).run(); 101 102 check(countNodes(from) == countNodes(to), "Wrong copy."); 103 check(countArcs(from) == countArcs(to), "Wrong copy."); 93 104 } 94 105 … … 96 107 const int nn = 10; 97 108 109 // Build a graph 98 110 SmartGraph from; 99 111 SmartGraph::NodeMap<int> fnm(from); … … 123 135 } 124 136 137 // Test graph copy 125 138 ListGraph to; 126 139 ListGraph::NodeMap<int> tnm(to); … … 144 157 nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr). 145 158 node(fn, tn).arc(fa, ta).edge(fe, te).run(); 159 160 check(countNodes(from) == countNodes(to), "Wrong copy."); 161 check(countEdges(from) == countEdges(to), "Wrong copy."); 162 check(countArcs(from) == countArcs(to), "Wrong copy."); 146 163 147 164 for (SmartGraph::NodeIt it(from); it != INVALID; ++it) { … … 181 198 check(ta == ar[fa], "Wrong copy."); 182 199 check(te == er[fe], "Wrong copy."); 200 201 // Test repeated copy 202 graphCopy(from, to).run(); 203 204 check(countNodes(from) == countNodes(to), "Wrong copy."); 205 check(countEdges(from) == countEdges(to), "Wrong copy."); 206 check(countArcs(from) == countArcs(to), "Wrong copy."); 183 207 } 184 208 -
test/maps_test.cc
r477 r684 23 23 #include <lemon/concepts/maps.h> 24 24 #include <lemon/maps.h> 25 #include <lemon/list_graph.h> 25 26 26 27 #include "test_tools.h" … … 349 350 check(v1[i++] == *it, "Something is wrong with LoggerBoolMap"); 350 351 } 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 } 351 386 352 387 return 0;
Note: See TracChangeset
for help on using the changeset viewer.