COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
53 deleted
103 edited

Legend:

Unmodified
Added
Removed

  • .hgignore

    r564 r514  
    2828.deps/*
    2929demo/*.eps
    30 m4/libtool.m4
    31 m4/ltoptions.m4
    32 m4/ltsugar.m4
    33 m4/ltversion.m4
    34 m4/lt~obsolete.m4
    3530
    3631syntax: regexp
    … …  
    4136^autom4te.cache/.*
    4237^build-aux/.*
    43 ^.*objs.*/.*
     38^objs.*/.*
    4439^test/[a-z_]*$
    45 ^tools/[a-z-_]*$
    4640^demo/.*_demo$
    47 ^.*build.*/.*
     41^build/.*
    4842^doc/gen-images/.*
    4943CMakeFiles

  • CMakeLists.txt

    r574 r520  
    1414INCLUDE(FindDoxygen)
    1515INCLUDE(FindGhostscript)
    16 FIND_PACKAGE(GLPK 4.33)
    17 
    18 ADD_DEFINITIONS(-DHAVE_CONFIG_H)
    19 
    20 IF(MSVC)
    21   SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} /wd4250 /wd4355 /wd4800 /wd4996")
    22 # Suppressed warnings:
    23 # C4250: 'class1' : inherits 'class2::member' via dominance
    24 # C4355: 'this' : used in base member initializer list
    25 # C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
    26 # C4996: 'function': was declared deprecated
    27 ENDIF(MSVC)
    28 
    29 IF(GLPK_FOUND)
    30   SET(HAVE_LP TRUE)
    31   SET(HAVE_MIP TRUE)
    32   SET(HAVE_GLPK TRUE)
    33 ENDIF(GLPK_FOUND)
    3416
    3517INCLUDE(CheckTypeSize)
    … …  
    4022ADD_SUBDIRECTORY(lemon)
    4123ADD_SUBDIRECTORY(demo)
    42 ADD_SUBDIRECTORY(tools)
    4324ADD_SUBDIRECTORY(doc)
    4425ADD_SUBDIRECTORY(test)
    … …  
    5839    "${PROJECT_NAME} ${PROJECT_VERSION}")
    5940
    60   SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
     41  SET(CPACK_COMPONENTS_ALL headers library html_documentation)
    6142
    6243  SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
    6344  SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
    64   SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
    6545  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
    6646
    … …  
    6949  SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
    7050    "DLL and import library")
    71   SET(CPACK_COMPONENT_BIN_DESCRIPTION
    72     "Command line utilities")
    7351  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
    7452    "Doxygen generated documentation")

  • LICENSE

    r463 r107  
    22copyright/license.
    33
    4 Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi
     4Copyright (C) 2003-2008 Egervary Jeno Kombinatorikus Optimalizalasi
    55Kutatocsoport (Egervary Combinatorial Optimization Research Group,
    66EGRES).

  • Makefile.am

    r555 r503  
    11ACLOCAL_AMFLAGS = -I m4
    2 
    3 AM_CXXFLAGS = $(WARNINGCXXFLAGS)
    42
    53AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)
    … …  
    1412        CMakeLists.txt \
    1513        cmake/FindGhostscript.cmake \
    16         cmake/FindGLPK.cmake \
    1714        cmake/version.cmake.in \
    1815        cmake/version.cmake \

  • configure.ac

    r564 r515  
    1919AC_CONFIG_SRCDIR([lemon/list_graph.h])
    2020AC_CONFIG_HEADERS([config.h lemon/config.h])
     21
     22lx_cmdline_cxxflags_set=${CXXFLAGS+set}
    2123
    2224dnl Do compilation tests using the C++ compiler.
    … …  
    5153
    5254dnl Set custom compiler flags when using g++.
    53 if test "$GXX" = yes -a "$ICC" = no; then
    54   WARNINGCXXFLAGS="-Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
     55if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes -a "$ICC" = no; then
     56  CXXFLAGS="$CXXFLAGS -Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
    5557fi
    56 AC_SUBST([WARNINGCXXFLAGS])
    5758
    5859dnl Checks for libraries.
    59 LX_CHECK_GLPK
    60 LX_CHECK_CPLEX
    61 LX_CHECK_SOPLEX
    62 LX_CHECK_CLP
    63 
    64 AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
    65 AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
     60#LX_CHECK_GLPK
     61#LX_CHECK_CPLEX
     62#LX_CHECK_SOPLEX
    6663
    6764dnl Disable/enable building the demo programs.
    … …  
    124121echo
    125122echo C++ compiler.................. : $CXX
    126 echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
     123echo C++ compiles flags............ : $CXXFLAGS
    127124echo
    128125echo Compiler supports long long... : $long_long_found
    129126echo
    130 echo GLPK support.................. : $lx_glpk_found
    131 echo CPLEX support................. : $lx_cplex_found
    132 echo SOPLEX support................ : $lx_soplex_found
    133 echo CLP support................... : $lx_clp_found
    134 echo
     127#echo GLPK support.................. : $lx_glpk_found
     128#echo CPLEX support................. : $lx_cplex_found
     129#echo SOPLEX support................ : $lx_soplex_found
     130#echo
    135131echo Build demo programs........... : $enable_demo
    136132echo Build additional tools........ : $enable_tools

  • demo/CMakeLists.txt

    r498 r225  
    1 INCLUDE_DIRECTORIES(
    2   ${CMAKE_SOURCE_DIR}
    3   ${CMAKE_BINARY_DIR}
    4 )
     1INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
    52
    63LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)

  • demo/arg_parser_demo.cc

    r463 r311  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • demo/graph_to_eps_demo.cc

    r463 r313  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    8686    coords(coords).
    8787    title("Sample .eps figure").
    88     copyright("(C) 2003-2009 LEMON Project").
     88    copyright("(C) 2003-2008 LEMON Project").
    8989    run();
    9090
    … …  
    9393    coords(coords).
    9494    title("Sample .eps figure").
    95     copyright("(C) 2003-2009 LEMON Project").
     95    copyright("(C) 2003-2008 LEMON Project").
    9696    absoluteNodeSizes().absoluteArcWidths().
    9797    nodeScale(2).nodeSizes(sizes).
    … …  
    106106  graphToEps(g,"graph_to_eps_demo_out_3_arr.eps").
    107107    title("Sample .eps figure (with arrowheads)").
    108     copyright("(C) 2003-2009 LEMON Project").
     108    copyright("(C) 2003-2008 LEMON Project").
    109109    absoluteNodeSizes().absoluteArcWidths().
    110110    nodeColors(composeMap(palette,colors)).
    … …  
    133133  graphToEps(g,"graph_to_eps_demo_out_4_par.eps").
    134134    title("Sample .eps figure (parallel arcs)").
    135     copyright("(C) 2003-2009 LEMON Project").
     135    copyright("(C) 2003-2008 LEMON Project").
    136136    absoluteNodeSizes().absoluteArcWidths().
    137137    nodeShapes(shapes).
    … …  
    148148  graphToEps(g,"graph_to_eps_demo_out_5_par_arr.eps").
    149149    title("Sample .eps figure (parallel arcs and arrowheads)").
    150     copyright("(C) 2003-2009 LEMON Project").
     150    copyright("(C) 2003-2008 LEMON Project").
    151151    absoluteNodeSizes().absoluteArcWidths().
    152152    nodeScale(2).nodeSizes(sizes).
    … …  
    164164  graphToEps(g,"graph_to_eps_demo_out_6_par_arr_a4.eps").
    165165    title("Sample .eps figure (fits to A4)").
    166     copyright("(C) 2003-2009 LEMON Project").
     166    copyright("(C) 2003-2008 LEMON Project").
    167167    scaleToA4().
    168168    absoluteNodeSizes().absoluteArcWidths().
    … …  
    194194    scale(60).
    195195    title("Sample .eps figure (Palette demo)").
    196     copyright("(C) 2003-2009 LEMON Project").
     196    copyright("(C) 2003-2008 LEMON Project").
    197197    coords(hcoords).
    198198    absoluteNodeSizes().absoluteArcWidths().

  • demo/lgf_demo.cc

    r463 r294  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • doc/CMakeLists.txt

    r565 r520  
    1515      COMMAND rm -rf gen-images
    1616      COMMAND mkdir gen-images
    17       COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
    1817      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
    1918      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps

  • doc/Doxyfile.in

    r379 r316  
    6767ENABLED_SECTIONS       =
    6868MAX_INITIALIZER_LINES  = 5
    69 SHOW_USED_FILES        = NO
     69SHOW_USED_FILES        = YES
    7070SHOW_DIRECTORIES       = YES
    7171SHOW_FILES             = YES

  • doc/Makefile.am

    r349 r317  
    1515
    1616DOC_EPS_IMAGES18 = \
    17         grid_graph.eps \
    1817        nodeshape_0.eps \
    1918        nodeshape_1.eps \

  • doc/coding_style.dox

    r463 r210  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • doc/dirs.dox

    r463 r318  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    7272\brief Auxiliary tools for implementation.
    7373
    74 This directory contains some auxiliary classes for implementing graphs,
     74This directory contains some auxiliary classes for implementing graphs, 
    7575maps and some other classes.
    7676As a user you typically don't have to deal with these files.

  • doc/groups.dox

    r478 r318  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    1717 */
    1818
    19 namespace lemon {
    20 
    2119/**
    2220@defgroup datas Data Structures
    … …  
    6361
    6462/**
    65 @defgroup graph_adaptors Adaptor Classes for Graphs
    66 @ingroup graphs
    67 \brief Adaptor classes for digraphs and graphs
    68 
    69 This group contains several useful adaptor classes for digraphs and graphs.
    70 
    71 The main parts of LEMON are the different graph structures, generic
    72 graph algorithms, graph concepts, which couple them, and graph
    73 adaptors. While the previous notions are more or less clear, the
    74 latter one needs further explanation. Graph adaptors are graph classes
    75 which serve for considering graph structures in different ways.
    76 
    77 A short example makes this much clearer.  Suppose that we have an
    78 instance \c g of a directed graph type, say ListDigraph and an algorithm
    79 \code
    80 template <typename Digraph>
    81 int algorithm(const Digraph&);
    82 \endcode
    83 is needed to run on the reverse oriented graph.  It may be expensive
    84 (in time or in memory usage) to copy \c g with the reversed
    85 arcs.  In this case, an adaptor class is used, which (according
    86 to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
    87 The adaptor uses the original digraph structure and digraph operations when
    88 methods of the reversed oriented graph are called.  This means that the adaptor
    89 have minor memory usage, and do not perform sophisticated algorithmic
    90 actions.  The purpose of it is to give a tool for the cases when a
    91 graph have to be used in a specific alteration.  If this alteration is
    92 obtained by a usual construction like filtering the node or the arc set or
    93 considering a new orientation, then an adaptor is worthwhile to use.
    94 To come back to the reverse oriented graph, in this situation
    95 \code
    96 template<typename Digraph> class ReverseDigraph;
    97 \endcode
    98 template class can be used. The code looks as follows
    99 \code
    100 ListDigraph g;
    101 ReverseDigraph<ListDigraph> rg(g);
    102 int result = algorithm(rg);
    103 \endcode
    104 During running the algorithm, the original digraph \c g is untouched.
    105 This techniques give rise to an elegant code, and based on stable
    106 graph adaptors, complex algorithms can be implemented easily.
    107 
    108 In flow, circulation and matching problems, the residual
    109 graph is of particular importance. Combining an adaptor implementing
    110 this with shortest path algorithms or minimum mean cycle algorithms,
    111 a range of weighted and cardinality optimization algorithms can be
    112 obtained. For other examples, the interested user is referred to the
    113 detailed documentation of particular adaptors.
    114 
    115 The behavior of graph adaptors can be very different. Some of them keep
    116 capabilities of the original graph while in other cases this would be
    117 meaningless. This means that the concepts that they meet depend
    118 on the graph adaptor, and the wrapped graph.
    119 For example, if an arc of a reversed digraph is deleted, this is carried
    120 out by deleting the corresponding arc of the original digraph, thus the
    121 adaptor modifies the original digraph.
    122 However in case of a residual digraph, this operation has no sense.
    123 
    124 Let us stand one more example here to simplify your work.
    125 ReverseDigraph has constructor
    126 \code
    127 ReverseDigraph(Digraph& digraph);
    128 \endcode
    129 This means that in a situation, when a <tt>const %ListDigraph&</tt>
    130 reference to a graph is given, then it have to be instantiated with
    131 <tt>Digraph=const %ListDigraph</tt>.
    132 \code
    133 int algorithm1(const ListDigraph& g) {
    134   ReverseDigraph<const ListDigraph> rg(g);
    135   return algorithm2(rg);
    136 }
    137 \endcode
    138 */
    139 
    140 /**
    14163@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
    14264@ingroup graphs
    … …  
    16789
    16890This group describes maps that are specifically designed to assign
    169 values to the nodes and arcs/edges of graphs.
    170 
    171 If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
    172 \c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
     91values to the nodes and arcs of graphs.
    17392*/
    17493
    … …  
    181100maps from other maps.
    182101
    183 Most of them are \ref concepts::ReadMap "read-only maps".
     102Most of them are \ref lemon::concepts::ReadMap "read-only maps".
    184103They can make arithmetic and logical operations between one or two maps
    185104(negation, shifting, addition, multiplication, logical 'and', 'or',
    … …  
    283202\brief Common graph search algorithms.
    284203
    285 This group describes the common graph search algorithms, namely
    286 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
     204This group describes the common graph search algorithms like
     205Breadth-First Search (BFS) and Depth-First Search (DFS).
    287206*/
    288207
    … …  
    292211\brief Algorithms for finding shortest paths.
    293212
    294 This group describes the algorithms for finding shortest paths in digraphs.
    295 
    296  - \ref Dijkstra algorithm for finding shortest paths from a source node
    297    when all arc lengths are non-negative.
    298  - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
    299    from a source node when arc lenghts can be either positive or negative,
    300    but the digraph should not contain directed cycles with negative total
    301    length.
    302  - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
    303    for solving the \e all-pairs \e shortest \e paths \e problem when arc
    304    lenghts can be either positive or negative, but the digraph should
    305    not contain directed cycles with negative total length.
    306  - \ref Suurballe A successive shortest path algorithm for finding
    307    arc-disjoint paths between two nodes having minimum total length.
     213This group describes the algorithms for finding shortest paths in graphs.
    308214*/
    309215
    … …  
    316222feasible circulations.
    317223
    318 The \e maximum \e flow \e problem is to find a flow of maximum value between
    319 a single source and a single target. Formally, there is a \f$G=(V,A)\f$
    320 digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
    321 \f$s, t \in V\f$ source and target nodes.
    322 A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
    323 following optimization problem.
    324 
    325 \f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
    326 \f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
    327     \qquad \forall v\in V\setminus\{s,t\} \f]
    328 \f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
     224The maximum flow problem is to find a flow between a single source and
     225a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
     226directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
     227function and given \f$s, t \in V\f$ source and target node. The
     228maximum flow is the \f$f_a\f$ solution of the next optimization problem:
     229
     230\f[ 0 \le f_a \le c_a \f]
     231\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
     232\qquad \forall u \in V \setminus \{s,t\}\f]
     233\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
    329234
    330235LEMON contains several algorithms for solving maximum flow problems:
    331 - \ref EdmondsKarp Edmonds-Karp algorithm.
    332 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
    333 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
    334 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
    335 
    336 In most cases the \ref Preflow "Preflow" algorithm provides the
    337 fastest method for computing a maximum flow. All implementations
    338 provides functions to also query the minimum cut, which is the dual
    339 problem of the maximum flow.
     236- \ref lemon::EdmondsKarp "Edmonds-Karp"
     237- \ref lemon::Preflow "Goldberg's Preflow algorithm"
     238- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
     239- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
     240
     241In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
     242fastest method to compute the maximum flow. All impelementations
     243provides functions to query the minimum cut, which is the dual linear
     244programming problem of the maximum flow.
    340245*/
    341246
    … …  
    348253This group describes the algorithms for finding minimum cost flows and
    349254circulations.
    350 
    351 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
    352 minimum total cost from a set of supply nodes to a set of demand nodes
    353 in a network with capacity constraints and arc costs.
    354 Formally, let \f$G=(V,A)\f$ be a digraph,
    355 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
    356 upper bounds for the flow values on the arcs,
    357 \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
    358 on the arcs, and
    359 \f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
    360 of the nodes.
    361 A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
    362 the following optimization problem.
    363 
    364 \f[ \min\sum_{a\in A} f(a) cost(a) \f]
    365 \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
    366     supply(v) \qquad \forall v\in V \f]
    367 \f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
    368 
    369 LEMON contains several algorithms for solving minimum cost flow problems:
    370  - \ref CycleCanceling Cycle-canceling algorithms.
    371  - \ref CapacityScaling Successive shortest path algorithm with optional
    372    capacity scaling.
    373  - \ref CostScaling Push-relabel and augment-relabel algorithms based on
    374    cost scaling.
    375  - \ref NetworkSimplex Primal network simplex algorithm with various
    376    pivot strategies.
    377255*/
    378256
    … …  
    385263This group describes the algorithms for finding minimum cut in graphs.
    386264
    387 The \e minimum \e cut \e problem is to find a non-empty and non-complete
    388 \f$X\f$ subset of the nodes with minimum overall capacity on
    389 outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
    390 \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
     265The minimum cut problem is to find a non-empty and non-complete
     266\f$X\f$ subset of the vertices with minimum overall capacity on
     267outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
     268\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
    391269cut is the \f$X\f$ solution of the next optimization problem:
    392270
    393271\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    394     \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
     272\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
    395273
    396274LEMON contains several algorithms related to minimum cut problems:
    397275
    398 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
    399   in directed graphs.
    400 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
    401   calculating minimum cut in undirected graphs.
    402 - \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
    403   all-pairs minimum cut in undirected graphs.
     276- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
     277  in directed graphs
     278- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
     279  calculate minimum cut in undirected graphs
     280- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
     281  pairs minimum cut in undirected graphs
    404282
    405283If you want to find minimum cut just between two distinict nodes,
    406 see the \ref max_flow "maximum flow problem".
     284please see the \ref max_flow "Maximum Flow page".
    407285*/
    408286
    … …  
    443321graphs.  The matching problems in bipartite graphs are generally
    444322easier than in general graphs. The goal of the matching optimization
    445 can be finding maximum cardinality, maximum weight or minimum cost
     323can be the finding maximum cardinality, maximum weight or minimum cost
    446324matching. The search can be constrained to find perfect or
    447325maximum cardinality matching.
    448326
    449 The matching algorithms implemented in LEMON:
    450 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
    451   for calculating maximum cardinality matching in bipartite graphs.
    452 - \ref PrBipartiteMatching Push-relabel algorithm
    453   for calculating maximum cardinality matching in bipartite graphs.
    454 - \ref MaxWeightedBipartiteMatching
    455   Successive shortest path algorithm for calculating maximum weighted
    456   matching and maximum weighted bipartite matching in bipartite graphs.
    457 - \ref MinCostMaxBipartiteMatching
    458   Successive shortest path algorithm for calculating minimum cost maximum
    459   matching in bipartite graphs.
    460 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    461   maximum cardinality matching in general graphs.
    462 - \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
    463   maximum weighted matching in general graphs.
    464 - \ref MaxWeightedPerfectMatching
    465   Edmond's blossom shrinking algorithm for calculating maximum weighted
    466   perfect matching in general graphs.
     327LEMON contains the next algorithms:
     328- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
     329  augmenting path algorithm for calculate maximum cardinality matching in
     330  bipartite graphs
     331- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
     332  algorithm for calculate maximum cardinality matching in bipartite graphs
     333- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
     334  Successive shortest path algorithm for calculate maximum weighted matching
     335  and maximum weighted bipartite matching in bipartite graph
     336- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
     337  Successive shortest path algorithm for calculate minimum cost maximum
     338  matching in bipartite graph
     339- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
     340  for calculate maximum cardinality matching in general graph
     341- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
     342  shrinking algorithm for calculate maximum weighted matching in general
     343  graph
     344- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
     345  Edmond's blossom shrinking algorithm for calculate maximum weighted
     346  perfect matching in general graph
    467347
    468348\image html bipartite_matching.png
    … …  
    476356
    477357This group describes the algorithms for finding a minimum cost spanning
    478 tree in a graph.
     358tree in a graph
    479359*/
    480360
    … …  
    585465
    586466/**
    587 @defgroup lemon_io LEMON Graph Format
     467@defgroup lemon_io LEMON Input-Output
    588468@ingroup io_group
    589469\brief Reading and writing LEMON Graph Format.
    … …  
    600480This group describes general \c EPS drawing methods and special
    601481graph exporting tools.
    602 */
    603 
    604 /**
    605 @defgroup dimacs_group DIMACS format
    606 @ingroup io_group
    607 \brief Read and write files in DIMACS format
    608 
    609 Tools to read a digraph from or write it to a file in DIMACS format data.
    610 */
    611 
    612 /**
    613 @defgroup nauty_group NAUTY Format
    614 @ingroup io_group
    615 \brief Read \e Nauty format
    616 
    617 Tool to read graphs from \e Nauty format data.
    618482*/
    619483
    … …  
    667531\anchor demoprograms
    668532
    669 @defgroup demos Demo Programs
     533@defgroup demos Demo programs
    670534
    671535Some demo programs are listed here. Their full source codes can be found in
    … …  
    677541
    678542/**
    679 @defgroup tools Standalone Utility Applications
     543@defgroup tools Standalone utility applications
    680544
    681545Some utility applications are listed here.
    … …  
    685549*/
    686550
    687 }

  • doc/lgf.dox

    r463 r313  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • doc/license.dox

    r463 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • doc/mainpage.dox

    r463 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • doc/migration.dox

    r463 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    2626
    2727Many of these changes adjusted automatically by the
    28 <tt>lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual
     28<tt>script/lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual
    2929update are typeset <b>boldface</b>.
    3030
    … …  
    5454
    5555\warning
    56 <b>The <tt>lemon-0.x-to-1.x.sh</tt> script replaces the words \c graph,
    57 \c ugraph, \c edge and \c uedge in your own identifiers and in
    58 strings, comments etc. as well as in all LEMON specific identifiers.
    59 So use the script carefully and make a backup copy of your source files
    60 before applying the script to them.</b>
     56<b>The <tt>script/lemon-0.x-to-1.x.sh</tt> tool replaces all instances of
     57the words \c graph, \c digraph, \c edge and \c arc, so it replaces them
     58in strings, comments etc. as well as in all identifiers.</b>
    6159
    6260\section migration-lgf LGF tools

  • doc/named-param.dox

    r463 r269  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • doc/namespaces.dox

    r463 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • doc/template.h

    r463 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/CMakeLists.txt

    r562 r511  
    1 INCLUDE_DIRECTORIES(
    2   ${CMAKE_SOURCE_DIR}
    3   ${CMAKE_BINARY_DIR}
    4 )
     1INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
    52
    6 CONFIGURE_FILE(
    7   ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake
    8   ${CMAKE_CURRENT_BINARY_DIR}/config.h
    9 )
    10 
    11 SET(LEMON_SOURCES
     3ADD_LIBRARY(lemon
    124  arg_parser.cc
    135  base.cc
    146  color.cc
    15   lp_base.cc
    16   lp_skeleton.cc
    177  random.cc
    188  bits/windows.cc
    199)
    20 
    21 IF(HAVE_GLPK)
    22   SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc)
    23   INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR})
    24   IF(WIN32)
    25     INSTALL(FILES ${GLPK_BIN_DIR}/glpk.dll DESTINATION bin)
    26     INSTALL(FILES ${GLPK_BIN_DIR}/libltdl3.dll DESTINATION bin)
    27     INSTALL(FILES ${GLPK_BIN_DIR}/zlib1.dll DESTINATION bin)
    28   ENDIF(WIN32)
    29 ENDIF(HAVE_GLPK)
    30 
    31 ADD_LIBRARY(lemon ${LEMON_SOURCES})
    3210
    3311INSTALL(

  • lemon/Makefile.am

    r575 r511  
    88
    99lemon_libemon_la_SOURCES = \
    10         lemon/arg_parser.cc \
    11         lemon/base.cc \
    12         lemon/color.cc \
    13         lemon/lp_base.cc \
    14         lemon/lp_skeleton.cc \
     10        lemon/arg_parser.cc \
     11        lemon/base.cc \
     12        lemon/color.cc \
    1513        lemon/random.cc \
    1614        lemon/bits/windows.cc
    1715
    18 
    19 lemon_libemon_la_CXXFLAGS = \
    20         $(GLPK_CFLAGS) \
    21         $(CPLEX_CFLAGS) \
    22         $(SOPLEX_CXXFLAGS) \
    23         $(CLP_CXXFLAGS)
    24 
    25 lemon_libemon_la_LDFLAGS = \
    26         $(GLPK_LIBS) \
    27         $(CPLEX_LIBS) \
    28         $(SOPLEX_LIBS) \
    29         $(CLP_LIBS)
    30 
    31 if HAVE_GLPK
    32 lemon_libemon_la_SOURCES += lemon/glpk.cc
    33 endif
    34 
    35 if HAVE_CPLEX
    36 lemon_libemon_la_SOURCES += lemon/cplex.cc
    37 endif
    38 
    39 if HAVE_SOPLEX
    40 lemon_libemon_la_SOURCES += lemon/soplex.cc
    41 endif
    42 
    43 if HAVE_CLP
    44 lemon_libemon_la_SOURCES += lemon/clp.cc
    45 endif
     16#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
     17#lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
    4618
    4719lemon_HEADERS += \
    48         lemon/adaptors.h \
    49         lemon/arg_parser.h \
     20        lemon/arg_parser.h \
    5021        lemon/assert.h \
    51         lemon/bfs.h \
    52         lemon/bin_heap.h \
    53         lemon/circulation.h \
    54         lemon/clp.h \
    55         lemon/color.h \
     22        lemon/bfs.h \
     23        lemon/bin_heap.h \
     24        lemon/color.h \
    5625        lemon/concept_check.h \
    57         lemon/connectivity.h \
    58         lemon/counter.h \
     26        lemon/counter.h \
    5927        lemon/core.h \
    60         lemon/cplex.h \
    61         lemon/dfs.h \
    62         lemon/dijkstra.h \
    63         lemon/dim2.h \
    64         lemon/dimacs.h \
    65         lemon/edge_set.h \
    66         lemon/elevator.h \
     28        lemon/dfs.h \
     29        lemon/dijkstra.h \
     30        lemon/dim2.h \
    6731        lemon/error.h \
    68         lemon/euler.h \
    69         lemon/full_graph.h \
    70         lemon/glpk.h \
    71         lemon/graph_to_eps.h \
    72         lemon/grid_graph.h \
    73         lemon/hypercube_graph.h \
     32        lemon/graph_to_eps.h \
    7433        lemon/kruskal.h \
    75         lemon/hao_orlin.h \
    7634        lemon/lgf_reader.h \
    7735        lemon/lgf_writer.h \
    7836        lemon/list_graph.h \
    79         lemon/lp.h \
    80         lemon/lp_base.h \
    81         lemon/lp_skeleton.h \
    82         lemon/list_graph.h \
    8337        lemon/maps.h \
    8438        lemon/math.h \
    85         lemon/max_matching.h \
    86         lemon/min_cost_arborescence.h \
    87         lemon/nauty_reader.h \
    8839        lemon/path.h \
    89         lemon/preflow.h \
    90         lemon/radix_sort.h \
    91         lemon/random.h \
     40        lemon/random.h \
    9241        lemon/smart_graph.h \
    93         lemon/soplex.h \
    94         lemon/suurballe.h \
    95         lemon/time_measure.h \
    96         lemon/tolerance.h \
     42        lemon/time_measure.h \
     43        lemon/tolerance.h \
    9744        lemon/unionfind.h \
    9845        lemon/bits/windows.h
    … …  
    10249        lemon/bits/array_map.h \
    10350        lemon/bits/base_extender.h \
    104         lemon/bits/bezier.h \
     51        lemon/bits/bezier.h \
    10552        lemon/bits/default_map.h \
    106         lemon/bits/edge_set_extender.h \
    107         lemon/bits/enable_if.h \
    108         lemon/bits/graph_adaptor_extender.h \
     53        lemon/bits/enable_if.h \
    10954        lemon/bits/graph_extender.h \
    11055        lemon/bits/map_extender.h \
    11156        lemon/bits/path_dump.h \
    112         lemon/bits/solver_bits.h \
    11357        lemon/bits/traits.h \
    114         lemon/bits/variant.h \
    11558        lemon/bits/vector_map.h
    11659

  • lemon/arg_parser.cc

    r463 r311  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/arg_parser.h

    r463 r311  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/assert.h

    r463 r290  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/base.cc

    r554 r220  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    2424namespace lemon {
    2525
    26   float Tolerance<float>::def_epsilon = static_cast<float>(1e-4);
     26  float Tolerance<float>::def_epsilon = 1e-4;
    2727  double Tolerance<double>::def_epsilon = 1e-10;
    2828  long double Tolerance<long double>::def_epsilon = 1e-14;

  • lemon/bfs.h

    r525 r301  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    5050    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    52     ///Instantiates a \c PredMap.
    53 
    54     ///This function instantiates a \ref PredMap.
     52    ///Instantiates a PredMap.
     53
     54    ///This function instantiates a PredMap.
    5555    ///\param g is the digraph, to which we would like to define the
    56     ///\ref PredMap.
     56    ///PredMap.
    5757    static PredMap *createPredMap(const Digraph &g)
    5858    {
    … …  
    6565    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6666    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    67     ///Instantiates a \c ProcessedMap.
    68 
    69     ///This function instantiates a \ref ProcessedMap.
     67    ///Instantiates a ProcessedMap.
     68
     69    ///This function instantiates a ProcessedMap.
    7070    ///\param g is the digraph, to which
    71     ///we would like to define the \ref ProcessedMap
     71    ///we would like to define the ProcessedMap
    7272#ifdef DOXYGEN
    7373    static ProcessedMap *createProcessedMap(const Digraph &g)
    … …  
    8484    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8585    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    86     ///Instantiates a \c ReachedMap.
    87 
    88     ///This function instantiates a \ref ReachedMap.
     86    ///Instantiates a ReachedMap.
     87
     88    ///This function instantiates a ReachedMap.
    8989    ///\param g is the digraph, to which
    90     ///we would like to define the \ref ReachedMap.
     90    ///we would like to define the ReachedMap.
    9191    static ReachedMap *createReachedMap(const Digraph &g)
    9292    {
    … …  
    9999    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    100100    typedef typename Digraph::template NodeMap<int> DistMap;
    101     ///Instantiates a \c DistMap.
    102 
    103     ///This function instantiates a \ref DistMap.
     101    ///Instantiates a DistMap.
     102
     103    ///This function instantiates a DistMap.
    104104    ///\param g is the digraph, to which we would like to define the
    105     ///\ref DistMap.
     105    ///DistMap.
    106106    static DistMap *createDistMap(const Digraph &g)
    107107    {
    … …  
    120120  ///
    121121  ///\tparam GR The type of the digraph the algorithm runs on.
    122   ///The default type is \ref ListDigraph.
     122  ///The default value is \ref ListDigraph. The value of GR is not used
     123  ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
     124  ///\tparam TR Traits class to set various data types used by the algorithm.
     125  ///The default traits class is
     126  ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
     127  ///See \ref BfsDefaultTraits for the documentation of
     128  ///a Bfs traits class.
    123129#ifdef DOXYGEN
    124130  template <typename GR,
    … …  
    146152    typedef PredMapPath<Digraph, PredMap> Path;
    147153
    148     ///The \ref BfsDefaultTraits "traits class" of the algorithm.
     154    ///The traits class.
    149155    typedef TR Traits;
    150156
    … …  
    208214    typedef Bfs Create;
    209215
    210     ///\name Named Template Parameters
     216    ///\name Named template parameters
    211217
    212218    ///@{
    … …  
    222228    };
    223229    ///\brief \ref named-templ-param "Named parameter" for setting
    224     ///\c PredMap type.
     230    ///PredMap type.
    225231    ///
    226232    ///\ref named-templ-param "Named parameter" for setting
    227     ///\c PredMap type.
    228     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     233    ///PredMap type.
    229234    template <class T>
    230235    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
    … …  
    242247    };
    243248    ///\brief \ref named-templ-param "Named parameter" for setting
    244     ///\c DistMap type.
     249    ///DistMap type.
    245250    ///
    246251    ///\ref named-templ-param "Named parameter" for setting
    247     ///\c DistMap type.
    248     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     252    ///DistMap type.
    249253    template <class T>
    250254    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
    … …  
    262266    };
    263267    ///\brief \ref named-templ-param "Named parameter" for setting
    264     ///\c ReachedMap type.
     268    ///ReachedMap type.
    265269    ///
    266270    ///\ref named-templ-param "Named parameter" for setting
    267     ///\c ReachedMap type.
    268     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     271    ///ReachedMap type.
    269272    template <class T>
    270273    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
    … …  
    282285    };
    283286    ///\brief \ref named-templ-param "Named parameter" for setting
    284     ///\c ProcessedMap type.
     287    ///ProcessedMap type.
    285288    ///
    286289    ///\ref named-templ-param "Named parameter" for setting
    287     ///\c ProcessedMap type.
    288     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     290    ///ProcessedMap type.
    289291    template <class T>
    290292    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
    … …  
    301303    };
    302304    ///\brief \ref named-templ-param "Named parameter" for setting
    303     ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     305    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    304306    ///
    305307    ///\ref named-templ-param "Named parameter" for setting
    306     ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     308    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    307309    ///If you don't set it explicitly, it will be automatically allocated.
    308310    struct SetStandardProcessedMap :
    … …  
    339341
    340342    ///Sets the map that stores the predecessor arcs.
    341     ///If you don't use this function before calling \ref run(Node) "run()"
    342     ///or \ref init(), an instance will be allocated automatically.
    343     ///The destructor deallocates this automatically allocated map,
    344     ///of course.
     343    ///If you don't use this function before calling \ref run(),
     344    ///it will allocate one. The destructor deallocates this
     345    ///automatically allocated map, of course.
    345346    ///\return <tt> (*this) </tt>
    346347    Bfs &predMap(PredMap &m)
    … …  
    357358
    358359    ///Sets the map that indicates which nodes are reached.
    359     ///If you don't use this function before calling \ref run(Node) "run()"
    360     ///or \ref init(), an instance will be allocated automatically.
    361     ///The destructor deallocates this automatically allocated map,
    362     ///of course.
     360    ///If you don't use this function before calling \ref run(),
     361    ///it will allocate one. The destructor deallocates this
     362    ///automatically allocated map, of course.
    363363    ///\return <tt> (*this) </tt>
    364364    Bfs &reachedMap(ReachedMap &m)
    … …  
    375375
    376376    ///Sets the map that indicates which nodes are processed.
    377     ///If you don't use this function before calling \ref run(Node) "run()"
    378     ///or \ref init(), an instance will be allocated automatically.
    379     ///The destructor deallocates this automatically allocated map,
    380     ///of course.
     377    ///If you don't use this function before calling \ref run(),
     378    ///it will allocate one. The destructor deallocates this
     379    ///automatically allocated map, of course.
    381380    ///\return <tt> (*this) </tt>
    382381    Bfs &processedMap(ProcessedMap &m)
    … …  
    394393    ///Sets the map that stores the distances of the nodes calculated by
    395394    ///the algorithm.
    396     ///If you don't use this function before calling \ref run(Node) "run()"
    397     ///or \ref init(), an instance will be allocated automatically.
    398     ///The destructor deallocates this automatically allocated map,
    399     ///of course.
     395    ///If you don't use this function before calling \ref run(),
     396    ///it will allocate one. The destructor deallocates this
     397    ///automatically allocated map, of course.
    400398    ///\return <tt> (*this) </tt>
    401399    Bfs &distMap(DistMap &m)
    … …  
    411409  public:
    412410
    413     ///\name Execution Control
    414     ///The simplest way to execute the BFS algorithm is to use one of the
    415     ///member functions called \ref run(Node) "run()".\n
    416     ///If you need more control on the execution, first you have to call
    417     ///\ref init(), then you can add several source nodes with
    418     ///\ref addSource(). Finally the actual path computation can be
    419     ///performed with one of the \ref start() functions.
     411    ///\name Execution control
     412    ///The simplest way to execute the algorithm is to use
     413    ///one of the member functions called \ref lemon::Bfs::run() "run()".
     414    ///\n
     415    ///If you need more control on the execution, first you must call
     416    ///\ref lemon::Bfs::init() "init()", then you can add several source
     417    ///nodes with \ref lemon::Bfs::addSource() "addSource()".
     418    ///Finally \ref lemon::Bfs::start() "start()" will perform the
     419    ///actual path computation.
    420420
    421421    ///@{
    422422
    423     ///\brief Initializes the internal data structures.
    424     ///
    425423    ///Initializes the internal data structures.
     424
     425    ///Initializes the internal data structures.
     426    ///
    426427    void init()
    427428    {
    … …  
    557558    }
    558559
    559     ///Returns \c false if there are nodes to be processed.
    560 
    561     ///Returns \c false if there are nodes to be processed
    562     ///in the queue.
     560    ///\brief Returns \c false if there are nodes
     561    ///to be processed.
     562    ///
     563    ///Returns \c false if there are nodes
     564    ///to be processed in the queue.
    563565    bool emptyQueue() const { return _queue_tail==_queue_head; }
    564566
    565567    ///Returns the number of the nodes to be processed.
    566568
    567     ///Returns the number of the nodes to be processed
    568     ///in the queue.
     569    ///Returns the number of the nodes to be processed in the queue.
    569570    int queueSize() const { return _queue_head-_queue_tail; }
    570571
    … …  
    731732
    732733    ///\name Query Functions
    733     ///The results of the BFS algorithm can be obtained using these
     734    ///The result of the %BFS algorithm can be obtained using these
    734735    ///functions.\n
    735     ///Either \ref run(Node) "run()" or \ref start() should be called
    736     ///before using them.
     736    ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
     737    ///"start()" must be called before using them.
    737738
    738739    ///@{
    … …  
    742743    ///Returns the shortest path to a node.
    743744    ///
    744     ///\warning \c t should be reached from the root(s).
    745     ///
    746     ///\pre Either \ref run(Node) "run()" or \ref init()
    747     ///must be called before using this function.
     745    ///\warning \c t should be reachable from the root(s).
     746    ///
     747    ///\pre Either \ref run() or \ref start() must be called before
     748    ///using this function.
    748749    Path path(Node t) const { return Path(*G, *_pred, t); }
    749750
    … …  
    752753    ///Returns the distance of a node from the root(s).
    753754    ///
    754     ///\warning If node \c v is not reached from the root(s), then
     755    ///\warning If node \c v is not reachable from the root(s), then
    755756    ///the return value of this function is undefined.
    756757    ///
    757     ///\pre Either \ref run(Node) "run()" or \ref init()
    758     ///must be called before using this function.
     758    ///\pre Either \ref run() or \ref start() must be called before
     759    ///using this function.
    759760    int dist(Node v) const { return (*_dist)[v]; }
    760761
    … …  
    763764    ///This function returns the 'previous arc' of the shortest path
    764765    ///tree for the node \c v, i.e. it returns the last arc of a
    765     ///shortest path from a root to \c v. It is \c INVALID if \c v
    766     ///is not reached from the root(s) or if \c v is a root.
     766    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
     767    ///is not reachable from the root(s) or if \c v is a root.
    767768    ///
    768769    ///The shortest path tree used here is equal to the shortest path
    769770    ///tree used in \ref predNode().
    770771    ///
    771     ///\pre Either \ref run(Node) "run()" or \ref init()
    772     ///must be called before using this function.
     772    ///\pre Either \ref run() or \ref start() must be called before
     773    ///using this function.
    773774    Arc predArc(Node v) const { return (*_pred)[v];}
    774775
    … …  
    777778    ///This function returns the 'previous node' of the shortest path
    778779    ///tree for the node \c v, i.e. it returns the last but one node
    779     ///from a shortest path from a root to \c v. It is \c INVALID
    780     ///if \c v is not reached from the root(s) or if \c v is a root.
     780    ///from a shortest path from the root(s) to \c v. It is \c INVALID
     781    ///if \c v is not reachable from the root(s) or if \c v is a root.
    781782    ///
    782783    ///The shortest path tree used here is equal to the shortest path
    783784    ///tree used in \ref predArc().
    784785    ///
    785     ///\pre Either \ref run(Node) "run()" or \ref init()
    786     ///must be called before using this function.
     786    ///\pre Either \ref run() or \ref start() must be called before
     787    ///using this function.
    787788    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    788789                                  G->source((*_pred)[v]); }
    … …  
    794795    ///of the nodes calculated by the algorithm.
    795796    ///
    796     ///\pre Either \ref run(Node) "run()" or \ref init()
     797    ///\pre Either \ref run() or \ref init()
    797798    ///must be called before using this function.
    798799    const DistMap &distMap() const { return *_dist;}
    … …  
    804805    ///arcs, which form the shortest path tree.
    805806    ///
    806     ///\pre Either \ref run(Node) "run()" or \ref init()
     807    ///\pre Either \ref run() or \ref init()
    807808    ///must be called before using this function.
    808809    const PredMap &predMap() const { return *_pred;}
    809810
    810     ///Checks if a node is reached from the root(s).
    811 
    812     ///Returns \c true if \c v is reached from the root(s).
    813     ///
    814     ///\pre Either \ref run(Node) "run()" or \ref init()
     811    ///Checks if a node is reachable from the root(s).
     812
     813    ///Returns \c true if \c v is reachable from the root(s).
     814    ///\pre Either \ref run() or \ref start()
    815815    ///must be called before using this function.
    816816    bool reached(Node v) const { return (*_reached)[v]; }
    … …  
    958958  /// This auxiliary class is created to implement the
    959959  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
    960   /// It does not have own \ref run(Node) "run()" method, it uses the
    961   /// functions and features of the plain \ref Bfs.
     960  /// It does not have own \ref run() method, it uses the functions
     961  /// and features of the plain \ref Bfs.
    962962  ///
    963963  /// This class should only be used through the \ref bfs() function,
    … …  
    11791179  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
    11801180  ///\endcode
    1181   ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
     1181  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
    11821182  ///to the end of the parameter list.
    11831183  ///\sa BfsWizard
    … …  
    11951195  /// This class defines the interface of the BfsVisit events, and
    11961196  /// it could be the base of a real visitor class.
    1197   template <typename GR>
     1197  template <typename _Digraph>
    11981198  struct BfsVisitor {
    1199     typedef GR Digraph;
     1199    typedef _Digraph Digraph;
    12001200    typedef typename Digraph::Arc Arc;
    12011201    typedef typename Digraph::Node Node;
    … …  
    12251225  };
    12261226#else
    1227   template <typename GR>
     1227  template <typename _Digraph>
    12281228  struct BfsVisitor {
    1229     typedef GR Digraph;
     1229    typedef _Digraph Digraph;
    12301230    typedef typename Digraph::Arc Arc;
    12311231    typedef typename Digraph::Node Node;
    … …  
    12551255  ///
    12561256  /// Default traits class of BfsVisit class.
    1257   /// \tparam GR The type of the digraph the algorithm runs on.
    1258   template<class GR>
     1257  /// \tparam _Digraph The type of the digraph the algorithm runs on.
     1258  template<class _Digraph>
    12591259  struct BfsVisitDefaultTraits {
    12601260
    12611261    /// \brief The type of the digraph the algorithm runs on.
    1262     typedef GR Digraph;
     1262    typedef _Digraph Digraph;
    12631263
    12641264    /// \brief The type of the map that indicates which nodes are reached.
    … …  
    12811281  /// \ingroup search
    12821282  ///
    1283   /// \brief BFS algorithm class with visitor interface.
     1283  /// \brief %BFS algorithm class with visitor interface.
    12841284  ///
    1285   /// This class provides an efficient implementation of the BFS algorithm
     1285  /// This class provides an efficient implementation of the %BFS algorithm
    12861286  /// with visitor interface.
    12871287  ///
    1288   /// The BfsVisit class provides an alternative interface to the Bfs
     1288  /// The %BfsVisit class provides an alternative interface to the Bfs
    12891289  /// class. It works with callback mechanism, the BfsVisit object calls
    12901290  /// the member functions of the \c Visitor class on every BFS event.
    … …  
    12951295  /// instead.
    12961296  ///
    1297   /// \tparam GR The type of the digraph the algorithm runs on.
    1298   /// The default type is \ref ListDigraph.
    1299   /// The value of GR is not used directly by \ref BfsVisit,
    1300   /// it is only passed to \ref BfsVisitDefaultTraits.
    1301   /// \tparam VS The Visitor type that is used by the algorithm.
    1302   /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
     1297  /// \tparam _Digraph The type of the digraph the algorithm runs on.
     1298  /// The default value is
     1299  /// \ref ListDigraph. The value of _Digraph is not used directly by
     1300  /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
     1301  /// \tparam _Visitor The Visitor type that is used by the algorithm.
     1302  /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
    13031303  /// does not observe the BFS events. If you want to observe the BFS
    13041304  /// events, you should implement your own visitor class.
    1305   /// \tparam TR Traits class to set various data types used by the
     1305  /// \tparam _Traits Traits class to set various data types used by the
    13061306  /// algorithm. The default traits class is
    1307   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
     1307  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
    13081308  /// See \ref BfsVisitDefaultTraits for the documentation of
    13091309  /// a BFS visit traits class.
    13101310#ifdef DOXYGEN
    1311   template <typename GR, typename VS, typename TR>
     1311  template <typename _Digraph, typename _Visitor, typename _Traits>
    13121312#else
    1313   template <typename GR = ListDigraph,
    1314             typename VS = BfsVisitor<GR>,
    1315             typename TR = BfsVisitDefaultTraits<GR> >
     1313  template <typename _Digraph = ListDigraph,
     1314            typename _Visitor = BfsVisitor<_Digraph>,
     1315            typename _Traits = BfsVisitDefaultTraits<_Digraph> >
    13161316#endif
    13171317  class BfsVisit {
    … …  
    13191319
    13201320    ///The traits class.
    1321     typedef TR Traits;
     1321    typedef _Traits Traits;
    13221322
    13231323    ///The type of the digraph the algorithm runs on.
    … …  
    13251325
    13261326    ///The visitor type used by the algorithm.
    1327     typedef VS Visitor;
     1327    typedef _Visitor Visitor;
    13281328
    13291329    ///The type of the map that indicates which nodes are reached.
    … …  
    13651365    typedef BfsVisit Create;
    13661366
    1367     /// \name Named Template Parameters
     1367    /// \name Named template parameters
    13681368
    13691369    ///@{
    … …  
    14071407    ///
    14081408    /// Sets the map that indicates which nodes are reached.
    1409     /// If you don't use this function before calling \ref run(Node) "run()"
    1410     /// or \ref init(), an instance will be allocated automatically.
    1411     /// The destructor deallocates this automatically allocated map,
    1412     /// of course.
     1409    /// If you don't use this function before calling \ref run(),
     1410    /// it will allocate one. The destructor deallocates this
     1411    /// automatically allocated map, of course.
    14131412    /// \return <tt> (*this) </tt>
    14141413    BfsVisit &reachedMap(ReachedMap &m) {
    … …  
    14231422  public:
    14241423
    1425     /// \name Execution Control
    1426     /// The simplest way to execute the BFS algorithm is to use one of the
    1427     /// member functions called \ref run(Node) "run()".\n
    1428     /// If you need more control on the execution, first you have to call
    1429     /// \ref init(), then you can add several source nodes with
    1430     /// \ref addSource(). Finally the actual path computation can be
    1431     /// performed with one of the \ref start() functions.
     1424    /// \name Execution control
     1425    /// The simplest way to execute the algorithm is to use
     1426    /// one of the member functions called \ref lemon::BfsVisit::run()
     1427    /// "run()".
     1428    /// \n
     1429    /// If you need more control on the execution, first you must call
     1430    /// \ref lemon::BfsVisit::init() "init()", then you can add several
     1431    /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
     1432    /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
     1433    /// actual path computation.
    14321434
    14331435    /// @{
    … …  
    17291731
    17301732    /// \name Query Functions
    1731     /// The results of the BFS algorithm can be obtained using these
     1733    /// The result of the %BFS algorithm can be obtained using these
    17321734    /// functions.\n
    1733     /// Either \ref run(Node) "run()" or \ref start() should be called
    1734     /// before using them.
    1735 
     1735    /// Either \ref lemon::BfsVisit::run() "run()" or
     1736    /// \ref lemon::BfsVisit::start() "start()" must be called before
     1737    /// using them.
    17361738    ///@{
    17371739
    1738     /// \brief Checks if a node is reached from the root(s).
    1739     ///
    1740     /// Returns \c true if \c v is reached from the root(s).
    1741     ///
    1742     /// \pre Either \ref run(Node) "run()" or \ref init()
     1740    /// \brief Checks if a node is reachable from the root(s).
     1741    ///
     1742    /// Returns \c true if \c v is reachable from the root(s).
     1743    /// \pre Either \ref run() or \ref start()
    17431744    /// must be called before using this function.
    1744     bool reached(Node v) const { return (*_reached)[v]; }
     1745    bool reached(Node v) { return (*_reached)[v]; }
    17451746
    17461747    ///@}

  • lemon/bin_heap.h

    r463 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/bits/alteration_notifier.h

    r463 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    3636  // a container.
    3737  //
    38   // The simple graphs can be refered as two containers: a node container
    39   // and an edge container. But they do not store values directly, they
    40   // are just key continars for more value containers, which are the
    41   // node and edge maps.
    42   //
    43   // The node and edge sets of the graphs can be changed as we add or erase
     38  // The simple graph's can be refered as two containers, one node container
     39  // and one edge container. But they are not standard containers they
     40  // does not store values directly they are just key continars for more
     41  // value containers which are the node and edge maps.
     42  //
     43  // The graph's node and edge sets can be changed as we add or erase
    4444  // nodes and edges in the graph. LEMON would like to handle easily
    4545  // that the node and edge maps should contain values for all nodes or
    4646  // edges. If we want to check on every indicing if the map contains
    4747  // the current indicing key that cause a drawback in the performance
    48   // in the library. We use another solution: we notify all maps about
     48  // in the library. We use another solution we notify all maps about
    4949  // an alteration in the graph, which cause only drawback on the
    5050  // alteration of the graph.
    5151  //
    52   // This class provides an interface to a node or edge container.
    53   // The first() and next() member functions make possible
    54   // to iterate on the keys of the container.
    55   // The id() function returns an integer id for each key.
    56   // The maxId() function gives back an upper bound of the ids.
     52  // This class provides an interface to the container. The \e first() and \e
     53  // next() member functions make possible to iterate on the keys of the
     54  // container. The \e id() function returns an integer id for each key.
     55  // The \e maxId() function gives back an upper bound of the ids.
    5756  //
    5857  // For the proper functonality of this class, we should notify it
    59   // about each alteration in the container. The alterations have four type:
    60   // add(), erase(), build() and clear(). The add() and
    61   // erase() signal that only one or few items added or erased to or
    62   // from the graph. If all items are erased from the graph or if a new graph
    63   // is built from an empty graph, then it can be signaled with the
     58  // about each alteration in the container. The alterations have four type
     59  // as \e add(), \e erase(), \e build() and \e clear(). The \e add() and
     60  // \e erase() signals that only one or few items added or erased to or
     61  // from the graph. If all items are erased from the graph or from an empty
     62  // graph a new graph is builded then it can be signaled with the
    6463  // clear() and build() members. Important rule that if we erase items
    65   // from graphs we should first signal the alteration and after that erase
     64  // from graph we should first signal the alteration and after that erase
    6665  // them from the container, on the other way on item addition we should
    6766  // first extend the container and just after that signal the alteration.
    6867  //
    6968  // The alteration can be observed with a class inherited from the
    70   // ObserverBase nested class. The signals can be handled with
     69  // \e ObserverBase nested class. The signals can be handled with
    7170  // overriding the virtual functions defined in the base class.  The
    7271  // observer base can be attached to the notifier with the
    73   // attach() member and can be detached with detach() function. The
     72  // \e attach() member and can be detached with detach() function. The
    7473  // alteration handlers should not call any function which signals
    7574  // an other alteration in the same notifier and should not
    7675  // detach any observer from the notifier.
    7776  //
    78   // Alteration observers try to be exception safe. If an add() or
    79   // a clear() function throws an exception then the remaining
     77  // Alteration observers try to be exception safe. If an \e add() or
     78  // a \e clear() function throws an exception then the remaining
    8079  // observeres will not be notified and the fulfilled additions will
    81   // be rolled back by calling the erase() or clear() functions.
    82   // Hence erase() and clear() should not throw exception.
    83   // Actullay, they can throw only \ref ImmediateDetach exception,
    84   // which detach the observer from the notifier.
    85   //
    86   // There are some cases, when the alteration observing is not completly
     80  // be rolled back by calling the \e erase() or \e clear()
     81  // functions. Thence the \e erase() and \e clear() should not throw
     82  // exception. Actullay, it can be throw only \ref ImmediateDetach
     83  // exception which detach the observer from the notifier.
     84  //
     85  // There are some place when the alteration observing is not completly
    8786  // reliable. If we want to carry out the node degree in the graph
    88   // as in the \ref InDegMap and we use the reverseArc(), then it cause
     87  // as in the \ref InDegMap and we use the reverseEdge that cause
    8988  // unreliable functionality. Because the alteration observing signals
    90   // only erasing and adding but not the reversing, it will stores bad
    91   // degrees. Apart form that the subgraph adaptors cannot even signal
    92   // the alterations because just a setting in the filter map can modify
    93   // the graph and this cannot be watched in any way.
     89  // only erasing and adding but not the reversing it will stores bad
     90  // degrees. The sub graph adaptors cannot signal the alterations because
     91  // just a setting in the filter map can modify the graph and this cannot
     92  // be watched in any way.
    9493  //
    9594  // \param _Container The container which is observed.
    … …  
    105104    typedef _Item Item;
    106105
    107     // \brief Exception which can be called from clear() and
    108     // erase().
    109     //
    110     // From the clear() and erase() function only this
     106    // \brief Exception which can be called from \e clear() and
     107    // \e erase().
     108    //
     109    // From the \e clear() and \e erase() function only this
    111110    // exception is allowed to throw. The exception immediatly
    112111    // detaches the current observer from the notifier. Because the
    113     // clear() and erase() should not throw other exceptions
     112    // \e clear() and \e erase() should not throw other exceptions
    114113    // it can be used to invalidate the observer.
    115114    struct ImmediateDetach {};
    … …  
    123122    // The observer interface contains some pure virtual functions
    124123    // to override. The add() and erase() functions are
    125     // to notify the oberver when one item is added or erased.
     124    // to notify the oberver when one item is added or
     125    // erased.
    126126    //
    127127    // The build() and clear() members are to notify the observer

  • lemon/bits/array_map.h

    r525 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    3737  // \brief Graph map based on the array storage.
    3838  //
    39   // The ArrayMap template class is graph map structure that automatically
    40   // updates the map when a key is added to or erased from the graph.
    41   // This map uses the allocators to implement the container functionality.
     39  // The ArrayMap template class is graph map structure what
     40  // automatically updates the map when a key is added to or erased from
     41  // the map. This map uses the allocators to implement
     42  // the container functionality.
    4243  //
    43   // The template parameters are the Graph, the current Item type and
     44  // The template parameters are the Graph the current Item type and
    4445  // the Value type of the map.
    4546  template <typename _Graph, typename _Item, typename _Value>
    … …  
    4748    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    4849  public:
    49     // The graph type.
     50    // The graph type of the maps.
    5051    typedef _Graph Graph;
    51     // The item type.
     52    // The item type of the map.
    5253    typedef _Item Item;
    5354    // The reference map tag.
    5455    typedef True ReferenceMapTag;
    5556
    56     // The key type of the map.
     57    // The key type of the maps.
    5758    typedef _Item Key;
    5859    // The value type of the map.
    … …  
    136137    // \brief Template assign operator.
    137138    //
    138     // The given parameter should conform to the ReadMap
     139    // The given parameter should be conform to the ReadMap
    139140    // concecpt and could be indiced by the current item set of
    140141    // the NodeMap. In this case the value for each item
    … …  
    200201    // \brief Adds a new key to the map.
    201202    //
    202     // It adds a new key to the map. It is called by the observer notifier
     203    // It adds a new key to the map. It called by the observer notifier
    203204    // and it overrides the add() member function of the observer base.
    204205    virtual void add(const Key& key) {
    … …  
    228229    // \brief Adds more new keys to the map.
    229230    //
    230     // It adds more new keys to the map. It is called by the observer notifier
     231    // It adds more new keys to the map. It called by the observer notifier
    231232    // and it overrides the add() member function of the observer base.
    232233    virtual void add(const std::vector<Key>& keys) {
    … …  
    272273    // \brief Erase a key from the map.
    273274    //
    274     // Erase a key from the map. It is called by the observer notifier
     275    // Erase a key from the map. It called by the observer notifier
    275276    // and it overrides the erase() member function of the observer base.
    276277    virtual void erase(const Key& key) {
    … …  
    281282    // \brief Erase more keys from the map.
    282283    //
    283     // Erase more keys from the map. It is called by the observer notifier
     284    // Erase more keys from the map. It called by the observer notifier
    284285    // and it overrides the erase() member function of the observer base.
    285286    virtual void erase(const std::vector<Key>& keys) {
    … …  
    290291    }
    291292
    292     // \brief Builds the map.
    293     //
    294     // It builds the map. It is called by the observer notifier
     293    // \brief Buildes the map.
     294    //
     295    // It buildes the map. It called by the observer notifier
    295296    // and it overrides the build() member function of the observer base.
    296297    virtual void build() {
    … …  
    306307    // \brief Clear the map.
    307308    //
    308     // It erase all items from the map. It is called by the observer notifier
     309    // It erase all items from the map. It called by the observer notifier
    309310    // and it overrides the clear() member function of the observer base.
    310311    virtual void clear() {

  • lemon/bits/base_extender.h

    r463 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    3131//\ingroup digraphbits
    3232//\file
    33 //\brief Extenders for the graph types
     33//\brief Extenders for the digraph types
    3434namespace lemon {
    3535

  • lemon/bits/bezier.h

    r463 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/bits/default_map.h

    r582 r523  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/bits/enable_if.h

    r463 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/bits/graph_extender.h

    r463 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    3030//\ingroup graphbits
    3131//\file
    32 //\brief Extenders for the graph types
     32//\brief Extenders for the digraph types
    3333namespace lemon {
    3434
    3535  // \ingroup graphbits
    3636  //
    37   // \brief Extender for the digraph implementations
     37  // \brief Extender for the Digraphs
    3838  template <typename Base>
    3939  class DigraphExtender : public Base {

  • lemon/bits/map_extender.h

    r463 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/bits/path_dump.h

    r576 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    1717 */
    1818
    19 #ifndef LEMON_BITS_PATH_DUMP_H
    20 #define LEMON_BITS_PATH_DUMP_H
    21 
    22 #include <lemon/core.h>
    23 #include <lemon/concept_check.h>
     19#ifndef LEMON_BITS_PRED_MAP_PATH_H
     20#define LEMON_BITS_PRED_MAP_PATH_H
    2421
    2522namespace lemon {

  • lemon/bits/traits.h

    r463 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    219219
    220220  template <typename Graph, typename Enable = void>
    221   struct ArcNumTagIndicator {
    222     static const bool value = false;
    223   };
    224 
    225   template <typename Graph>
    226   struct ArcNumTagIndicator<
    227     Graph,
    228     typename enable_if<typename Graph::ArcNumTag, void>::type
    229   > {
    230     static const bool value = true;
    231   };
    232 
    233   template <typename Graph, typename Enable = void>
    234221  struct EdgeNumTagIndicator {
    235222    static const bool value = false;
    … …  
    245232
    246233  template <typename Graph, typename Enable = void>
    247   struct FindArcTagIndicator {
    248     static const bool value = false;
    249   };
    250 
    251   template <typename Graph>
    252   struct FindArcTagIndicator<
    253     Graph,
    254     typename enable_if<typename Graph::FindArcTag, void>::type
    255   > {
    256     static const bool value = true;
    257   };
    258 
    259   template <typename Graph, typename Enable = void>
    260234  struct FindEdgeTagIndicator {
    261235    static const bool value = false;

  • lemon/bits/vector_map.h

    r525 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    3939  // \brief Graph map based on the std::vector storage.
    4040  //
    41   // The VectorMap template class is graph map structure that automatically
    42   // updates the map when a key is added to or erased from the graph.
    43   // This map type uses std::vector to store the values.
     41  // The VectorMap template class is graph map structure what
     42  // automatically updates the map when a key is added to or erased from
     43  // the map. This map type uses the std::vector to store the values.
    4444  //
    4545  // \tparam _Graph The graph this map is attached to.
    … …  
    125125    // \brief Template assign operator.
    126126    //
    127     // The given parameter should conform to the ReadMap
     127    // The given parameter should be conform to the ReadMap
    128128    // concecpt and could be indiced by the current item set of
    129129    // the NodeMap. In this case the value for each item
    … …  
    170170    // \brief Adds a new key to the map.
    171171    //
    172     // It adds a new key to the map. It is called by the observer notifier
     172    // It adds a new key to the map. It called by the observer notifier
    173173    // and it overrides the add() member function of the observer base.
    174174    virtual void add(const Key& key) {
    … …  
    181181    // \brief Adds more new keys to the map.
    182182    //
    183     // It adds more new keys to the map. It is called by the observer notifier
     183    // It adds more new keys to the map. It called by the observer notifier
    184184    // and it overrides the add() member function of the observer base.
    185185    virtual void add(const std::vector<Key>& keys) {
    … …  
    196196    // \brief Erase a key from the map.
    197197    //
    198     // Erase a key from the map. It is called by the observer notifier
     198    // Erase a key from the map. It called by the observer notifier
    199199    // and it overrides the erase() member function of the observer base.
    200200    virtual void erase(const Key& key) {
    … …  
    204204    // \brief Erase more keys from the map.
    205205    //
    206     // It erases more keys from the map. It is called by the observer notifier
     206    // Erase more keys from the map. It called by the observer notifier
    207207    // and it overrides the erase() member function of the observer base.
    208208    virtual void erase(const std::vector<Key>& keys) {
    … …  
    212212    }
    213213
    214     // \brief Build the map.
    215     //
    216     // It builds the map. It is called by the observer notifier
     214    // \brief Buildes the map.
     215    //
     216    // It buildes the map. It called by the observer notifier
    217217    // and it overrides the build() member function of the observer base.
    218218    virtual void build() {
    … …  
    224224    // \brief Clear the map.
    225225    //
    226     // It erases all items from the map. It is called by the observer notifier
     226    // It erase all items from the map. It called by the observer notifier
    227227    // and it overrides the clear() member function of the observer base.
    228228    virtual void clear() {

  • lemon/bits/windows.h

    r576 r511  
    1717 */
    1818
    19 #ifndef LEMON_BITS_WINDOWS_H
    20 #define LEMON_BITS_WINDOWS_H
     19#ifndef LEMON_WINDOWS_H
     20#define LEMON_WINDOWS_H
    2121
    2222#include <string>

  • lemon/color.cc

    r463 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/color.h

    r463 r313  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/concept_check.h

    r463 r285  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/concepts/digraph.h

    r576 r263  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    1717 */
    1818
    19 #ifndef LEMON_CONCEPTS_DIGRAPH_H
    20 #define LEMON_CONCEPTS_DIGRAPH_H
     19#ifndef LEMON_CONCEPT_DIGRAPH_H
     20#define LEMON_CONCEPT_DIGRAPH_H
    2121
    2222///\ingroup graph_concepts
    … …  
    485485
    486486
    487 #endif
     487#endif // LEMON_CONCEPT_DIGRAPH_H

  • lemon/concepts/graph.h

    r576 r263  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    2121///\brief The concept of Undirected Graphs.
    2222
    23 #ifndef LEMON_CONCEPTS_GRAPH_H
    24 #define LEMON_CONCEPTS_GRAPH_H
     23#ifndef LEMON_CONCEPT_GRAPH_H
     24#define LEMON_CONCEPT_GRAPH_H
    2525
    2626#include <lemon/concepts/graph_components.h>
     27#include <lemon/concepts/graph.h>
    2728#include <lemon/core.h>
    2829

  • lemon/concepts/graph_components.h

    r581 r313  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    2222
    2323
    24 #ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
    25 #define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
     24#ifndef LEMON_CONCEPT_GRAPH_COMPONENTS_H
     25#define LEMON_CONCEPT_GRAPH_COMPONENTS_H
    2626
    2727#include <lemon/core.h>
    … …  
    115115    ///
    116116    /// This class provides the minimal set of features needed for a
    117     /// directed graph structure. All digraph concepts have to
     117    /// directed graph structure. All digraph concepts have to be
    118118    /// conform to this base directed graph. It just provides types
    119119    /// for nodes and arcs and functions to get the source and the
    … …  
    180180    /// This class provides the minimal set of features needed for an
    181181    /// undirected graph structure. All undirected graph concepts have
    182     /// to conform to this base graph. It just provides types for
     182    /// to be conform to this base graph. It just provides types for
    183183    /// nodes, arcs and edges and functions to get the
    184184    /// source and the target of the arcs and edges,
    … …  
    295295    /// This class provides beside the core digraph features
    296296    /// core id functions for the digraph structure.
    297     /// The most of the base digraphs should conform to this concept.
     297    /// The most of the base digraphs should be conform to this concept.
    298298    /// The id's are unique and immutable.
    299299    template <typename _Base = BaseDigraphComponent>
    … …  
    373373    /// This class provides beside the core undirected graph features
    374374    /// core id functions for the undirected graph structure.  The
    375     /// most of the base undirected graphs should conform to this
     375    /// most of the base undirected graphs should be conform to this
    376376    /// concept.  The id's are unique and immutable.
    377377    template <typename _Base = BaseGraphComponent>

  • lemon/concepts/heap.h

    r576 r290  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    2121///\brief The concept of heaps.
    2222
    23 #ifndef LEMON_CONCEPTS_HEAP_H
    24 #define LEMON_CONCEPTS_HEAP_H
     23#ifndef LEMON_CONCEPT_HEAP_H
     24#define LEMON_CONCEPT_HEAP_H
    2525
    2626#include <lemon/core.h>
    27 #include <lemon/concept_check.h>
    2827
    2928namespace lemon {
    … …  
    244243  } // namespace lemon
    245244}
    246 #endif
     245#endif // LEMON_CONCEPT_PATH_H

  • lemon/concepts/maps.h

    r576 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    1717 */
    1818
    19 #ifndef LEMON_CONCEPTS_MAPS_H
    20 #define LEMON_CONCEPTS_MAPS_H
     19#ifndef LEMON_CONCEPT_MAPS_H
     20#define LEMON_CONCEPT_MAPS_H
    2121
    2222#include <lemon/core.h>
    … …  
    214214} //namespace lemon
    215215
    216 #endif
     216#endif // LEMON_CONCEPT_MAPS_H

  • lemon/concepts/path.h

    r576 r281  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    2222///
    2323
    24 #ifndef LEMON_CONCEPTS_PATH_H
    25 #define LEMON_CONCEPTS_PATH_H
     24#ifndef LEMON_CONCEPT_PATH_H
     25#define LEMON_CONCEPT_PATH_H
    2626
    2727#include <lemon/core.h>
    … …  
    306306} // namespace lemon
    307307
    308 #endif
     308#endif // LEMON_CONCEPT_PATH_H

  • lemon/config.h.cmake

    r564 r515  
    11#cmakedefine HAVE_LONG_LONG 1
    2 #cmakedefine HAVE_LP 1
    3 #cmakedefine HAVE_MIP 1
    4 #cmakedefine HAVE_GLPK 1

  • lemon/config.h.in

    r564 r515  
    1 /* Define to 1 if you have long long */
    2 #undef HAVE_LONG_LONG
    3 
    4 /* Define to 1 if you have any LP solver. */
    5 #undef HAVE_LP
    6 
    7 /* Define to 1 if you have any MIP solver. */
    8 #undef HAVE_MIP
    9 
    101/* Define to 1 if you have CPLEX. */
    112#undef HAVE_CPLEX
    … …  
    145#undef HAVE_GLPK
    156
    16 /* Define to 1 if you have SOPLEX */
    17 #undef HAVE_SOPLEX
    18 
    19 /* Define to 1 if you have CLP */
    20 #undef HAVE_CLP
     7/* Define to 1 if you have long long */
     8#undef HAVE_LONG_LONG

  • lemon/core.h

    r582 r523  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/counter.h

    r463 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/dfs.h

    r525 r319  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    5050    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    52     ///Instantiates a \c PredMap.
    53 
    54     ///This function instantiates a \ref PredMap.
     52    ///Instantiates a PredMap.
     53
     54    ///This function instantiates a PredMap.
    5555    ///\param g is the digraph, to which we would like to define the
    56     ///\ref PredMap.
     56    ///PredMap.
    5757    static PredMap *createPredMap(const Digraph &g)
    5858    {
    … …  
    6565    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6666    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    67     ///Instantiates a \c ProcessedMap.
    68 
    69     ///This function instantiates a \ref ProcessedMap.
     67    ///Instantiates a ProcessedMap.
     68
     69    ///This function instantiates a ProcessedMap.
    7070    ///\param g is the digraph, to which
    71     ///we would like to define the \ref ProcessedMap.
     71    ///we would like to define the ProcessedMap
    7272#ifdef DOXYGEN
    7373    static ProcessedMap *createProcessedMap(const Digraph &g)
    … …  
    8484    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8585    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    86     ///Instantiates a \c ReachedMap.
    87 
    88     ///This function instantiates a \ref ReachedMap.
     86    ///Instantiates a ReachedMap.
     87
     88    ///This function instantiates a ReachedMap.
    8989    ///\param g is the digraph, to which
    90     ///we would like to define the \ref ReachedMap.
     90    ///we would like to define the ReachedMap.
    9191    static ReachedMap *createReachedMap(const Digraph &g)
    9292    {
    … …  
    9999    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    100100    typedef typename Digraph::template NodeMap<int> DistMap;
    101     ///Instantiates a \c DistMap.
    102 
    103     ///This function instantiates a \ref DistMap.
     101    ///Instantiates a DistMap.
     102
     103    ///This function instantiates a DistMap.
    104104    ///\param g is the digraph, to which we would like to define the
    105     ///\ref DistMap.
     105    ///DistMap.
    106106    static DistMap *createDistMap(const Digraph &g)
    107107    {
    … …  
    120120  ///
    121121  ///\tparam GR The type of the digraph the algorithm runs on.
    122   ///The default type is \ref ListDigraph.
     122  ///The default value is \ref ListDigraph. The value of GR is not used
     123  ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
     124  ///\tparam TR Traits class to set various data types used by the algorithm.
     125  ///The default traits class is
     126  ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
     127  ///See \ref DfsDefaultTraits for the documentation of
     128  ///a Dfs traits class.
    123129#ifdef DOXYGEN
    124130  template <typename GR,
    … …  
    146152    typedef PredMapPath<Digraph, PredMap> Path;
    147153
    148     ///The \ref DfsDefaultTraits "traits class" of the algorithm.
     154    ///The traits class.
    149155    typedef TR Traits;
    150156
    … …  
    221227    };
    222228    ///\brief \ref named-templ-param "Named parameter" for setting
    223     ///\c PredMap type.
     229    ///PredMap type.
    224230    ///
    225231    ///\ref named-templ-param "Named parameter" for setting
    226     ///\c PredMap type.
    227     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     232    ///PredMap type.
    228233    template <class T>
    229234    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
    … …  
    241246    };
    242247    ///\brief \ref named-templ-param "Named parameter" for setting
    243     ///\c DistMap type.
     248    ///DistMap type.
    244249    ///
    245250    ///\ref named-templ-param "Named parameter" for setting
    246     ///\c DistMap type.
    247     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     251    ///DistMap type.
    248252    template <class T>
    249253    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
    … …  
    261265    };
    262266    ///\brief \ref named-templ-param "Named parameter" for setting
    263     ///\c ReachedMap type.
     267    ///ReachedMap type.
    264268    ///
    265269    ///\ref named-templ-param "Named parameter" for setting
    266     ///\c ReachedMap type.
    267     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     270    ///ReachedMap type.
    268271    template <class T>
    269272    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
    … …  
    281284    };
    282285    ///\brief \ref named-templ-param "Named parameter" for setting
    283     ///\c ProcessedMap type.
     286    ///ProcessedMap type.
    284287    ///
    285288    ///\ref named-templ-param "Named parameter" for setting
    286     ///\c ProcessedMap type.
    287     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     289    ///ProcessedMap type.
    288290    template <class T>
    289291    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
    … …  
    299301    };
    300302    ///\brief \ref named-templ-param "Named parameter" for setting
    301     ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     303    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    302304    ///
    303305    ///\ref named-templ-param "Named parameter" for setting
    304     ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     306    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    305307    ///If you don't set it explicitly, it will be automatically allocated.
    306308    struct SetStandardProcessedMap :
    … …  
    337339
    338340    ///Sets the map that stores the predecessor arcs.
    339     ///If you don't use this function before calling \ref run(Node) "run()"
    340     ///or \ref init(), an instance will be allocated automatically.
    341     ///The destructor deallocates this automatically allocated map,
    342     ///of course.
     341    ///If you don't use this function before calling \ref run(),
     342    ///it will allocate one. The destructor deallocates this
     343    ///automatically allocated map, of course.
    343344    ///\return <tt> (*this) </tt>
    344345    Dfs &predMap(PredMap &m)
    … …  
    355356
    356357    ///Sets the map that indicates which nodes are reached.
    357     ///If you don't use this function before calling \ref run(Node) "run()"
    358     ///or \ref init(), an instance will be allocated automatically.
    359     ///The destructor deallocates this automatically allocated map,
    360     ///of course.
     358    ///If you don't use this function before calling \ref run(),
     359    ///it will allocate one. The destructor deallocates this
     360    ///automatically allocated map, of course.
    361361    ///\return <tt> (*this) </tt>
    362362    Dfs &reachedMap(ReachedMap &m)
    … …  
    373373
    374374    ///Sets the map that indicates which nodes are processed.
    375     ///If you don't use this function before calling \ref run(Node) "run()"
    376     ///or \ref init(), an instance will be allocated automatically.
    377     ///The destructor deallocates this automatically allocated map,
    378     ///of course.
     375    ///If you don't use this function before calling \ref run(),
     376    ///it will allocate one. The destructor deallocates this
     377    ///automatically allocated map, of course.
    379378    ///\return <tt> (*this) </tt>
    380379    Dfs &processedMap(ProcessedMap &m)
    … …  
    392391    ///Sets the map that stores the distances of the nodes calculated by
    393392    ///the algorithm.
    394     ///If you don't use this function before calling \ref run(Node) "run()"
    395     ///or \ref init(), an instance will be allocated automatically.
    396     ///The destructor deallocates this automatically allocated map,
    397     ///of course.
     393    ///If you don't use this function before calling \ref run(),
     394    ///it will allocate one. The destructor deallocates this
     395    ///automatically allocated map, of course.
    398396    ///\return <tt> (*this) </tt>
    399397    Dfs &distMap(DistMap &m)
    … …  
    409407  public:
    410408
    411     ///\name Execution Control
    412     ///The simplest way to execute the DFS algorithm is to use one of the
    413     ///member functions called \ref run(Node) "run()".\n
    414     ///If you need more control on the execution, first you have to call
    415     ///\ref init(), then you can add a source node with \ref addSource()
    416     ///and perform the actual computation with \ref start().
    417     ///This procedure can be repeated if there are nodes that have not
    418     ///been reached.
     409    ///\name Execution control
     410    ///The simplest way to execute the algorithm is to use
     411    ///one of the member functions called \ref lemon::Dfs::run() "run()".
     412    ///\n
     413    ///If you need more control on the execution, first you must call
     414    ///\ref lemon::Dfs::init() "init()", then you can add a source node
     415    ///with \ref lemon::Dfs::addSource() "addSource()".
     416    ///Finally \ref lemon::Dfs::start() "start()" will perform the
     417    ///actual path computation.
    419418
    420419    ///@{
    421420
    422     ///\brief Initializes the internal data structures.
    423     ///
    424421    ///Initializes the internal data structures.
     422
     423    ///Initializes the internal data structures.
     424    ///
    425425    void init()
    426426    {
    … …  
    439439    ///Adds a new source node to the set of nodes to be processed.
    440440    ///
    441     ///\pre The stack must be empty. Otherwise the algorithm gives
    442     ///wrong results. (One of the outgoing arcs of all the source nodes
    443     ///except for the last one will not be visited and distances will
    444     ///also be wrong.)
     441    ///\pre The stack must be empty. (Otherwise the algorithm gives
     442    ///false results.)
     443    ///
     444    ///\warning Distances will be wrong (or at least strange) in case of
     445    ///multiple sources.
    445446    void addSource(Node s)
    446447    {
    … …  
    506507    }
    507508
    508     ///Returns \c false if there are nodes to be processed.
    509 
    510     ///Returns \c false if there are nodes to be processed
    511     ///in the queue (stack).
     509    ///\brief Returns \c false if there are nodes
     510    ///to be processed.
     511    ///
     512    ///Returns \c false if there are nodes
     513    ///to be processed in the queue (stack).
    512514    bool emptyQueue() const { return _stack_head<0; }
    513515
    514516    ///Returns the number of the nodes to be processed.
    515517
    516     ///Returns the number of the nodes to be processed
    517     ///in the queue (stack).
     518    ///Returns the number of the nodes to be processed in the queue (stack).
    518519    int queueSize() const { return _stack_head+1; }
    519520
    … …  
    637638    ///
    638639    ///The algorithm computes
    639     ///- the %DFS tree (forest),
    640     ///- the distance of each node from the root(s) in the %DFS tree.
     640    ///- the %DFS tree,
     641    ///- the distance of each node from the root in the %DFS tree.
    641642    ///
    642643    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
    … …  
    663664
    664665    ///\name Query Functions
    665     ///The results of the DFS algorithm can be obtained using these
     666    ///The result of the %DFS algorithm can be obtained using these
    666667    ///functions.\n
    667     ///Either \ref run(Node) "run()" or \ref start() should be called
    668     ///before using them.
     668    ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
     669    ///"start()" must be called before using them.
    669670
    670671    ///@{
    … …  
    674675    ///Returns the DFS path to a node.
    675676    ///
    676     ///\warning \c t should be reached from the root(s).
    677     ///
    678     ///\pre Either \ref run(Node) "run()" or \ref init()
    679     ///must be called before using this function.
     677    ///\warning \c t should be reachable from the root.
     678    ///
     679    ///\pre Either \ref run() or \ref start() must be called before
     680    ///using this function.
    680681    Path path(Node t) const { return Path(*G, *_pred, t); }
    681682
    682     ///The distance of a node from the root(s).
    683 
    684     ///Returns the distance of a node from the root(s).
    685     ///
    686     ///\warning If node \c v is not reached from the root(s), then
     683    ///The distance of a node from the root.
     684
     685    ///Returns the distance of a node from the root.
     686    ///
     687    ///\warning If node \c v is not reachable from the root, then
    687688    ///the return value of this function is undefined.
    688689    ///
    689     ///\pre Either \ref run(Node) "run()" or \ref init()
    690     ///must be called before using this function.
     690    ///\pre Either \ref run() or \ref start() must be called before
     691    ///using this function.
    691692    int dist(Node v) const { return (*_dist)[v]; }
    692693
    … …  
    694695
    695696    ///This function returns the 'previous arc' of the %DFS tree for the
    696     ///node \c v, i.e. it returns the last arc of a %DFS path from a
    697     ///root to \c v. It is \c INVALID if \c v is not reached from the
    698     ///root(s) or if \c v is a root.
     697    ///node \c v, i.e. it returns the last arc of a %DFS path from the
     698    ///root to \c v. It is \c INVALID
     699    ///if \c v is not reachable from the root(s) or if \c v is a root.
    699700    ///
    700701    ///The %DFS tree used here is equal to the %DFS tree used in
    701702    ///\ref predNode().
    702703    ///
    703     ///\pre Either \ref run(Node) "run()" or \ref init()
    704     ///must be called before using this function.
     704    ///\pre Either \ref run() or \ref start() must be called before using
     705    ///this function.
    705706    Arc predArc(Node v) const { return (*_pred)[v];}
    706707
    … …  
    709710    ///This function returns the 'previous node' of the %DFS
    710711    ///tree for the node \c v, i.e. it returns the last but one node
    711     ///from a %DFS path from a root to \c v. It is \c INVALID
    712     ///if \c v is not reached from the root(s) or if \c v is a root.
     712    ///from a %DFS path from the root to \c v. It is \c INVALID
     713    ///if \c v is not reachable from the root(s) or if \c v is a root.
    713714    ///
    714715    ///The %DFS tree used here is equal to the %DFS tree used in
    715716    ///\ref predArc().
    716717    ///
    717     ///\pre Either \ref run(Node) "run()" or \ref init()
    718     ///must be called before using this function.
     718    ///\pre Either \ref run() or \ref start() must be called before
     719    ///using this function.
    719720    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    720721                                  G->source((*_pred)[v]); }
    … …  
    726727    ///distances of the nodes calculated by the algorithm.
    727728    ///
    728     ///\pre Either \ref run(Node) "run()" or \ref init()
     729    ///\pre Either \ref run() or \ref init()
    729730    ///must be called before using this function.
    730731    const DistMap &distMap() const { return *_dist;}
    … …  
    736737    ///arcs, which form the DFS tree.
    737738    ///
    738     ///\pre Either \ref run(Node) "run()" or \ref init()
     739    ///\pre Either \ref run() or \ref init()
    739740    ///must be called before using this function.
    740741    const PredMap &predMap() const { return *_pred;}
    741742
    742     ///Checks if a node is reached from the root(s).
    743 
    744     ///Returns \c true if \c v is reached from the root(s).
    745     ///
    746     ///\pre Either \ref run(Node) "run()" or \ref init()
     743    ///Checks if a node is reachable from the root(s).
     744
     745    ///Returns \c true if \c v is reachable from the root(s).
     746    ///\pre Either \ref run() or \ref start()
    747747    ///must be called before using this function.
    748748    bool reached(Node v) const { return (*_reached)[v]; }
    … …  
    890890  /// This auxiliary class is created to implement the
    891891  /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
    892   /// It does not have own \ref run(Node) "run()" method, it uses the
    893   /// functions and features of the plain \ref Dfs.
     892  /// It does not have own \ref run() method, it uses the functions
     893  /// and features of the plain \ref Dfs.
    894894  ///
    895895  /// This class should only be used through the \ref dfs() function,
    … …  
    11111111  ///  bool reached = dfs(g).path(p).dist(d).run(s,t);
    11121112  ///\endcode
    1113   ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()"
     1113
     1114  ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
    11141115  ///to the end of the parameter list.
    11151116  ///\sa DfsWizard
    … …  
    11271128  /// This class defines the interface of the DfsVisit events, and
    11281129  /// it could be the base of a real visitor class.
    1129   template <typename GR>
     1130  template <typename _Digraph>
    11301131  struct DfsVisitor {
    1131     typedef GR Digraph;
     1132    typedef _Digraph Digraph;
    11321133    typedef typename Digraph::Arc Arc;
    11331134    typedef typename Digraph::Node Node;
    … …  
    11651166  };
    11661167#else
    1167   template <typename GR>
     1168  template <typename _Digraph>
    11681169  struct DfsVisitor {
    1169     typedef GR Digraph;
     1170    typedef _Digraph Digraph;
    11701171    typedef typename Digraph::Arc Arc;
    11711172    typedef typename Digraph::Node Node;
    … …  
    12001201  /// Default traits class of DfsVisit class.
    12011202  /// \tparam _Digraph The type of the digraph the algorithm runs on.
    1202   template<class GR>
     1203  template<class _Digraph>
    12031204  struct DfsVisitDefaultTraits {
    12041205
    12051206    /// \brief The type of the digraph the algorithm runs on.
    1206     typedef GR Digraph;
     1207    typedef _Digraph Digraph;
    12071208
    12081209    /// \brief The type of the map that indicates which nodes are reached.
    … …  
    12251226  /// \ingroup search
    12261227  ///
    1227   /// \brief DFS algorithm class with visitor interface.
     1228  /// \brief %DFS algorithm class with visitor interface.
    12281229  ///
    1229   /// This class provides an efficient implementation of the DFS algorithm
     1230  /// This class provides an efficient implementation of the %DFS algorithm
    12301231  /// with visitor interface.
    12311232  ///
    1232   /// The DfsVisit class provides an alternative interface to the Dfs
     1233  /// The %DfsVisit class provides an alternative interface to the Dfs
    12331234  /// class. It works with callback mechanism, the DfsVisit object calls
    12341235  /// the member functions of the \c Visitor class on every DFS event.
    … …  
    12391240  /// instead.
    12401241  ///
    1241   /// \tparam GR The type of the digraph the algorithm runs on.
    1242   /// The default type is \ref ListDigraph.
    1243   /// The value of GR is not used directly by \ref DfsVisit,
    1244   /// it is only passed to \ref DfsVisitDefaultTraits.
    1245   /// \tparam VS The Visitor type that is used by the algorithm.
    1246   /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which
     1242  /// \tparam _Digraph The type of the digraph the algorithm runs on.
     1243  /// The default value is
     1244  /// \ref ListDigraph. The value of _Digraph is not used directly by
     1245  /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
     1246  /// \tparam _Visitor The Visitor type that is used by the algorithm.
     1247  /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
    12471248  /// does not observe the DFS events. If you want to observe the DFS
    12481249  /// events, you should implement your own visitor class.
    1249   /// \tparam TR Traits class to set various data types used by the
     1250  /// \tparam _Traits Traits class to set various data types used by the
    12501251  /// algorithm. The default traits class is
    1251   /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
     1252  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
    12521253  /// See \ref DfsVisitDefaultTraits for the documentation of
    12531254  /// a DFS visit traits class.
    12541255#ifdef DOXYGEN
    1255   template <typename GR, typename VS, typename TR>
     1256  template <typename _Digraph, typename _Visitor, typename _Traits>
    12561257#else
    1257   template <typename GR = ListDigraph,
    1258             typename VS = DfsVisitor<GR>,
    1259             typename TR = DfsVisitDefaultTraits<GR> >
     1258  template <typename _Digraph = ListDigraph,
     1259            typename _Visitor = DfsVisitor<_Digraph>,
     1260            typename _Traits = DfsVisitDefaultTraits<_Digraph> >
    12601261#endif
    12611262  class DfsVisit {
    … …  
    12631264
    12641265    ///The traits class.
    1265     typedef TR Traits;
     1266    typedef _Traits Traits;
    12661267
    12671268    ///The type of the digraph the algorithm runs on.
    … …  
    12691270
    12701271    ///The visitor type used by the algorithm.
    1271     typedef VS Visitor;
     1272    typedef _Visitor Visitor;
    12721273
    12731274    ///The type of the map that indicates which nodes are reached.
    … …  
    13091310    typedef DfsVisit Create;
    13101311
    1311     /// \name Named Template Parameters
     1312    /// \name Named template parameters
    13121313
    13131314    ///@{
    … …  
    13511352    ///
    13521353    /// Sets the map that indicates which nodes are reached.
    1353     /// If you don't use this function before calling \ref run(Node) "run()"
    1354     /// or \ref init(), an instance will be allocated automatically.
    1355     /// The destructor deallocates this automatically allocated map,
    1356     /// of course.
     1354    /// If you don't use this function before calling \ref run(),
     1355    /// it will allocate one. The destructor deallocates this
     1356    /// automatically allocated map, of course.
    13571357    /// \return <tt> (*this) </tt>
    13581358    DfsVisit &reachedMap(ReachedMap &m) {
    … …  
    13671367  public:
    13681368
    1369     /// \name Execution Control
    1370     /// The simplest way to execute the DFS algorithm is to use one of the
    1371     /// member functions called \ref run(Node) "run()".\n
    1372     /// If you need more control on the execution, first you have to call
    1373     /// \ref init(), then you can add a source node with \ref addSource()
    1374     /// and perform the actual computation with \ref start().
    1375     /// This procedure can be repeated if there are nodes that have not
    1376     /// been reached.
     1369    /// \name Execution control
     1370    /// The simplest way to execute the algorithm is to use
     1371    /// one of the member functions called \ref lemon::DfsVisit::run()
     1372    /// "run()".
     1373    /// \n
     1374    /// If you need more control on the execution, first you must call
     1375    /// \ref lemon::DfsVisit::init() "init()", then you can add several
     1376    /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
     1377    /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
     1378    /// actual path computation.
    13771379
    13781380    /// @{
    … …  
    13901392    }
    13911393
    1392     /// \brief Adds a new source node.
    1393     ///
    1394     /// Adds a new source node to the set of nodes to be processed.
    1395     ///
    1396     /// \pre The stack must be empty. Otherwise the algorithm gives
    1397     /// wrong results. (One of the outgoing arcs of all the source nodes
    1398     /// except for the last one will not be visited and distances will
    1399     /// also be wrong.)
     1394    ///Adds a new source node.
     1395
     1396    ///Adds a new source node to the set of nodes to be processed.
     1397    ///
     1398    ///\pre The stack must be empty. (Otherwise the algorithm gives
     1399    ///false results.)
     1400    ///
     1401    ///\warning Distances will be wrong (or at least strange) in case of
     1402    ///multiple sources.
    14001403    void addSource(Node s)
    14011404    {
    … …  
    14111414          } else {
    14121415            _visitor->leave(s);
    1413             _visitor->stop(s);
    14141416          }
    14151417        }
    … …  
    15881590    ///
    15891591    /// The algorithm computes
    1590     /// - the %DFS tree (forest),
    1591     /// - the distance of each node from the root(s) in the %DFS tree.
     1592    /// - the %DFS tree,
     1593    /// - the distance of each node from the root in the %DFS tree.
    15921594    ///
    15931595    /// \note <tt>d.run()</tt> is just a shortcut of the following code.
    … …  
    16141616
    16151617    /// \name Query Functions
    1616     /// The results of the DFS algorithm can be obtained using these
     1618    /// The result of the %DFS algorithm can be obtained using these
    16171619    /// functions.\n
    1618     /// Either \ref run(Node) "run()" or \ref start() should be called
    1619     /// before using them.
    1620 
     1620    /// Either \ref lemon::DfsVisit::run() "run()" or
     1621    /// \ref lemon::DfsVisit::start() "start()" must be called before
     1622    /// using them.
    16211623    ///@{
    16221624
    1623     /// \brief Checks if a node is reached from the root(s).
    1624     ///
    1625     /// Returns \c true if \c v is reached from the root(s).
    1626     ///
    1627     /// \pre Either \ref run(Node) "run()" or \ref init()
     1625    /// \brief Checks if a node is reachable from the root(s).
     1626    ///
     1627    /// Returns \c true if \c v is reachable from the root(s).
     1628    /// \pre Either \ref run() or \ref start()
    16281629    /// must be called before using this function.
    1629     bool reached(Node v) const { return (*_reached)[v]; }
     1630    bool reached(Node v) { return (*_reached)[v]; }
    16301631
    16311632    ///@}

  • lemon/dijkstra.h

    r525 r412  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    7474    typedef typename LM::Value Value;
    7575
    76     /// Operation traits for %Dijkstra algorithm.
     76    /// Operation traits for Dijkstra algorithm.
    7777
    7878    /// This class defines the operations that are used in the algorithm.
    … …  
    8585    /// Usually it is \c Digraph::NodeMap<int>.
    8686    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
    87     ///Instantiates a \c HeapCrossRef.
     87    ///Instantiates a \ref HeapCrossRef.
    8888
    8989    ///This function instantiates a \ref HeapCrossRef.
    … …  
    9595    }
    9696
    97     ///The heap type used by the %Dijkstra algorithm.
     97    ///The heap type used by the Dijkstra algorithm.
    9898
    9999    ///The heap type used by the Dijkstra algorithm.
    … …  
    102102    ///\sa Dijkstra
    103103    typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
    104     ///Instantiates a \c Heap.
     104    ///Instantiates a \ref Heap.
    105105
    106106    ///This function instantiates a \ref Heap.
    … …  
    117117    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    118118    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    119     ///Instantiates a \c PredMap.
    120 
    121     ///This function instantiates a \ref PredMap.
     119    ///Instantiates a PredMap.
     120
     121    ///This function instantiates a PredMap.
    122122    ///\param g is the digraph, to which we would like to define the
    123     ///\ref PredMap.
     123    ///PredMap.
    124124    static PredMap *createPredMap(const Digraph &g)
    125125    {
    … …  
    133133    ///By default it is a NullMap.
    134134    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    135     ///Instantiates a \c ProcessedMap.
    136 
    137     ///This function instantiates a \ref ProcessedMap.
     135    ///Instantiates a ProcessedMap.
     136
     137    ///This function instantiates a ProcessedMap.
    138138    ///\param g is the digraph, to which
    139     ///we would like to define the \ref ProcessedMap.
     139    ///we would like to define the ProcessedMap
    140140#ifdef DOXYGEN
    141141    static ProcessedMap *createProcessedMap(const Digraph &g)
    … …  
    152152    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    153153    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
    154     ///Instantiates a \c DistMap.
    155 
    156     ///This function instantiates a \ref DistMap.
     154    ///Instantiates a DistMap.
     155
     156    ///This function instantiates a DistMap.
    157157    ///\param g is the digraph, to which we would like to define
    158     ///the \ref DistMap.
     158    ///the DistMap
    159159    static DistMap *createDistMap(const Digraph &g)
    160160    {
    … …  
    180180  ///
    181181  ///\tparam GR The type of the digraph the algorithm runs on.
    182   ///The default type is \ref ListDigraph.
    183   ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies
    184   ///the lengths of the arcs.
    185   ///It is read once for each arc, so the map may involve in
     182  ///The default value is \ref ListDigraph.
     183  ///The value of GR is not used directly by \ref Dijkstra, it is only
     184  ///passed to \ref DijkstraDefaultTraits.
     185  ///\tparam LM A readable arc map that determines the lengths of the
     186  ///arcs. It is read once for each arc, so the map may involve in
    186187  ///relatively time consuming process to compute the arc lengths if
    187188  ///it is necessary. The default map type is \ref
    188   ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
     189  ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
     190  ///The value of LM is not used directly by \ref Dijkstra, it is only
     191  ///passed to \ref DijkstraDefaultTraits.
     192  ///\tparam TR Traits class to set various data types used by the algorithm.
     193  ///The default traits class is \ref DijkstraDefaultTraits
     194  ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
     195  ///for the documentation of a Dijkstra traits class.
    189196#ifdef DOXYGEN
    190197  template <typename GR, typename LM, typename TR>
    … …  
    217224    ///The heap type used by the algorithm.
    218225    typedef typename TR::Heap Heap;
    219     ///\brief The \ref DijkstraDefaultOperationTraits "operation traits class"
    220     ///of the algorithm.
     226    ///The operation traits class.
    221227    typedef typename TR::OperationTraits OperationTraits;
    222228
    223     ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
     229    ///The traits class.
    224230    typedef TR Traits;
    225231
    … …  
    234240    const Digraph *G;
    235241    //Pointer to the length map.
    236     const LengthMap *_length;
     242    const LengthMap *length;
    237243    //Pointer to the map of predecessors arcs.
    238244    PredMap *_pred;
    … …  
    299305    };
    300306    ///\brief \ref named-templ-param "Named parameter" for setting
    301     ///\c PredMap type.
     307    ///PredMap type.
    302308    ///
    303309    ///\ref named-templ-param "Named parameter" for setting
    304     ///\c PredMap type.
    305     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     310    ///PredMap type.
    306311    template <class T>
    307312    struct SetPredMap
    … …  
    320325    };
    321326    ///\brief \ref named-templ-param "Named parameter" for setting
    322     ///\c DistMap type.
     327    ///DistMap type.
    323328    ///
    324329    ///\ref named-templ-param "Named parameter" for setting
    325     ///\c DistMap type.
    326     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     330    ///DistMap type.
    327331    template <class T>
    328332    struct SetDistMap
    … …  
    341345    };
    342346    ///\brief \ref named-templ-param "Named parameter" for setting
    343     ///\c ProcessedMap type.
     347    ///ProcessedMap type.
    344348    ///
    345349    ///\ref named-templ-param "Named parameter" for setting
    346     ///\c ProcessedMap type.
    347     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     350    ///ProcessedMap type.
    348351    template <class T>
    349352    struct SetProcessedMap
    … …  
    360363    };
    361364    ///\brief \ref named-templ-param "Named parameter" for setting
    362     ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     365    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    363366    ///
    364367    ///\ref named-templ-param "Named parameter" for setting
    365     ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     368    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    366369    ///If you don't set it explicitly, it will be automatically allocated.
    367370    struct SetStandardProcessedMap
    … …  
    386389    };
    387390    ///\brief \ref named-templ-param "Named parameter" for setting
    388     ///heap and cross reference types
     391    ///heap and cross reference type
    389392    ///
    390393    ///\ref named-templ-param "Named parameter" for setting heap and cross
    391     ///reference types. If this named parameter is used, then external
    392     ///heap and cross reference objects must be passed to the algorithm
    393     ///using the \ref heap() function before calling \ref run(Node) "run()"
    394     ///or \ref init().
    395     ///\sa SetStandardHeap
     394    ///reference type.
    396395    template <class H, class CR = typename Digraph::template NodeMap<int> >
    397396    struct SetHeap
    … …  
    413412    };
    414413    ///\brief \ref named-templ-param "Named parameter" for setting
    415     ///heap and cross reference types with automatic allocation
     414    ///heap and cross reference type with automatic allocation
    416415    ///
    417416    ///\ref named-templ-param "Named parameter" for setting heap and cross
    418     ///reference types with automatic allocation.
    419     ///They should have standard constructor interfaces to be able to
    420     ///automatically created by the algorithm (i.e. the digraph should be
    421     ///passed to the constructor of the cross reference and the cross
    422     ///reference should be passed to the constructor of the heap).
    423     ///However external heap and cross reference objects could also be
    424     ///passed to the algorithm using the \ref heap() function before
    425     ///calling \ref run(Node) "run()" or \ref init().
    426     ///\sa SetHeap
     417    ///reference type. It can allocate the heap and the cross reference
     418    ///object if the cross reference's constructor waits for the digraph as
     419    ///parameter and the heap's constructor waits for the cross reference.
    427420    template <class H, class CR = typename Digraph::template NodeMap<int> >
    428421    struct SetStandardHeap
    … …  
    441434    ///
    442435    ///\ref named-templ-param "Named parameter" for setting
    443     ///\c OperationTraits type.
     436    ///\ref OperationTraits type.
    444437    template <class T>
    445438    struct SetOperationTraits
    … …  
    460453
    461454    ///Constructor.
    462     ///\param g The digraph the algorithm runs on.
    463     ///\param length The length map used by the algorithm.
    464     Dijkstra(const Digraph& g, const LengthMap& length) :
    465       G(&g), _length(&length),
     455    ///\param _g The digraph the algorithm runs on.
     456    ///\param _length The length map used by the algorithm.
     457    Dijkstra(const Digraph& _g, const LengthMap& _length) :
     458      G(&_g), length(&_length),
    466459      _pred(NULL), local_pred(false),
    467460      _dist(NULL), local_dist(false),
    … …  
    487480    Dijkstra &lengthMap(const LengthMap &m)
    488481    {
    489       _length = &m;
     482      length = &m;
    490483      return *this;
    491484    }
    … …  
    494487
    495488    ///Sets the map that stores the predecessor arcs.
    496     ///If you don't use this function before calling \ref run(Node) "run()"
    497     ///or \ref init(), an instance will be allocated automatically.
    498     ///The destructor deallocates this automatically allocated map,
    499     ///of course.
     489    ///If you don't use this function before calling \ref run(),
     490    ///it will allocate one. The destructor deallocates this
     491    ///automatically allocated map, of course.
    500492    ///\return <tt> (*this) </tt>
    501493    Dijkstra &predMap(PredMap &m)
    … …  
    512504
    513505    ///Sets the map that indicates which nodes are processed.
    514     ///If you don't use this function before calling \ref run(Node) "run()"
    515     ///or \ref init(), an instance will be allocated automatically.
    516     ///The destructor deallocates this automatically allocated map,
    517     ///of course.
     506    ///If you don't use this function before calling \ref run(),
     507    ///it will allocate one. The destructor deallocates this
     508    ///automatically allocated map, of course.
    518509    ///\return <tt> (*this) </tt>
    519510    Dijkstra &processedMap(ProcessedMap &m)
    … …  
    531522    ///Sets the map that stores the distances of the nodes calculated by the
    532523    ///algorithm.
    533     ///If you don't use this function before calling \ref run(Node) "run()"
    534     ///or \ref init(), an instance will be allocated automatically.
    535     ///The destructor deallocates this automatically allocated map,
    536     ///of course.
     524    ///If you don't use this function before calling \ref run(),
     525    ///it will allocate one. The destructor deallocates this
     526    ///automatically allocated map, of course.
    537527    ///\return <tt> (*this) </tt>
    538528    Dijkstra &distMap(DistMap &m)
    … …  
    549539
    550540    ///Sets the heap and the cross reference used by algorithm.
    551     ///If you don't use this function before calling \ref run(Node) "run()"
    552     ///or \ref init(), heap and cross reference instances will be
    553     ///allocated automatically.
    554     ///The destructor deallocates these automatically allocated objects,
    555     ///of course.
     541    ///If you don't use this function before calling \ref run(),
     542    ///it will allocate one. The destructor deallocates this
     543    ///automatically allocated heap and cross reference, of course.
    556544    ///\return <tt> (*this) </tt>
    557545    Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
    … …  
    580568  public:
    581569
    582     ///\name Execution Control
    583     ///The simplest way to execute the %Dijkstra algorithm is to use
    584     ///one of the member functions called \ref run(Node) "run()".\n
    585     ///If you need more control on the execution, first you have to call
    586     ///\ref init(), then you can add several source nodes with
    587     ///\ref addSource(). Finally the actual path computation can be
    588     ///performed with one of the \ref start() functions.
     570    ///\name Execution control
     571    ///The simplest way to execute the algorithm is to use one of the
     572    ///member functions called \ref lemon::Dijkstra::run() "run()".
     573    ///\n
     574    ///If you need more control on the execution, first you must call
     575    ///\ref lemon::Dijkstra::init() "init()", then you can add several
     576    ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
     577    ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
     578    ///actual path computation.
    589579
    590580    ///@{
    591581
    592     ///\brief Initializes the internal data structures.
    593     ///
    594582    ///Initializes the internal data structures.
     583
     584    ///Initializes the internal data structures.
     585    ///
    595586    void init()
    596587    {
    … …  
    640631        switch(_heap->state(w)) {
    641632        case Heap::PRE_HEAP:
    642           _heap->push(w,OperationTraits::plus(oldvalue, (*_length)[e]));
     633          _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
    643634          _pred->set(w,e);
    644635          break;
    645636        case Heap::IN_HEAP:
    646637          {
    647             Value newvalue = OperationTraits::plus(oldvalue, (*_length)[e]);
     638            Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
    648639            if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
    649640              _heap->decrease(w, newvalue);
    … …  
    668659    }
    669660
    670     ///Returns \c false if there are nodes to be processed.
    671 
    672     ///Returns \c false if there are nodes to be processed
    673     ///in the priority heap.
     661    ///\brief Returns \c false if there are nodes
     662    ///to be processed.
     663    ///
     664    ///Returns \c false if there are nodes
     665    ///to be processed in the priority heap.
    674666    bool emptyQueue() const { return _heap->empty(); }
    675667
    676     ///Returns the number of the nodes to be processed.
    677 
    678     ///Returns the number of the nodes to be processed
    679     ///in the priority heap.
     668    ///Returns the number of the nodes to be processed in the priority heap
     669
     670    ///Returns the number of the nodes to be processed in the priority heap.
     671    ///
    680672    int queueSize() const { return _heap->size(); }
    681673
    … …  
    798790
    799791    ///\name Query Functions
    800     ///The results of the %Dijkstra algorithm can be obtained using these
     792    ///The result of the %Dijkstra algorithm can be obtained using these
    801793    ///functions.\n
    802     ///Either \ref run(Node) "run()" or \ref start() should be called
    803     ///before using them.
     794    ///Either \ref lemon::Dijkstra::run() "run()" or
     795    ///\ref lemon::Dijkstra::start() "start()" must be called before
     796    ///using them.
    804797
    805798    ///@{
    … …  
    809802    ///Returns the shortest path to a node.
    810803    ///
    811     ///\warning \c t should be reached from the root(s).
    812     ///
    813     ///\pre Either \ref run(Node) "run()" or \ref init()
    814     ///must be called before using this function.
     804    ///\warning \c t should be reachable from the root(s).
     805    ///
     806    ///\pre Either \ref run() or \ref start() must be called before
     807    ///using this function.
    815808    Path path(Node t) const { return Path(*G, *_pred, t); }
    816809
    … …  
    819812    ///Returns the distance of a node from the root(s).
    820813    ///
    821     ///\warning If node \c v is not reached from the root(s), then
     814    ///\warning If node \c v is not reachable from the root(s), then
    822815    ///the return value of this function is undefined.
    823816    ///
    824     ///\pre Either \ref run(Node) "run()" or \ref init()
    825     ///must be called before using this function.
     817    ///\pre Either \ref run() or \ref start() must be called before
     818    ///using this function.
    826819    Value dist(Node v) const { return (*_dist)[v]; }
    827820
    … …  
    830823    ///This function returns the 'previous arc' of the shortest path
    831824    ///tree for the node \c v, i.e. it returns the last arc of a
    832     ///shortest path from a root to \c v. It is \c INVALID if \c v
    833     ///is not reached from the root(s) or if \c v is a root.
     825    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
     826    ///is not reachable from the root(s) or if \c v is a root.
    834827    ///
    835828    ///The shortest path tree used here is equal to the shortest path
    836829    ///tree used in \ref predNode().
    837830    ///
    838     ///\pre Either \ref run(Node) "run()" or \ref init()
    839     ///must be called before using this function.
     831    ///\pre Either \ref run() or \ref start() must be called before
     832    ///using this function.
    840833    Arc predArc(Node v) const { return (*_pred)[v]; }
    841834
    … …  
    844837    ///This function returns the 'previous node' of the shortest path
    845838    ///tree for the node \c v, i.e. it returns the last but one node
    846     ///from a shortest path from a root to \c v. It is \c INVALID
    847     ///if \c v is not reached from the root(s) or if \c v is a root.
     839    ///from a shortest path from the root(s) to \c v. It is \c INVALID
     840    ///if \c v is not reachable from the root(s) or if \c v is a root.
    848841    ///
    849842    ///The shortest path tree used here is equal to the shortest path
    850843    ///tree used in \ref predArc().
    851844    ///
    852     ///\pre Either \ref run(Node) "run()" or \ref init()
    853     ///must be called before using this function.
     845    ///\pre Either \ref run() or \ref start() must be called before
     846    ///using this function.
    854847    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    855848                                  G->source((*_pred)[v]); }
    … …  
    861854    ///of the nodes calculated by the algorithm.
    862855    ///
    863     ///\pre Either \ref run(Node) "run()" or \ref init()
     856    ///\pre Either \ref run() or \ref init()
    864857    ///must be called before using this function.
    865858    const DistMap &distMap() const { return *_dist;}
    … …  
    871864    ///arcs, which form the shortest path tree.
    872865    ///
    873     ///\pre Either \ref run(Node) "run()" or \ref init()
     866    ///\pre Either \ref run() or \ref init()
    874867    ///must be called before using this function.
    875868    const PredMap &predMap() const { return *_pred;}
    876869
    877     ///Checks if a node is reached from the root(s).
    878 
    879     ///Returns \c true if \c v is reached from the root(s).
    880     ///
    881     ///\pre Either \ref run(Node) "run()" or \ref init()
     870    ///Checks if a node is reachable from the root(s).
     871
     872    ///Returns \c true if \c v is reachable from the root(s).
     873    ///\pre Either \ref run() or \ref start()
    882874    ///must be called before using this function.
    883875    bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
    … …  
    888880    ///Returns \c true if \c v is processed, i.e. the shortest
    889881    ///path to \c v has already found.
    890     ///
    891     ///\pre Either \ref run(Node) "run()" or \ref init()
     882    ///\pre Either \ref run() or \ref init()
    892883    ///must be called before using this function.
    893884    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
    … …  
    898889    ///Returns the current distance of a node from the root(s).
    899890    ///It may be decreased in the following processes.
    900     ///
    901     ///\pre Either \ref run(Node) "run()" or \ref init()
     891    ///\pre Either \ref run() or \ref init()
    902892    ///must be called before using this function and
    903893    ///node \c v must be reached but not necessarily processed.
    … …  
    10821072  /// This auxiliary class is created to implement the
    10831073  /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
    1084   /// It does not have own \ref run(Node) "run()" method, it uses the
    1085   /// functions and features of the plain \ref Dijkstra.
     1074  /// It does not have own \ref run() method, it uses the functions
     1075  /// and features of the plain \ref Dijkstra.
    10861076  ///
    10871077  /// This class should only be used through the \ref dijkstra() function,
    … …  
    12781268  ///  bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
    12791269  ///\endcode
    1280   ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()"
     1270  ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
    12811271  ///to the end of the parameter list.
    12821272  ///\sa DijkstraWizard

  • lemon/dim2.h

    r463 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/error.h

    r463 r291  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/graph_to_eps.h

    r562 r511  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/kruskal.h

    r463 r220  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/lgf_reader.h

    r564 r517  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    848848        readLine();
    849849      }
    850       if (readSuccess()) {
    851         line.putback(c);
    852       }
     850      line.putback(c);
    853851    }
    854852
    … …  
    16901688        readLine();
    16911689      }
    1692       if (readSuccess()) {
    1693         line.putback(c);
    1694       }
     1690      line.putback(c);
    16951691    }
    16961692
    … …  
    22492245        readLine();
    22502246      }
    2251       if (readSuccess()) {
    2252         line.putback(c);
    2253       }
     2247      line.putback(c);
    22542248    }
    22552249
    … …  
    25922586        readLine();
    25932587      }
    2594       if (readSuccess()) {
    2595         line.putback(c);
    2596       }
     2588      line.putback(c);
    25972589    }
    25982590

  • lemon/lgf_writer.h

    r564 r517  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/list_graph.h

    r463 r313  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    841841
    842842    public:
    843       operator Edge() const {
    844         return id != -1 ? edgeFromId(id / 2) : INVALID;
     843      operator Edge() const { 
     844        return id != -1 ? edgeFromId(id / 2) : INVALID; 
    845845      }
    846846

  • lemon/maps.h

    r463 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/math.h

    r558 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    5656  const long double SQRT1_2 = 0.7071067811865475244008443621048490L;
    5757
    58   ///Check whether the parameter is NaN or not
    59  
    60   ///This function checks whether the parameter is NaN or not.
    61   ///Is should be equivalent with std::isnan(), but it is not
    62   ///provided by all compilers.
    63   inline bool isNaN(double v)
    64     {
    65       return v!=v;
    66     }
    6758
    6859  /// @}

  • lemon/path.h

    r564 r517  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/random.cc

    r463 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/random.h

    r564 r517  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    531531    /// @{
    532532
     533    ///\name Initialization
     534    ///
     535    /// @{
     536
    533537    /// \brief Default constructor
    534538    ///
    … …  
    677681    }
    678682
     683    /// @}
     684
     685    ///\name Uniform distributions
     686    ///
     687    /// @{
     688
    679689    /// \brief Returns a random real number from the range [0, 1)
    680690    ///
    … …  
    731741      return _random_bits::IntConversion<Number, Word>::convert(core);
    732742    }
     743
     744    /// @}
    733745
    734746    unsigned int uinteger() {
    … …  
    765777    ///\name Non-uniform distributions
    766778    ///
     779
    767780    ///@{
    768781
    769     /// \brief Returns a random bool with given probability of true result.
     782    /// \brief Returns a random bool
    770783    ///
    771784    /// It returns a random bool with given probability of true result.
    … …  
    774787    }
    775788
    776     /// Standard normal (Gauss) distribution
    777 
    778     /// Standard normal (Gauss) distribution.
     789    /// Standard Gauss distribution
     790
     791    /// Standard Gauss distribution.
    779792    /// \note The Cartesian form of the Box-Muller
    780793    /// transformation is used to generate a random normal distribution.
    … …  
    789802      return std::sqrt(-2*std::log(S)/S)*V1;
    790803    }
    791     /// Normal (Gauss) distribution with given mean and standard deviation
    792 
    793     /// Normal (Gauss) distribution with given mean and standard deviation.
     804    /// Gauss distribution with given mean and standard deviation
     805
     806    /// Gauss distribution with given mean and standard deviation.
    794807    /// \sa gauss()
    795808    double gauss(double mean,double std_dev)
    796809    {
    797810      return gauss()*std_dev+mean;
    798     }
    799 
    800     /// Lognormal distribution
    801 
    802     /// Lognormal distribution. The parameters are the mean and the standard
    803     /// deviation of <tt>exp(X)</tt>.
    804     ///
    805     double lognormal(double n_mean,double n_std_dev)
    806     {
    807       return std::exp(gauss(n_mean,n_std_dev));
    808     }
    809     /// Lognormal distribution
    810 
    811     /// Lognormal distribution. The parameter is an <tt>std::pair</tt> of
    812     /// the mean and the standard deviation of <tt>exp(X)</tt>.
    813     ///
    814     double lognormal(const std::pair<double,double> &params)
    815     {
    816       return std::exp(gauss(params.first,params.second));
    817     }
    818     /// Compute the lognormal parameters from mean and standard deviation
    819 
    820     /// This function computes the lognormal parameters from mean and
    821     /// standard deviation. The return value can direcly be passed to
    822     /// lognormal().
    823     std::pair<double,double> lognormalParamsFromMD(double mean,
    824                                                    double std_dev)
    825     {
    826       double fr=std_dev/mean;
    827       fr*=fr;
    828       double lg=std::log(1+fr);
    829       return std::pair<double,double>(std::log(mean)-lg/2.0,std::sqrt(lg));
    830     }
    831     /// Lognormal distribution with given mean and standard deviation
    832 
    833     /// Lognormal distribution with given mean and standard deviation.
    834     ///
    835     double lognormalMD(double mean,double std_dev)
    836     {
    837       return lognormal(lognormalParamsFromMD(mean,std_dev));
    838811    }
    839812
    … …  
    941914    ///\name Two dimensional distributions
    942915    ///
     916
    943917    ///@{
    944918
    … …  
    957931      return dim2::Point<double>(V1,V2);
    958932    }
    959     /// A kind of two dimensional normal (Gauss) distribution
     933    /// A kind of two dimensional Gauss distribution
    960934
    961935    /// This function provides a turning symmetric two-dimensional distribution.

  • lemon/smart_graph.h

    r463 r313  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    6868
    6969    typedef True NodeNumTag;
    70     typedef True ArcNumTag;
     70    typedef True EdgeNumTag;
    7171
    7272    int nodeNum() const { return nodes.size(); }
    … …  
    306306      nodes[b._id].first_out=nodes[n._id].first_out;
    307307      nodes[n._id].first_out=-1;
    308       for(int i=nodes[b._id].first_out; i!=-1; i=arcs[i].next_out) {
    309         arcs[i].source=b._id;
    310       }
     308      for(int i=nodes[b._id].first_out;i!=-1;i++) arcs[i].source=b._id;
    311309      if(connect) addArc(n,b);
    312310      return b;
    … …  
    467465
    468466    public:
    469       operator Edge() const {
    470         return _id != -1 ? edgeFromId(_id / 2) : INVALID;
     467      operator Edge() const { 
     468        return _id != -1 ? edgeFromId(_id / 2) : INVALID; 
    471469      }
    472470
    … …  
    483481      : nodes(), arcs() {}
    484482
    485     typedef True NodeNumTag;
    486     typedef True EdgeNumTag;
    487     typedef True ArcNumTag;
    488 
    489     int nodeNum() const { return nodes.size(); }
    490     int edgeNum() const { return arcs.size() / 2; }
    491     int arcNum() const { return arcs.size(); }
    492483
    493484    int maxNodeId() const { return nodes.size()-1; }
    … …  
    738729        dir.push_back(arcFromId(n-1));
    739730        Parent::notifier(Arc()).erase(dir);
    740         nodes[arcs[n-1].target].first_out=arcs[n].next_out;
    741         nodes[arcs[n].target].first_out=arcs[n-1].next_out;
     731        nodes[arcs[n].target].first_out=arcs[n].next_out;
     732        nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
    742733        arcs.pop_back();
    743734        arcs.pop_back();

  • lemon/time_measure.h

    r562 r511  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/tolerance.h

    r564 r516  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/unionfind.h

    r463 r460  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    11901190              popLeft(nodes[jd].next);
    11911191              pushRight(jd, ld);
    1192               if (less(ld, nodes[jd].left) ||
     1192              if (less(ld, nodes[jd].left) || 
    11931193                  nodes[ld].item == nodes[pd].item) {
    11941194                nodes[jd].item = nodes[ld].item;

  • m4/lx_check_cplex.m4

    r480 r187  
    6363    if test x"$lx_cplex_found" = x"yes"; then
    6464      AC_DEFINE([HAVE_CPLEX], [1], [Define to 1 if you have CPLEX.])
    65       lx_lp_found=yes
    66       AC_DEFINE([HAVE_LP], [1], [Define to 1 if you have any LP solver.])
    67       lx_mip_found=yes
    68       AC_DEFINE([HAVE_MIP], [1], [Define to 1 if you have any MIP solver.])
    6965      AC_MSG_RESULT([yes])
    7066    else

  • m4/lx_check_glpk.m4

    r482 r187  
    4343      }
    4444
    45       #if (GLP_MAJOR_VERSION < 4) \
    46          || (GLP_MAJOR_VERSION == 4 && GLP_MINOR_VERSION < 33)
    47       #error Supported GLPK versions: 4.33 or above
    48       #endif
    49 
    5045      int main(int argc, char** argv)
    5146      {
    … …  
    6661    if test x"$lx_glpk_found" = x"yes"; then
    6762      AC_DEFINE([HAVE_GLPK], [1], [Define to 1 if you have GLPK.])
    68       lx_lp_found=yes
    69       AC_DEFINE([HAVE_LP], [1], [Define to 1 if you have any LP solver.])
    70       lx_mip_found=yes
    71       AC_DEFINE([HAVE_MIP], [1], [Define to 1 if you have any MIP solver.])
    7263      AC_MSG_RESULT([yes])
    7364    else

  • m4/lx_check_soplex.m4

    r480 r187  
    5757    if test x"$lx_soplex_found" = x"yes"; then
    5858      AC_DEFINE([HAVE_SOPLEX], [1], [Define to 1 if you have SOPLEX.])
    59       lx_lp_found=yes
    60       AC_DEFINE([HAVE_LP], [1], [Define to 1 if you have any LP solver.])
    6159      AC_MSG_RESULT([yes])
    6260    else

  • scripts/chg-len.py

    r439 r284  
    22
    33import sys
    4 
    5 from mercurial import ui, hg
    6 from mercurial import util
    7 
    8 util.rcpath = lambda : []
     4import os
    95
    106if len(sys.argv)>1 and sys.argv[1] in ["-h","--help"]:
    … …  
    1410"""
    1511    exit(0)
     12plist = os.popen("HGRCPATH='' hg parents --template='{rev}\n'").readlines()
     13if len(plist)>1:
     14    print "You are in the process of merging"
     15    exit(1)
     16PAR = int(plist[0])
    1617
    17 u = ui.ui()
    18 r = hg.repository(u, ".")
    19 N = r.changectx(".").rev()
    20 lengths=[0]*(N+1)
    21 for i in range(N+1):
    22     p=r.changectx(i).parents()
    23     if p[0]:
    24         p0=lengths[p[0].rev()]
     18f = os.popen("HGRCPATH='' hg log -r 0:tip --template='{rev} {parents}\n'").\
     19    readlines()
     20REV = -1
     21lengths=[]
     22for l in f:
     23    REV+=1
     24    s = l.split()
     25    rev = int(s[0])
     26    if REV != rev:
     27        print "Something is seriously wrong"
     28        exit(1)
     29    if len(s) == 1:
     30        par1 = par2 = rev - 1
     31    elif len(s) == 2:
     32        par1 = par2 = int(s[1].split(":")[0])
    2533    else:
    26         p0=-1
    27     if len(p)>1 and p[1]:
    28         p1=lengths[p[1].rev()]
     34        par1 = int(s[1].split(":")[0])
     35        par2 = int(s[2].split(":")[0])
     36    if rev == 0:
     37        lengths.append(0)
    2938    else:
    30         p1=-1
    31     lengths[i]=max(p0,p1)+1
    32 print lengths[N]
     39        lengths.append(max(lengths[par1],lengths[par2])+1)
     40print lengths[PAR]

  • scripts/unify-sources.sh

    r411 r208  
    44HGROOT=`hg root`
    55
    6 # file enumaration modes
    7 
    8 function all_files() {
    9     hg status -a -m -c |
    10     cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' |
    11     while read file; do echo $HGROOT/$file; done
    12 }
    13 
    14 function modified_files() {
    15     hg status -a -m |
    16     cut -d ' ' -f 2 | grep -E  '(\.(cc|h|dox)$|Makefile\.am$)' |
    17     while read file; do echo $HGROOT/$file; done
    18 }
    19 
    20 function changed_files() {
    21     {
    22         if [ -n "$HG_PARENT1" ]
    23         then
    24             hg status --rev $HG_PARENT1:$HG_NODE -a -m
    25         fi
    26         if [ -n "$HG_PARENT2" ]
    27         then
    28             hg status --rev $HG_PARENT2:$HG_NODE -a -m
    29         fi
    30     } | cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' |
    31     sort | uniq |
    32     while read file; do echo $HGROOT/$file; done
    33 }
    34 
    35 function given_files() {
    36     for file in $GIVEN_FILES
    37     do
    38         echo $file
    39     done
    40 }
    41 
    42 # actions
    43 
    44 function update_action() {
    45     if ! diff -q $1 $2 >/dev/null
    46     then
    47         echo -n " [$3 updated]"
    48         rm $2
    49         mv $1 $2
    50         CHANGED=YES
    51     fi
    52 }
    53 
    54 function update_warning() {
    55     echo -n " [$2 warning]"
    56     WARNED=YES
    57 }
    58 
    59 function update_init() {
    60     echo Update source files...
    61     TOTAL_FILES=0
    62     CHANGED_FILES=0
    63     WARNED_FILES=0
    64 }
    65 
    66 function update_done() {
    67     echo $CHANGED_FILES out of $TOTAL_FILES files has been changed.
    68     echo $WARNED_FILES out of $TOTAL_FILES files triggered warnings.
    69 }
    70 
    71 function update_begin() {
    72     ((TOTAL_FILES++))
    73     CHANGED=NO
    74     WARNED=NO
    75 }
    76 
    77 function update_end() {
    78     if [ $CHANGED == YES ]
    79     then
    80         ((++CHANGED_FILES))
    81     fi
    82     if [ $WARNED == YES ]
    83     then
    84         ((++WARNED_FILES))
    85     fi
    86 }
    87 
    88 function check_action() {
    89     if [ "$3" == 'tabs' ]
    90     then
    91         PATTERN=$(echo -e '\t')
    92     elif [ "$3" == 'trailing spaces' ]
    93     then
    94         PATTERN='\ +$'
    95     else
    96         PATTERN='*'
    97     fi
    98 
    99     if ! diff -q $1 $2 >/dev/null
    100     then
    101         if [ "$PATTERN" == '*' ]
    102         then
    103             diff $1 $2 | grep '^[0-9]' | sed "s|^\(.*\)c.*$|$2:\1: check failed: $3|g" |
    104               sed "s/:\([0-9]*\),\([0-9]*\):\(.*\)$/:\1:\3 (until line \2)/g"
    105         else
    106             grep -n -E "$PATTERN" $2 | sed "s|^\([0-9]*\):.*$|$2:\1: check failed: $3|g"
    107         fi
    108         FAILED=YES
    109     fi
    110 }
    111 
    112 function check_warning() {
    113     if [ "$2" == 'long lines' ]
    114     then
    115         grep -n -E '.{81,}' $1 | sed "s|^\([0-9]*\):.*$|$1:\1: warning: $2|g"
    116     else
    117         echo "$1: warning: $2"
    118     fi
    119     WARNED=YES
    120 }
    121 
    122 function check_init() {
    123     echo Check source files...
    124     FAILED_FILES=0
    125     WARNED_FILES=0
    126     TOTAL_FILES=0
    127 }
    128 
    129 function check_done() {
    130     echo $FAILED_FILES out of $TOTAL_FILES files has been failed.
    131     echo $WARNED_FILES out of $TOTAL_FILES files triggered warnings.
    132 
    133     if [ $WARNED_FILES -gt 0 -o $FAILED_FILES -gt 0 ]
    134     then
    135         if [ "$WARNING" == 'INTERACTIVE' ]
    136         then
    137             echo -n "Are the files with errors/warnings acceptable? (yes/no) "
    138             while read answer
    139             do
    140                 if [ "$answer" == 'yes' ]
    141                 then
    142                     return 0
    143                 elif [ "$answer" == 'no' ]
    144                 then
    145                     return 1
    146                 fi
    147                 echo -n "Are the files with errors/warnings acceptable? (yes/no) "
    148             done
    149         elif [ "$WARNING" == 'WERROR' ]
    150         then
    151             return 1
    152         fi
    153     fi
    154 }
    155 
    156 function check_begin() {
    157     ((TOTAL_FILES++))
    158     FAILED=NO
    159     WARNED=NO
    160 }
    161 
    162 function check_end() {
    163     if [ $FAILED == YES ]
    164     then
    165         ((++FAILED_FILES))
    166     fi
    167     if [ $WARNED == YES ]
    168     then
    169         ((++WARNED_FILES))
    170     fi
    171 }
    172 
    173 
    174 
    175 # checks
    176 
    177 function header_check() {
    178     if echo $1 | grep -q -E 'Makefile\.am$'
    179     then
    180         return
    181     fi
    182 
     6function update_header() {
    1837    TMP_FILE=`mktemp`
     8    FILE_NAME=$1
    1849
    18510    (echo "/* -*- mode: C++; indent-tabs-mode: nil; -*-
    … …  
    20126 */
    20227"
    203     awk 'BEGIN { pm=0; }
     28        awk 'BEGIN { pm=0; }
    20429     pm==3 { print }
    20530     /\/\* / && pm==0 { pm=1;}
    … …  
    20732     /\*\// && pm==1 { pm=2;}
    20833    ' $1
    209     ) >$TMP_FILE
     34        ) >$TMP_FILE
    21035
    211     "$ACTION"_action "$TMP_FILE" "$1" header
     36    HEADER_CH=`diff -q $TMP_FILE $FILE_NAME >/dev/null&&echo NO||echo YES`
     37
     38    rm $FILE_NAME
     39    mv $TMP_FILE $FILE_NAME
    21240}
    21341
    214 function tabs_check() {
    215     if echo $1 | grep -q -v -E 'Makefile\.am$'
    216     then
    217         OLD_PATTERN=$(echo -e '\t')
    218         NEW_PATTERN='        '
    219     else
    220         OLD_PATTERN='        '
    221         NEW_PATTERN=$(echo -e '\t')
    222     fi
     42function update_tabs() {
    22343    TMP_FILE=`mktemp`
    224     cat $1 | sed -e "s/$OLD_PATTERN/$NEW_PATTERN/g" >$TMP_FILE
     44    FILE_NAME=$1
    22545
    226     "$ACTION"_action "$TMP_FILE" "$1" 'tabs'
     46    cat $1 |
     47    sed -e 's/\t/        /g' >$TMP_FILE
     48
     49    TABS_CH=`diff -q $TMP_FILE $FILE_NAME >/dev/null&&echo NO||echo YES`
     50
     51    rm $FILE_NAME
     52    mv $TMP_FILE $FILE_NAME
    22753}
    22854
    229 function spaces_check() {
     55function remove_trailing_space() {
    23056    TMP_FILE=`mktemp`
    231     cat $1 | sed -e 's/ \+$//g' >$TMP_FILE
     57    FILE_NAME=$1
    23258
    233     "$ACTION"_action "$TMP_FILE" "$1" 'trailing spaces'
     59    cat $1 |
     60    sed -e 's/ \+$//g' >$TMP_FILE
     61
     62    SPACES_CH=`diff -q $TMP_FILE $FILE_NAME >/dev/null&&echo NO||echo YES`
     63
     64    rm $FILE_NAME
     65    mv $TMP_FILE $FILE_NAME
    23466}
    23567
    236 function long_lines_check() {
    237     if cat $1 | grep -q -E '.{81,}'
     68function long_line_test() {
     69    cat $1 |grep -q -E '.{81,}'
     70}
     71
     72function update_file() {
     73    echo -n '    update' $i ...
     74
     75    update_header $1
     76    update_tabs $1
     77    remove_trailing_space $1
     78
     79    CHANGED=NO;
     80    if [[ $HEADER_CH = YES ]];
    23881    then
    239         "$ACTION"_warning $1 'long lines'
     82        echo -n '  [header updated]'
     83        CHANGED=YES;
     84    fi
     85    if [[ $TABS_CH = YES ]];
     86    then
     87        echo -n ' [tabs removed]'
     88        CHANGED=YES;
     89    fi
     90    if [[ $SPACES_CH = YES ]];
     91    then
     92        echo -n ' [trailing spaces removed]'
     93        CHANGED=YES;
     94    fi
     95    if long_line_test $1 ;
     96    then
     97        echo -n ' [LONG LINES]'
     98        ((LONG_LINE_FILES++))
     99    fi
     100    echo
     101    if [[ $CHANGED = YES ]];
     102    then
     103        ((CHANGED_FILES++))
    240104    fi
    241105}
    242106
    243 # process the file
    244 
    245 function process_file() {
    246     if [ "$ACTION" == 'update' ]
    247     then
    248         echo -n "    $ACTION $1..."
    249     else
    250         echo "    $ACTION $1..."
    251     fi
    252 
    253     CHECKING="header tabs spaces long_lines"
    254 
    255     "$ACTION"_begin $1
    256     for check in $CHECKING
     107CHANGED_FILES=0
     108TOTAL_FILES=0
     109LONG_LINE_FILES=0
     110if [ $# == 0 ]; then
     111    echo Update all source files...
     112    for i in `hg manifest|grep -E  '\.(cc|h|dox)$'`
    257113    do
    258         "$check"_check $1
     114        update_file $HGROOT/$i
     115        ((TOTAL_FILES++))
    259116    done
    260     "$ACTION"_end $1
    261     if [ "$ACTION" == 'update' ]
    262     then
    263         echo
    264     fi
    265 }
    266 
    267 function process_all {
    268     "$ACTION"_init
    269     while read file
     117    echo '  done.'
     118else
     119    for i in $*
    270120    do
    271         process_file $file
    272     done < <($FILES)
    273     "$ACTION"_done
    274 }
    275 
    276 while [ $# -gt 0 ]
    277 do
    278    
    279     if [ "$1" == '--help' ] || [ "$1" == '-h' ]
    280     then
    281         echo -n \
    282 "Usage:
    283   $0 [OPTIONS] [files]
    284 Options:
    285   --dry-run|-n
    286      Check the files, but do not modify them.
    287   --interactive|-i
    288      If --dry-run is specified and the checker emits warnings,
    289      then the user is asked if the warnings should be considered
    290      errors.
    291   --werror|-w
    292      Make all warnings into errors.
    293   --all|-a
    294      Check all source files in the repository.
    295   --modified|-m
    296      Check only the modified (and new) source files. This option is
    297      useful to check the modification before making a commit.
    298   --changed|-c
    299      Check only the changed source files compared to the parent(s) of
    300      the current hg node.  This option is useful as hg hook script.
    301      To automatically check all your changes before making a commit,
    302      add the following section to the appropriate .hg/hgrc file.
    303 
    304        [hooks]
    305        pretxncommit.checksources = scripts/unify-sources.sh -c -n -i
    306 
    307   --help|-h
    308      Print this help message.
    309   files
    310      The files to check/unify. If no file names are given, the modified
    311      source files will be checked/unified (just like using the
    312      --modified|-m option).
    313 "
    314         exit 0
    315     elif [ "$1" == '--dry-run' ] || [ "$1" == '-n' ]
    316     then
    317         [ -n "$ACTION" ] && echo "Conflicting action options" >&2 && exit 1
    318         ACTION=check
    319     elif [ "$1" == "--all" ] || [ "$1" == '-a' ]
    320     then
    321         [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1
    322         FILES=all_files
    323     elif [ "$1" == "--changed" ] || [ "$1" == '-c' ]
    324     then
    325         [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1
    326         FILES=changed_files
    327     elif [ "$1" == "--modified" ] || [ "$1" == '-m' ]
    328     then
    329         [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1
    330         FILES=modified_files
    331     elif [ "$1" == "--interactive" ] || [ "$1" == "-i" ]
    332     then
    333         [ -n "$WARNING" ] && echo "Conflicting warning options" >&2 && exit 1
    334         WARNING='INTERACTIVE'
    335     elif [ "$1" == "--werror" ] || [ "$1" == "-w" ]
    336     then
    337         [ -n "$WARNING" ] && echo "Conflicting warning options" >&2 && exit 1
    338         WARNING='WERROR'
    339     elif [ $(echo x$1 | cut -c 2) == '-' ]
    340     then
    341         echo "Invalid option $1" >&2 && exit 1
    342     else
    343         [ -n "$FILES" ] && echo "Invalid option $1" >&2 && exit 1
    344         GIVEN_FILES=$@
    345         FILES=given_files
    346         break
    347     fi
    348    
    349     shift
    350 done
    351 
    352 if [ -z $FILES ]
    353 then
    354     FILES=modified_files
     121        update_file $i
     122        ((TOTAL_FILES++))
     123    done
    355124fi
    356 
    357 if [ -z $ACTION ]
    358 then
    359     ACTION=update
     125echo $CHANGED_FILES out of $TOTAL_FILES files has been changed.
     126if [[ $LONG_LINE_FILES -gt 1 ]]; then
     127    echo
     128    echo WARNING: $LONG_LINE_FILES files contains long lines!   
     129    echo
     130elif [[ $LONG_LINE_FILES -gt 0 ]]; then
     131    echo
     132    echo WARNING: a file contains long lines!
     133    echo
    360134fi
    361 
    362 process_all

  • test/CMakeLists.txt

    r575 r225  
    1 INCLUDE_DIRECTORIES(
    2   ${CMAKE_SOURCE_DIR}
    3   ${CMAKE_BINARY_DIR}
    4 )
    5 
    6 IF(HAVE_GLPK)
    7   INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR})
    8 ENDIF(HAVE_GLPK)
     1INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
    92
    103LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
    114
    125SET(TESTS
    13   adaptors_test
    146  bfs_test
    15   circulation_test
    167  counter_test
    178  dfs_test
    … …  
    1910  dijkstra_test
    2011  dim_test
    21   edge_set_test
    2212  error_test
    23   euler_test
    2413  graph_copy_test
    2514  graph_test
    2615  graph_utils_test
    27   hao_orlin_test
    2816  heap_test
    2917  kruskal_test
    3018  maps_test
    31   max_matching_test
    32   min_cost_arborescence_test
     19  random_test
    3320  path_test
    34   preflow_test
    35   radix_sort_test
    36   random_test
    37   suurballe_test
    3821  time_measure_test
    3922  unionfind_test)
    40 
    41 IF(HAVE_LP)
    42   ADD_EXECUTABLE(lp_test lp_test.cc)
    43   IF(HAVE_GLPK)
    44     TARGET_LINK_LIBRARIES(lp_test lemon ${GLPK_LIBRARIES})
    45   ENDIF(HAVE_GLPK)
    46   ADD_TEST(lp_test lp_test)
    47 
    48   IF(WIN32 AND HAVE_GLPK)
    49     GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION)
    50     GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
    51     ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD
    52       COMMAND cmake -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}
    53       COMMAND cmake -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}
    54       COMMAND cmake -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}
    55     )
    56   ENDIF(WIN32 AND HAVE_GLPK)
    57 ENDIF(HAVE_LP)
    58 
    59 IF(HAVE_MIP)
    60   ADD_EXECUTABLE(mip_test mip_test.cc)
    61   IF(HAVE_GLPK)
    62     TARGET_LINK_LIBRARIES(mip_test lemon ${GLPK_LIBRARIES})
    63   ENDIF(HAVE_GLPK)
    64   ADD_TEST(mip_test mip_test)
    65 
    66   IF(WIN32 AND HAVE_GLPK)
    67     GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION)
    68     GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
    69     ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD
    70       COMMAND cmake -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}
    71       COMMAND cmake -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}
    72       COMMAND cmake -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}
    73     )
    74   ENDIF(WIN32 AND HAVE_GLPK)
    75 ENDIF(HAVE_MIP)
    7623
    7724FOREACH(TEST_NAME ${TESTS})

  • test/Makefile.am

    r575 r228  
    44noinst_HEADERS += \
    55        test/graph_test.h \
    6         test/test_tools.h
     6        test/test_tools.h
    77
    88check_PROGRAMS += \
    9         test/adaptors_test \
    109        test/bfs_test \
    11         test/circulation_test \
    12         test/counter_test \
     10        test/counter_test \
    1311        test/dfs_test \
    1412        test/digraph_test \
    1513        test/dijkstra_test \
    16         test/dim_test \
    17         test/edge_set_test \
     14        test/dim_test \
    1815        test/error_test \
    19         test/euler_test \
    2016        test/graph_copy_test \
    2117        test/graph_test \
    2218        test/graph_utils_test \
    23         test/hao_orlin_test \
    2419        test/heap_test \
    2520        test/kruskal_test \
    26         test/maps_test \
    27         test/max_matching_test \
    28         test/min_cost_arborescence_test \
    29         test/path_test \
    30         test/preflow_test \
    31         test/radix_sort_test \
    32         test/random_test \
    33         test/suurballe_test \
    34         test/test_tools_fail \
    35         test/test_tools_pass \
    36         test/time_measure_test \
     21        test/maps_test \
     22        test/random_test \
     23        test/path_test \
     24        test/test_tools_fail \
     25        test/test_tools_pass \
     26        test/time_measure_test \
    3727        test/unionfind_test
    38 
    39 if HAVE_LP
    40 check_PROGRAMS += test/lp_test
    41 endif HAVE_LP
    42 if HAVE_MIP
    43 check_PROGRAMS += test/mip_test
    44 endif HAVE_MIP
    4528
    4629TESTS += $(check_PROGRAMS)
    4730XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
    4831
    49 test_adaptors_test_SOURCES = test/adaptors_test.cc
    5032test_bfs_test_SOURCES = test/bfs_test.cc
    51 test_circulation_test_SOURCES = test/circulation_test.cc
    5233test_counter_test_SOURCES = test/counter_test.cc
    5334test_dfs_test_SOURCES = test/dfs_test.cc
    … …  
    5536test_dijkstra_test_SOURCES = test/dijkstra_test.cc
    5637test_dim_test_SOURCES = test/dim_test.cc
    57 test_edge_set_test_SOURCES = test/edge_set_test.cc
    5838test_error_test_SOURCES = test/error_test.cc
    59 test_euler_test_SOURCES = test/euler_test.cc
    6039test_graph_copy_test_SOURCES = test/graph_copy_test.cc
    6140test_graph_test_SOURCES = test/graph_test.cc
    … …  
    6342test_heap_test_SOURCES = test/heap_test.cc
    6443test_kruskal_test_SOURCES = test/kruskal_test.cc
    65 test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
    66 test_lp_test_SOURCES = test/lp_test.cc
    6744test_maps_test_SOURCES = test/maps_test.cc
    68 test_mip_test_SOURCES = test/mip_test.cc
    69 test_max_matching_test_SOURCES = test/max_matching_test.cc
    70 test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
    7145test_path_test_SOURCES = test/path_test.cc
    72 test_preflow_test_SOURCES = test/preflow_test.cc
    73 test_radix_sort_test_SOURCES = test/radix_sort_test.cc
    74 test_suurballe_test_SOURCES = test/suurballe_test.cc
    7546test_random_test_SOURCES = test/random_test.cc
    7647test_test_tools_fail_SOURCES = test/test_tools_fail.cc

  • test/bfs_test.cc

    r463 r293  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/counter_test.cc

    r463 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/dfs_test.cc

    r463 r293  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/digraph_test.cc

    r463 r228  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    2020#include <lemon/list_graph.h>
    2121#include <lemon/smart_graph.h>
    22 #include <lemon/full_graph.h>
     22//#include <lemon/full_graph.h>
     23//#include <lemon/hypercube_graph.h>
    2324
    2425#include "test_tools.h"
    … …  
    2930
    3031template <class Digraph>
    31 void checkDigraphBuild() {
     32void checkDigraph() {
    3233  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    3334  Digraph G;
    … …  
    5859  checkGraphConArcList(G, 1);
    5960
    60   Arc a2 = G.addArc(n2, n1),
    61       a3 = G.addArc(n2, n3),
    62       a4 = G.addArc(n2, n3);
    63 
    64   checkGraphNodeList(G, 3);
    65   checkGraphArcList(G, 4);
    66 
    67   checkGraphOutArcList(G, n1, 1);
    68   checkGraphOutArcList(G, n2, 3);
    69   checkGraphOutArcList(G, n3, 0);
    70 
    71   checkGraphInArcList(G, n1, 1);
    72   checkGraphInArcList(G, n2, 1);
    73   checkGraphInArcList(G, n3, 2);
    74 
    75   checkGraphConArcList(G, 4);
    76 
    77   checkNodeIds(G);
    78   checkArcIds(G);
    79   checkGraphNodeMap(G);
    80   checkGraphArcMap(G);
    81 }
    82 
    83 template <class Digraph>
    84 void checkDigraphSplit() {
    85   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    86 
    87   Digraph G;
    88   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
    89   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
    90       a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
    91 
    92   Node n4 = G.split(n2);
    93 
    94   check(G.target(OutArcIt(G, n2)) == n4 &&
    95         G.source(InArcIt(G, n4)) == n2,
    96         "Wrong split.");
    97 
    98   checkGraphNodeList(G, 4);
    99   checkGraphArcList(G, 5);
    100 
    101   checkGraphOutArcList(G, n1, 1);
    102   checkGraphOutArcList(G, n2, 1);
    103   checkGraphOutArcList(G, n3, 0);
    104   checkGraphOutArcList(G, n4, 3);
    105 
    106   checkGraphInArcList(G, n1, 1);
    107   checkGraphInArcList(G, n2, 1);
    108   checkGraphInArcList(G, n3, 2);
    109   checkGraphInArcList(G, n4, 1);
    110 
    111   checkGraphConArcList(G, 5);
    112 }
    113 
    114 template <class Digraph>
    115 void checkDigraphAlter() {
    116   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    117 
    118   Digraph G;
    119   Node n1 = G.addNode(), n2 = G.addNode(),
    120        n3 = G.addNode(), n4 = G.addNode();
    121   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
    122       a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),
    123       a5 = G.addArc(n2, n4);
    124 
    125   checkGraphNodeList(G, 4);
    126   checkGraphArcList(G, 5);
    127 
    128   // Check changeSource() and changeTarget()
    129   G.changeTarget(a4, n1);
    130 
    131   checkGraphNodeList(G, 4);
    132   checkGraphArcList(G, 5);
    133 
    134   checkGraphOutArcList(G, n1, 1);
    135   checkGraphOutArcList(G, n2, 1);
    136   checkGraphOutArcList(G, n3, 0);
    137   checkGraphOutArcList(G, n4, 3);
    138 
    139   checkGraphInArcList(G, n1, 2);
    140   checkGraphInArcList(G, n2, 1);
    141   checkGraphInArcList(G, n3, 1);
    142   checkGraphInArcList(G, n4, 1);
    143 
    144   checkGraphConArcList(G, 5);
    145 
    146   G.changeSource(a4, n3);
    147 
    148   checkGraphNodeList(G, 4);
    149   checkGraphArcList(G, 5);
    150 
    151   checkGraphOutArcList(G, n1, 1);
    152   checkGraphOutArcList(G, n2, 1);
    153   checkGraphOutArcList(G, n3, 1);
    154   checkGraphOutArcList(G, n4, 2);
    155 
    156   checkGraphInArcList(G, n1, 2);
    157   checkGraphInArcList(G, n2, 1);
    158   checkGraphInArcList(G, n3, 1);
    159   checkGraphInArcList(G, n4, 1);
    160 
    161   checkGraphConArcList(G, 5);
    162 
    163   // Check contract()
    164   G.contract(n2, n4, false);
    165 
    166   checkGraphNodeList(G, 3);
    167   checkGraphArcList(G, 5);
    168 
    169   checkGraphOutArcList(G, n1, 1);
    170   checkGraphOutArcList(G, n2, 3);
    171   checkGraphOutArcList(G, n3, 1);
    172 
    173   checkGraphInArcList(G, n1, 2);
    174   checkGraphInArcList(G, n2, 2);
    175   checkGraphInArcList(G, n3, 1);
    176 
    177   checkGraphConArcList(G, 5);
    178 
    179   G.contract(n2, n1);
    180 
    181   checkGraphNodeList(G, 2);
    182   checkGraphArcList(G, 3);
    183 
    184   checkGraphOutArcList(G, n2, 2);
    185   checkGraphOutArcList(G, n3, 1);
    186 
    187   checkGraphInArcList(G, n2, 2);
    188   checkGraphInArcList(G, n3, 1);
    189 
    190   checkGraphConArcList(G, 3);
    191 }
    192 
    193 template <class Digraph>
    194 void checkDigraphErase() {
    195   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    196 
    197   Digraph G;
    198   Node n1 = G.addNode(), n2 = G.addNode(),
    199        n3 = G.addNode(), n4 = G.addNode();
    200   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
    201       a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1),
    202       a5 = G.addArc(n2, n4);
    203 
    204   // Check arc deletion
    205   G.erase(a1);
    206 
    207   checkGraphNodeList(G, 4);
    208   checkGraphArcList(G, 4);
    209 
    210   checkGraphOutArcList(G, n1, 0);
    211   checkGraphOutArcList(G, n2, 1);
    212   checkGraphOutArcList(G, n3, 1);
    213   checkGraphOutArcList(G, n4, 2);
    214 
    215   checkGraphInArcList(G, n1, 2);
    216   checkGraphInArcList(G, n2, 0);
    217   checkGraphInArcList(G, n3, 1);
    218   checkGraphInArcList(G, n4, 1);
    219 
    220   checkGraphConArcList(G, 4);
    221 
    222   // Check node deletion
    223   G.erase(n4);
    224 
    225   checkGraphNodeList(G, 3);
    226   checkGraphArcList(G, 1);
    227 
    228   checkGraphOutArcList(G, n1, 0);
    229   checkGraphOutArcList(G, n2, 0);
    230   checkGraphOutArcList(G, n3, 1);
    231   checkGraphOutArcList(G, n4, 0);
    232 
    233   checkGraphInArcList(G, n1, 1);
    234   checkGraphInArcList(G, n2, 0);
    235   checkGraphInArcList(G, n3, 0);
    236   checkGraphInArcList(G, n4, 0);
    237 
    238   checkGraphConArcList(G, 1);
    239 }
    240 
    241 
    242 template <class Digraph>
    243 void checkDigraphSnapshot() {
    244   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    245 
    246   Digraph G;
    247   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
    248   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
    249       a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
    250 
    251   typename Digraph::Snapshot snapshot(G);
    252 
    253   Node n = G.addNode();
    254   G.addArc(n3, n);
    255   G.addArc(n, n3);
    256 
    257   checkGraphNodeList(G, 4);
    258   checkGraphArcList(G, 6);
    259 
    260   snapshot.restore();
    261 
     61  Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
    26262  checkGraphNodeList(G, 3);
    26363  checkGraphArcList(G, 4);
    … …  
    27878  checkGraphArcMap(G);
    27979
    280   G.addNode();
    281   snapshot.save(G);
     80}
    28281
    283   G.addArc(G.addNode(), G.addNode());
    284 
    285   snapshot.restore();
    286 
    287   checkGraphNodeList(G, 4);
    288   checkGraphArcList(G, 4);
    289 }
    29082
    29183void checkConcepts() {
    … …  
    318110    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
    319111  }
    320   { // Checking FullDigraph
    321     checkConcept<Digraph, FullDigraph>();
    322   }
     112//  { // Checking FullDigraph
     113//    checkConcept<Digraph, FullDigraph>();
     114//  }
     115//  { // Checking HyperCubeDigraph
     116//    checkConcept<Digraph, HyperCubeDigraph>();
     117//  }
    323118}
    324119
    … …  
    373168}
    374169
    375 void checkFullDigraph(int num) {
    376   typedef FullDigraph Digraph;
    377   DIGRAPH_TYPEDEFS(Digraph);
    378   Digraph G(num);
    379 
    380   checkGraphNodeList(G, num);
    381   checkGraphArcList(G, num * num);
    382 
    383   for (NodeIt n(G); n != INVALID; ++n) {
    384     checkGraphOutArcList(G, n, num);
    385     checkGraphInArcList(G, n, num);
    386   }
    387 
    388   checkGraphConArcList(G, num * num);
    389 
    390   checkNodeIds(G);
    391   checkArcIds(G);
    392   checkGraphNodeMap(G);
    393   checkGraphArcMap(G);
    394 
    395   for (int i = 0; i < G.nodeNum(); ++i) {
    396     check(G.index(G(i)) == i, "Wrong index");
    397   }
    398 
    399   for (NodeIt s(G); s != INVALID; ++s) {
    400     for (NodeIt t(G); t != INVALID; ++t) {
    401       Arc a = G.arc(s, t);
    402       check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
    403     }
    404   }
    405 }
    406 
    407170void checkDigraphs() {
    408171  { // Checking ListDigraph
    409     checkDigraphBuild<ListDigraph>();
    410     checkDigraphSplit<ListDigraph>();
    411     checkDigraphAlter<ListDigraph>();
    412     checkDigraphErase<ListDigraph>();
    413     checkDigraphSnapshot<ListDigraph>();
     172    checkDigraph<ListDigraph>();
    414173    checkDigraphValidityErase<ListDigraph>();
    415174  }
    416175  { // Checking SmartDigraph
    417     checkDigraphBuild<SmartDigraph>();
    418     checkDigraphSplit<SmartDigraph>();
    419     checkDigraphSnapshot<SmartDigraph>();
     176    checkDigraph<SmartDigraph>();
    420177    checkDigraphValidity<SmartDigraph>();
    421   }
    422   { // Checking FullDigraph
    423     checkFullDigraph(8);
    424178  }
    425179}

  • test/dijkstra_test.cc

    r463 r412  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/dim_test.cc

    r463 r253  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/error_test.cc

    r463 r277  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/graph_copy_test.cc

    r463 r282  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/graph_test.cc

    r463 r228  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    2020#include <lemon/list_graph.h>
    2121#include <lemon/smart_graph.h>
    22 #include <lemon/full_graph.h>
    23 #include <lemon/grid_graph.h>
    24 #include <lemon/hypercube_graph.h>
     22// #include <lemon/full_graph.h>
     23// #include <lemon/grid_graph.h>
    2524
    2625#include "test_tools.h"
    … …  
    3130
    3231template <class Graph>
    33 void checkGraphBuild() {
     32void checkGraph() {
    3433  TEMPLATE_GRAPH_TYPEDEFS(Graph);
    3534
    … …  
    3736  checkGraphNodeList(G, 0);
    3837  checkGraphEdgeList(G, 0);
    39   checkGraphArcList(G, 0);
    4038
    4139  Node
    … …  
    4543  checkGraphNodeList(G, 3);
    4644  checkGraphEdgeList(G, 0);
    47   checkGraphArcList(G, 0);
    4845
    4946  Edge e1 = G.addEdge(n1, n2);
    5047  check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
    5148        "Wrong edge");
    52 
    5349  checkGraphNodeList(G, 3);
     50  checkGraphArcList(G, 2);
    5451  checkGraphEdgeList(G, 1);
    55   checkGraphArcList(G, 2);
    56 
    57   checkGraphIncEdgeArcLists(G, n1, 1);
    58   checkGraphIncEdgeArcLists(G, n2, 1);
    59   checkGraphIncEdgeArcLists(G, n3, 0);
    60 
     52
     53  checkGraphOutArcList(G, n1, 1);
     54  checkGraphOutArcList(G, n2, 1);
     55  checkGraphOutArcList(G, n3, 0);
     56
     57  checkGraphInArcList(G, n1, 1);
     58  checkGraphInArcList(G, n2, 1);
     59  checkGraphInArcList(G, n3, 0);
     60
     61  checkGraphIncEdgeList(G, n1, 1);
     62  checkGraphIncEdgeList(G, n2, 1);
     63  checkGraphIncEdgeList(G, n3, 0);
     64
     65  checkGraphConArcList(G, 2);
    6166  checkGraphConEdgeList(G, 1);
    62   checkGraphConArcList(G, 2);
    63 
    64   Edge e2 = G.addEdge(n2, n1),
    65        e3 = G.addEdge(n2, n3);
    66 
     67
     68  Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
    6769  checkGraphNodeList(G, 3);
     70  checkGraphArcList(G, 6);
    6871  checkGraphEdgeList(G, 3);
    69   checkGraphArcList(G, 6);
    70 
    71   checkGraphIncEdgeArcLists(G, n1, 2);
    72   checkGraphIncEdgeArcLists(G, n2, 3);
    73   checkGraphIncEdgeArcLists(G, n3, 1);
    74 
     72
     73  checkGraphOutArcList(G, n1, 2);
     74  checkGraphOutArcList(G, n2, 3);
     75  checkGraphOutArcList(G, n3, 1);
     76
     77  checkGraphInArcList(G, n1, 2);
     78  checkGraphInArcList(G, n2, 3);
     79  checkGraphInArcList(G, n3, 1);
     80
     81  checkGraphIncEdgeList(G, n1, 2);
     82  checkGraphIncEdgeList(G, n2, 3);
     83  checkGraphIncEdgeList(G, n3, 1);
     84
     85  checkGraphConArcList(G, 6);
    7586  checkGraphConEdgeList(G, 3);
    76   checkGraphConArcList(G, 6);
    7787
    7888  checkArcDirections(G);
    … …  
    8696}
    8797
    88 template <class Graph>
    89 void checkGraphAlter() {
    90   TEMPLATE_GRAPH_TYPEDEFS(Graph);
    91 
    92   Graph G;
    93   Node n1 = G.addNode(), n2 = G.addNode(),
    94        n3 = G.addNode(), n4 = G.addNode();
    95   Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
    96        e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
    97        e5 = G.addEdge(n4, n3);
    98 
    99   checkGraphNodeList(G, 4);
    100   checkGraphEdgeList(G, 5);
    101   checkGraphArcList(G, 10);
    102 
    103   // Check changeU() and changeV()
    104   if (G.u(e2) == n2) {
    105     G.changeU(e2, n3);
    106   } else {
    107     G.changeV(e2, n3);
    108   }
    109 
    110   checkGraphNodeList(G, 4);
    111   checkGraphEdgeList(G, 5);
    112   checkGraphArcList(G, 10);
    113 
    114   checkGraphIncEdgeArcLists(G, n1, 3);
    115   checkGraphIncEdgeArcLists(G, n2, 2);
    116   checkGraphIncEdgeArcLists(G, n3, 3);
    117   checkGraphIncEdgeArcLists(G, n4, 2);
    118 
    119   checkGraphConEdgeList(G, 5);
    120   checkGraphConArcList(G, 10);
    121 
    122   if (G.u(e2) == n1) {
    123     G.changeU(e2, n2);
    124   } else {
    125     G.changeV(e2, n2);
    126   }
    127 
    128   checkGraphNodeList(G, 4);
    129   checkGraphEdgeList(G, 5);
    130   checkGraphArcList(G, 10);
    131 
    132   checkGraphIncEdgeArcLists(G, n1, 2);
    133   checkGraphIncEdgeArcLists(G, n2, 3);
    134   checkGraphIncEdgeArcLists(G, n3, 3);
    135   checkGraphIncEdgeArcLists(G, n4, 2);
    136 
    137   checkGraphConEdgeList(G, 5);
    138   checkGraphConArcList(G, 10);
    139 
    140   // Check contract()
    141   G.contract(n1, n4, false);
    142 
    143   checkGraphNodeList(G, 3);
    144   checkGraphEdgeList(G, 5);
    145   checkGraphArcList(G, 10);
    146 
    147   checkGraphIncEdgeArcLists(G, n1, 4);
    148   checkGraphIncEdgeArcLists(G, n2, 3);
    149   checkGraphIncEdgeArcLists(G, n3, 3);
    150 
    151   checkGraphConEdgeList(G, 5);
    152   checkGraphConArcList(G, 10);
    153 
    154   G.contract(n2, n3);
    155 
    156   checkGraphNodeList(G, 2);
    157   checkGraphEdgeList(G, 3);
    158   checkGraphArcList(G, 6);
    159 
    160   checkGraphIncEdgeArcLists(G, n1, 4);
    161   checkGraphIncEdgeArcLists(G, n2, 2);
    162 
    163   checkGraphConEdgeList(G, 3);
    164   checkGraphConArcList(G, 6);
    165 }
    166 
    167 template <class Graph>
    168 void checkGraphErase() {
    169   TEMPLATE_GRAPH_TYPEDEFS(Graph);
    170 
    171   Graph G;
    172   Node n1 = G.addNode(), n2 = G.addNode(),
    173        n3 = G.addNode(), n4 = G.addNode();
    174   Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
    175        e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
    176        e5 = G.addEdge(n4, n3);
    177 
    178   // Check edge deletion
    179   G.erase(e2);
    180 
    181   checkGraphNodeList(G, 4);
    182   checkGraphEdgeList(G, 4);
    183   checkGraphArcList(G, 8);
    184 
    185   checkGraphIncEdgeArcLists(G, n1, 2);
    186   checkGraphIncEdgeArcLists(G, n2, 2);
    187   checkGraphIncEdgeArcLists(G, n3, 2);
    188   checkGraphIncEdgeArcLists(G, n4, 2);
    189 
    190   checkGraphConEdgeList(G, 4);
    191   checkGraphConArcList(G, 8);
    192 
    193   // Check node deletion
    194   G.erase(n3);
    195 
    196   checkGraphNodeList(G, 3);
    197   checkGraphEdgeList(G, 2);
    198   checkGraphArcList(G, 4);
    199 
    200   checkGraphIncEdgeArcLists(G, n1, 2);
    201   checkGraphIncEdgeArcLists(G, n2, 1);
    202   checkGraphIncEdgeArcLists(G, n4, 1);
    203 
    204   checkGraphConEdgeList(G, 2);
    205   checkGraphConArcList(G, 4);
    206 }
    207 
    208 
    209 template <class Graph>
    210 void checkGraphSnapshot() {
    211   TEMPLATE_GRAPH_TYPEDEFS(Graph);
    212 
    213   Graph G;
    214   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
    215   Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
    216        e3 = G.addEdge(n2, n3);
    217 
    218   checkGraphNodeList(G, 3);
    219   checkGraphEdgeList(G, 3);
    220   checkGraphArcList(G, 6);
    221 
    222   typename Graph::Snapshot snapshot(G);
    223 
    224   Node n = G.addNode();
    225   G.addEdge(n3, n);
    226   G.addEdge(n, n3);
    227   G.addEdge(n3, n2);
    228 
    229   checkGraphNodeList(G, 4);
    230   checkGraphEdgeList(G, 6);
    231   checkGraphArcList(G, 12);
    232 
    233   snapshot.restore();
    234 
    235   checkGraphNodeList(G, 3);
    236   checkGraphEdgeList(G, 3);
    237   checkGraphArcList(G, 6);
    238 
    239   checkGraphIncEdgeArcLists(G, n1, 2);
    240   checkGraphIncEdgeArcLists(G, n2, 3);
    241   checkGraphIncEdgeArcLists(G, n3, 1);
    242 
    243   checkGraphConEdgeList(G, 3);
    244   checkGraphConArcList(G, 6);
    245 
    246   checkNodeIds(G);
    247   checkEdgeIds(G);
    248   checkArcIds(G);
    249   checkGraphNodeMap(G);
    250   checkGraphEdgeMap(G);
    251   checkGraphArcMap(G);
    252 
    253   G.addNode();
    254   snapshot.save(G);
    255 
    256   G.addEdge(G.addNode(), G.addNode());
    257 
    258   snapshot.restore();
    259 
    260   checkGraphNodeList(G, 4);
    261   checkGraphEdgeList(G, 3);
    262   checkGraphArcList(G, 6);
    263 }
    264 
    265 void checkFullGraph(int num) {
    266   typedef FullGraph Graph;
    267   GRAPH_TYPEDEFS(Graph);
    268 
    269   Graph G(num);
    270   checkGraphNodeList(G, num);
    271   checkGraphEdgeList(G, num * (num - 1) / 2);
    272 
    273   for (NodeIt n(G); n != INVALID; ++n) {
    274     checkGraphOutArcList(G, n, num - 1);
    275     checkGraphInArcList(G, n, num - 1);
    276     checkGraphIncEdgeList(G, n, num - 1);
    277   }
    278 
    279   checkGraphConArcList(G, num * (num - 1));
    280   checkGraphConEdgeList(G, num * (num - 1) / 2);
    281 
    282   checkArcDirections(G);
    283 
    284   checkNodeIds(G);
    285   checkArcIds(G);
    286   checkEdgeIds(G);
    287   checkGraphNodeMap(G);
    288   checkGraphArcMap(G);
    289   checkGraphEdgeMap(G);
    290 
    291 
    292   for (int i = 0; i < G.nodeNum(); ++i) {
    293     check(G.index(G(i)) == i, "Wrong index");
    294   }
    295 
    296   for (NodeIt u(G); u != INVALID; ++u) {
    297     for (NodeIt v(G); v != INVALID; ++v) {
    298       Edge e = G.edge(u, v);
    299       Arc a = G.arc(u, v);
    300       if (u == v) {
    301         check(e == INVALID, "Wrong edge lookup");
    302         check(a == INVALID, "Wrong arc lookup");
    303       } else {
    304         check((G.u(e) == u && G.v(e) == v) ||
    305               (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
    306         check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
    307       }
    308     }
    309   }
    310 }
    311 
    31298void checkConcepts() {
    31399  { // Checking graph components
    … …  
    339125    checkConcept<ClearableGraphComponent<>, SmartGraph>();
    340126  }
    341   { // Checking FullGraph
    342     checkConcept<Graph, FullGraph>();
    343   }
    344   { // Checking GridGraph
    345     checkConcept<Graph, GridGraph>();
    346   }
    347   { // Checking HypercubeGraph
    348     checkConcept<Graph, HypercubeGraph>();
    349   }
     127//  { // Checking FullGraph
     128//    checkConcept<Graph, FullGraph>();
     129//    checkGraphIterators<FullGraph>();
     130//  }
     131//  { // Checking GridGraph
     132//    checkConcept<Graph, GridGraph>();
     133//    checkGraphIterators<GridGraph>();
     134//  }
    350135}
    351136
    … …  
    404189}
    405190
    406 void checkGridGraph(int width, int height) {
    407   typedef GridGraph Graph;
    408   GRAPH_TYPEDEFS(Graph);
    409   Graph G(width, height);
    410 
    411   check(G.width() == width, "Wrong column number");
    412   check(G.height() == height, "Wrong row number");
    413 
    414   for (int i = 0; i < width; ++i) {
    415     for (int j = 0; j < height; ++j) {
    416       check(G.col(G(i, j)) == i, "Wrong column");
    417       check(G.row(G(i, j)) == j, "Wrong row");
    418       check(G.pos(G(i, j)).x == i, "Wrong column");
    419       check(G.pos(G(i, j)).y == j, "Wrong row");
    420     }
    421   }
    422 
    423   for (int j = 0; j < height; ++j) {
    424     for (int i = 0; i < width - 1; ++i) {
    425       check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");
    426       check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");
    427     }
    428     check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
    429   }
    430 
    431   for (int j = 0; j < height; ++j) {
    432     for (int i = 1; i < width; ++i) {
    433       check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");
    434       check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");
    435     }
    436     check(G.left(G(0, j)) == INVALID, "Wrong left");
    437   }
    438 
    439   for (int i = 0; i < width; ++i) {
    440     for (int j = 0; j < height - 1; ++j) {
    441       check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");
    442       check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");
    443     }
    444     check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
    445   }
    446 
    447   for (int i = 0; i < width; ++i) {
    448     for (int j = 1; j < height; ++j) {
    449       check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");
    450       check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");
    451     }
    452     check(G.down(G(i, 0)) == INVALID, "Wrong down");
    453   }
    454 
    455   checkGraphNodeList(G, width * height);
    456   checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
    457   checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
    458 
    459   for (NodeIt n(G); n != INVALID; ++n) {
    460     int nb = 4;
    461     if (G.col(n) == 0) --nb;
    462     if (G.col(n) == width - 1) --nb;
    463     if (G.row(n) == 0) --nb;
    464     if (G.row(n) == height - 1) --nb;
    465 
    466     checkGraphOutArcList(G, n, nb);
    467     checkGraphInArcList(G, n, nb);
    468     checkGraphIncEdgeList(G, n, nb);
    469   }
    470 
    471   checkArcDirections(G);
    472 
    473   checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
    474   checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
    475 
    476   checkNodeIds(G);
    477   checkArcIds(G);
    478   checkEdgeIds(G);
    479   checkGraphNodeMap(G);
    480   checkGraphArcMap(G);
    481   checkGraphEdgeMap(G);
    482 
    483 }
    484 
    485 void checkHypercubeGraph(int dim) {
    486   GRAPH_TYPEDEFS(HypercubeGraph);
    487 
    488   HypercubeGraph G(dim);
    489   checkGraphNodeList(G, 1 << dim);
    490   checkGraphEdgeList(G, dim * (1 << (dim-1)));
    491   checkGraphArcList(G, dim * (1 << dim));
    492 
    493   Node n = G.nodeFromId(dim);
    494 
    495   for (NodeIt n(G); n != INVALID; ++n) {
    496     checkGraphIncEdgeList(G, n, dim);
    497     for (IncEdgeIt e(G, n); e != INVALID; ++e) {
    498       check( (G.u(e) == n &&
    499               G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) ||
    500              (G.v(e) == n &&
    501               G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))),
    502              "Wrong edge or wrong dimension");
    503     }
    504 
    505     checkGraphOutArcList(G, n, dim);
    506     for (OutArcIt a(G, n); a != INVALID; ++a) {
    507       check(G.source(a) == n &&
    508             G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))),
    509             "Wrong arc or wrong dimension");
    510     }
    511 
    512     checkGraphInArcList(G, n, dim);
    513     for (InArcIt a(G, n); a != INVALID; ++a) {
    514       check(G.target(a) == n &&
    515             G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))),
    516             "Wrong arc or wrong dimension");
    517     }
    518   }
    519 
    520   checkGraphConArcList(G, (1 << dim) * dim);
    521   checkGraphConEdgeList(G, dim * (1 << (dim-1)));
    522 
    523   checkArcDirections(G);
    524 
    525   checkNodeIds(G);
    526   checkArcIds(G);
    527   checkEdgeIds(G);
    528   checkGraphNodeMap(G);
    529   checkGraphArcMap(G);
    530   checkGraphEdgeMap(G);
    531 }
     191// void checkGridGraph(const GridGraph& g, int w, int h) {
     192//   check(g.width() == w, "Wrong width");
     193//   check(g.height() == h, "Wrong height");
     194
     195//   for (int i = 0; i < w; ++i) {
     196//     for (int j = 0; j < h; ++j) {
     197//       check(g.col(g(i, j)) == i, "Wrong col");
     198//       check(g.row(g(i, j)) == j, "Wrong row");
     199//     }
     200//   }
     201
     202//   for (int i = 0; i < w; ++i) {
     203//     for (int j = 0; j < h - 1; ++j) {
     204//       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
     205//       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
     206//     }
     207//     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
     208//   }
     209
     210//   for (int i = 0; i < w; ++i) {
     211//     for (int j = 1; j < h; ++j) {
     212//       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
     213//       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
     214//     }
     215//     check(g.up(g(i, 0)) == INVALID, "Wrong up");
     216//   }
     217
     218//   for (int j = 0; j < h; ++j) {
     219//     for (int i = 0; i < w - 1; ++i) {
     220//       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
     221//       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
     222//     }
     223//     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
     224//   }
     225
     226//   for (int j = 0; j < h; ++j) {
     227//     for (int i = 1; i < w; ++i) {
     228//       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
     229//       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
     230//     }
     231//     check(g.left(g(0, j)) == INVALID, "Wrong left");
     232//   }
     233// }
    532234
    533235void checkGraphs() {
    534236  { // Checking ListGraph
    535     checkGraphBuild<ListGraph>();
    536     checkGraphAlter<ListGraph>();
    537     checkGraphErase<ListGraph>();
    538     checkGraphSnapshot<ListGraph>();
     237    checkGraph<ListGraph>();
    539238    checkGraphValidityErase<ListGraph>();
    540239  }
    541240  { // Checking SmartGraph
    542     checkGraphBuild<SmartGraph>();
    543     checkGraphSnapshot<SmartGraph>();
     241    checkGraph<SmartGraph>();
    544242    checkGraphValidity<SmartGraph>();
    545243  }
    546   { // Checking FullGraph
    547     checkFullGraph(7);
    548     checkFullGraph(8);
    549   }
    550   { // Checking GridGraph
    551     checkGridGraph(5, 8);
    552     checkGridGraph(8, 5);
    553     checkGridGraph(5, 5);
    554     checkGridGraph(0, 0);
    555     checkGridGraph(1, 1);
    556   }
    557   { // Checking HypercubeGraph
    558     checkHypercubeGraph(1);
    559     checkHypercubeGraph(2);
    560     checkHypercubeGraph(3);
    561     checkHypercubeGraph(4);
    562   }
     244//   { // Checking FullGraph
     245//     FullGraph g(5);
     246//     checkGraphNodeList(g, 5);
     247//     checkGraphEdgeList(g, 10);
     248//   }
     249//   { // Checking GridGraph
     250//     GridGraph g(5, 6);
     251//     checkGraphNodeList(g, 30);
     252//     checkGraphEdgeList(g, 49);
     253//     checkGridGraph(g, 5, 6);
     254//   }
    563255}
    564256

  • test/graph_test.h

    r463 r263  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    115115    check(e==INVALID,"Wrong IncEdge list linking.");
    116116    check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
    117   }
    118 
    119   template <class Graph>
    120   void checkGraphIncEdgeArcLists(const Graph &G, typename Graph::Node n,
    121                                  int cnt)
    122   {
    123     checkGraphIncEdgeList(G, n, cnt);
    124     checkGraphOutArcList(G, n, cnt);
    125     checkGraphInArcList(G, n, cnt);
    126117  }
    127118

  • test/graph_utils_test.cc

    r463 r220  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/heap_test.cc

    r463 r293  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/kruskal_test.cc

    r463 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/maps_test.cc

    r554 r210  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    171171    typedef ComposeMap<DoubleMap, ReadMap<B,A> > CompMap;
    172172    checkConcept<ReadMap<B,double>, CompMap>();
    173     CompMap map1 = CompMap(DoubleMap(),ReadMap<B,A>());
     173    CompMap map1(DoubleMap(),ReadMap<B,A>());
    174174    CompMap map2 = composeMap(DoubleMap(), ReadMap<B,A>());
    175175
    … …  
    184184    typedef CombineMap<DoubleMap, DoubleMap, std::plus<double> > CombMap;
    185185    checkConcept<ReadMap<A,double>, CombMap>();
    186     CombMap map1 = CombMap(DoubleMap(), DoubleMap());
     186    CombMap map1(DoubleMap(), DoubleMap());
    187187    CombMap map2 = combineMap(DoubleMap(), DoubleMap(), std::plus<double>());
    188188
    … …  
    196196    checkConcept<ReadMap<A,B>, FunctorToMap<F> >();
    197197    FunctorToMap<F> map1;
    198     FunctorToMap<F> map2 = FunctorToMap<F>(F());
     198    FunctorToMap<F> map2(F());
    199199    B b = functorToMap(F())[A()];
    200200
    201201    checkConcept<ReadMap<A,B>, MapToFunctor<ReadMap<A,B> > >();
    202     MapToFunctor<ReadMap<A,B> > map = MapToFunctor<ReadMap<A,B> >(ReadMap<A,B>());
     202    MapToFunctor<ReadMap<A,B> > map(ReadMap<A,B>());
    203203
    204204    check(functorToMap(&func)[A()] == 3,

  • test/path_test.cc

    r463 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/random_test.cc

    r463 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/test_tools.h

    r463 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/test_tools_fail.cc

    r463 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/test_tools_pass.cc

    r463 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/time_measure_test.cc

    r463 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/unionfind_test.cc

    r463 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • tools/Makefile.am

    r573 r310  
    11if WANT_TOOLS
    22
    3 bin_PROGRAMS += \
    4         tools/dimacs-solver \
    5         tools/dimacs-to-lgf \
    6         tools/lgf-gen
    7 
     3bin_PROGRAMS +=
    84dist_bin_SCRIPTS += tools/lemon-0.x-to-1.x.sh
    95
    106endif WANT_TOOLS
    11 
    12 tools_dimacs_solver_SOURCES = tools/dimacs-solver.cc
    13 tools_dimacs_to_lgf_SOURCES = tools/dimacs-to-lgf.cc
    14 tools_lgf_gen_SOURCES = tools/lgf-gen.cc

  • tools/lemon-0.x-to-1.x.sh

    r489 r310  
    44
    55if [ $# -eq 0 -o x$1 = "x-h" -o x$1 = "x-help" -o x$1 = "x--help" ]; then
    6     echo "Usage:"
    7     echo "  $0 source-file(s)"
    8     exit
     6        echo "Usage:"
     7        echo "  $0 source-file"
     8        exit
    99fi
    1010
    11 for i in $@
    12 do
    13     echo Update $i...
    14     TMP=`mktemp`
    15     sed -e "s/\<undirected graph\>/_gr_aph_label_/g"\
    16         -e "s/\<undirected graphs\>/_gr_aph_label_s/g"\
    17         -e "s/\<undirected edge\>/_ed_ge_label_/g"\
    18         -e "s/\<undirected edges\>/_ed_ge_label_s/g"\
    19         -e "s/\<directed graph\>/_digr_aph_label_/g"\
    20         -e "s/\<directed graphs\>/_digr_aph_label_s/g"\
    21         -e "s/\<directed edge\>/_ar_c_label_/g"\
    22         -e "s/\<directed edges\>/_ar_c_label_s/g"\
    23         -e "s/UGraph/_Gr_aph_label_/g"\
    24         -e "s/u[Gg]raph/_gr_aph_label_/g"\
    25         -e "s/\<Graph\>/_Digr_aph_label_/g"\
    26         -e "s/\<graph\>/_digr_aph_label_/g"\
    27         -e "s/\<Graphs\>/_Digr_aph_label_s/g"\
    28         -e "s/\<graphs\>/_digr_aph_label_s/g"\
    29         -e "s/_Graph/__Gr_aph_label_/g"\
    30         -e "s/\([Gg]\)raph\([a-z_]\)/_\1r_aph_label_\2/g"\
    31         -e "s/\([a-z_]\)graph/\1_gr_aph_label_/g"\
    32         -e "s/Graph/_Digr_aph_label_/g"\
    33         -e "s/graph/_digr_aph_label_/g"\
    34         -e "s/UEdge/_Ed_ge_label_/g"\
    35         -e "s/u[Ee]dge/_ed_ge_label_/g"\
    36         -e "s/IncEdgeIt/_In_cEd_geIt_label_/g"\
    37         -e "s/\<Edge\>/_Ar_c_label_/g"\
    38         -e "s/\<edge\>/_ar_c_label_/g"\
    39         -e "s/\<Edges\>/_Ar_c_label_s/g"\
    40         -e "s/\<edges\>/_ar_c_label_s/g"\
    41         -e "s/_Edge/__Ed_ge_label_/g"\
    42         -e "s/Edge\([a-z_]\)/_Ed_ge_label_\1/g"\
    43         -e "s/edge\([a-z_]\)/_ed_ge_label_\1/g"\
    44         -e "s/\([a-z_]\)edge/\1_ed_ge_label_/g"\
    45         -e "s/Edge/_Ar_c_label_/g"\
    46         -e "s/edge/_ar_c_label_/g"\
    47         -e "s/A[Nn]ode/_Re_d_label_/g"\
    48         -e "s/B[Nn]ode/_Blu_e_label_/g"\
    49         -e "s/A-[Nn]ode/_Re_d_label_/g"\
    50         -e "s/B-[Nn]ode/_Blu_e_label_/g"\
    51         -e "s/a[Nn]ode/_re_d_label_/g"\
    52         -e "s/b[Nn]ode/_blu_e_label_/g"\
    53         -e "s/\<UGRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__GR_APH_TY_PEDE_FS_label_\1/g"\
    54         -e "s/\<GRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__DIGR_APH_TY_PEDE_FS_label_\1/g"\
    55         -e "s/\<UGRAPH_TYPEDEFS\>/_GR_APH_TY_PEDE_FS_label_/g"\
    56         -e "s/\<GRAPH_TYPEDEFS\>/_DIGR_APH_TY_PEDE_FS_label_/g"\
    57         -e "s/_Digr_aph_label_/Digraph/g"\
    58         -e "s/_digr_aph_label_/digraph/g"\
    59         -e "s/_Gr_aph_label_/Graph/g"\
    60         -e "s/_gr_aph_label_/graph/g"\
    61         -e "s/_Ar_c_label_/Arc/g"\
    62         -e "s/_ar_c_label_/arc/g"\
    63         -e "s/_Ed_ge_label_/Edge/g"\
    64         -e "s/_ed_ge_label_/edge/g"\
    65         -e "s/_In_cEd_geIt_label_/IncEdgeIt/g"\
    66         -e "s/_Re_d_label_/Red/g"\
    67         -e "s/_Blu_e_label_/Blue/g"\
    68         -e "s/_re_d_label_/red/g"\
    69         -e "s/_blu_e_label_/blue/g"\
    70         -e "s/_GR_APH_TY_PEDE_FS_label_/GRAPH_TYPEDEFS/g"\
    71         -e "s/_DIGR_APH_TY_PEDE_FS_label_/DIGRAPH_TYPEDEFS/g"\
    72         -e "s/DigraphToEps/GraphToEps/g"\
    73         -e "s/digraphToEps/graphToEps/g"\
    74         -e "s/\<DefPredMap\>/SetPredMap/g"\
    75         -e "s/\<DefDistMap\>/SetDistMap/g"\
    76         -e "s/\<DefReachedMap\>/SetReachedMap/g"\
    77         -e "s/\<DefProcessedMap\>/SetProcessedMap/g"\
    78         -e "s/\<DefHeap\>/SetHeap/g"\
    79         -e "s/\<DefStandardHeap\>/SetStandradHeap/g"\
    80         -e "s/\<DefOperationTraits\>/SetOperationTraits/g"\
    81         -e "s/\<DefProcessedMapToBeDefaultMap\>/SetStandardProcessedMap/g"\
    82         -e "s/\<copyGraph\>/graphCopy/g"\
    83         -e "s/\<copyDigraph\>/digraphCopy/g"\
    84         -e "s/\<HyperCubeDigraph\>/HypercubeGraph/g"\
    85         -e "s/\<IntegerMap\>/RangeMap/g"\
    86         -e "s/\<integerMap\>/rangeMap/g"\
    87         -e "s/\<\([sS]\)tdMap\>/\1parseMap/g"\
    88         -e "s/\<\([Ff]\)unctorMap\>/\1unctorToMap/g"\
    89         -e "s/\<\([Mm]\)apFunctor\>/\1apToFunctor/g"\
    90         -e "s/\<\([Ff]\)orkWriteMap\>/\1orkMap/g"\
    91         -e "s/\<StoreBoolMap\>/LoggerBoolMap/g"\
    92         -e "s/\<storeBoolMap\>/loggerBoolMap/g"\
    93         -e "s/\<BoundingBox\>/Box/g"\
    94         -e "s/\<readNauty\>/readNautyGraph/g"\
    95         -e "s/\<RevDigraphAdaptor\>/ReverseDigraph/g"\
    96         -e "s/\<revDigraphAdaptor\>/reverseDigraph/g"\
    97         -e "s/\<SubDigraphAdaptor\>/SubDigraph/g"\
    98         -e "s/\<subDigraphAdaptor\>/subDigraph/g"\
    99         -e "s/\<SubGraphAdaptor\>/SubGraph/g"\
    100         -e "s/\<subGraphAdaptor\>/subGraph/g"\
    101         -e "s/\<NodeSubDigraphAdaptor\>/FilterNodes/g"\
    102         -e "s/\<nodeSubDigraphAdaptor\>/filterNodes/g"\
    103         -e "s/\<ArcSubDigraphAdaptor\>/FilterArcs/g"\
    104         -e "s/\<arcSubDigraphAdaptor\>/filterArcs/g"\
    105         -e "s/\<UndirDigraphAdaptor\>/Undirector/g"\
    106         -e "s/\<undirDigraphAdaptor\>/undirector/g"\
    107         -e "s/\<ResDigraphAdaptor\>/ResidualDigraph/g"\
    108         -e "s/\<resDigraphAdaptor\>/residualDigraph/g"\
    109         -e "s/\<SplitDigraphAdaptor\>/SplitNodes/g"\
    110         -e "s/\<splitDigraphAdaptor\>/splitNodes/g"\
    111         -e "s/\<SubGraphAdaptor\>/SubGraph/g"\
    112         -e "s/\<subGraphAdaptor\>/subGraph/g"\
    113         -e "s/\<NodeSubGraphAdaptor\>/FilterNodes/g"\
    114         -e "s/\<nodeSubGraphAdaptor\>/filterNodes/g"\
    115         -e "s/\<ArcSubGraphAdaptor\>/FilterEdges/g"\
    116         -e "s/\<arcSubGraphAdaptor\>/filterEdges/g"\
    117         -e "s/\<DirGraphAdaptor\>/Orienter/g"\
    118         -e "s/\<dirGraphAdaptor\>/orienter/g"\
    119     <$i > $TMP
    120     mv $TMP $i
    121 done
     11TMP=`mktemp`
     12
     13sed     -e "s/undirected graph/_gr_aph_label_/g"\
     14        -e "s/undirected edge/_ed_ge_label_/g"\
     15        -e "s/graph_/_gr_aph_label__/g"\
     16        -e "s/_graph/__gr_aph_label_/g"\
     17        -e "s/UGraph/_Gr_aph_label_/g"\
     18        -e "s/uGraph/_gr_aph_label_/g"\
     19        -e "s/ugraph/_gr_aph_label_/g"\
     20        -e "s/Graph/_Digr_aph_label_/g"\
     21        -e "s/graph/_digr_aph_label_/g"\
     22        -e "s/UEdge/_Ed_ge_label_/g"\
     23        -e "s/uEdge/_ed_ge_label_/g"\
     24        -e "s/uedge/_ed_ge_label_/g"\
     25        -e "s/IncEdgeIt/_In_cEd_geIt_label_/g"\
     26        -e "s/Edge/_Ar_c_label_/g"\
     27        -e "s/edge/_ar_c_label_/g"\
     28        -e "s/ANode/_Re_d_label_/g"\
     29        -e "s/BNode/_Blu_e_label_/g"\
     30        -e "s/A-Node/_Re_d_label_/g"\
     31        -e "s/B-Node/_Blu_e_label_/g"\
     32        -e "s/anode/_re_d_label_/g"\
     33        -e "s/bnode/_blu_e_label_/g"\
     34        -e "s/aNode/_re_d_label_/g"\
     35        -e "s/bNode/_blu_e_label_/g"\
     36        -e "s/_Digr_aph_label_/Digraph/g"\
     37        -e "s/_digr_aph_label_/digraph/g"\
     38        -e "s/_Gr_aph_label_/Graph/g"\
     39        -e "s/_gr_aph_label_/graph/g"\
     40        -e "s/_Ar_c_label_/Arc/g"\
     41        -e "s/_ar_c_label_/arc/g"\
     42        -e "s/_Ed_ge_label_/Edge/g"\
     43        -e "s/_ed_ge_label_/edge/g"\
     44        -e "s/_In_cEd_geIt_label_/IncEdgeIt/g"\
     45        -e "s/_Re_d_label_/Red/g"\
     46        -e "s/_Blu_e_label_/Blue/g"\
     47        -e "s/_re_d_label_/red/g"\
     48        -e "s/_blu_e_label_/blue/g"\
     49        -e "s/\(\W\)DefPredMap\(\W\)/\1SetPredMap\2/g"\
     50        -e "s/\(\W\)DefPredMap$/\1SetPredMap/g"\
     51        -e "s/^DefPredMap\(\W\)/SetPredMap\1/g"\
     52        -e "s/^DefPredMap$/SetPredMap/g"\
     53        -e "s/\(\W\)DefDistMap\(\W\)/\1SetDistMap\2/g"\
     54        -e "s/\(\W\)DefDistMap$/\1SetDistMap/g"\
     55        -e "s/^DefDistMap\(\W\)/SetDistMap\1/g"\
     56        -e "s/^DefDistMap$/SetDistMap/g"\
     57        -e "s/\(\W\)DefReachedMap\(\W\)/\1SetReachedMap\2/g"\
     58        -e "s/\(\W\)DefReachedMap$/\1SetReachedMap/g"\
     59        -e "s/^DefReachedMap\(\W\)/SetReachedMap\1/g"\
     60        -e "s/^DefReachedMap$/SetReachedMap/g"\
     61        -e "s/\(\W\)DefProcessedMap\(\W\)/\1SetProcessedMap\2/g"\
     62        -e "s/\(\W\)DefProcessedMap$/\1SetProcessedMap/g"\
     63        -e "s/^DefProcessedMap\(\W\)/SetProcessedMap\1/g"\
     64        -e "s/^DefProcessedMap$/SetProcessedMap/g"\
     65        -e "s/\(\W\)DefHeap\(\W\)/\1SetHeap\2/g"\
     66        -e "s/\(\W\)DefHeap$/\1SetHeap/g"\
     67        -e "s/^DefHeap\(\W\)/SetHeap\1/g"\
     68        -e "s/^DefHeap$/SetHeap/g"\
     69        -e "s/\(\W\)DefStandardHeap\(\W\)/\1SetStandradHeap\2/g"\
     70        -e "s/\(\W\)DefStandardHeap$/\1SetStandradHeap/g"\
     71        -e "s/^DefStandardHeap\(\W\)/SetStandradHeap\1/g"\
     72        -e "s/^DefStandardHeap$/SetStandradHeap/g"\
     73        -e "s/\(\W\)DefOperationTraits\(\W\)/\1SetOperationTraits\2/g"\
     74        -e "s/\(\W\)DefOperationTraits$/\1SetOperationTraits/g"\
     75        -e "s/^DefOperationTraits\(\W\)/SetOperationTraits\1/g"\
     76        -e "s/^DefOperationTraits$/SetOperationTraits/g"\
     77        -e "s/\(\W\)DefProcessedMapToBeDefaultMap\(\W\)/\1SetStandardProcessedMap\2/g"\
     78        -e "s/\(\W\)DefProcessedMapToBeDefaultMap$/\1SetStandardProcessedMap/g"\
     79        -e "s/^DefProcessedMapToBeDefaultMap\(\W\)/SetStandardProcessedMap\1/g"\
     80        -e "s/^DefProcessedMapToBeDefaultMap$/SetStandardProcessedMap/g"\
     81        -e "s/\(\W\)IntegerMap\(\W\)/\1RangeMap\2/g"\
     82        -e "s/\(\W\)IntegerMap$/\1RangeMap/g"\
     83        -e "s/^IntegerMap\(\W\)/RangeMap\1/g"\
     84        -e "s/^IntegerMap$/RangeMap/g"\
     85        -e "s/\(\W\)integerMap\(\W\)/\1rangeMap\2/g"\
     86        -e "s/\(\W\)integerMap$/\1rangeMap/g"\
     87        -e "s/^integerMap\(\W\)/rangeMap\1/g"\
     88        -e "s/^integerMap$/rangeMap/g"\
     89        -e "s/\(\W\)copyGraph\(\W\)/\1graphCopy\2/g"\
     90        -e "s/\(\W\)copyGraph$/\1graphCopy/g"\
     91        -e "s/^copyGraph\(\W\)/graphCopy\1/g"\
     92        -e "s/^copyGraph$/graphCopy/g"\
     93        -e "s/\(\W\)copyDigraph\(\W\)/\1digraphCopy\2/g"\
     94        -e "s/\(\W\)copyDigraph$/\1digraphCopy/g"\
     95        -e "s/^copyDigraph\(\W\)/digraphCopy\1/g"\
     96        -e "s/^copyDigraph$/digraphCopy/g"\
     97        -e "s/\(\W\)\([sS]\)tdMap\(\W\)/\1\2parseMap\3/g"\
     98        -e "s/\(\W\)\([sS]\)tdMap$/\1\2parseMap/g"\
     99        -e "s/^\([sS]\)tdMap\(\W\)/\1parseMap\2/g"\
     100        -e "s/^\([sS]\)tdMap$/\1parseMap/g"\
     101        -e "s/\(\W\)\([Ff]\)unctorMap\(\W\)/\1\2unctorToMap\3/g"\
     102        -e "s/\(\W\)\([Ff]\)unctorMap$/\1\2unctorToMap/g"\
     103        -e "s/^\([Ff]\)unctorMap\(\W\)/\1unctorToMap\2/g"\
     104        -e "s/^\([Ff]\)unctorMap$/\1unctorToMap/g"\
     105        -e "s/\(\W\)\([Mm]\)apFunctor\(\W\)/\1\2apToFunctor\3/g"\
     106        -e "s/\(\W\)\([Mm]\)apFunctor$/\1\2apToFunctor/g"\
     107        -e "s/^\([Mm]\)apFunctor\(\W\)/\1apToFunctor\2/g"\
     108        -e "s/^\([Mm]\)apFunctor$/\1apToFunctor/g"\
     109        -e "s/\(\W\)\([Ff]\)orkWriteMap\(\W\)/\1\2orkMap\3/g"\
     110        -e "s/\(\W\)\([Ff]\)orkWriteMap$/\1\2orkMap/g"\
     111        -e "s/^\([Ff]\)orkWriteMap\(\W\)/\1orkMap\2/g"\
     112        -e "s/^\([Ff]\)orkWriteMap$/\1orkMap/g"\
     113        -e "s/\(\W\)StoreBoolMap\(\W\)/\1LoggerBoolMap\2/g"\
     114        -e "s/\(\W\)StoreBoolMap$/\1LoggerBoolMap/g"\
     115        -e "s/^StoreBoolMap\(\W\)/LoggerBoolMap\1/g"\
     116        -e "s/^StoreBoolMap$/LoggerBoolMap/g"\
     117        -e "s/\(\W\)storeBoolMap\(\W\)/\1loggerBoolMap\2/g"\
     118        -e "s/\(\W\)storeBoolMap$/\1loggerBoolMap/g"\
     119        -e "s/^storeBoolMap\(\W\)/loggerBoolMap\1/g"\
     120        -e "s/^storeBoolMap$/loggerBoolMap/g"\
     121        -e "s/\(\W\)BoundingBox\(\W\)/\1Box\2/g"\
     122        -e "s/\(\W\)BoundingBox$/\1Box/g"\
     123        -e "s/^BoundingBox\(\W\)/Box\1/g"\
     124        -e "s/^BoundingBox$/Box/g"\
     125<$1 > $TMP
     126
     127mv $TMP $1
Note: See TracChangeset for help on using the changeset viewer.