Changes in / [740:075de3c84e1f:739:30d5f950aa5f] in lemon-1.1
- Files:
-
- 1 deleted
- 18 edited
Legend:
- Unmodified
- Added
- Removed
-
NEWS
r735 r663 1 2010-10-21 Version 1.1.3 released2 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 matchings10 #364: Add missing UndirectedTags11 #368: Fix the usage of std::numeric_limits<>::min() in Network Simplex12 #372: Fix a critical bug in preflow13 14 2010-03-08 Version 1.1.2 released15 16 Bugfix release.17 18 #317: Fix (and improve) error message in mip_test.cc19 Remove unnecessary OsiCbc dependency20 #250: Fix in pathSource() and pathTarget()21 #322: Distribute LEMONConfig.cmake.in22 #321: Use pathCopy(from,to) instead of copyPath(to,from)23 #330: Bug fix in map_extender.h24 #335: Fix clear() function in ExtendFindEnum25 #337: Use void* as LPX object pointer26 #336: Fix the date field comment of graphToEps() output27 #323: Bug fix in Suurballe28 29 2009-10-03 Version 1.1.1 released30 31 Bugfix release.32 33 #295: Suppress MSVC warnings using pragmas34 ----: Various CMAKE related improvements35 * Remove duplications from doc/CMakeLists.txt36 * Rename documentation install folder from 'docs' to 'html'37 * Add tools/CMakeLists.txt to the tarball38 * Generate and install LEMONConfig.cmake39 * Change the label of the html project in Visual Studio40 * Fix the check for the 'long long' type41 * Put the version string into config.h42 * Minor CMake improvements43 * Set the version to 'hg-tip' if everything fails44 #311: Add missing 'explicit' keywords45 #302: Fix the implementation and doc of CrossRefMap46 #308: Remove duplicate list_graph.h entry from source list47 #307: Bug fix in Preflow and Circulation48 49 1 2009-05-13 Version 1.1 released 50 2 -
doc/groups.dox
r664 r661 227 227 228 228 /** 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 /** 229 237 @defgroup paths Path Structures 230 238 @ingroup datas … … 276 284 This group contains the algorithms for finding shortest paths in digraphs. 277 285 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. 280 296 - \ref Suurballe A successive shortest path algorithm for finding 281 297 arc-disjoint paths between two nodes having minimum total length. … … 302 318 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] 303 319 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 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. 308 330 309 331 \ref Circulation is a preflow push-relabel algorithm implemented directly … … 323 345 solution see \ref min_cost_flow "Minimum Cost Flow Problem". 324 346 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. 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). 328 361 */ 329 362 … … 349 382 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut 350 383 in directed graphs. 384 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for 385 calculating minimum cut in undirected graphs. 351 386 - \ref GomoryHu "Gomory-Hu tree computation" for calculating 352 387 all-pairs minimum cut in undirected graphs. … … 369 404 370 405 /** 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 /** 371 418 @defgroup matching Matching Algorithms 372 419 @ingroup algs 373 420 \brief Algorithms for finding matchings in graphs and bipartite graphs. 374 421 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. 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. 378 426 379 427 There are several different algorithms for calculate matchings in 380 graphs. The goal of the matching optimization 428 graphs. The matching problems in bipartite graphs are generally 429 easier than in general graphs. The goal of the matching optimization 381 430 can be finding maximum cardinality, maximum weight or minimum cost 382 431 matching. The search can be constrained to find perfect or … … 384 433 385 434 The 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. 386 445 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating 387 446 maximum cardinality matching in general graphs. … … 415 474 416 475 /** 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 /** 417 485 @defgroup gen_opt_group General Optimization Tools 418 486 \brief This group contains some general optimization frameworks … … 431 499 various LP solvers could be used in the same manner with this 432 500 interface. 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. 433 518 */ 434 519 -
lemon/Makefile.am
r716 r666 91 91 lemon/lp_base.h \ 92 92 lemon/lp_skeleton.h \ 93 lemon/list_graph.h \ 93 94 lemon/maps.h \ 94 95 lemon/matching.h \ -
lemon/bits/edge_set_extender.h
r725 r609 281 281 typedef EdgeSetExtender Graph; 282 282 283 typedef True UndirectedTag;284 285 283 typedef typename Parent::Node Node; 286 284 typedef typename Parent::Arc Arc; … … 540 538 541 539 public: 542 explicitArcMap(const Graph& _g)540 ArcMap(const Graph& _g) 543 541 : Parent(_g) {} 544 542 ArcMap(const Graph& _g, const _Value& _v) … … 564 562 565 563 public: 566 explicitEdgeMap(const Graph& _g)564 EdgeMap(const Graph& _g) 567 565 : Parent(_g) {} 568 566 -
lemon/bits/graph_adaptor_extender.h
r724 r609 182 182 typedef GraphAdaptorExtender Adaptor; 183 183 184 typedef True UndirectedTag;185 186 184 typedef typename Parent::Node Node; 187 185 typedef typename Parent::Arc Arc; -
lemon/bits/graph_extender.h
r686 r609 605 605 606 606 public: 607 explicitNodeMap(const Graph& graph)607 NodeMap(const Graph& graph) 608 608 : Parent(graph) {} 609 609 NodeMap(const Graph& graph, const _Value& value) … … 629 629 630 630 public: 631 explicitArcMap(const Graph& graph)631 ArcMap(const Graph& graph) 632 632 : Parent(graph) {} 633 633 ArcMap(const Graph& graph, const _Value& value) … … 653 653 654 654 public: 655 explicitEdgeMap(const Graph& graph)655 EdgeMap(const Graph& graph) 656 656 : Parent(graph) {} 657 657 -
lemon/bits/map_extender.h
r716 r609 83 83 typedef typename Map::Value Value; 84 84 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); 91 91 } 92 92 93 93 MapIt(const Map& _map, const Item& item) 94 : Parent(item), map( &_map) {}94 : Parent(item), map(_map) {} 95 95 96 96 MapIt& operator++() { 97 map ->notifier()->next(*this);97 map.notifier()->next(*this); 98 98 return *this; 99 99 } 100 100 101 101 typename MapTraits<Map>::ConstReturnValue operator*() const { 102 return (*map)[*this];102 return map[*this]; 103 103 } 104 104 105 105 typename MapTraits<Map>::ReturnValue operator*() { 106 return (*map)[*this];106 return map[*this]; 107 107 } 108 108 109 109 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; 115 115 116 116 }; … … 123 123 typedef typename Map::Value Value; 124 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);125 ConstMapIt() {} 126 127 ConstMapIt(Invalid i) : Parent(i) { } 128 129 explicit ConstMapIt(Map& _map) : map(_map) { 130 map.notifier()->first(*this); 131 131 } 132 132 … … 135 135 136 136 ConstMapIt& operator++() { 137 map ->notifier()->next(*this);137 map.notifier()->next(*this); 138 138 return *this; 139 139 } … … 144 144 145 145 protected: 146 const Map *map;146 const Map& map; 147 147 }; 148 148 … … 151 151 152 152 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); 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 *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() : 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); 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 *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() : 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); 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 *map;287 return map[*this]; 288 } 289 290 protected: 291 const Map& map; 292 292 }; 293 293 … … 296 296 297 297 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); 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 *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
r728 r514 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 predMatrixMap(source, target) == INVALID;126 return source != target; 127 127 } 128 128 -
lemon/core.h
r734 r672 395 395 static void copy(const From& from, Digraph &to, 396 396 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { 397 to.clear();398 397 for (typename From::NodeIt it(from); it != INVALID; ++it) { 399 398 nodeRefMap[it] = to.addNode(); … … 423 422 static void copy(const From& from, Graph &to, 424 423 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { 425 to.clear();426 424 for (typename From::NodeIt it(from); it != INVALID; ++it) { 427 425 nodeRefMap[it] = to.addNode(); -
lemon/dfs.h
r738 r576 558 558 void start(Node t) 559 559 { 560 while ( !emptyQueue() && !(*_reached)[t])560 while ( !emptyQueue() && G->target(_stack[_stack_head])!=t ) 561 561 processNextArc(); 562 562 } … … 1510 1510 /// with addSource() before using this function. 1511 1511 void start(Node t) { 1512 while ( !emptyQueue() && !(*_reached)[t])1512 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t ) 1513 1513 processNextArc(); 1514 1514 } -
lemon/glpk.h
r711 r648 26 26 #include <lemon/lp_base.h> 27 27 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 28 36 namespace lemon { 29 37 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 }50 38 51 39 /// \brief Base interface for the GLPK LP and MIP solver … … 56 44 protected: 57 45 58 _solver_bits::VoidPtr lp; 46 typedef glp_prob LPX; 47 glp_prob* lp; 59 48 60 49 GlpkBase(); … … 134 123 135 124 ///Pointer to the underlying GLPK data structure. 136 _solver_bits::VoidPtrlpx() {return lp;}125 LPX *lpx() {return lp;} 137 126 ///Const pointer to the underlying GLPK data structure. 138 _solver_bits::VoidPtrlpx() const {return lp;}127 const LPX *lpx() const {return lp;} 139 128 140 129 ///Returns the constraint identifier understood by GLPK. -
lemon/graph_to_eps.h
r714 r609 685 685 #else 686 686 os << bits::getWinFormattedDate(); 687 os << std::endl;688 687 #endif 689 688 } 689 os << std::endl; 690 690 691 691 if (_autoArcWidthScale) { -
lemon/maps.h
r684 r609 1903 1903 1904 1904 /// 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 /// 1907 1909 /// The values of the map can be accessed 1908 1910 /// with stl compatible forward iterator. 1909 ///1910 /// This type is not reference map, so it cannot be modified with1911 /// the subscript operator.1912 1911 /// 1913 1912 /// \tparam GR The graph type. … … 1925 1924 template Map<V>::Type Map; 1926 1925 1927 typedef std::m ultimap<V, K> Container;1926 typedef std::map<V, K> Container; 1928 1927 Container _inv_map; 1929 1928 … … 1950 1949 /// iterator on the values of the map. The values can 1951 1950 /// be accessed in the <tt>[beginValue, endValue)</tt> range. 1952 /// They are considered with multiplicity, so each value is1953 /// traversed for each item it is assigned to.1954 1951 class ValueIterator 1955 1952 : public std::iterator<std::forward_iterator_tag, Value> { … … 2004 2001 void set(const Key& key, const Value& val) { 2005 2002 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); 2013 2006 } 2014 _inv_map.insert( std::make_pair(val, key));2007 _inv_map.insert(make_pair(val, key)); 2015 2008 Map::set(key, val); 2016 2009 } … … 2024 2017 } 2025 2018 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); 2034 2024 return it != _inv_map.end() ? it->second : INVALID; 2035 2025 } … … 2043 2033 virtual void erase(const Key& key) { 2044 2034 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); 2052 2038 } 2053 2039 Map::erase(key); … … 2061 2047 for (int i = 0; i < int(keys.size()); ++i) { 2062 2048 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); 2070 2052 } 2071 2053 } … … 2103 2085 /// \brief Subscript operator. 2104 2086 /// 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. 2108 2089 Value operator[](const Key& key) const { 2109 2090 return _inverted(key); -
lemon/path.h
r709 r550 71 71 template <typename CPath> 72 72 Path(const CPath& cpath) { 73 pathCopy(cpath, *this);73 copyPath(*this, cpath); 74 74 } 75 75 … … 79 79 template <typename CPath> 80 80 Path& operator=(const CPath& cpath) { 81 pathCopy(cpath, *this);81 copyPath(*this, cpath); 82 82 return *this; 83 83 } … … 259 259 template <typename CPath> 260 260 SimplePath(const CPath& cpath) { 261 pathCopy(cpath, *this);261 copyPath(*this, cpath); 262 262 } 263 263 … … 268 268 template <typename CPath> 269 269 SimplePath& operator=(const CPath& cpath) { 270 pathCopy(cpath, *this);270 copyPath(*this, cpath); 271 271 return *this; 272 272 } … … 438 438 template <typename CPath> 439 439 ListPath(const CPath& cpath) : first(0), last(0) { 440 pathCopy(cpath, *this);440 copyPath(*this, cpath); 441 441 } 442 442 … … 454 454 template <typename CPath> 455 455 ListPath& operator=(const CPath& cpath) { 456 pathCopy(cpath, *this);456 copyPath(*this, cpath); 457 457 return *this; 458 458 } … … 764 764 template <typename CPath> 765 765 StaticPath(const CPath& cpath) : arcs(0) { 766 pathCopy(cpath, *this);766 copyPath(*this, cpath); 767 767 } 768 768 … … 780 780 template <typename CPath> 781 781 StaticPath& operator=(const CPath& cpath) { 782 pathCopy(cpath, *this);782 copyPath(*this, cpath); 783 783 return *this; 784 784 } … … 929 929 }; 930 930 931 template <typename From, typename To,932 bool buildEnable = BuildTagIndicator<T o>::value>931 template <typename Target, typename Source, 932 bool buildEnable = BuildTagIndicator<Target>::value> 933 933 struct PathCopySelectorForward { 934 static void copy( const From& from, To& to) {935 t o.clear();936 for (typename From::ArcIt it(from); it != INVALID; ++it) {937 t o.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); 938 938 } 939 939 } 940 940 }; 941 941 942 template <typename From, typename To>943 struct PathCopySelectorForward< From, To, true> {944 static void copy( const From& from, To& to) {945 t o.clear();946 t o.build(from);947 } 948 }; 949 950 template <typename From, typename To,951 bool buildEnable = BuildTagIndicator<T o>::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> 952 952 struct PathCopySelectorBackward { 953 static void copy( const From& from, To& to) {954 t o.clear();955 for (typename From::RevArcIt it(from); it != INVALID; ++it) {956 t o.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); 957 957 } 958 958 } 959 959 }; 960 960 961 template <typename From, typename To>962 struct PathCopySelectorBackward< From, To, true> {963 static void copy( const From& from, To& to) {964 t o.clear();965 t o.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); 966 966 } 967 967 }; 968 968 969 969 970 template <typename From, typename To,971 bool revEnable = RevPathTagIndicator< From>::value>970 template <typename Target, typename Source, 971 bool revEnable = RevPathTagIndicator<Source>::value> 972 972 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); 975 975 } 976 976 }; 977 977 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); 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 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); 1003 995 } 1004 996 … … 1024 1016 /// \brief The source of a path 1025 1017 /// 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. 1028 1019 template <typename Digraph, typename Path> 1029 1020 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()); 1031 1022 } 1032 1023 1033 1024 /// \brief The target of a path 1034 1025 /// 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. 1037 1027 template <typename Digraph, typename Path> 1038 1028 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()); 1040 1030 } 1041 1031 -
lemon/suurballe.h
r719 r718 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 Successive Shortest Path49 /// algorithm directly for this problem.48 /// efficient specialized version of the \ref CapacityScaling 49 /// "Successive Shortest Path" 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
r738 r577 51 51 "@attributes\n" 52 52 "source 0\n" 53 "target 5\n" 54 "source1 6\n" 55 "target1 3\n"; 56 53 "target 5\n"; 57 54 58 55 void checkDfsCompile() … … 183 180 Digraph G; 184 181 Node s, t; 185 Node s1, t1;186 182 187 183 std::istringstream input(test_lgf); … … 189 185 node("source", s). 190 186 node("target", t). 191 node("source1", s1).192 node("target1", t1).193 187 run(); 194 188 … … 217 211 218 212 { 219 Dfs<Digraph> dfs(G);220 check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");221 }222 223 {224 213 NullMap<Node,Arc> myPredMap; 225 214 dfs(G).predMap(myPredMap).run(s); -
test/graph_copy_test.cc
r734 r440 30 30 const int nn = 10; 31 31 32 // Build a digraph33 32 SmartDigraph from; 34 33 SmartDigraph::NodeMap<int> fnm(from); … … 53 52 } 54 53 55 // Test digraph copy56 54 ListDigraph to; 57 55 ListDigraph::NodeMap<int> tnm(to); … … 71 69 nodeCrossRef(ncr).arcCrossRef(ecr). 72 70 node(fn, tn).arc(fa, ta).run(); 73 74 check(countNodes(from) == countNodes(to), "Wrong copy.");75 check(countArcs(from) == countArcs(to), "Wrong copy.");76 71 77 72 for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) { … … 96 91 check(tn == nr[fn], "Wrong copy."); 97 92 check(ta == er[fa], "Wrong copy."); 98 99 // Test repeated copy100 digraphCopy(from, to).run();101 102 check(countNodes(from) == countNodes(to), "Wrong copy.");103 check(countArcs(from) == countArcs(to), "Wrong copy.");104 93 } 105 94 … … 107 96 const int nn = 10; 108 97 109 // Build a graph110 98 SmartGraph from; 111 99 SmartGraph::NodeMap<int> fnm(from); … … 135 123 } 136 124 137 // Test graph copy138 125 ListGraph to; 139 126 ListGraph::NodeMap<int> tnm(to); … … 157 144 nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr). 158 145 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.");163 146 164 147 for (SmartGraph::NodeIt it(from); it != INVALID; ++it) { … … 198 181 check(ta == ar[fa], "Wrong copy."); 199 182 check(te == er[fe], "Wrong copy."); 200 201 // Test repeated copy202 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.");207 183 } 208 184 -
test/maps_test.cc
r684 r477 23 23 #include <lemon/concepts/maps.h> 24 24 #include <lemon/maps.h> 25 #include <lemon/list_graph.h>26 25 27 26 #include "test_tools.h" … … 350 349 check(v1[i++] == *it, "Something is wrong with LoggerBoolMap"); 351 350 } 352 353 // CrossRefMap354 {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 }386 351 387 352 return 0;
Note: See TracChangeset
for help on using the changeset viewer.