Changes in / [1054:632a72b27123:1053:64260c0f58eb] in lemon
- Files:
-
- 1 added
- 2 deleted
- 23 edited
Legend:
- Unmodified
- Added
- Removed
-
NEWS
r1003 r712 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 -
configure.ac
r1037 r727 99 99 dnl Add dependencies on files generated by configure. 100 100 AC_SUBST([CONFIG_STATUS_DEPENDENCIES], 101 ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/ doc/mainpage.dox.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])101 ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in']) 102 102 103 103 AC_CONFIG_FILES([ … … 106 106 cmake/version.cmake 107 107 doc/Doxyfile 108 doc/mainpage.dox109 108 lemon/lemon.pc 110 109 ]) -
doc/CMakeLists.txt
r1037 r1033 9 9 ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in 10 10 ${PROJECT_BINARY_DIR}/doc/Doxyfile 11 @ONLY12 )13 14 CONFIGURE_FILE(15 ${PROJECT_SOURCE_DIR}/doc/mainpage.dox.in16 ${PROJECT_BINARY_DIR}/doc/mainpage.dox17 11 @ONLY 18 12 ) -
doc/Doxyfile.in
r1037 r1033 1 # Doxyfile 1. 7.31 # Doxyfile 1.5.9 2 2 3 3 #--------------------------------------------------------------------------- … … 5 5 #--------------------------------------------------------------------------- 6 6 DOXYFILE_ENCODING = UTF-8 7 PROJECT_NAME = 8 PROJECT_NUMBER = 9 PROJECT_BRIEF = 10 PROJECT_LOGO = 7 PROJECT_NAME = @PACKAGE_NAME@ 8 PROJECT_NUMBER = @PACKAGE_VERSION@ 11 9 OUTPUT_DIRECTORY = 12 10 CREATE_SUBDIRS = NO … … 32 30 OPTIMIZE_FOR_FORTRAN = NO 33 31 OPTIMIZE_OUTPUT_VHDL = NO 34 EXTENSION_MAPPING =35 32 BUILTIN_STL_SUPPORT = YES 36 33 CPP_CLI_SUPPORT = NO … … 58 55 HIDE_SCOPE_NAMES = YES 59 56 SHOW_INCLUDE_FILES = YES 60 FORCE_LOCAL_INCLUDES = NO61 57 INLINE_INFO = YES 62 58 SORT_MEMBER_DOCS = NO 63 59 SORT_BRIEF_DOCS = NO 64 SORT_MEMBERS_CTORS_1ST = NO65 60 SORT_GROUP_NAMES = NO 66 61 SORT_BY_SCOPE_NAME = NO 67 STRICT_PROTO_MATCHING = NO68 62 GENERATE_TODOLIST = YES 69 63 GENERATE_TESTLIST = YES … … 97 91 "@abs_top_srcdir@/demo" \ 98 92 "@abs_top_srcdir@/tools" \ 99 "@abs_top_srcdir@/test/test_tools.h" \ 100 "@abs_top_builddir@/doc/mainpage.dox" 93 "@abs_top_srcdir@/test/test_tools.h" 101 94 INPUT_ENCODING = UTF-8 102 95 FILE_PATTERNS = *.h \ … … 118 111 FILTER_PATTERNS = 119 112 FILTER_SOURCE_FILES = NO 120 FILTER_SOURCE_PATTERNS =121 113 #--------------------------------------------------------------------------- 122 114 # configuration options related to source browsing … … 145 137 HTML_FOOTER = 146 138 HTML_STYLESHEET = 147 HTML_COLORSTYLE_HUE = 220148 HTML_COLORSTYLE_SAT = 100149 HTML_COLORSTYLE_GAMMA = 80150 HTML_TIMESTAMP = YES151 139 HTML_ALIGN_MEMBERS = YES 152 HTML_DYNAMIC_SECTIONS = YES140 HTML_DYNAMIC_SECTIONS = NO 153 141 GENERATE_DOCSET = NO 154 142 DOCSET_FEEDNAME = "Doxygen generated docs" 155 143 DOCSET_BUNDLE_ID = org.doxygen.Project 156 DOCSET_PUBLISHER_ID = org.doxygen.Publisher157 DOCSET_PUBLISHER_NAME = Publisher158 144 GENERATE_HTMLHELP = NO 159 145 CHM_FILE = … … 167 153 QHP_NAMESPACE = org.doxygen.Project 168 154 QHP_VIRTUAL_FOLDER = doc 169 QHP_CUST_FILTER_NAME =170 QHP_CUST_FILTER_ATTRS =171 QHP_SECT_FILTER_ATTRS =172 155 QHG_LOCATION = 173 GENERATE_ECLIPSEHELP = NO174 ECLIPSE_DOC_ID = org.doxygen.Project175 156 DISABLE_INDEX = NO 176 157 ENUM_VALUES_PER_LINE = 4 177 158 GENERATE_TREEVIEW = NO 178 USE_INLINE_TREES = NO179 159 TREEVIEW_WIDTH = 250 180 EXT_LINKS_IN_WINDOW = NO181 160 FORMULA_FONTSIZE = 10 182 FORMULA_TRANSPARENT = YES183 USE_MATHJAX = NO184 MATHJAX_RELPATH = http://www.mathjax.org/mathjax185 SEARCHENGINE = YES186 SERVER_BASED_SEARCH = NO187 161 #--------------------------------------------------------------------------- 188 162 # configuration options related to the LaTeX output … … 201 175 LATEX_BATCHMODE = NO 202 176 LATEX_HIDE_INDICES = NO 203 LATEX_SOURCE_CODE = NO204 177 #--------------------------------------------------------------------------- 205 178 # configuration options related to the RTF output … … 250 223 SKIP_FUNCTION_MACROS = YES 251 224 #--------------------------------------------------------------------------- 252 # Configuration::additions related to external references225 # Options related to the search engine 253 226 #--------------------------------------------------------------------------- 254 227 TAGFILES = "@abs_top_builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/ " … … 264 237 HIDE_UNDOC_RELATIONS = YES 265 238 HAVE_DOT = YES 266 DOT_NUM_THREADS = 0267 239 DOT_FONTNAME = FreeSans 268 240 DOT_FONTSIZE = 10 … … 282 254 DOT_PATH = 283 255 DOTFILE_DIRS = 284 MSCFILE_DIRS =285 256 DOT_GRAPH_MAX_NODES = 50 286 257 MAX_DOT_GRAPH_DEPTH = 0 … … 289 260 GENERATE_LEGEND = YES 290 261 DOT_CLEANUP = YES 262 #--------------------------------------------------------------------------- 263 # Configuration::additions related to the search engine 264 #--------------------------------------------------------------------------- 265 SEARCHENGINE = NO -
doc/DoxygenLayout.xml
r1036 r316 3 3 <navindex> 4 4 <tab type="mainpage" visible="yes" title=""/> 5 <tab type="modules" visible="yes" title="" intro=""/>5 <tab type="modules" visible="yes" title=""/> 6 6 <tab type="classes" visible="yes" title=""> 7 <tab type="classes" visible="yes" title="" intro=""/>8 <tab type="classindex" visible="$ALPHABETICAL_INDEX" title=""/> 9 <tab type="hierarchy" visible="yes" title="" intro=""/>10 <tab type="classmembers" visible="yes" title="" intro=""/>7 <tab type="classes" visible="yes" title=""/> 8 <tab type="classindex" visible="$ALPHABETICAL_INDEX" title=""/> 9 <tab type="hierarchy" visible="yes" title=""/> 10 <tab type="classmembers" visible="yes" title=""/> 11 11 </tab> 12 12 <tab type="namespaces" visible="yes" title=""> 13 <tab type="namespaces" visible="yes" title="" intro=""/>14 <tab type="namespacemembers" visible="yes" title="" intro=""/>13 <tab type="namespaces" visible="yes" title=""/> 14 <tab type="namespacemembers" visible="yes" title=""/> 15 15 </tab> 16 16 <tab type="files" visible="yes" title=""> 17 <tab type="files" visible="yes" title="" intro=""/>18 <tab type="globals" visible="yes" title="" intro=""/>17 <tab type="files" visible="yes" title=""/> 18 <tab type="globals" visible="yes" title=""/> 19 19 </tab> 20 <tab type="dirs" visible="yes" title="" intro=""/>21 <tab type="examples" visible="yes" title="" intro=""/>22 <tab type="pages" visible="yes" title="" intro=""/>20 <tab type="dirs" visible="yes" title=""/> 21 <tab type="examples" visible="yes" title=""/> 22 <tab type="pages" visible="yes" title=""/> 23 23 </navindex> 24 24 -
doc/groups.dox
r844 r710 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
r913 r714 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
r967 r664 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
r965 r664 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
r732 r664 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
r913 r664 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
r973 r576 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
r984 r718 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
r1009 r631 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
r900 r697 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
r908 r664 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
r731 r664 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
r868 r606 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
r928 r925 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/CMakeLists.txt
r1044 r1033 7 7 ${PROJECT_BINARY_DIR}/lemon 8 8 ) 9 10 SET(TEST_WITH_VALGRIND "NO" CACHE STRING11 "Run the test with valgrind (YES/NO).")12 SET(VALGRIND_FLAGS "" CACHE STRING "Valgrind flags used by the tests.")13 9 14 10 SET(TESTS … … 134 130 ENDIF() 135 131 TARGET_LINK_LIBRARIES(${TEST_NAME} lemon) 136 IF(TEST_WITH_VALGRIND) 137 ADD_TEST(${TEST_NAME} 138 valgrind --error-exitcode=1 ${VALGRIND_FLAGS} 139 ${CMAKE_CURRENT_BINARY_DIR}/${TEST_NAME} ) 140 ELSE() 141 ADD_TEST(${TEST_NAME} ${TEST_NAME}) 142 ENDIF() 132 ADD_TEST(${TEST_NAME} ${TEST_NAME}) 143 133 ADD_DEPENDENCIES(check ${TEST_NAME}) 144 134 ENDFOREACH() -
test/dfs_test.cc
r1009 r632 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
r984 r463 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
r731 r554 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.