COIN-OR::LEMON - Graph Library

Ignore:
Files:
5 deleted
29 edited

Legend:

Unmodified
Added
Removed
  • Makefile.am

    r799 r676  
    1818        cmake/FindGLPK.cmake \
    1919        cmake/FindCOIN.cmake \
    20         cmake/LEMONConfig.cmake.in \
    2120        cmake/version.cmake.in \
    2221        cmake/version.cmake \
  • doc/Doxyfile.in

    r803 r791  
    1 # Doxyfile 1.5.9
     1# Doxyfile 1.5.7.1
    22
    33#---------------------------------------------------------------------------
     
    2222QT_AUTOBRIEF           = NO
    2323MULTILINE_CPP_IS_BRIEF = NO
     24DETAILS_AT_TOP         = YES
    2425INHERIT_DOCS           = NO
    2526SEPARATE_MEMBER_PAGES  = NO
     
    224225SKIP_FUNCTION_MACROS   = YES
    225226#---------------------------------------------------------------------------
    226 # Options related to the search engine   
     227# Configuration::additions related to external references   
    227228#---------------------------------------------------------------------------
    228229TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
  • doc/groups.dox

    r818 r789  
    317317
    318318This 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).
    321320*/
    322321
     
    326325\brief Algorithms for finding shortest paths.
    327326
    328 This group contains the algorithms for finding shortest paths in digraphs
    329 \ref clrs01algorithms.
     327This group contains the algorithms for finding shortest paths in digraphs.
    330328
    331329 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    349347
    350348This group contains the algorithms for finding minimum cost spanning
    351 trees and arborescences \ref clrs01algorithms.
     349trees and arborescences.
    352350*/
    353351
     
    358356
    359357This group contains the algorithms for finding maximum flows and
    360 feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
     358feasible circulations.
    361359
    362360The \e maximum \e flow \e problem is to find a flow of maximum value between
     
    373371
    374372LEMON 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
     378In most cases the \ref Preflow "Preflow" algorithm provides the
    385379fastest method for computing a maximum flow. All implementations
    386380also provide functions to query the minimum cut, which is the dual
     
    400394
    401395This 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".
     396circulations. For more information about this problem and its dual
     397solution see \ref min_cost_flow "Minimum Cost Flow Problem".
    405398
    406399LEMON contains several algorithms for this problem.
    407400 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    408    pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
     401   pivot strategies.
    409402 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
    410    cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
    411    \ref bunnagel98efficient.
     403   cost scaling.
    412404 - \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.
    418408
    419409In general NetworkSimplex is the most efficient implementation,
     
    451441If you want to find minimum cut just between two distinict nodes,
    452442see the \ref max_flow "maximum flow problem".
    453 */
    454 
    455 /**
    456 @defgroup min_mean_cycle Minimum Mean Cycle Algorithms
    457 @ingroup algs
    458 \brief Algorithms for finding minimum mean cycles.
    459 
    460 This group contains the algorithms for finding minimum mean cycles
    461 \ref clrs01algorithms, \ref amo93networkflows.
    462 
    463 The \e minimum \e mean \e cycle \e problem is to find a directed cycle
    464 of minimum mean length (cost) in a digraph.
    465 The mean length of a cycle is the average length of its arcs, i.e. the
    466 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 length
    469 \e functions, too. A length function on the arcs of a digraph is called
    470 conservative if and only if there is no directed cycle of negative total
    471 length. For an arbitrary length function, the negative of the minimum
    472 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
    473 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
    474 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 improved
    480   version of Karp's algorithm \ref dasdan98minmeancycle.
    481 - \ref Howard "Howard"'s policy iteration algorithm
    482   \ref dasdan98minmeancycle.
    483 
    484 In practice, the Howard algorithm proved to be by far the most efficient
    485 one, though the best known theoretical bound on its running time is
    486 exponential.
    487 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
    488 O(n<sup>2</sup>+e), but the latter one is typically faster due to the
    489 applied early termination scheme.
    490443*/
    491444
     
    582535
    583536/**
    584 @defgroup lp_group LP and MIP Solvers
     537@defgroup lp_group Lp and Mip Solvers
    585538@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
     541This group contains Lp and Mip solver interfaces for LEMON. The
     542various LP solvers could be used in the same manner with this
     543interface.
    594544*/
    595545
  • doc/mainpage.dox

    r802 r705  
    2222\section intro Introduction
    2323
    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
     26LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
     27and <b>O</b>ptimization in <b>N</b>etworks.
     28It is a C++ template
     29library aimed at combinatorial optimization tasks which
     30often involve in working
     31with graphs.
    2932
    3033<b>
     
    3639</b>
    3740
    38 The project is maintained by the
    39 <a href="http://www.cs.elte.hu/egres/">Egerv&aacute;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&ouml;tv&ouml;s Lor&aacute;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
    4842
    4943If you would like to get to know the library, see
  • doc/min_cost_flow.dox

    r835 r833  
    2727minimum total cost from a set of supply nodes to a set of demand nodes
    2828in a network with capacity constraints (lower and upper bounds)
    29 and arc costs \ref amo93networkflows.
     29and arc costs.
    3030
    3131Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
  • doc/references.bib

    r802 r790  
    1313  title =        {{EGRES} -- {E}gerv{\'a}ry {R}esearch {G}roup on
    1414                  {C}ombinatorial {O}ptimization},
    15   url =          {http://www.cs.elte.hu/egres/}
     15  howpublished = {\url{http://www.cs.elte.hu/egres/}},
     16  year =         2009
    1617}
    1718
     
    2021  title =        {{COIN-OR} -- {C}omputational {I}nfrastructure for
    2122                  {O}perations {R}esearch},
    22   url =          {http://www.coin-or.org/}
     23  howpublished = {\url{http://www.coin-or.org/}},
     24  year =         2009
    2325}
    2426
     
    2931  key =          {Boost},
    3032  title =        {{B}oost {C++} {L}ibraries},
    31   url =          {http://www.boost.org/}
     33  howpublished = {\url{http://www.boost.org/}},
     34  year =         2009
    3235}
    3336
     
    4548  title =        {{LEDA} -- {L}ibrary of {E}fficient {D}ata {T}ypes and
    4649                  {A}lgorithms},
    47   url =          {http://www.algorithmic-solutions.com/}
     50  howpublished = {\url{http://www.algorithmic-solutions.com/}},
     51  year =         2009
    4852}
    4953
     
    6468  key =          {CMake},
    6569  title =        {{CMake} -- {C}ross {P}latform {M}ake},
    66   url =          {http://www.cmake.org/}
     70  howpublished = {\url{http://www.cmake.org/}},
     71  year =         2009
    6772}
    6873
     
    7176  title =        {{Doxygen} -- {S}ource code documentation generator
    7277                  tool},
    73   url =          {http://www.doxygen.org/}
     78  howpublished = {\url{http://www.doxygen.org/}},
     79  year =         2009
    7480}
    7581
     
    8086  key =          {GLPK},
    8187  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
    8390}
    8491
     
    8693  key =          {Clp},
    8794  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
    8997}
    9098
     
    92100  key =          {Cbc},
    93101  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
    95104}
    96105
     
    98107  key =          {CPLEX},
    99108  title =        {{ILOG} {CPLEX}},
    100   url =          {http://www.ilog.com/}
     109  howpublished = {\url{http://www.ilog.com/}},
     110  year =         2009
    101111}
    102112
     
    105115  title =        {{SoPlex} -- {T}he {S}equential {O}bject-{O}riented
    106116                  {S}implex},
    107   url =          {http://soplex.zib.de/}
     117  howpublished = {\url{http://soplex.zib.de/}},
     118  year =         2009
    108119}
    109120
     
    151162%%%%% Maximum flow algorithms %%%%%
    152163
    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,
    165165  author =       {Andrew V. Goldberg and Robert E. Tarjan},
    166166  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}
    172173}
    173174
     
    240241}
    241242
    242 @article{goldberg89cyclecanceling,
     243@inproceedings{goldberg88cyclecanceling,
    243244  author =       {Andrew V. Goldberg and Robert E. Tarjan},
    244245  title =        {Finding minimum-cost circulations by canceling
    245246                  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},
    246259  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,
    254279  author =       {Andrew V. Goldberg and Robert E. Tarjan},
    255280  title =        {Finding Minimum-Cost Circulations by Successive
     
    284309}
    285310
    286 @book{dantzig63linearprog,
    287   author =       {George B. Dantzig},
    288   title =        {Linear Programming and Extensions},
    289   publisher =    {Princeton University Press},
    290   year =         1963
    291 }
    292 
    293311@mastersthesis{kellyoneill91netsimplex,
    294312  author =       {Damian J. Kelly and Garrett M. O'Neill},
     
    300318  month =        sep,
    301319}
     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

    r827 r755  
    8787        lemon/graph_to_eps.h \
    8888        lemon/grid_graph.h \
    89         lemon/hartmann_orlin.h \
    90         lemon/howard.h \
    9189        lemon/hypercube_graph.h \
    92         lemon/karp.h \
    9390        lemon/kary_heap.h \
    9491        lemon/kruskal.h \
     
    114111        lemon/smart_graph.h \
    115112        lemon/soplex.h \
    116         lemon/static_graph.h \
    117113        lemon/suurballe.h \
    118114        lemon/time_measure.h \
  • lemon/adaptors.h

    r834 r703  
    361361  /// parameter is set to be \c const.
    362362  ///
    363   /// This class provides item counting in the same time as the adapted
    364   /// digraph structure.
    365   ///
    366363  /// \tparam DGR The type of the adapted digraph.
    367364  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     
    722719  /// by adding or removing nodes or arcs, unless the \c GR template
    723720  /// parameter is set to be \c const.
    724   ///
    725   /// This class provides only linear time counting for nodes and arcs.
    726721  ///
    727722  /// \tparam DGR The type of the adapted digraph.
     
    13201315  /// parameter is set to be \c const.
    13211316  ///
    1322   /// This class provides only linear time counting for nodes, edges and arcs.
    1323   ///
    13241317  /// \tparam GR The type of the adapted graph.
    13251318  /// It must conform to the \ref concepts::Graph "Graph" concept.
     
    14781471  /// by adding or removing nodes or arcs/edges, unless the \c GR template
    14791472  /// parameter is set to be \c const.
    1480   ///
    1481   /// This class provides only linear time item counting.
    14821473  ///
    14831474  /// \tparam GR The type of the adapted digraph or graph.
     
    16291620  /// parameter is set to be \c const.
    16301621  ///
    1631   /// This class provides only linear time counting for nodes and arcs.
    1632   ///
    16331622  /// \tparam DGR The type of the adapted digraph.
    16341623  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     
    17401729  /// by adding or removing nodes or edges, unless the \c GR template
    17411730  /// parameter is set to be \c const.
    1742   ///
    1743   /// This class provides only linear time counting for nodes, edges and arcs.
    17441731  ///
    17451732  /// \tparam GR The type of the adapted graph.
     
    22462233  /// parameter is set to be \c const.
    22472234  ///
    2248   /// This class provides item counting in the same time as the adapted
    2249   /// digraph structure.
    2250   ///
    22512235  /// \tparam DGR The type of the adapted digraph.
    22522236  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     
    25512535  /// by adding or removing nodes or arcs, unless the \c GR template
    25522536  /// parameter is set to be \c const.
    2553   ///
    2554   /// This class provides item counting in the same time as the adapted
    2555   /// graph structure.
    25562537  ///
    25572538  /// \tparam GR The type of the adapted graph.
     
    26972678  /// arcs).
    26982679  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
    2699   ///
    2700   /// This class provides only linear time counting for nodes and arcs.
    27012680  ///
    27022681  /// \tparam DGR The type of the adapted digraph.
     
    33473326  /// in the adaptor.
    33483327  ///
    3349   /// This class provides item counting in the same time as the adapted
    3350   /// digraph structure.
    3351   ///
    33523328  /// \tparam DGR The type of the adapted digraph.
    33533329  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
  • lemon/bellman_ford.h

    r835 r833  
    2424/// \brief Bellman-Ford algorithm.
    2525
    26 #include <lemon/list_graph.h>
    2726#include <lemon/bits/path_dump.h>
    2827#include <lemon/core.h>
     
    777776    /// length if the algorithm has already found one.
    778777    /// Otherwise it gives back an empty path.
    779     lemon::Path<Digraph> negativeCycle() const {
     778    lemon::Path<Digraph> negativeCycle() {
    780779      typename Digraph::template NodeMap<int> state(*_gr, -1);
    781780      lemon::Path<Digraph> cycle;
  • lemon/bfs.h

    r835 r833  
    702702    ///Runs the algorithm to visit all nodes in the digraph.
    703703
    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).
    706710    ///
    707711    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
     
    10431047    ///Runs BFS algorithm to visit all nodes in the digraph.
    10441048
    1045     ///This method runs BFS algorithm in order to visit all nodes
    1046     ///in the digraph.
     1049    ///This method runs BFS algorithm in order to compute
     1050    ///the shortest path to each node.
    10471051    void run()
    10481052    {
     
    16921696    /// \brief Runs the algorithm to visit all nodes in the digraph.
    16931697    ///
    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).
    16961704    ///
    16971705    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
  • lemon/bits/graph_extender.h

    r825 r732  
    5757    }
    5858
    59     static Node fromId(int id, Node) {
     59    Node fromId(int id, Node) const {
    6060      return Parent::nodeFromId(id);
    6161    }
    6262
    63     static Arc fromId(int id, Arc) {
     63    Arc fromId(int id, Arc) const {
    6464      return Parent::arcFromId(id);
    6565    }
     
    356356    }
    357357
    358     static Node fromId(int id, Node) {
     358    Node fromId(int id, Node) const {
    359359      return Parent::nodeFromId(id);
    360360    }
    361361
    362     static Arc fromId(int id, Arc) {
     362    Arc fromId(int id, Arc) const {
    363363      return Parent::arcFromId(id);
    364364    }
    365365
    366     static Edge fromId(int id, Edge) {
     366    Edge fromId(int id, Edge) const {
    367367      return Parent::edgeFromId(id);
    368368    }
  • lemon/dfs.h

    r835 r833  
    634634    ///Runs the algorithm to visit all nodes in the digraph.
    635635
    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.
    638642    ///
    639643    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
     
    973977    ///Runs DFS algorithm to visit all nodes in the digraph.
    974978
    975     ///This method runs DFS algorithm in order to visit all nodes
    976     ///in the digraph.
     979    ///This method runs DFS algorithm in order to compute
     980    ///the DFS path to each node.
    977981    void run()
    978982    {
     
    15751579    /// \brief Runs the algorithm to visit all nodes in the digraph.
    15761580
    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.
    15791587    ///
    15801588    /// \note <tt>d.run()</tt> is just a shortcut of the following code.
  • lemon/dijkstra.h

    r835 r833  
    207207
    208208    ///The type of the arc lengths.
    209     typedef typename TR::Value Value;
     209    typedef typename TR::LengthMap::Value Value;
    210210    ///The type of the map that stores the arc lengths.
    211211    typedef typename TR::LengthMap LengthMap;
  • lemon/edge_set.h

    r834 r717  
    256256  /// all arcs incident to the given node is erased from the arc set.
    257257  ///
    258   /// This class fully conforms to the \ref concepts::Digraph
    259   /// "Digraph" concept.
    260   /// It provides only linear time counting for nodes and arcs.
    261   ///
    262258  /// \param GR The type of the graph which shares its node set with
    263259  /// this class. Its interface must conform to the
    264260  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
    265261  /// concept.
     262  ///
     263  /// This class fully conforms to the \ref concepts::Digraph
     264  /// "Digraph" concept.
    266265  template <typename GR>
    267266  class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
     
    687686  /// incident to the given node is erased from the arc set.
    688687  ///
    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   ///
    693688  /// \param GR The type of the graph which shares its node set
    694689  /// with this class. Its interface must conform to the
    695690  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
     691  /// concept.
     692  ///
     693  /// This class fully conforms to the \ref concepts::Graph "Graph"
    696694  /// concept.
    697695  template <typename GR>
     
    870868    }
    871869
    872     static void next(Arc& arc) {
     870    void next(Arc& arc) const {
    873871      --arc.id;
    874872    }
     
    957955  /// arcs. Therefore the arcs cannot be erased from the arc sets.
    958956  ///
    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   ///
    963957  /// \warning If a node is erased from the underlying graph and this
    964958  /// node is the source or target of one arc in the arc set, then
    965959  /// the arc set is invalidated, and it cannot be used anymore. The
    966960  /// validity can be checked with the \c valid() member function.
     961  ///
     962  /// This class fully conforms to the \ref concepts::Digraph
     963  /// "Digraph" concept.
    967964  template <typename GR>
    968965  class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
     
    11771174    }
    11781175
    1179     static void next(Arc& arc) {
     1176    void next(Arc& arc) const {
    11801177      --arc.id;
    11811178    }
     
    11851182    }
    11861183
    1187     static void next(Edge& arc) {
     1184    void next(Edge& arc) const {
    11881185      --arc.id;
    11891186    }
     
    13081305  /// edges cannot be erased from the edge sets.
    13091306  ///
    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   ///
    13141307  /// \warning If a node is erased from the underlying graph and this
    13151308  /// node is incident to one edge in the edge set, then the edge set
    13161309  /// is invalidated, and it cannot be used anymore. The validity can
    13171310  /// be checked with the \c valid() member function.
     1311  ///
     1312  /// This class fully conforms to the \ref concepts::Graph
     1313  /// "Graph" concept.
    13181314  template <typename GR>
    13191315  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {
  • lemon/full_graph.h

    r834 r782  
    5252
    5353    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; }
    5555
    5656    Arc arc(const Node& s, const Node& t) const {
     
    163163  /// only in the concept class.
    164164  ///
    165   /// This class provides constant time counting for nodes and arcs.
    166   ///
    167165  /// \note FullDigraph and FullGraph classes are very similar,
    168166  /// but there are two differences. While this class conforms only
     
    207205    /// completely static, the nodes can be indexed with integers from
    208206    /// the range <tt>[0..nodeNum()-1]</tt>.
    209     /// The index of a node is the same as its ID.
    210207    /// \sa index()
    211208    Node operator()(int ix) const { return Parent::operator()(ix); }
     
    216213    /// completely static, the nodes can be indexed with integers from
    217214    /// the range <tt>[0..nodeNum()-1]</tt>.
    218     /// The index of a node is the same as its ID.
    219215    /// \sa operator()()
    220     static int index(const Node& node) { return Parent::index(node); }
     216    int index(Node node) const { return Parent::index(node); }
    221217
    222218    /// \brief Returns the arc connecting the given nodes.
     
    292288
    293289    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; }
    295291
    296292    Edge edge(const Node& u, const Node& v) const {
     
    540536  /// only in the concept class.
    541537  ///
    542   /// This class provides constant time counting for nodes, edges and arcs.
    543   ///
    544538  /// \note FullDigraph and FullGraph classes are very similar,
    545539  /// but there are two differences. While FullDigraph
     
    586580    /// completely static, the nodes can be indexed with integers from
    587581    /// the range <tt>[0..nodeNum()-1]</tt>.
    588     /// The index of a node is the same as its ID.
    589582    /// \sa index()
    590583    Node operator()(int ix) const { return Parent::operator()(ix); }
     
    595588    /// completely static, the nodes can be indexed with integers from
    596589    /// the range <tt>[0..nodeNum()-1]</tt>.
    597     /// The index of a node is the same as its ID.
    598590    /// \sa operator()()
    599     static int index(const Node& node) { return Parent::index(node); }
     591    int index(Node node) const { return Parent::index(node); }
    600592
    601593    /// \brief Returns the arc connecting the given nodes.
  • lemon/grid_graph.h

    r834 r782  
    504504  /// Most of its member functions and nested classes are documented
    505505  /// only in the concept class.
    506   ///
    507   /// This class provides constant time counting for nodes, edges and arcs.
    508506  class GridGraph : public ExtendedGridGraphBase {
    509507    typedef ExtendedGridGraphBase Parent;
  • lemon/hypercube_graph.h

    r835 r833  
    263263    }
    264264
    265     static int index(Node node) {
     265    int index(Node node) const {
    266266      return node._id;
    267267    }
     
    295295  /// only in the concept class.
    296296  ///
    297   /// This class provides constant time counting for nodes, edges and arcs.
    298   ///
    299297  /// \note The type of the indices is chosen to \c int for efficiency
    300298  /// reasons. Thus the maximum dimension of this implementation is 26
     
    359357    /// Gives back the index of the given node.
    360358    /// The lower bits of the integer describes the node.
    361     static int index(Node node) {
     359    int index(Node node) const {
    362360      return Parent::index(node);
    363361    }
  • lemon/list_graph.h

    r835 r833  
    325325  ///only in the concept class.
    326326  ///
    327   ///This class provides only linear time counting for nodes and arcs.
    328   ///
    329327  ///\sa concepts::Digraph
    330328  ///\sa ListGraph
     
    363361    ///\brief Erase a node from the digraph.
    364362    ///
    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.
    370364    void erase(Node n) { Parent::erase(n); }
    371365
     
    373367    ///
    374368    ///This function erases the given arc from the digraph.
    375     ///
    376     ///\note All iterators referencing the removed arc are invalidated,
    377     ///of course.
    378369    void erase(Arc a) { Parent::erase(a); }
    379370
     
    520511    ///This function erases all nodes and arcs from the digraph.
    521512    ///
    522     ///\note All iterators of the digraph are invalidated, of course.
    523513    void clear() {
    524514      Parent::clear();
     
    11901180  ///only in the concept class.
    11911181  ///
    1192   ///This class provides only linear time counting for nodes, edges and arcs.
    1193   ///
    11941182  ///\sa concepts::Graph
    11951183  ///\sa ListDigraph
     
    12301218    ///\brief Erase a node from the graph.
    12311219    ///
    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.
    12371221    void erase(Node n) { Parent::erase(n); }
    12381222
     
    12401224    ///
    12411225    /// This function erases the given edge from the graph.
    1242     ///
    1243     /// \note All iterators referencing the removed edge are invalidated,
    1244     /// of course.
    12451226    void erase(Edge e) { Parent::erase(e); }
    12461227    /// Node validity check
     
    13321313    ///This function erases all nodes and arcs from the graph.
    13331314    ///
    1334     ///\note All iterators of the graph are invalidated, of course.
    13351315    void clear() {
    13361316      Parent::clear();
  • lemon/network_simplex.h

    r835 r833  
    4141  ///
    4242  /// \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".
    4644  /// This algorithm is a specialized version of the linear programming
    4745  /// simplex method directly for the minimum cost flow problem.
  • lemon/path.h

    r831 r606  
    7171    template <typename CPath>
    7272    Path(const CPath& cpath) {
    73       pathCopy(cpath, *this);
     73      copyPath(*this, cpath);
    7474    }
    7575
     
    7979    template <typename CPath>
    8080    Path& operator=(const CPath& cpath) {
    81       pathCopy(cpath, *this);
     81      copyPath(*this, cpath);
    8282      return *this;
    8383    }
     
    259259    template <typename CPath>
    260260    SimplePath(const CPath& cpath) {
    261       pathCopy(cpath, *this);
     261      copyPath(*this, cpath);
    262262    }
    263263
     
    268268    template <typename CPath>
    269269    SimplePath& operator=(const CPath& cpath) {
    270       pathCopy(cpath, *this);
     270      copyPath(*this, cpath);
    271271      return *this;
    272272    }
     
    438438    template <typename CPath>
    439439    ListPath(const CPath& cpath) : first(0), last(0) {
    440       pathCopy(cpath, *this);
     440      copyPath(*this, cpath);
    441441    }
    442442
     
    454454    template <typename CPath>
    455455    ListPath& operator=(const CPath& cpath) {
    456       pathCopy(cpath, *this);
     456      copyPath(*this, cpath);
    457457      return *this;
    458458    }
     
    764764    template <typename CPath>
    765765    StaticPath(const CPath& cpath) : arcs(0) {
    766       pathCopy(cpath, *this);
     766      copyPath(*this, cpath);
    767767    }
    768768
     
    780780    template <typename CPath>
    781781    StaticPath& operator=(const CPath& cpath) {
    782       pathCopy(cpath, *this);
     782      copyPath(*this, cpath);
    783783      return *this;
    784784    }
     
    929929    };
    930930
    931     template <typename From, typename To,
    932               bool buildEnable = BuildTagIndicator<To>::value>
     931    template <typename Target, typename Source,
     932              bool buildEnable = BuildTagIndicator<Target>::value>
    933933    struct PathCopySelectorForward {
    934       static void copy(const From& from, To& to) {
    935         to.clear();
    936         for (typename From::ArcIt it(from); it != INVALID; ++it) {
    937           to.addBack(it);
     934      static void copy(Target& target, const Source& source) {
     935        target.clear();
     936        for (typename Source::ArcIt it(source); it != INVALID; ++it) {
     937          target.addBack(it);
    938938        }
    939939      }
    940940    };
    941941
    942     template <typename From, typename To>
    943     struct PathCopySelectorForward<From, To, true> {
    944       static void copy(const From& from, To& to) {
    945         to.clear();
    946         to.build(from);
    947       }
    948     };
    949 
    950     template <typename From, typename To,
    951               bool buildEnable = BuildTagIndicator<To>::value>
     942    template <typename Target, typename Source>
     943    struct PathCopySelectorForward<Target, Source, true> {
     944      static void copy(Target& target, const Source& source) {
     945        target.clear();
     946        target.build(source);
     947      }
     948    };
     949
     950    template <typename Target, typename Source,
     951              bool buildEnable = BuildTagIndicator<Target>::value>
    952952    struct PathCopySelectorBackward {
    953       static void copy(const From& from, To& to) {
    954         to.clear();
    955         for (typename From::RevArcIt it(from); it != INVALID; ++it) {
    956           to.addFront(it);
     953      static void copy(Target& target, const Source& source) {
     954        target.clear();
     955        for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
     956          target.addFront(it);
    957957        }
    958958      }
    959959    };
    960960
    961     template <typename From, typename To>
    962     struct PathCopySelectorBackward<From, To, true> {
    963       static void copy(const From& from, To& to) {
    964         to.clear();
    965         to.buildRev(from);
     961    template <typename Target, typename Source>
     962    struct PathCopySelectorBackward<Target, Source, true> {
     963      static void copy(Target& target, const Source& source) {
     964        target.clear();
     965        target.buildRev(source);
    966966      }
    967967    };
    968968
    969969   
    970     template <typename From, typename To,
    971               bool revEnable = RevPathTagIndicator<From>::value>
     970    template <typename Target, typename Source,
     971              bool revEnable = RevPathTagIndicator<Source>::value>
    972972    struct PathCopySelector {
    973       static void copy(const From& from, To& to) {
    974         PathCopySelectorForward<From, To>::copy(from, to);
     973      static void copy(Target& target, const Source& source) {
     974        PathCopySelectorForward<Target, Source>::copy(target, source);
    975975      }     
    976976    };
    977977
    978     template <typename From, typename To>
    979     struct PathCopySelector<From, To, true> {
    980       static void copy(const From& from, To& to) {
    981         PathCopySelectorBackward<From, To>::copy(from, to);
     978    template <typename Target, typename Source>
     979    struct PathCopySelector<Target, Source, true> {
     980      static void copy(Target& target, const Source& source) {
     981        PathCopySelectorBackward<Target, Source>::copy(target, source);
    982982      }     
    983983    };
     
    988988  /// \brief Make a copy of a path.
    989989  ///
    990   /// This function makes a copy of a path.
    991   template <typename From, typename To>
    992   void pathCopy(const From& from, To& to) {
    993     checkConcept<concepts::PathDumper<typename From::Digraph>, From>();
    994     _path_bits::PathCopySelector<From, To>::copy(from, to);
    995   }
    996 
    997   /// \brief Deprecated version of \ref pathCopy().
    998   ///
    999   /// Deprecated version of \ref pathCopy() (only for reverse compatibility).
    1000   template <typename To, typename From>
    1001   void copyPath(To& to, const From& from) {
    1002     pathCopy(from, to);
     990  ///  This function makes a copy of a path.
     991  template <typename Target, typename Source>
     992  void copyPath(Target& target, const Source& source) {
     993    checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
     994    _path_bits::PathCopySelector<Target, Source>::copy(target, source);
    1003995  }
    1004996
     
    10241016  /// \brief The source of a path
    10251017  ///
    1026   /// This function returns the source node of the given path.
    1027   /// If the path is empty, then it returns \c INVALID.
     1018  /// This function returns the source of the given path.
    10281019  template <typename Digraph, typename Path>
    10291020  typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
    1030     return path.empty() ? INVALID : digraph.source(path.front());
     1021    return digraph.source(path.front());
    10311022  }
    10321023
    10331024  /// \brief The target of a path
    10341025  ///
    1035   /// This function returns the target node of the given path.
    1036   /// If the path is empty, then it returns \c INVALID.
     1026  /// This function returns the target of the given path.
    10371027  template <typename Digraph, typename Path>
    10381028  typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
    1039     return path.empty() ? INVALID : digraph.target(path.back());
     1029    return digraph.target(path.back());
    10401030  }
    10411031
  • lemon/preflow.h

    r835 r833  
    103103  /// This class provides an implementation of Goldberg-Tarjan's \e preflow
    104104  /// \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.
    107106  /// The preflow algorithms are the fastest known maximum
    108107  /// flow algorithms. The current implementation uses a mixture of the
  • lemon/smart_graph.h

    r834 r783  
    195195  ///only in the concept class.
    196196  ///
    197   ///This class provides constant time counting for nodes and arcs.
    198   ///
    199197  ///\sa concepts::Digraph
    200198  ///\sa SmartGraph
     
    500498    }
    501499
    502     static void next(Node& node) {
     500    void next(Node& node) const {
    503501      --node._id;
    504502    }
     
    508506    }
    509507
    510     static void next(Arc& arc) {
     508    void next(Arc& arc) const {
    511509      --arc._id;
    512510    }
     
    516514    }
    517515
    518     static void next(Edge& arc) {
     516    void next(Edge& arc) const {
    519517      --arc._id;
    520518    }
     
    623621  /// only in the concept class.
    624622  ///
    625   /// This class provides constant time counting for nodes, edges and arcs.
    626   ///
    627623  /// \sa concepts::Graph
    628624  /// \sa SmartDigraph
  • scripts/bib2dox.py

    r801 r792  
    7171author_rex = re.compile('\s+and\s+')
    7272rembraces_rex = re.compile('[{}]')
    73 capitalize_rex = re.compile('({[^}]*})')
     73capitalize_rex = re.compile('({\w*})')
    7474
    7575# used by bibtexkeywords(data)
     
    364364            if entrycont.has_key('note') and (entrycont['note'] != ''):
    365365                entry.append(entrycont['note'] + '.')
    366             if entrycont.has_key('url') and (entrycont['url'] != ''):
    367                 entry.append(entrycont['url'] + '.')
    368366
    369367            # generate keys for sorting and for the output
     
    413411                field = string.lower(field)
    414412                data =  data_rex.sub('\g<2>', line)
    415 
    416             if field == 'url':
    417                 data = '\\url{' + data.strip() + '}'
    418413           
    419414            if field in ('author', 'editor'):
  • test/CMakeLists.txt

    r817 r745  
    3333  min_cost_arborescence_test
    3434  min_cost_flow_test
    35   min_mean_cycle_test
    3635  path_test
    3736  preflow_test
  • test/Makefile.am

    r817 r745  
    3131        test/min_cost_arborescence_test \
    3232        test/min_cost_flow_test \
    33         test/min_mean_cycle_test \
    3433        test/path_test \
    3534        test/preflow_test \
     
    8079test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
    8180test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
    82 test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc
    8381test_path_test_SOURCES = test/path_test.cc
    8482test_preflow_test_SOURCES = test/preflow_test.cc
  • test/adaptors_test.cc

    r550 r488  
    13721372
    13731373  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;
    13781378
    13791379  // 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;
    13821384  typedef Undirector<const SplitGridGraph> USplitGridGraph;
     1385  typedef Undirector<const USplitGridGraph> UUSplitGridGraph;
     1386  checkConcept<concepts::Digraph, RevSplitGridGraph>();
    13831387  checkConcept<concepts::Digraph, SplitGridGraph>();
    13841388  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);
    13871394  USplitGridGraph uadaptor = undirector(adaptor);
     1395  UUSplitGridGraph uuadaptor = undirector(uadaptor);
    13881396
    13891397  // Check adaptor
     
    13921400  checkGraphConArcList(adaptor, 8);
    13931401
    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);
    14111419
    14121420  checkNodeIds(adaptor);
     
    14311439  checkGraphArcMap(uadaptor);
    14321440
    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);
    14411464}
    14421465
  • test/bellman_ford_test.cc

    r828 r746  
    9797    p  = const_bf_test.predMap();
    9898    pp = const_bf_test.path(t);
    99     pp = const_bf_test.negativeCycle();
    10099   
    101100    for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
     
    134133    b  = bf_test.reached(t);
    135134    pp = bf_test.path(t);
    136     pp = bf_test.negativeCycle();
    137135  }
    138136}
  • test/digraph_test.cc

    r827 r787  
    2020#include <lemon/list_graph.h>
    2121#include <lemon/smart_graph.h>
    22 #include <lemon/static_graph.h>
    2322#include <lemon/full_graph.h>
    2423
     
    330329    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
    331330  }
    332   { // Checking StaticDigraph
    333     checkConcept<Digraph, StaticDigraph>();
    334     checkConcept<ClearableDigraphComponent<>, StaticDigraph>();
    335   }
    336331  { // Checking FullDigraph
    337332    checkConcept<Digraph, FullDigraph>();
     
    387382  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
    388383  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::Node
    407     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::Arc
    436     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.");
    496384}
    497385
     
    548436    checkDigraphValidity<SmartDigraph>();
    549437  }
    550   { // Checking StaticDigraph
    551     checkStaticDigraph();
    552   }
    553438  { // Checking FullDigraph
    554439    checkFullDigraph(8);
  • test/test_tools.h

    r810 r463  
    3838///print something like this (and then exits).
    3939///\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 { } \
    4945
    5046#endif
Note: See TracChangeset for help on using the changeset viewer.