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:
47 deleted
101 edited

Legend:

Unmodified
Added
Removed

  • .hgignore

    r495 r298  
    2727.deps/*
    2828demo/*.eps
    29 m4/libtool.m4
    30 m4/ltoptions.m4
    31 m4/ltsugar.m4
    32 m4/ltversion.m4
    33 m4/lt~obsolete.m4
    3429
    3530syntax: regexp
    … …  
    4035^autom4te.cache/.*
    4136^build-aux/.*
    42 ^.*objs.*/.*
     37^objs.*/.*
    4338^test/[a-z_]*$
    44 ^tools/[a-z-_]*$
    4539^demo/.*_demo$
    46 ^.*build.*/.*
     40^build/.*
    4741^doc/gen-images/.*
    4842CMakeFiles

  • CMakeLists.txt

    r496 r274  
    1010INCLUDE(FindDoxygen)
    1111INCLUDE(FindGhostscript)
    12 FIND_PACKAGE(GLPK 4.33)
    13 
    14 ADD_DEFINITIONS(-DHAVE_CONFIG_H)
    15 
    16 IF(GLPK_FOUND)
    17   SET(HAVE_LP TRUE)
    18   SET(HAVE_MIP TRUE)
    19   SET(HAVE_GLPK TRUE)
    20 ENDIF(GLPK_FOUND)
    2112
    2213ENABLE_TESTING()

  • 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

    r375 r321  
    11ACLOCAL_AMFLAGS = -I m4
    2 
    3 AM_CXXFLAGS = $(WARNINGCXXFLAGS)
    42
    53AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)

  • configure.ac

    r482 r310  
    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.
    … …  
    4547
    4648dnl Set custom compiler flags when using g++.
    47 if test "$GXX" = yes -a "$ICC" = no; then
    48   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"
     49if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes -a "$ICC" = no; then
     50  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"
    4951fi
    50 AC_SUBST([WARNINGCXXFLAGS])
    5152
    5253dnl Checks for libraries.
    53 LX_CHECK_GLPK
    54 LX_CHECK_CPLEX
    55 LX_CHECK_SOPLEX
    56 LX_CHECK_CLP
    57 
    58 AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
    59 AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
     54#LX_CHECK_GLPK
     55#LX_CHECK_CPLEX
     56#LX_CHECK_SOPLEX
    6057
    6158dnl Disable/enable building the demo programs.
    … …  
    117114echo
    118115echo C++ compiler.................. : $CXX
    119 echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
     116echo C++ compiles flags............ : $CXXFLAGS
    120117echo
    121 echo GLPK support.................. : $lx_glpk_found
    122 echo CPLEX support................. : $lx_cplex_found
    123 echo SOPLEX support................ : $lx_soplex_found
    124 echo CLP support................... : $lx_clp_found
    125 echo
     118#echo GLPK support.................. : $lx_glpk_found
     119#echo CPLEX support................. : $lx_cplex_found
     120#echo SOPLEX support................ : $lx_soplex_found
     121#echo
    126122echo Build demo programs........... : $enable_demo
    127123echo 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

    r553 r497  
    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

    r498 r225  
    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)
    18 
    19 IF(HAVE_GLPK)
    20   SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc)
    21   INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR})
    22   IF(WIN32)
    23     INSTALL(FILES ${GLPK_BIN_DIR}/glpk.dll DESTINATION bin)
    24     INSTALL(FILES ${GLPK_BIN_DIR}/libltdl3.dll DESTINATION bin)
    25     INSTALL(FILES ${GLPK_BIN_DIR}/zlib1.dll DESTINATION bin)
    26   ENDIF(WIN32)
    27 ENDIF(HAVE_GLPK)
    28 
    29 ADD_LIBRARY(lemon ${LEMON_SOURCES})
    308
    319INSTALL(

  • lemon/Makefile.am

    r492 r259  
    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 \
    15         lemon/random.cc
     10        lemon/arg_parser.cc \
     11        lemon/base.cc \
     12        lemon/color.cc \
     13        lemon/random.cc
    1614
    17 
    18 lemon_libemon_la_CXXFLAGS = \
    19         $(GLPK_CFLAGS) \
    20         $(CPLEX_CFLAGS) \
    21         $(SOPLEX_CXXFLAGS) \
    22         $(CLP_CXXFLAGS)
    23 
    24 lemon_libemon_la_LDFLAGS = \
    25         $(GLPK_LIBS) \
    26         $(CPLEX_LIBS) \
    27         $(SOPLEX_LIBS) \
    28         $(CLP_LIBS)
    29 
    30 if HAVE_GLPK
    31 lemon_libemon_la_SOURCES += lemon/glpk.cc
    32 endif
    33 
    34 if HAVE_CPLEX
    35 lemon_libemon_la_SOURCES += lemon/cplex.cc
    36 endif
    37 
    38 if HAVE_SOPLEX
    39 lemon_libemon_la_SOURCES += lemon/soplex.cc
    40 endif
    41 
    42 if HAVE_CLP
    43 lemon_libemon_la_SOURCES += lemon/clp.cc
    44 endif
     15#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
     16#lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
    4517
    4618lemon_HEADERS += \
    47         lemon/adaptors.h \
    48         lemon/arg_parser.h \
     19        lemon/arg_parser.h \
    4920        lemon/assert.h \
    50         lemon/bfs.h \
    51         lemon/bin_heap.h \
    52         lemon/circulation.h \
    53         lemon/clp.h \
    54         lemon/color.h \
     21        lemon/bfs.h \
     22        lemon/bin_heap.h \
     23        lemon/color.h \
    5524        lemon/concept_check.h \
    56         lemon/counter.h \
     25        lemon/counter.h \
    5726        lemon/core.h \
    58         lemon/cplex.h \
    59         lemon/dfs.h \
    60         lemon/dijkstra.h \
    61         lemon/dim2.h \
    62         lemon/dimacs.h \
    63         lemon/edge_set.h \
    64         lemon/elevator.h \
     27        lemon/dfs.h \
     28        lemon/dijkstra.h \
     29        lemon/dim2.h \
    6530        lemon/error.h \
    66         lemon/full_graph.h \
    67         lemon/glpk.h \
    68         lemon/graph_to_eps.h \
    69         lemon/grid_graph.h \
    70         lemon/hypercube_graph.h \
     31        lemon/graph_to_eps.h \
    7132        lemon/kruskal.h \
    72         lemon/hao_orlin.h \
    7333        lemon/lgf_reader.h \
    7434        lemon/lgf_writer.h \
    7535        lemon/list_graph.h \
    76         lemon/lp.h \
    77         lemon/lp_base.h \
    78         lemon/lp_skeleton.h \
    79         lemon/list_graph.h \
    8036        lemon/maps.h \
    8137        lemon/math.h \
    82         lemon/max_matching.h \
    83         lemon/nauty_reader.h \
    8438        lemon/path.h \
    85         lemon/preflow.h \
    86         lemon/radix_sort.h \
    87         lemon/random.h \
     39        lemon/random.h \
    8840        lemon/smart_graph.h \
    89         lemon/soplex.h \
    90         lemon/suurballe.h \
    91         lemon/time_measure.h \
    92         lemon/tolerance.h \
     41        lemon/time_measure.h \
     42        lemon/tolerance.h \
    9343        lemon/unionfind.h
    9444
    … …  
    9747        lemon/bits/array_map.h \
    9848        lemon/bits/base_extender.h \
    99         lemon/bits/bezier.h \
     49        lemon/bits/bezier.h \
    10050        lemon/bits/default_map.h \
    101         lemon/bits/edge_set_extender.h \
    102         lemon/bits/enable_if.h \
    103         lemon/bits/graph_adaptor_extender.h \
     51        lemon/bits/enable_if.h \
    10452        lemon/bits/graph_extender.h \
    10553        lemon/bits/map_extender.h \
    10654        lemon/bits/path_dump.h \
    107         lemon/bits/solver_bits.h \
    10855        lemon/bits/traits.h \
    109         lemon/bits/variant.h \
    11056        lemon/bits/vector_map.h
    11157

  • 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

    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/bfs.h

    r463 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).
    … …  
    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    ///@{
    … …  
    226232    ///\ref named-templ-param "Named parameter" for setting
    227233    ///PredMap type.
    228     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    229234    template <class T>
    230235    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
    … …  
    246251    ///\ref named-templ-param "Named parameter" for setting
    247252    ///DistMap type.
    248     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    249253    template <class T>
    250254    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
    … …  
    266270    ///\ref named-templ-param "Named parameter" for setting
    267271    ///ReachedMap type.
    268     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    269272    template <class T>
    270273    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
    … …  
    286289    ///\ref named-templ-param "Named parameter" for setting
    287290    ///ProcessedMap type.
    288     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    289291    template <class T>
    290292    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
    … …  
    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
    … …  
    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

    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).
    … …  
    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.
    … …  
    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

    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/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

    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/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

    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).
    … …  
    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.
    … …  
    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/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

    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).

  • lemon/concepts/graph.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).

  • lemon/concepts/graph_components.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/concepts/heap.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/concepts/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/concepts/path.h

    r463 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).

  • lemon/config.h.in

    r482 r1  
    1 /* Define to 1 if you have any LP solver. */
    2 #undef HAVE_LP
    3 
    4 /* Define to 1 if you have any MIP solver. */
    5 #undef HAVE_MIP
    6 
    71/* Define to 1 if you have CPLEX. */
    82#undef HAVE_CPLEX
    … …  
    104/* Define to 1 if you have GLPK. */
    115#undef HAVE_GLPK
    12 
    13 /* Define to 1 if you have SOPLEX */
    14 #undef HAVE_SOPLEX
    15 
    16 /* Define to 1 if you have CLP */
    17 #undef HAVE_CLP

  • lemon/core.h

    r463 r449  
    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

    r463 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).
    … …  
    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
    … …  
    225231    ///\ref named-templ-param "Named parameter" for setting
    226232    ///PredMap type.
    227     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    228233    template <class T>
    229234    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
    … …  
    245250    ///\ref named-templ-param "Named parameter" for setting
    246251    ///DistMap type.
    247     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    248252    template <class T>
    249253    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
    … …  
    265269    ///\ref named-templ-param "Named parameter" for setting
    266270    ///ReachedMap type.
    267     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    268271    template <class T>
    269272    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
    … …  
    285288    ///\ref named-templ-param "Named parameter" for setting
    286289    ///ProcessedMap type.
    287     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    288290    template <class T>
    289291    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
    … …  
    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
    … …  
    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

    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).
    … …  
    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>
    … …  
    220227    typedef typename TR::OperationTraits OperationTraits;
    221228
    222     ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
     229    ///The traits class.
    223230    typedef TR Traits;
    224231
    … …  
    302309    ///\ref named-templ-param "Named parameter" for setting
    303310    ///PredMap type.
    304     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    305311    template <class T>
    306312    struct SetPredMap
    … …  
    323329    ///\ref named-templ-param "Named parameter" for setting
    324330    ///DistMap type.
    325     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    326331    template <class T>
    327332    struct SetDistMap
    … …  
    344349    ///\ref named-templ-param "Named parameter" for setting
    345350    ///ProcessedMap type.
    346     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    347351    template <class T>
    348352    struct SetProcessedMap
    … …  
    385389    };
    386390    ///\brief \ref named-templ-param "Named parameter" for setting
    387     ///heap and cross reference types
     391    ///heap and cross reference type
    388392    ///
    389393    ///\ref named-templ-param "Named parameter" for setting heap and cross
    390     ///reference types. If this named parameter is used, then external
    391     ///heap and cross reference objects must be passed to the algorithm
    392     ///using the \ref heap() function before calling \ref run(Node) "run()"
    393     ///or \ref init().
    394     ///\sa SetStandardHeap
     394    ///reference type.
    395395    template <class H, class CR = typename Digraph::template NodeMap<int> >
    396396    struct SetHeap
    … …  
    412412    };
    413413    ///\brief \ref named-templ-param "Named parameter" for setting
    414     ///heap and cross reference types with automatic allocation
     414    ///heap and cross reference type with automatic allocation
    415415    ///
    416416    ///\ref named-templ-param "Named parameter" for setting heap and cross
    417     ///reference types with automatic allocation.
    418     ///They should have standard constructor interfaces to be able to
    419     ///automatically created by the algorithm (i.e. the digraph should be
    420     ///passed to the constructor of the cross reference and the cross
    421     ///reference should be passed to the constructor of the heap).
    422     ///However external heap and cross reference objects could also be
    423     ///passed to the algorithm using the \ref heap() function before
    424     ///calling \ref run(Node) "run()" or \ref init().
    425     ///\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.
    426420    template <class H, class CR = typename Digraph::template NodeMap<int> >
    427421    struct SetStandardHeap
    … …  
    493487
    494488    ///Sets the map that stores the predecessor arcs.
    495     ///If you don't use this function before calling \ref run(Node) "run()"
    496     ///or \ref init(), an instance will be allocated automatically.
    497     ///The destructor deallocates this automatically allocated map,
    498     ///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.
    499492    ///\return <tt> (*this) </tt>
    500493    Dijkstra &predMap(PredMap &m)
    … …  
    511504
    512505    ///Sets the map that indicates which nodes are processed.
    513     ///If you don't use this function before calling \ref run(Node) "run()"
    514     ///or \ref init(), an instance will be allocated automatically.
    515     ///The destructor deallocates this automatically allocated map,
    516     ///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.
    517509    ///\return <tt> (*this) </tt>
    518510    Dijkstra &processedMap(ProcessedMap &m)
    … …  
    530522    ///Sets the map that stores the distances of the nodes calculated by the
    531523    ///algorithm.
    532     ///If you don't use this function before calling \ref run(Node) "run()"
    533     ///or \ref init(), an instance will be allocated automatically.
    534     ///The destructor deallocates this automatically allocated map,
    535     ///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.
    536527    ///\return <tt> (*this) </tt>
    537528    Dijkstra &distMap(DistMap &m)
    … …  
    548539
    549540    ///Sets the heap and the cross reference used by algorithm.
    550     ///If you don't use this function before calling \ref run(Node) "run()"
    551     ///or \ref init(), heap and cross reference instances will be
    552     ///allocated automatically.
    553     ///The destructor deallocates these automatically allocated objects,
    554     ///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.
    555544    ///\return <tt> (*this) </tt>
    556545    Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
    … …  
    579568  public:
    580569
    581     ///\name Execution Control
    582     ///The simplest way to execute the %Dijkstra algorithm is to use
    583     ///one of the member functions called \ref run(Node) "run()".\n
    584     ///If you need more control on the execution, first you have to call
    585     ///\ref init(), then you can add several source nodes with
    586     ///\ref addSource(). Finally the actual path computation can be
    587     ///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.
    588579
    589580    ///@{
    590581
    591     ///\brief Initializes the internal data structures.
    592     ///
    593582    ///Initializes the internal data structures.
     583
     584    ///Initializes the internal data structures.
     585    ///
    594586    void init()
    595587    {
    … …  
    667659    }
    668660
    669     ///Returns \c false if there are nodes to be processed.
    670 
    671     ///Returns \c false if there are nodes to be processed
    672     ///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.
    673666    bool emptyQueue() const { return _heap->empty(); }
    674667
    675     ///Returns the number of the nodes to be processed.
    676 
    677     ///Returns the number of the nodes to be processed
    678     ///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    ///
    679672    int queueSize() const { return _heap->size(); }
    680673
    … …  
    797790
    798791    ///\name Query Functions
    799     ///The results of the %Dijkstra algorithm can be obtained using these
     792    ///The result of the %Dijkstra algorithm can be obtained using these
    800793    ///functions.\n
    801     ///Either \ref run(Node) "run()" or \ref start() should be called
    802     ///before using them.
     794    ///Either \ref lemon::Dijkstra::run() "run()" or
     795    ///\ref lemon::Dijkstra::start() "start()" must be called before
     796    ///using them.
    803797
    804798    ///@{
    … …  
    808802    ///Returns the shortest path to a node.
    809803    ///
    810     ///\warning \c t should be reached from the root(s).
    811     ///
    812     ///\pre Either \ref run(Node) "run()" or \ref init()
    813     ///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.
    814808    Path path(Node t) const { return Path(*G, *_pred, t); }
    815809
    … …  
    818812    ///Returns the distance of a node from the root(s).
    819813    ///
    820     ///\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
    821815    ///the return value of this function is undefined.
    822816    ///
    823     ///\pre Either \ref run(Node) "run()" or \ref init()
    824     ///must be called before using this function.
     817    ///\pre Either \ref run() or \ref start() must be called before
     818    ///using this function.
    825819    Value dist(Node v) const { return (*_dist)[v]; }
    826820
    … …  
    829823    ///This function returns the 'previous arc' of the shortest path
    830824    ///tree for the node \c v, i.e. it returns the last arc of a
    831     ///shortest path from a root to \c v. It is \c INVALID if \c v
    832     ///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.
    833827    ///
    834828    ///The shortest path tree used here is equal to the shortest path
    835829    ///tree used in \ref predNode().
    836830    ///
    837     ///\pre Either \ref run(Node) "run()" or \ref init()
    838     ///must be called before using this function.
     831    ///\pre Either \ref run() or \ref start() must be called before
     832    ///using this function.
    839833    Arc predArc(Node v) const { return (*_pred)[v]; }
    840834
    … …  
    843837    ///This function returns the 'previous node' of the shortest path
    844838    ///tree for the node \c v, i.e. it returns the last but one node
    845     ///from a shortest path from a root to \c v. It is \c INVALID
    846     ///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.
    847841    ///
    848842    ///The shortest path tree used here is equal to the shortest path
    849843    ///tree used in \ref predArc().
    850844    ///
    851     ///\pre Either \ref run(Node) "run()" or \ref init()
    852     ///must be called before using this function.
     845    ///\pre Either \ref run() or \ref start() must be called before
     846    ///using this function.
    853847    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    854848                                  G->source((*_pred)[v]); }
    … …  
    860854    ///of the nodes calculated by the algorithm.
    861855    ///
    862     ///\pre Either \ref run(Node) "run()" or \ref init()
     856    ///\pre Either \ref run() or \ref init()
    863857    ///must be called before using this function.
    864858    const DistMap &distMap() const { return *_dist;}
    … …  
    870864    ///arcs, which form the shortest path tree.
    871865    ///
    872     ///\pre Either \ref run(Node) "run()" or \ref init()
     866    ///\pre Either \ref run() or \ref init()
    873867    ///must be called before using this function.
    874868    const PredMap &predMap() const { return *_pred;}
    875869
    876     ///Checks if a node is reached from the root(s).
    877 
    878     ///Returns \c true if \c v is reached from the root(s).
    879     ///
    880     ///\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()
    881874    ///must be called before using this function.
    882875    bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
    … …  
    887880    ///Returns \c true if \c v is processed, i.e. the shortest
    888881    ///path to \c v has already found.
    889     ///
    890     ///\pre Either \ref run(Node) "run()" or \ref init()
     882    ///\pre Either \ref run() or \ref init()
    891883    ///must be called before using this function.
    892884    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
    … …  
    897889    ///Returns the current distance of a node from the root(s).
    898890    ///It may be decreased in the following processes.
    899     ///
    900     ///\pre Either \ref run(Node) "run()" or \ref init()
     891    ///\pre Either \ref run() or \ref init()
    901892    ///must be called before using this function and
    902893    ///node \c v must be reached but not necessarily processed.
    … …  
    10811072  /// This auxiliary class is created to implement the
    10821073  /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
    1083   /// It does not have own \ref run(Node) "run()" method, it uses the
    1084   /// 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.
    10851076  ///
    10861077  /// This class should only be used through the \ref dijkstra() function,
    … …  
    12771268  ///  bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
    12781269  ///\endcode
    1279   ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()"
     1270  ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
    12801271  ///to the end of the parameter list.
    12811272  ///\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

    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/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

    r463 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).
    … …  
    871871        readLine();
    872872      }
    873       if (readSuccess()) {
    874         line.putback(c);
    875       }
     873      line.putback(c);
    876874    }
    877875
    … …  
    17021700        readLine();
    17031701      }
    1704       if (readSuccess()) {
    1705         line.putback(c);
    1706       }
     1702      line.putback(c);
    17071703    }
    17081704
    … …  
    22312227        readLine();
    22322228      }
    2233       if (readSuccess()) {
    2234         line.putback(c);
    2235       }
     2229      line.putback(c);
    22362230    }
    22372231
    … …  
    25742568        readLine();
    25752569      }
    2576       if (readSuccess()) {
    2577         line.putback(c);
    2578       }
     2570      line.putback(c);
    25792571    }
    25802572

  • lemon/lgf_writer.h

    r463 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).

  • 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

    r493 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

    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/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

    r463 r391  
    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).
    … …  
    541541    /// @{
    542542
     543    ///\name Initialization
     544    ///
     545    /// @{
     546
    543547    /// \brief Default constructor
    544548    ///
    … …  
    689693    }
    690694
     695    /// @}
     696
     697    ///\name Uniform distributions
     698    ///
     699    /// @{
     700
    691701    /// \brief Returns a random real number from the range [0, 1)
    692702    ///
    … …  
    743753      return _random_bits::IntConversion<Number, Word>::convert(core);
    744754    }
     755
     756    /// @}
    745757
    746758    unsigned int uinteger() {
    … …  
    777789    ///\name Non-uniform distributions
    778790    ///
     791
    779792    ///@{
    780793
    781     /// \brief Returns a random bool with given probability of true result.
     794    /// \brief Returns a random bool
    782795    ///
    783796    /// It returns a random bool with given probability of true result.
    … …  
    786799    }
    787800
    788     /// Standard normal (Gauss) distribution
    789 
    790     /// Standard normal (Gauss) distribution.
     801    /// Standard Gauss distribution
     802
     803    /// Standard Gauss distribution.
    791804    /// \note The Cartesian form of the Box-Muller
    792805    /// transformation is used to generate a random normal distribution.
    … …  
    801814      return std::sqrt(-2*std::log(S)/S)*V1;
    802815    }
    803     /// Normal (Gauss) distribution with given mean and standard deviation
    804 
    805     /// Normal (Gauss) distribution with given mean and standard deviation.
     816    /// Gauss distribution with given mean and standard deviation
     817
     818    /// Gauss distribution with given mean and standard deviation.
    806819    /// \sa gauss()
    807820    double gauss(double mean,double std_dev)
    808821    {
    809822      return gauss()*std_dev+mean;
    810     }
    811 
    812     /// Lognormal distribution
    813 
    814     /// Lognormal distribution. The parameters are the mean and the standard
    815     /// deviation of <tt>exp(X)</tt>.
    816     ///
    817     double lognormal(double n_mean,double n_std_dev)
    818     {
    819       return std::exp(gauss(n_mean,n_std_dev));
    820     }
    821     /// Lognormal distribution
    822 
    823     /// Lognormal distribution. The parameter is an <tt>std::pair</tt> of
    824     /// the mean and the standard deviation of <tt>exp(X)</tt>.
    825     ///
    826     double lognormal(const std::pair<double,double> &params)
    827     {
    828       return std::exp(gauss(params.first,params.second));
    829     }
    830     /// Compute the lognormal parameters from mean and standard deviation
    831 
    832     /// This function computes the lognormal parameters from mean and
    833     /// standard deviation. The return value can direcly be passed to
    834     /// lognormal().
    835     std::pair<double,double> lognormalParamsFromMD(double mean,
    836                                                    double std_dev)
    837     {
    838       double fr=std_dev/mean;
    839       fr*=fr;
    840       double lg=std::log(1+fr);
    841       return std::pair<double,double>(std::log(mean)-lg/2.0,std::sqrt(lg));
    842     }
    843     /// Lognormal distribution with given mean and standard deviation
    844 
    845     /// Lognormal distribution with given mean and standard deviation.
    846     ///
    847     double lognormalMD(double mean,double std_dev)
    848     {
    849       return lognormal(lognormalParamsFromMD(mean,std_dev));
    850823    }
    851824
    … …  
    953926    ///\name Two dimensional distributions
    954927    ///
     928
    955929    ///@{
    956930
    … …  
    969943      return dim2::Point<double>(V1,V2);
    970944    }
    971     /// A kind of two dimensional normal (Gauss) distribution
     945    /// A kind of two dimensional Gauss distribution
    972946
    973947    /// 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

    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/tolerance.h

    r463 r280  
    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

    r498 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
    2313  graph_copy_test
    2414  graph_test
    2515  graph_utils_test
    26   hao_orlin_test
    2716  heap_test
    2817  kruskal_test
    2918  maps_test
    30   max_matching_test
     19  random_test
    3120  path_test
    32   preflow_test
    33   radix_sort_test
    34   random_test
    35   suurballe_test
    3621  time_measure_test
    3722  unionfind_test)
    38 
    39 IF(HAVE_LP)
    40   ADD_EXECUTABLE(lp_test lp_test.cc)
    41   IF(HAVE_GLPK)
    42     TARGET_LINK_LIBRARIES(lp_test lemon ${GLPK_LIBRARIES})
    43   ENDIF(HAVE_GLPK)
    44   ADD_TEST(lp_test lp_test)
    45 
    46   IF(WIN32 AND HAVE_GLPK)
    47     GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION)
    48     GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
    49     ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD
    50       COMMAND cmake -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}
    51       COMMAND cmake -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}
    52       COMMAND cmake -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}
    53     )
    54   ENDIF(WIN32 AND HAVE_GLPK)
    55 ENDIF(HAVE_LP)
    56 
    57 IF(HAVE_MIP)
    58   ADD_EXECUTABLE(mip_test mip_test.cc)
    59   IF(HAVE_GLPK)
    60     TARGET_LINK_LIBRARIES(mip_test lemon ${GLPK_LIBRARIES})
    61   ENDIF(HAVE_GLPK)
    62   ADD_TEST(mip_test mip_test)
    63 
    64   IF(WIN32 AND HAVE_GLPK)
    65     GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION)
    66     GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
    67     ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD
    68       COMMAND cmake -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}
    69       COMMAND cmake -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}
    70       COMMAND cmake -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}
    71     )
    72   ENDIF(WIN32 AND HAVE_GLPK)
    73 ENDIF(HAVE_MIP)
    7423
    7524FOREACH(TEST_NAME ${TESTS})

  • test/Makefile.am

    r492 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 \
    1916        test/graph_copy_test \
    2017        test/graph_test \
    2118        test/graph_utils_test \
    22         test/hao_orlin_test \
    2319        test/heap_test \
    2420        test/kruskal_test \
    25         test/maps_test \
    26         test/max_matching_test \
    27         test/path_test \
    28         test/preflow_test \
    29         test/radix_sort_test \
    30         test/random_test \
    31         test/suurballe_test \
    32         test/test_tools_fail \
    33         test/test_tools_pass \
    34         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 \
    3527        test/unionfind_test
    36 
    37 if HAVE_LP
    38 check_PROGRAMS += test/lp_test
    39 endif HAVE_LP
    40 if HAVE_MIP
    41 check_PROGRAMS += test/mip_test
    42 endif HAVE_MIP
    4328
    4429TESTS += $(check_PROGRAMS)
    4530XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
    4631
    47 test_adaptors_test_SOURCES = test/adaptors_test.cc
    4832test_bfs_test_SOURCES = test/bfs_test.cc
    49 test_circulation_test_SOURCES = test/circulation_test.cc
    5033test_counter_test_SOURCES = test/counter_test.cc
    5134test_dfs_test_SOURCES = test/dfs_test.cc
    … …  
    5336test_dijkstra_test_SOURCES = test/dijkstra_test.cc
    5437test_dim_test_SOURCES = test/dim_test.cc
    55 test_edge_set_test_SOURCES = test/edge_set_test.cc
    5638test_error_test_SOURCES = test/error_test.cc
    5739test_graph_copy_test_SOURCES = test/graph_copy_test.cc
    … …  
    6042test_heap_test_SOURCES = test/heap_test.cc
    6143test_kruskal_test_SOURCES = test/kruskal_test.cc
    62 test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
    63 test_lp_test_SOURCES = test/lp_test.cc
    6444test_maps_test_SOURCES = test/maps_test.cc
    65 test_mip_test_SOURCES = test/mip_test.cc
    66 test_max_matching_test_SOURCES = test/max_matching_test.cc
    6745test_path_test_SOURCES = test/path_test.cc
    68 test_preflow_test_SOURCES = test/preflow_test.cc
    69 test_radix_sort_test_SOURCES = test/radix_sort_test.cc
    70 test_suurballe_test_SOURCES = test/suurballe_test.cc
    7146test_random_test_SOURCES = test/random_test.cc
    7247test_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

    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).

  • 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

    r400 r310  
    11if WANT_TOOLS
    22
    3 bin_PROGRAMS += \
    4         tools/dimacs-to-lgf
    5 
     3bin_PROGRAMS +=
    64dist_bin_SCRIPTS += tools/lemon-0.x-to-1.x.sh
    75
    86endif WANT_TOOLS
    9 
    10 tools_dimacs_to_lgf_SOURCES = tools/dimacs-to-lgf.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.