Changes in / [788:c92296660262:786:e20173729589] in lemon-main
- Files:
-
- 5 deleted
- 29 edited
Legend:
- Unmodified
- Added
- Removed
-
Makefile.am
r752 r629 18 18 cmake/FindGLPK.cmake \ 19 19 cmake/FindCOIN.cmake \ 20 cmake/LEMONConfig.cmake.in \21 20 cmake/version.cmake.in \ 22 21 cmake/version.cmake \ -
doc/Doxyfile.in
r756 r744 1 # Doxyfile 1.5. 91 # Doxyfile 1.5.7.1 2 2 3 3 #--------------------------------------------------------------------------- … … 22 22 QT_AUTOBRIEF = NO 23 23 MULTILINE_CPP_IS_BRIEF = NO 24 DETAILS_AT_TOP = YES 24 25 INHERIT_DOCS = NO 25 26 SEPARATE_MEMBER_PAGES = NO … … 224 225 SKIP_FUNCTION_MACROS = YES 225 226 #--------------------------------------------------------------------------- 226 # Options related to the search engine227 # Configuration::additions related to external references 227 228 #--------------------------------------------------------------------------- 228 229 TAGFILES = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/ " -
doc/groups.dox
r771 r742 317 317 318 318 This group contains the common graph search algorithms, namely 319 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS) 320 \ref clrs01algorithms. 319 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS). 321 320 */ 322 321 … … 326 325 \brief Algorithms for finding shortest paths. 327 326 328 This group contains the algorithms for finding shortest paths in digraphs 329 \ref clrs01algorithms. 327 This group contains the algorithms for finding shortest paths in digraphs. 330 328 331 329 - \ref Dijkstra algorithm for finding shortest paths from a source node … … 349 347 350 348 This group contains the algorithms for finding minimum cost spanning 351 trees and arborescences \ref clrs01algorithms.349 trees and arborescences. 352 350 */ 353 351 … … 358 356 359 357 This group contains the algorithms for finding maximum flows and 360 feasible circulations \ref clrs01algorithms, \ref amo93networkflows.358 feasible circulations. 361 359 362 360 The \e maximum \e flow \e problem is to find a flow of maximum value between … … 373 371 374 372 LEMON contains several algorithms for solving maximum flow problems: 375 - \ref EdmondsKarp Edmonds-Karp algorithm 376 \ref edmondskarp72theoretical. 377 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm 378 \ref goldberg88newapproach. 379 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees 380 \ref dinic70algorithm, \ref sleator83dynamic. 381 - \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees 382 \ref goldberg88newapproach, \ref sleator83dynamic. 383 384 In most cases the \ref Preflow algorithm provides the 373 - \ref EdmondsKarp Edmonds-Karp algorithm. 374 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm. 375 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. 376 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees. 377 378 In most cases the \ref Preflow "Preflow" algorithm provides the 385 379 fastest method for computing a maximum flow. All implementations 386 380 also provide functions to query the minimum cut, which is the dual … … 400 394 401 395 This group contains the algorithms for finding minimum cost flows and 402 circulations \ref amo93networkflows. For more information about this 403 problem and its dual solution, see \ref min_cost_flow 404 "Minimum Cost Flow Problem". 396 circulations. For more information about this problem and its dual 397 solution see \ref min_cost_flow "Minimum Cost Flow Problem". 405 398 406 399 LEMON contains several algorithms for this problem. 407 400 - \ref NetworkSimplex Primal Network Simplex algorithm with various 408 pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.401 pivot strategies. 409 402 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on 410 cost scaling \ref goldberg90approximation, \ref goldberg97efficient, 411 \ref bunnagel98efficient. 403 cost scaling. 412 404 - \ref CapacityScaling Successive Shortest %Path algorithm with optional 413 capacity scaling \ref edmondskarp72theoretical. 414 - \ref CancelAndTighten The Cancel and Tighten algorithm 415 \ref goldberg89cyclecanceling. 416 - \ref CycleCanceling Cycle-Canceling algorithms 417 \ref klein67primal, \ref goldberg89cyclecanceling. 405 capacity scaling. 406 - \ref CancelAndTighten The Cancel and Tighten algorithm. 407 - \ref CycleCanceling Cycle-Canceling algorithms. 418 408 419 409 In general NetworkSimplex is the most efficient implementation, … … 451 441 If you want to find minimum cut just between two distinict nodes, 452 442 see the \ref max_flow "maximum flow problem". 453 */454 455 /**456 @defgroup min_mean_cycle Minimum Mean Cycle Algorithms457 @ingroup algs458 \brief Algorithms for finding minimum mean cycles.459 460 This group contains the algorithms for finding minimum mean cycles461 \ref clrs01algorithms, \ref amo93networkflows.462 463 The \e minimum \e mean \e cycle \e problem is to find a directed cycle464 of minimum mean length (cost) in a digraph.465 The mean length of a cycle is the average length of its arcs, i.e. the466 ratio between the total length of the cycle and the number of arcs on it.467 468 This problem has an important connection to \e conservative \e length469 \e functions, too. A length function on the arcs of a digraph is called470 conservative if and only if there is no directed cycle of negative total471 length. For an arbitrary length function, the negative of the minimum472 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the473 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length474 function.475 476 LEMON contains three algorithms for solving the minimum mean cycle problem:477 - \ref Karp "Karp"'s original algorithm \ref amo93networkflows,478 \ref dasdan98minmeancycle.479 - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved480 version of Karp's algorithm \ref dasdan98minmeancycle.481 - \ref Howard "Howard"'s policy iteration algorithm482 \ref dasdan98minmeancycle.483 484 In practice, the Howard algorithm proved to be by far the most efficient485 one, though the best known theoretical bound on its running time is486 exponential.487 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space488 O(n<sup>2</sup>+e), but the latter one is typically faster due to the489 applied early termination scheme.490 443 */ 491 444 … … 582 535 583 536 /** 584 @defgroup lp_group L P and MIPSolvers537 @defgroup lp_group Lp and Mip Solvers 585 538 @ingroup gen_opt_group 586 \brief LP and MIP solver interfaces for LEMON. 587 588 This group contains LP and MIP solver interfaces for LEMON. 589 Various LP solvers could be used in the same manner with this 590 high-level interface. 591 592 The currently supported solvers are \ref glpk, \ref clp, \ref cbc, 593 \ref cplex, \ref soplex. 539 \brief Lp and Mip solver interfaces for LEMON. 540 541 This group contains Lp and Mip solver interfaces for LEMON. The 542 various LP solvers could be used in the same manner with this 543 interface. 594 544 */ 595 545 -
doc/mainpage.dox
r755 r658 22 22 \section intro Introduction 23 23 24 <b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling 25 and <b>O</b>ptimization in <b>N</b>etworks</i>. 26 It is a C++ template library providing efficient implementation of common 27 data structures and algorithms with focus on combinatorial optimization 28 problems in graphs and networks. 24 \subsection whatis What is LEMON 25 26 LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling 27 and <b>O</b>ptimization in <b>N</b>etworks. 28 It is a C++ template 29 library aimed at combinatorial optimization tasks which 30 often involve in working 31 with graphs. 29 32 30 33 <b> … … 36 39 </b> 37 40 38 The project is maintained by the 39 <a href="http://www.cs.elte.hu/egres/">Egerváry Research Group on 40 Combinatorial Optimization</a> \ref egres 41 at the Operations Research Department of the 42 <a href="http://www.elte.hu/">Eötvös Loránd University, 43 Budapest</a>, Hungary. 44 LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a> 45 initiative \ref coinor. 46 47 \section howtoread How to Read the Documentation 41 \subsection howtoread How to read the documentation 48 42 49 43 If you would like to get to know the library, see -
doc/min_cost_flow.dox
r788 r786 27 27 minimum total cost from a set of supply nodes to a set of demand nodes 28 28 in a network with capacity constraints (lower and upper bounds) 29 and arc costs \ref amo93networkflows.29 and arc costs. 30 30 31 31 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$, -
doc/references.bib
r755 r743 13 13 title = {{EGRES} -- {E}gerv{\'a}ry {R}esearch {G}roup on 14 14 {C}ombinatorial {O}ptimization}, 15 url = {http://www.cs.elte.hu/egres/} 15 howpublished = {\url{http://www.cs.elte.hu/egres/}}, 16 year = 2009 16 17 } 17 18 … … 20 21 title = {{COIN-OR} -- {C}omputational {I}nfrastructure for 21 22 {O}perations {R}esearch}, 22 url = {http://www.coin-or.org/} 23 howpublished = {\url{http://www.coin-or.org/}}, 24 year = 2009 23 25 } 24 26 … … 29 31 key = {Boost}, 30 32 title = {{B}oost {C++} {L}ibraries}, 31 url = {http://www.boost.org/} 33 howpublished = {\url{http://www.boost.org/}}, 34 year = 2009 32 35 } 33 36 … … 45 48 title = {{LEDA} -- {L}ibrary of {E}fficient {D}ata {T}ypes and 46 49 {A}lgorithms}, 47 url = {http://www.algorithmic-solutions.com/} 50 howpublished = {\url{http://www.algorithmic-solutions.com/}}, 51 year = 2009 48 52 } 49 53 … … 64 68 key = {CMake}, 65 69 title = {{CMake} -- {C}ross {P}latform {M}ake}, 66 url = {http://www.cmake.org/} 70 howpublished = {\url{http://www.cmake.org/}}, 71 year = 2009 67 72 } 68 73 … … 71 76 title = {{Doxygen} -- {S}ource code documentation generator 72 77 tool}, 73 url = {http://www.doxygen.org/} 78 howpublished = {\url{http://www.doxygen.org/}}, 79 year = 2009 74 80 } 75 81 … … 80 86 key = {GLPK}, 81 87 title = {{GLPK} -- {GNU} {L}inear {P}rogramming {K}it}, 82 url = {http://www.gnu.org/software/glpk/} 88 howpublished = {\url{http://www.gnu.org/software/glpk/}}, 89 year = 2009 83 90 } 84 91 … … 86 93 key = {Clp}, 87 94 title = {{Clp} -- {Coin-Or} {L}inear {P}rogramming}, 88 url = {http://projects.coin-or.org/Clp/} 95 howpublished = {\url{http://projects.coin-or.org/Clp/}}, 96 year = 2009 89 97 } 90 98 … … 92 100 key = {Cbc}, 93 101 title = {{Cbc} -- {Coin-Or} {B}ranch and {C}ut}, 94 url = {http://projects.coin-or.org/Cbc/} 102 howpublished = {\url{http://projects.coin-or.org/Cbc/}}, 103 year = 2009 95 104 } 96 105 … … 98 107 key = {CPLEX}, 99 108 title = {{ILOG} {CPLEX}}, 100 url = {http://www.ilog.com/} 109 howpublished = {\url{http://www.ilog.com/}}, 110 year = 2009 101 111 } 102 112 … … 105 115 title = {{SoPlex} -- {T}he {S}equential {O}bject-{O}riented 106 116 {S}implex}, 107 url = {http://soplex.zib.de/} 117 howpublished = {\url{http://soplex.zib.de/}}, 118 year = 2009 108 119 } 109 120 … … 151 162 %%%%% Maximum flow algorithms %%%%% 152 163 153 @article{edmondskarp72theoretical, 154 author = {Jack Edmonds and Richard M. Karp}, 155 title = {Theoretical improvements in algorithmic efficiency 156 for network flow problems}, 157 journal = {Journal of the ACM}, 158 year = 1972, 159 volume = 19, 160 number = 2, 161 pages = {248-264} 162 } 163 164 @article{goldberg88newapproach, 164 @inproceedings{goldberg86newapproach, 165 165 author = {Andrew V. Goldberg and Robert E. Tarjan}, 166 166 title = {A new approach to the maximum flow problem}, 167 journal = {Journal of the ACM}, 168 year = 1988, 169 volume = 35, 170 number = 4, 171 pages = {921-940} 167 booktitle = {STOC '86: Proceedings of the Eighteenth Annual ACM 168 Symposium on Theory of Computing}, 169 year = 1986, 170 publisher = {ACM Press}, 171 address = {New York, NY}, 172 pages = {136-146} 172 173 } 173 174 … … 240 241 } 241 242 242 @ article{goldberg89cyclecanceling,243 @inproceedings{goldberg88cyclecanceling, 243 244 author = {Andrew V. Goldberg and Robert E. Tarjan}, 244 245 title = {Finding minimum-cost circulations by canceling 245 246 negative cycles}, 247 booktitle = {STOC '88: Proceedings of the Twentieth Annual ACM 248 Symposium on Theory of Computing}, 249 year = 1988, 250 publisher = {ACM Press}, 251 address = {New York, NY}, 252 pages = {388-397} 253 } 254 255 @article{edmondskarp72theoretical, 256 author = {Jack Edmonds and Richard M. Karp}, 257 title = {Theoretical improvements in algorithmic efficiency 258 for network flow problems}, 246 259 journal = {Journal of the ACM}, 247 year = 1989, 248 volume = 36, 249 number = 4, 250 pages = {873-886} 251 } 252 253 @article{goldberg90approximation, 260 year = 1972, 261 volume = 19, 262 number = 2, 263 pages = {248-264} 264 } 265 266 @inproceedings{goldberg87approximation, 267 author = {Andrew V. Goldberg and Robert E. Tarjan}, 268 title = {Solving minimum-cost flow problems by successive 269 approximation}, 270 booktitle = {STOC '87: Proceedings of the Nineteenth Annual ACM 271 Symposium on Theory of Computing}, 272 year = 1987, 273 publisher = {ACM Press}, 274 address = {New York, NY}, 275 pages = {7-18} 276 } 277 278 @article{goldberg90finding, 254 279 author = {Andrew V. Goldberg and Robert E. Tarjan}, 255 280 title = {Finding Minimum-Cost Circulations by Successive … … 284 309 } 285 310 286 @book{dantzig63linearprog,287 author = {George B. Dantzig},288 title = {Linear Programming and Extensions},289 publisher = {Princeton University Press},290 year = 1963291 }292 293 311 @mastersthesis{kellyoneill91netsimplex, 294 312 author = {Damian J. Kelly and Garrett M. O'Neill}, … … 300 318 month = sep, 301 319 } 320 321 @techreport{lobel96networksimplex, 322 author = {Andreas L{\"o}bel}, 323 title = {Solving large-scale real-world minimum-cost flow 324 problems by a network simplex method}, 325 institution = {Konrad-Zuse-Zentrum fur Informationstechnik Berlin 326 ({ZIB})}, 327 address = {Berlin, Germany}, 328 year = 1996, 329 number = {SC 96-7} 330 } 331 332 @article{frangioni06computational, 333 author = {Antonio Frangioni and Antonio Manca}, 334 title = {A Computational Study of Cost Reoptimization for 335 Min-Cost Flow Problems}, 336 journal = {INFORMS Journal On Computing}, 337 year = 2006, 338 volume = 18, 339 number = 1, 340 pages = {61-70} 341 } -
lemon/Makefile.am
r780 r708 87 87 lemon/graph_to_eps.h \ 88 88 lemon/grid_graph.h \ 89 lemon/hartmann_orlin.h \90 lemon/howard.h \91 89 lemon/hypercube_graph.h \ 92 lemon/karp.h \93 90 lemon/kary_heap.h \ 94 91 lemon/kruskal.h \ … … 114 111 lemon/smart_graph.h \ 115 112 lemon/soplex.h \ 116 lemon/static_graph.h \117 113 lemon/suurballe.h \ 118 114 lemon/time_measure.h \ -
lemon/adaptors.h
r787 r656 361 361 /// parameter is set to be \c const. 362 362 /// 363 /// This class provides item counting in the same time as the adapted364 /// digraph structure.365 ///366 363 /// \tparam DGR The type of the adapted digraph. 367 364 /// It must conform to the \ref concepts::Digraph "Digraph" concept. … … 722 719 /// by adding or removing nodes or arcs, unless the \c GR template 723 720 /// parameter is set to be \c const. 724 ///725 /// This class provides only linear time counting for nodes and arcs.726 721 /// 727 722 /// \tparam DGR The type of the adapted digraph. … … 1320 1315 /// parameter is set to be \c const. 1321 1316 /// 1322 /// This class provides only linear time counting for nodes, edges and arcs.1323 ///1324 1317 /// \tparam GR The type of the adapted graph. 1325 1318 /// It must conform to the \ref concepts::Graph "Graph" concept. … … 1478 1471 /// by adding or removing nodes or arcs/edges, unless the \c GR template 1479 1472 /// parameter is set to be \c const. 1480 ///1481 /// This class provides only linear time item counting.1482 1473 /// 1483 1474 /// \tparam GR The type of the adapted digraph or graph. … … 1629 1620 /// parameter is set to be \c const. 1630 1621 /// 1631 /// This class provides only linear time counting for nodes and arcs.1632 ///1633 1622 /// \tparam DGR The type of the adapted digraph. 1634 1623 /// It must conform to the \ref concepts::Digraph "Digraph" concept. … … 1740 1729 /// by adding or removing nodes or edges, unless the \c GR template 1741 1730 /// parameter is set to be \c const. 1742 ///1743 /// This class provides only linear time counting for nodes, edges and arcs.1744 1731 /// 1745 1732 /// \tparam GR The type of the adapted graph. … … 2246 2233 /// parameter is set to be \c const. 2247 2234 /// 2248 /// This class provides item counting in the same time as the adapted2249 /// digraph structure.2250 ///2251 2235 /// \tparam DGR The type of the adapted digraph. 2252 2236 /// It must conform to the \ref concepts::Digraph "Digraph" concept. … … 2551 2535 /// by adding or removing nodes or arcs, unless the \c GR template 2552 2536 /// parameter is set to be \c const. 2553 ///2554 /// This class provides item counting in the same time as the adapted2555 /// graph structure.2556 2537 /// 2557 2538 /// \tparam GR The type of the adapted graph. … … 2697 2678 /// arcs). 2698 2679 /// This class conforms to the \ref concepts::Digraph "Digraph" concept. 2699 ///2700 /// This class provides only linear time counting for nodes and arcs.2701 2680 /// 2702 2681 /// \tparam DGR The type of the adapted digraph. … … 3347 3326 /// in the adaptor. 3348 3327 /// 3349 /// This class provides item counting in the same time as the adapted3350 /// digraph structure.3351 ///3352 3328 /// \tparam DGR The type of the adapted digraph. 3353 3329 /// It must conform to the \ref concepts::Digraph "Digraph" concept. -
lemon/bellman_ford.h
r788 r786 24 24 /// \brief Bellman-Ford algorithm. 25 25 26 #include <lemon/list_graph.h>27 26 #include <lemon/bits/path_dump.h> 28 27 #include <lemon/core.h> … … 777 776 /// length if the algorithm has already found one. 778 777 /// Otherwise it gives back an empty path. 779 lemon::Path<Digraph> negativeCycle() const{778 lemon::Path<Digraph> negativeCycle() { 780 779 typename Digraph::template NodeMap<int> state(*_gr, -1); 781 780 lemon::Path<Digraph> cycle; -
lemon/bfs.h
r788 r786 702 702 ///Runs the algorithm to visit all nodes in the digraph. 703 703 704 ///This method runs the %BFS algorithm in order to visit all nodes 705 ///in the digraph. 704 ///This method runs the %BFS algorithm in order to 705 ///compute the shortest path to each node. 706 /// 707 ///The algorithm computes 708 ///- the shortest path tree (forest), 709 ///- the distance of each node from the root(s). 706 710 /// 707 711 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code. … … 1043 1047 ///Runs BFS algorithm to visit all nodes in the digraph. 1044 1048 1045 ///This method runs BFS algorithm in order to visit all nodes1046 /// in the digraph.1049 ///This method runs BFS algorithm in order to compute 1050 ///the shortest path to each node. 1047 1051 void run() 1048 1052 { … … 1692 1696 /// \brief Runs the algorithm to visit all nodes in the digraph. 1693 1697 /// 1694 /// This method runs the %BFS algorithm in order to visit all nodes 1695 /// in the digraph. 1698 /// This method runs the %BFS algorithm in order to 1699 /// compute the shortest path to each node. 1700 /// 1701 /// The algorithm computes 1702 /// - the shortest path tree (forest), 1703 /// - the distance of each node from the root(s). 1696 1704 /// 1697 1705 /// \note <tt>b.run(s)</tt> is just a shortcut of the following code. -
lemon/bits/graph_extender.h
r778 r685 57 57 } 58 58 59 static Node fromId(int id, Node){59 Node fromId(int id, Node) const { 60 60 return Parent::nodeFromId(id); 61 61 } 62 62 63 static Arc fromId(int id, Arc){63 Arc fromId(int id, Arc) const { 64 64 return Parent::arcFromId(id); 65 65 } … … 356 356 } 357 357 358 static Node fromId(int id, Node){358 Node fromId(int id, Node) const { 359 359 return Parent::nodeFromId(id); 360 360 } 361 361 362 static Arc fromId(int id, Arc){362 Arc fromId(int id, Arc) const { 363 363 return Parent::arcFromId(id); 364 364 } 365 365 366 static Edge fromId(int id, Edge){366 Edge fromId(int id, Edge) const { 367 367 return Parent::edgeFromId(id); 368 368 } -
lemon/dfs.h
r788 r786 634 634 ///Runs the algorithm to visit all nodes in the digraph. 635 635 636 ///This method runs the %DFS algorithm in order to visit all nodes 637 ///in the digraph. 636 ///This method runs the %DFS algorithm in order to compute the 637 ///%DFS path to each node. 638 /// 639 ///The algorithm computes 640 ///- the %DFS tree (forest), 641 ///- the distance of each node from the root(s) in the %DFS tree. 638 642 /// 639 643 ///\note <tt>d.run()</tt> is just a shortcut of the following code. … … 973 977 ///Runs DFS algorithm to visit all nodes in the digraph. 974 978 975 ///This method runs DFS algorithm in order to visit all nodes976 /// in the digraph.979 ///This method runs DFS algorithm in order to compute 980 ///the DFS path to each node. 977 981 void run() 978 982 { … … 1575 1579 /// \brief Runs the algorithm to visit all nodes in the digraph. 1576 1580 1577 /// This method runs the %DFS algorithm in order to visit all nodes 1578 /// in the digraph. 1581 /// This method runs the %DFS algorithm in order to 1582 /// compute the %DFS path to each node. 1583 /// 1584 /// The algorithm computes 1585 /// - the %DFS tree (forest), 1586 /// - the distance of each node from the root(s) in the %DFS tree. 1579 1587 /// 1580 1588 /// \note <tt>d.run()</tt> is just a shortcut of the following code. -
lemon/dijkstra.h
r788 r786 207 207 208 208 ///The type of the arc lengths. 209 typedef typename TR:: Value Value;209 typedef typename TR::LengthMap::Value Value; 210 210 ///The type of the map that stores the arc lengths. 211 211 typedef typename TR::LengthMap LengthMap; -
lemon/edge_set.h
r787 r670 256 256 /// all arcs incident to the given node is erased from the arc set. 257 257 /// 258 /// This class fully conforms to the \ref concepts::Digraph259 /// "Digraph" concept.260 /// It provides only linear time counting for nodes and arcs.261 ///262 258 /// \param GR The type of the graph which shares its node set with 263 259 /// this class. Its interface must conform to the 264 260 /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" 265 261 /// concept. 262 /// 263 /// This class fully conforms to the \ref concepts::Digraph 264 /// "Digraph" concept. 266 265 template <typename GR> 267 266 class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > { … … 687 686 /// incident to the given node is erased from the arc set. 688 687 /// 689 /// This class fully conforms to the \ref concepts::Graph "Graph"690 /// concept.691 /// It provides only linear time counting for nodes, edges and arcs.692 ///693 688 /// \param GR The type of the graph which shares its node set 694 689 /// with this class. Its interface must conform to the 695 690 /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" 691 /// concept. 692 /// 693 /// This class fully conforms to the \ref concepts::Graph "Graph" 696 694 /// concept. 697 695 template <typename GR> … … 870 868 } 871 869 872 static void next(Arc& arc){870 void next(Arc& arc) const { 873 871 --arc.id; 874 872 } … … 957 955 /// arcs. Therefore the arcs cannot be erased from the arc sets. 958 956 /// 959 /// This class fully conforms to the \ref concepts::Digraph "Digraph"960 /// concept.961 /// It provides only linear time counting for nodes and arcs.962 ///963 957 /// \warning If a node is erased from the underlying graph and this 964 958 /// node is the source or target of one arc in the arc set, then 965 959 /// the arc set is invalidated, and it cannot be used anymore. The 966 960 /// validity can be checked with the \c valid() member function. 961 /// 962 /// This class fully conforms to the \ref concepts::Digraph 963 /// "Digraph" concept. 967 964 template <typename GR> 968 965 class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > { … … 1177 1174 } 1178 1175 1179 static void next(Arc& arc){1176 void next(Arc& arc) const { 1180 1177 --arc.id; 1181 1178 } … … 1185 1182 } 1186 1183 1187 static void next(Edge& arc){1184 void next(Edge& arc) const { 1188 1185 --arc.id; 1189 1186 } … … 1308 1305 /// edges cannot be erased from the edge sets. 1309 1306 /// 1310 /// This class fully conforms to the \ref concepts::Graph "Graph"1311 /// concept.1312 /// It provides only linear time counting for nodes, edges and arcs.1313 ///1314 1307 /// \warning If a node is erased from the underlying graph and this 1315 1308 /// node is incident to one edge in the edge set, then the edge set 1316 1309 /// is invalidated, and it cannot be used anymore. The validity can 1317 1310 /// be checked with the \c valid() member function. 1311 /// 1312 /// This class fully conforms to the \ref concepts::Graph 1313 /// "Graph" concept. 1318 1314 template <typename GR> 1319 1315 class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > { -
lemon/full_graph.h
r787 r735 52 52 53 53 Node operator()(int ix) const { return Node(ix); } 54 static int index(const Node& node){ return node._id; }54 int index(const Node& node) const { return node._id; } 55 55 56 56 Arc arc(const Node& s, const Node& t) const { … … 163 163 /// only in the concept class. 164 164 /// 165 /// This class provides constant time counting for nodes and arcs.166 ///167 165 /// \note FullDigraph and FullGraph classes are very similar, 168 166 /// but there are two differences. While this class conforms only … … 207 205 /// completely static, the nodes can be indexed with integers from 208 206 /// the range <tt>[0..nodeNum()-1]</tt>. 209 /// The index of a node is the same as its ID.210 207 /// \sa index() 211 208 Node operator()(int ix) const { return Parent::operator()(ix); } … … 216 213 /// completely static, the nodes can be indexed with integers from 217 214 /// the range <tt>[0..nodeNum()-1]</tt>. 218 /// The index of a node is the same as its ID.219 215 /// \sa operator()() 220 static int index(const Node& node){ return Parent::index(node); }216 int index(Node node) const { return Parent::index(node); } 221 217 222 218 /// \brief Returns the arc connecting the given nodes. … … 292 288 293 289 Node operator()(int ix) const { return Node(ix); } 294 static int index(const Node& node){ return node._id; }290 int index(const Node& node) const { return node._id; } 295 291 296 292 Edge edge(const Node& u, const Node& v) const { … … 540 536 /// only in the concept class. 541 537 /// 542 /// This class provides constant time counting for nodes, edges and arcs.543 ///544 538 /// \note FullDigraph and FullGraph classes are very similar, 545 539 /// but there are two differences. While FullDigraph … … 586 580 /// completely static, the nodes can be indexed with integers from 587 581 /// the range <tt>[0..nodeNum()-1]</tt>. 588 /// The index of a node is the same as its ID.589 582 /// \sa index() 590 583 Node operator()(int ix) const { return Parent::operator()(ix); } … … 595 588 /// completely static, the nodes can be indexed with integers from 596 589 /// the range <tt>[0..nodeNum()-1]</tt>. 597 /// The index of a node is the same as its ID.598 590 /// \sa operator()() 599 static int index(const Node& node){ return Parent::index(node); }591 int index(Node node) const { return Parent::index(node); } 600 592 601 593 /// \brief Returns the arc connecting the given nodes. -
lemon/grid_graph.h
r787 r735 504 504 /// Most of its member functions and nested classes are documented 505 505 /// only in the concept class. 506 ///507 /// This class provides constant time counting for nodes, edges and arcs.508 506 class GridGraph : public ExtendedGridGraphBase { 509 507 typedef ExtendedGridGraphBase Parent; -
lemon/hypercube_graph.h
r788 r786 263 263 } 264 264 265 static int index(Node node){265 int index(Node node) const { 266 266 return node._id; 267 267 } … … 295 295 /// only in the concept class. 296 296 /// 297 /// This class provides constant time counting for nodes, edges and arcs.298 ///299 297 /// \note The type of the indices is chosen to \c int for efficiency 300 298 /// reasons. Thus the maximum dimension of this implementation is 26 … … 359 357 /// Gives back the index of the given node. 360 358 /// The lower bits of the integer describes the node. 361 static int index(Node node){359 int index(Node node) const { 362 360 return Parent::index(node); 363 361 } -
lemon/list_graph.h
r788 r786 325 325 ///only in the concept class. 326 326 /// 327 ///This class provides only linear time counting for nodes and arcs.328 ///329 327 ///\sa concepts::Digraph 330 328 ///\sa ListGraph … … 363 361 ///\brief Erase a node from the digraph. 364 362 /// 365 ///This function erases the given node along with its outgoing and 366 ///incoming arcs from the digraph. 367 /// 368 ///\note All iterators referencing the removed node or the connected 369 ///arcs are invalidated, of course. 363 ///This function erases the given node from the digraph. 370 364 void erase(Node n) { Parent::erase(n); } 371 365 … … 373 367 /// 374 368 ///This function erases the given arc from the digraph. 375 ///376 ///\note All iterators referencing the removed arc are invalidated,377 ///of course.378 369 void erase(Arc a) { Parent::erase(a); } 379 370 … … 520 511 ///This function erases all nodes and arcs from the digraph. 521 512 /// 522 ///\note All iterators of the digraph are invalidated, of course.523 513 void clear() { 524 514 Parent::clear(); … … 1190 1180 ///only in the concept class. 1191 1181 /// 1192 ///This class provides only linear time counting for nodes, edges and arcs.1193 ///1194 1182 ///\sa concepts::Graph 1195 1183 ///\sa ListDigraph … … 1230 1218 ///\brief Erase a node from the graph. 1231 1219 /// 1232 /// This function erases the given node along with its incident arcs 1233 /// from the graph. 1234 /// 1235 /// \note All iterators referencing the removed node or the incident 1236 /// edges are invalidated, of course. 1220 /// This function erases the given node from the graph. 1237 1221 void erase(Node n) { Parent::erase(n); } 1238 1222 … … 1240 1224 /// 1241 1225 /// This function erases the given edge from the graph. 1242 ///1243 /// \note All iterators referencing the removed edge are invalidated,1244 /// of course.1245 1226 void erase(Edge e) { Parent::erase(e); } 1246 1227 /// Node validity check … … 1332 1313 ///This function erases all nodes and arcs from the graph. 1333 1314 /// 1334 ///\note All iterators of the graph are invalidated, of course.1335 1315 void clear() { 1336 1316 Parent::clear(); -
lemon/network_simplex.h
r788 r786 41 41 /// 42 42 /// \ref NetworkSimplex implements the primal Network Simplex algorithm 43 /// for finding a \ref min_cost_flow "minimum cost flow" 44 /// \ref amo93networkflows, \ref dantzig63linearprog, 45 /// \ref kellyoneill91netsimplex. 43 /// for finding a \ref min_cost_flow "minimum cost flow". 46 44 /// This algorithm is a specialized version of the linear programming 47 45 /// simplex method directly for the minimum cost flow problem. -
lemon/path.h
r784 r559 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/preflow.h
r788 r786 103 103 /// This class provides an implementation of Goldberg-Tarjan's \e preflow 104 104 /// \e push-relabel algorithm producing a \ref max_flow 105 /// "flow of maximum value" in a digraph \ref clrs01algorithms, 106 /// \ref amo93networkflows, \ref goldberg88newapproach. 105 /// "flow of maximum value" in a digraph. 107 106 /// The preflow algorithms are the fastest known maximum 108 107 /// flow algorithms. The current implementation uses a mixture of the -
lemon/smart_graph.h
r787 r736 195 195 ///only in the concept class. 196 196 /// 197 ///This class provides constant time counting for nodes and arcs.198 ///199 197 ///\sa concepts::Digraph 200 198 ///\sa SmartGraph … … 500 498 } 501 499 502 static void next(Node& node){500 void next(Node& node) const { 503 501 --node._id; 504 502 } … … 508 506 } 509 507 510 static void next(Arc& arc){508 void next(Arc& arc) const { 511 509 --arc._id; 512 510 } … … 516 514 } 517 515 518 static void next(Edge& arc){516 void next(Edge& arc) const { 519 517 --arc._id; 520 518 } … … 623 621 /// only in the concept class. 624 622 /// 625 /// This class provides constant time counting for nodes, edges and arcs.626 ///627 623 /// \sa concepts::Graph 628 624 /// \sa SmartDigraph -
scripts/bib2dox.py
r754 r745 71 71 author_rex = re.compile('\s+and\s+') 72 72 rembraces_rex = re.compile('[{}]') 73 capitalize_rex = re.compile('({ [^}]*})')73 capitalize_rex = re.compile('({\w*})') 74 74 75 75 # used by bibtexkeywords(data) … … 364 364 if entrycont.has_key('note') and (entrycont['note'] != ''): 365 365 entry.append(entrycont['note'] + '.') 366 if entrycont.has_key('url') and (entrycont['url'] != ''):367 entry.append(entrycont['url'] + '.')368 366 369 367 # generate keys for sorting and for the output … … 413 411 field = string.lower(field) 414 412 data = data_rex.sub('\g<2>', line) 415 416 if field == 'url':417 data = '\\url{' + data.strip() + '}'418 413 419 414 if field in ('author', 'editor'): -
test/CMakeLists.txt
r770 r698 33 33 min_cost_arborescence_test 34 34 min_cost_flow_test 35 min_mean_cycle_test36 35 path_test 37 36 preflow_test -
test/Makefile.am
r770 r698 31 31 test/min_cost_arborescence_test \ 32 32 test/min_cost_flow_test \ 33 test/min_mean_cycle_test \34 33 test/path_test \ 35 34 test/preflow_test \ … … 80 79 test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc 81 80 test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc 82 test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc83 81 test_path_test_SOURCES = test/path_test.cc 84 82 test_preflow_test_SOURCES = test/preflow_test.cc -
test/adaptors_test.cc
r515 r465 1372 1372 1373 1373 GridGraph::EdgeMap<bool> dir_map(graph); 1374 dir_map[graph.right(n1)] = graph.u(graph.right(n1)) != n1;1375 dir_map[graph.up(n1)] = graph.u(graph.up(n1)) == n1;1376 dir_map[graph.left(n4)] = graph.u(graph.left(n4)) == n4;1377 dir_map[graph.down(n4)] = graph.u(graph.down(n4)) == n4;1374 dir_map[graph.right(n1)] = graph.u(graph.right(n1)) == n1; 1375 dir_map[graph.up(n1)] = graph.u(graph.up(n1)) != n1; 1376 dir_map[graph.left(n4)] = graph.u(graph.left(n4)) != n4; 1377 dir_map[graph.down(n4)] = graph.u(graph.down(n4)) != n4; 1378 1378 1379 1379 // Apply several adaptors on the grid graph 1380 typedef SplitNodes<Orienter< const GridGraph, GridGraph::EdgeMap<bool> > > 1381 SplitGridGraph; 1380 typedef SplitNodes< ReverseDigraph< const Orienter< 1381 const GridGraph, GridGraph::EdgeMap<bool> > > > 1382 RevSplitGridGraph; 1383 typedef ReverseDigraph<const RevSplitGridGraph> SplitGridGraph; 1382 1384 typedef Undirector<const SplitGridGraph> USplitGridGraph; 1385 typedef Undirector<const USplitGridGraph> UUSplitGridGraph; 1386 checkConcept<concepts::Digraph, RevSplitGridGraph>(); 1383 1387 checkConcept<concepts::Digraph, SplitGridGraph>(); 1384 1388 checkConcept<concepts::Graph, USplitGridGraph>(); 1385 1386 SplitGridGraph adaptor = splitNodes(orienter(graph, dir_map)); 1389 checkConcept<concepts::Graph, UUSplitGridGraph>(); 1390 1391 RevSplitGridGraph rev_adaptor = 1392 splitNodes(reverseDigraph(orienter(graph, dir_map))); 1393 SplitGridGraph adaptor = reverseDigraph(rev_adaptor); 1387 1394 USplitGridGraph uadaptor = undirector(adaptor); 1395 UUSplitGridGraph uuadaptor = undirector(uadaptor); 1388 1396 1389 1397 // Check adaptor … … 1392 1400 checkGraphConArcList(adaptor, 8); 1393 1401 1394 checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);1395 checkGraphOutArcList(adaptor, adaptor.outNode(n1), 1);1396 checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);1397 checkGraphOutArcList(adaptor, adaptor.outNode(n2), 0);1398 checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);1399 checkGraphOutArcList(adaptor, adaptor.outNode(n3), 1);1400 checkGraphOutArcList(adaptor, adaptor.inNode(n4), 1);1401 checkGraphOutArcList(adaptor, adaptor.outNode(n4), 2);1402 1403 checkGraphInArcList(adaptor, adaptor.inNode(n1), 1);1404 checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);1405 checkGraphInArcList(adaptor, adaptor.inNode(n2), 2);1406 checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);1407 checkGraphInArcList(adaptor, adaptor.inNode(n3), 1);1408 checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);1409 checkGraphInArcList(adaptor, adaptor.inNode(n4), 0);1410 checkGraphInArcList(adaptor, adaptor.outNode(n4), 1);1402 checkGraphOutArcList(adaptor, rev_adaptor.inNode(n1), 1); 1403 checkGraphOutArcList(adaptor, rev_adaptor.outNode(n1), 1); 1404 checkGraphOutArcList(adaptor, rev_adaptor.inNode(n2), 2); 1405 checkGraphOutArcList(adaptor, rev_adaptor.outNode(n2), 1); 1406 checkGraphOutArcList(adaptor, rev_adaptor.inNode(n3), 1); 1407 checkGraphOutArcList(adaptor, rev_adaptor.outNode(n3), 1); 1408 checkGraphOutArcList(adaptor, rev_adaptor.inNode(n4), 0); 1409 checkGraphOutArcList(adaptor, rev_adaptor.outNode(n4), 1); 1410 1411 checkGraphInArcList(adaptor, rev_adaptor.inNode(n1), 1); 1412 checkGraphInArcList(adaptor, rev_adaptor.outNode(n1), 1); 1413 checkGraphInArcList(adaptor, rev_adaptor.inNode(n2), 1); 1414 checkGraphInArcList(adaptor, rev_adaptor.outNode(n2), 0); 1415 checkGraphInArcList(adaptor, rev_adaptor.inNode(n3), 1); 1416 checkGraphInArcList(adaptor, rev_adaptor.outNode(n3), 1); 1417 checkGraphInArcList(adaptor, rev_adaptor.inNode(n4), 1); 1418 checkGraphInArcList(adaptor, rev_adaptor.outNode(n4), 2); 1411 1419 1412 1420 checkNodeIds(adaptor); … … 1431 1439 checkGraphArcMap(uadaptor); 1432 1440 1433 checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n1), 2); 1434 checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n1), 2); 1435 checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n2), 3); 1436 checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n2), 1); 1437 checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n3), 2); 1438 checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n3), 2); 1439 checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n4), 1); 1440 checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n4), 3); 1441 checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n1), 2); 1442 checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n1), 2); 1443 checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n2), 3); 1444 checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n2), 1); 1445 checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n3), 2); 1446 checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n3), 2); 1447 checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n4), 1); 1448 checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n4), 3); 1449 1450 // Check uuadaptor 1451 checkGraphNodeList(uuadaptor, 8); 1452 checkGraphEdgeList(uuadaptor, 16); 1453 checkGraphArcList(uuadaptor, 32); 1454 checkGraphConEdgeList(uuadaptor, 16); 1455 checkGraphConArcList(uuadaptor, 32); 1456 1457 checkNodeIds(uuadaptor); 1458 checkEdgeIds(uuadaptor); 1459 checkArcIds(uuadaptor); 1460 1461 checkGraphNodeMap(uuadaptor); 1462 checkGraphEdgeMap(uuadaptor); 1463 checkGraphArcMap(uuadaptor); 1441 1464 } 1442 1465 -
test/bellman_ford_test.cc
r781 r699 97 97 p = const_bf_test.predMap(); 98 98 pp = const_bf_test.path(t); 99 pp = const_bf_test.negativeCycle();100 99 101 100 for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {} … … 134 133 b = bf_test.reached(t); 135 134 pp = bf_test.path(t); 136 pp = bf_test.negativeCycle();137 135 } 138 136 } -
test/digraph_test.cc
r780 r740 20 20 #include <lemon/list_graph.h> 21 21 #include <lemon/smart_graph.h> 22 #include <lemon/static_graph.h>23 22 #include <lemon/full_graph.h> 24 23 … … 330 329 checkConcept<ClearableDigraphComponent<>, SmartDigraph>(); 331 330 } 332 { // Checking StaticDigraph333 checkConcept<Digraph, StaticDigraph>();334 checkConcept<ClearableDigraphComponent<>, StaticDigraph>();335 }336 331 { // Checking FullDigraph 337 332 checkConcept<Digraph, FullDigraph>(); … … 387 382 check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); 388 383 check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); 389 }390 391 void checkStaticDigraph() {392 SmartDigraph g;393 SmartDigraph::NodeMap<StaticDigraph::Node> nref(g);394 SmartDigraph::ArcMap<StaticDigraph::Arc> aref(g);395 396 StaticDigraph G;397 398 checkGraphNodeList(G, 0);399 checkGraphArcList(G, 0);400 401 G.build(g, nref, aref);402 403 checkGraphNodeList(G, 0);404 checkGraphArcList(G, 0);405 406 SmartDigraph::Node407 n1 = g.addNode(),408 n2 = g.addNode(),409 n3 = g.addNode();410 411 G.build(g, nref, aref);412 413 checkGraphNodeList(G, 3);414 checkGraphArcList(G, 0);415 416 SmartDigraph::Arc a1 = g.addArc(n1, n2);417 418 G.build(g, nref, aref);419 420 check(G.source(aref[a1]) == nref[n1] && G.target(aref[a1]) == nref[n2],421 "Wrong arc or wrong references");422 checkGraphNodeList(G, 3);423 checkGraphArcList(G, 1);424 425 checkGraphOutArcList(G, nref[n1], 1);426 checkGraphOutArcList(G, nref[n2], 0);427 checkGraphOutArcList(G, nref[n3], 0);428 429 checkGraphInArcList(G, nref[n1], 0);430 checkGraphInArcList(G, nref[n2], 1);431 checkGraphInArcList(G, nref[n3], 0);432 433 checkGraphConArcList(G, 1);434 435 SmartDigraph::Arc436 a2 = g.addArc(n2, n1),437 a3 = g.addArc(n2, n3),438 a4 = g.addArc(n2, n3);439 440 digraphCopy(g, G).nodeRef(nref).run();441 442 checkGraphNodeList(G, 3);443 checkGraphArcList(G, 4);444 445 checkGraphOutArcList(G, nref[n1], 1);446 checkGraphOutArcList(G, nref[n2], 3);447 checkGraphOutArcList(G, nref[n3], 0);448 449 checkGraphInArcList(G, nref[n1], 1);450 checkGraphInArcList(G, nref[n2], 1);451 checkGraphInArcList(G, nref[n3], 2);452 453 checkGraphConArcList(G, 4);454 455 std::vector<std::pair<int,int> > arcs;456 arcs.push_back(std::make_pair(0,1));457 arcs.push_back(std::make_pair(0,2));458 arcs.push_back(std::make_pair(1,3));459 arcs.push_back(std::make_pair(1,2));460 arcs.push_back(std::make_pair(3,0));461 arcs.push_back(std::make_pair(3,3));462 arcs.push_back(std::make_pair(4,2));463 arcs.push_back(std::make_pair(4,3));464 arcs.push_back(std::make_pair(4,1));465 466 G.build(6, arcs.begin(), arcs.end());467 468 checkGraphNodeList(G, 6);469 checkGraphArcList(G, 9);470 471 checkGraphOutArcList(G, G.node(0), 2);472 checkGraphOutArcList(G, G.node(1), 2);473 checkGraphOutArcList(G, G.node(2), 0);474 checkGraphOutArcList(G, G.node(3), 2);475 checkGraphOutArcList(G, G.node(4), 3);476 checkGraphOutArcList(G, G.node(5), 0);477 478 checkGraphInArcList(G, G.node(0), 1);479 checkGraphInArcList(G, G.node(1), 2);480 checkGraphInArcList(G, G.node(2), 3);481 checkGraphInArcList(G, G.node(3), 3);482 checkGraphInArcList(G, G.node(4), 0);483 checkGraphInArcList(G, G.node(5), 0);484 485 checkGraphConArcList(G, 9);486 487 checkNodeIds(G);488 checkArcIds(G);489 checkGraphNodeMap(G);490 checkGraphArcMap(G);491 492 int n = G.nodeNum();493 int m = G.arcNum();494 check(G.index(G.node(n-1)) == n-1, "Wrong index.");495 check(G.index(G.arc(m-1)) == m-1, "Wrong index.");496 384 } 497 385 … … 548 436 checkDigraphValidity<SmartDigraph>(); 549 437 } 550 { // Checking StaticDigraph551 checkStaticDigraph();552 }553 438 { // Checking FullDigraph 554 439 checkFullDigraph(8); -
test/test_tools.h
r763 r440 38 38 ///print something like this (and then exits). 39 39 ///\verbatim file_name.cc:123: error: This is obviously false. \endverbatim 40 #define check(rc, msg) \ 41 { \ 42 if(!(rc)) { \ 43 std::cerr << __FILE__ ":" << __LINE__ << ": error: " \ 44 << msg << std::endl; \ 45 abort(); \ 46 } else { } \ 47 } \ 48 40 #define check(rc, msg) \ 41 if(!(rc)) { \ 42 std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \ 43 abort(); \ 44 } else { } \ 49 45 50 46 #endif
Note: See TracChangeset
for help on using the changeset viewer.