COIN-OR::LEMON - Graph Library

Ignore:
Files:
23 deleted
94 edited

Legend:

Unmodified
Added
Removed
  • .hgignore

    r400 r298  
    3737^objs.*/.*
    3838^test/[a-z_]*$
    39 ^tools/[a-z-_]*$
    4039^demo/.*_demo$
    4140^build/.*
  • 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

    r375 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.
     
    113114echo
    114115echo C++ compiler.................. : $CXX
    115 echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
     116echo C++ compiles flags............ : $CXXFLAGS
    116117echo
    117118#echo GLPK support.................. : $lx_glpk_found
  • 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

    r347 r225  
    1414      COMMAND rm -rf gen-images
    1515      COMMAND mkdir gen-images
    16       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
    1716      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
    1817      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

    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).
     
    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 This group contains several adaptor classes for digraphs and graphs
    68 
    69 The main parts of LEMON are the different graph structures, generic
    70 graph algorithms, graph concepts which couple these, and graph
    71 adaptors. While the previous notions are more or less clear, the
    72 latter one needs further explanation. Graph adaptors are graph classes
    73 which serve for considering graph structures in different ways.
    74 
    75 A short example makes this much clearer.  Suppose that we have an
    76 instance \c g of a directed graph type say ListDigraph and an algorithm
    77 \code
    78 template <typename Digraph>
    79 int algorithm(const Digraph&);
    80 \endcode
    81 is needed to run on the reverse oriented graph.  It may be expensive
    82 (in time or in memory usage) to copy \c g with the reversed
    83 arcs.  In this case, an adaptor class is used, which (according
    84 to LEMON digraph concepts) works as a digraph.  The adaptor uses the
    85 original digraph structure and digraph operations when methods of the
    86 reversed oriented graph are called.  This means that the adaptor have
    87 minor memory usage, and do not perform sophisticated algorithmic
    88 actions.  The purpose of it is to give a tool for the cases when a
    89 graph have to be used in a specific alteration.  If this alteration is
    90 obtained by a usual construction like filtering the arc-set or
    91 considering a new orientation, then an adaptor is worthwhile to use.
    92 To come back to the reverse oriented graph, in this situation
    93 \code
    94 template<typename Digraph> class ReverseDigraph;
    95 \endcode
    96 template class can be used. The code looks as follows
    97 \code
    98 ListDigraph g;
    99 ReverseDigraph<ListGraph> rg(g);
    100 int result = algorithm(rg);
    101 \endcode
    102 After running the algorithm, the original graph \c g is untouched.
    103 This techniques gives rise to an elegant code, and based on stable
    104 graph adaptors, complex algorithms can be implemented easily.
    105 
    106 In flow, circulation and bipartite matching problems, the residual
    107 graph is of particular importance. Combining an adaptor implementing
    108 this, shortest path algorithms and minimum mean cycle algorithms,
    109 a range of weighted and cardinality optimization algorithms can be
    110 obtained. For other examples, the interested user is referred to the
    111 detailed documentation of particular adaptors.
    112 
    113 The behavior of graph adaptors can be very different. Some of them keep
    114 capabilities of the original graph while in other cases this would be
    115 meaningless. This means that the concepts that they are models of depend
    116 on the graph adaptor, and the wrapped graph(s).
    117 If an arc of \c rg is deleted, this is carried out by deleting the
    118 corresponding arc of \c g, thus the adaptor modifies the original graph.
    119 
    120 But for a residual graph, this operation has no sense.
    121 Let us stand one more example here to simplify your work.
    122 RevGraphAdaptor has constructor
    123 \code
    124 ReverseDigraph(Digraph& digraph);
    125 \endcode
    126 This means that in a situation, when a <tt>const ListDigraph&</tt>
    127 reference to a graph is given, then it have to be instantiated with
    128 <tt>Digraph=const ListDigraph</tt>.
    129 \code
    130 int algorithm1(const ListDigraph& g) {
    131   RevGraphAdaptor<const ListDigraph> rg(g);
    132   return algorithm2(rg);
    133 }
    134 \endcode
    135 */
    136 
    137 /**
    13863@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
    13964@ingroup graphs
     
    16489
    16590This group describes maps that are specifically designed to assign
    166 values to the nodes and arcs/edges of graphs.
    167 
    168 If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
    169 \c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
     91values to the nodes and arcs of graphs.
    17092*/
    17193
     
    178100maps from other maps.
    179101
    180 Most of them are \ref concepts::ReadMap "read-only maps".
     102Most of them are \ref lemon::concepts::ReadMap "read-only maps".
    181103They can make arithmetic and logical operations between one or two maps
    182104(negation, shifting, addition, multiplication, logical 'and', 'or',
     
    280202\brief Common graph search algorithms.
    281203
    282 This group describes the common graph search algorithms, namely
    283 \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).
    284206*/
    285207
     
    289211\brief Algorithms for finding shortest paths.
    290212
    291 This group describes the algorithms for finding shortest paths in digraphs.
    292 
    293  - \ref Dijkstra algorithm for finding shortest paths from a source node
    294    when all arc lengths are non-negative.
    295  - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
    296    from a source node when arc lenghts can be either positive or negative,
    297    but the digraph should not contain directed cycles with negative total
    298    length.
    299  - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
    300    for solving the \e all-pairs \e shortest \e paths \e problem when arc
    301    lenghts can be either positive or negative, but the digraph should
    302    not contain directed cycles with negative total length.
    303  - \ref Suurballe A successive shortest path algorithm for finding
    304    arc-disjoint paths between two nodes having minimum total length.
     213This group describes the algorithms for finding shortest paths in graphs.
    305214*/
    306215
     
    313222feasible circulations.
    314223
    315 The \e maximum \e flow \e problem is to find a flow of maximum value between
    316 a single source and a single target. Formally, there is a \f$G=(V,A)\f$
    317 digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
    318 \f$s, t \in V\f$ source and target nodes.
    319 A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
    320 following optimization problem.
    321 
    322 \f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
    323 \f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
    324     \qquad \forall v\in V\setminus\{s,t\} \f]
    325 \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]
    326234
    327235LEMON contains several algorithms for solving maximum flow problems:
    328 - \ref EdmondsKarp Edmonds-Karp algorithm.
    329 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
    330 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
    331 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
    332 
    333 In most cases the \ref Preflow "Preflow" algorithm provides the
    334 fastest method for computing a maximum flow. All implementations
    335 provides functions to also query the minimum cut, which is the dual
    336 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.
    337245*/
    338246
     
    345253This group describes the algorithms for finding minimum cost flows and
    346254circulations.
    347 
    348 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
    349 minimum total cost from a set of supply nodes to a set of demand nodes
    350 in a network with capacity constraints and arc costs.
    351 Formally, let \f$G=(V,A)\f$ be a digraph,
    352 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
    353 upper bounds for the flow values on the arcs,
    354 \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
    355 on the arcs, and
    356 \f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
    357 of the nodes.
    358 A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
    359 the following optimization problem.
    360 
    361 \f[ \min\sum_{a\in A} f(a) cost(a) \f]
    362 \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
    363     supply(v) \qquad \forall v\in V \f]
    364 \f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
    365 
    366 LEMON contains several algorithms for solving minimum cost flow problems:
    367  - \ref CycleCanceling Cycle-canceling algorithms.
    368  - \ref CapacityScaling Successive shortest path algorithm with optional
    369    capacity scaling.
    370  - \ref CostScaling Push-relabel and augment-relabel algorithms based on
    371    cost scaling.
    372  - \ref NetworkSimplex Primal network simplex algorithm with various
    373    pivot strategies.
    374255*/
    375256
     
    382263This group describes the algorithms for finding minimum cut in graphs.
    383264
    384 The \e minimum \e cut \e problem is to find a non-empty and non-complete
    385 \f$X\f$ subset of the nodes with minimum overall capacity on
    386 outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
    387 \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
    388269cut is the \f$X\f$ solution of the next optimization problem:
    389270
    390271\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    391     \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]
    392273
    393274LEMON contains several algorithms related to minimum cut problems:
    394275
    395 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
    396   in directed graphs.
    397 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
    398   calculating minimum cut in undirected graphs.
    399 - \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
    400   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
    401282
    402283If you want to find minimum cut just between two distinict nodes,
    403 see the \ref max_flow "maximum flow problem".
     284please see the \ref max_flow "Maximum Flow page".
    404285*/
    405286
     
    440321graphs.  The matching problems in bipartite graphs are generally
    441322easier than in general graphs. The goal of the matching optimization
    442 can be finding maximum cardinality, maximum weight or minimum cost
     323can be the finding maximum cardinality, maximum weight or minimum cost
    443324matching. The search can be constrained to find perfect or
    444325maximum cardinality matching.
    445326
    446 The matching algorithms implemented in LEMON:
    447 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
    448   for calculating maximum cardinality matching in bipartite graphs.
    449 - \ref PrBipartiteMatching Push-relabel algorithm
    450   for calculating maximum cardinality matching in bipartite graphs.
    451 - \ref MaxWeightedBipartiteMatching
    452   Successive shortest path algorithm for calculating maximum weighted
    453   matching and maximum weighted bipartite matching in bipartite graphs.
    454 - \ref MinCostMaxBipartiteMatching
    455   Successive shortest path algorithm for calculating minimum cost maximum
    456   matching in bipartite graphs.
    457 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    458   maximum cardinality matching in general graphs.
    459 - \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
    460   maximum weighted matching in general graphs.
    461 - \ref MaxWeightedPerfectMatching
    462   Edmond's blossom shrinking algorithm for calculating maximum weighted
    463   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
    464347
    465348\image html bipartite_matching.png
     
    473356
    474357This group describes the algorithms for finding a minimum cost spanning
    475 tree in a graph.
     358tree in a graph
    476359*/
    477360
     
    582465
    583466/**
    584 @defgroup lemon_io LEMON Graph Format
     467@defgroup lemon_io LEMON Input-Output
    585468@ingroup io_group
    586469\brief Reading and writing LEMON Graph Format.
     
    597480This group describes general \c EPS drawing methods and special
    598481graph exporting tools.
    599 */
    600 
    601 /**
    602 @defgroup dimacs_group DIMACS format
    603 @ingroup io_group
    604 \brief Read and write files in DIMACS format
    605 
    606 Tools to read a digraph from or write it to a file in DIMACS format data.
    607 */
    608 
    609 /**
    610 @defgroup nauty_group NAUTY Format
    611 @ingroup io_group
    612 \brief Read \e Nauty format
    613 
    614 Tool to read graphs from \e Nauty format data.
    615482*/
    616483
     
    664531\anchor demoprograms
    665532
    666 @defgroup demos Demo Programs
     533@defgroup demos Demo programs
    667534
    668535Some demo programs are listed here. Their full source codes can be found in
     
    674541
    675542/**
    676 @defgroup tools Standalone Utility Applications
     543@defgroup tools Standalone utility applications
    677544
    678545Some utility applications are listed here.
     
    682549*/
    683550
    684 }
  • 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/Makefile.am

    r468 r464  
    88
    99lemon_libemon_la_SOURCES = \
    10         lemon/arg_parser.cc \
    11         lemon/base.cc \
    12         lemon/color.cc \
    13         lemon/random.cc
     10        lemon/arg_parser.cc \
     11        lemon/base.cc \
     12        lemon/color.cc \
     13        lemon/random.cc
    1414
    15 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) $(AM_CXXFLAGS)
     15#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
    1616#lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
    1717
    1818lemon_HEADERS += \
    19         lemon/adaptors.h \
    20         lemon/arg_parser.h \
     19        lemon/arg_parser.h \
    2120        lemon/assert.h \
    22         lemon/bfs.h \
    23         lemon/bin_heap.h \
    24         lemon/circulation.h \
    25         lemon/color.h \
     21        lemon/bfs.h \
     22        lemon/bin_heap.h \
     23        lemon/color.h \
    2624        lemon/concept_check.h \
    27         lemon/counter.h \
     25        lemon/counter.h \
    2826        lemon/core.h \
    29         lemon/dfs.h \
    30         lemon/dijkstra.h \
    31         lemon/dim2.h \
    32         lemon/dimacs.h \
    33         lemon/elevator.h \
     27        lemon/dfs.h \
     28        lemon/dijkstra.h \
     29        lemon/dim2.h \
    3430        lemon/error.h \
    35         lemon/full_graph.h \
    36         lemon/graph_to_eps.h \
    37         lemon/grid_graph.h \
    38         lemon/hypercube_graph.h \
     31        lemon/graph_to_eps.h \
    3932        lemon/kruskal.h \
    40         lemon/hao_orlin.h \
    4133        lemon/lgf_reader.h \
    4234        lemon/lgf_writer.h \
     
    4436        lemon/maps.h \
    4537        lemon/math.h \
    46         lemon/max_matching.h \
    47         lemon/nauty_reader.h \
    4838        lemon/path.h \
    49         lemon/preflow.h \
    5039        lemon/radix_sort.h \
    51         lemon/random.h \
     40        lemon/random.h \
    5241        lemon/smart_graph.h \
    53         lemon/suurballe.h \
    54         lemon/time_measure.h \
    55         lemon/tolerance.h \
     42        lemon/time_measure.h \
     43        lemon/tolerance.h \
    5644        lemon/unionfind.h
    5745
     
    6048        lemon/bits/array_map.h \
    6149        lemon/bits/base_extender.h \
    62         lemon/bits/bezier.h \
     50        lemon/bits/bezier.h \
    6351        lemon/bits/default_map.h \
    64         lemon/bits/enable_if.h \
    65         lemon/bits/graph_adaptor_extender.h \
     52        lemon/bits/enable_if.h \
    6653        lemon/bits/graph_extender.h \
    6754        lemon/bits/map_extender.h \
    6855        lemon/bits/path_dump.h \
    6956        lemon/bits/traits.h \
    70         lemon/bits/variant.h \
    7157        lemon/bits/vector_map.h
    7258
  • 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/core.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).
     
    11711171    /// Construct a new ConEdgeIt iterating on the edges that
    11721172    /// connects nodes \c u and \c v.
    1173     ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
    1174       Parent::operator=(findEdge(_graph, _u, _v));
     1173    ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
     1174      Parent::operator=(findEdge(_graph, u, v));
    11751175    }
    11761176
     
    11841184    /// It increments the iterator and gives back the next edge.
    11851185    ConEdgeIt& operator++() {
    1186       Parent::operator=(findEdge(_graph, _u, _v, *this));
     1186      Parent::operator=(findEdge(_graph, _graph.u(*this),
     1187                                 _graph.v(*this), *this));
    11871188      return *this;
    11881189    }
    11891190  private:
    11901191    const Graph& _graph;
    1191     Node _u, _v;
    11921192  };
    11931193
  • 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 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).
     
    4848    static Value plus(const Value& left, const Value& right) {
    4949      return left + right;
     50    }
     51    /// \brief Gives back true only if the first value is less than the second.
     52    static bool less(const Value& left, const Value& right) {
     53      return left < right;
     54    }
     55  };
     56
     57  /// \brief Widest path operation traits for the Dijkstra algorithm class.
     58  ///
     59  /// This operation traits class defines all computational operations and
     60  /// constants which are used in the Dijkstra algorithm for widest path
     61  /// computation.
     62  ///
     63  /// \see DijkstraDefaultOperationTraits
     64  template <typename Value>
     65  struct DijkstraWidestPathOperationTraits {
     66    /// \brief Gives back the maximum value of the type.
     67    static Value zero() {
     68      return std::numeric_limits<Value>::max();
     69    }
     70    /// \brief Gives back the minimum of the given two elements.
     71    static Value plus(const Value& left, const Value& right) {
     72      return std::min(left, right);
    5073    }
    5174    /// \brief Gives back true only if the first value is less than the second.
     
    180203  ///
    181204  ///\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
     205  ///The default value is \ref ListDigraph.
     206  ///The value of GR is not used directly by \ref Dijkstra, it is only
     207  ///passed to \ref DijkstraDefaultTraits.
     208  ///\tparam LM A readable arc map that determines the lengths of the
     209  ///arcs. It is read once for each arc, so the map may involve in
    186210  ///relatively time consuming process to compute the arc lengths if
    187211  ///it is necessary. The default map type is \ref
    188   ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
     212  ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
     213  ///The value of LM is not used directly by \ref Dijkstra, it is only
     214  ///passed to \ref DijkstraDefaultTraits.
     215  ///\tparam TR Traits class to set various data types used by the algorithm.
     216  ///The default traits class is \ref DijkstraDefaultTraits
     217  ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
     218  ///for the documentation of a Dijkstra traits class.
    189219#ifdef DOXYGEN
    190220  template <typename GR, typename LM, typename TR>
     
    220250    typedef typename TR::OperationTraits OperationTraits;
    221251
    222     ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
     252    ///The traits class.
    223253    typedef TR Traits;
    224254
     
    302332    ///\ref named-templ-param "Named parameter" for setting
    303333    ///PredMap type.
    304     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    305334    template <class T>
    306335    struct SetPredMap
     
    323352    ///\ref named-templ-param "Named parameter" for setting
    324353    ///DistMap type.
    325     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    326354    template <class T>
    327355    struct SetDistMap
     
    344372    ///\ref named-templ-param "Named parameter" for setting
    345373    ///ProcessedMap type.
    346     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    347374    template <class T>
    348375    struct SetProcessedMap
     
    385412    };
    386413    ///\brief \ref named-templ-param "Named parameter" for setting
    387     ///heap and cross reference types
     414    ///heap and cross reference type
    388415    ///
    389416    ///\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
     417    ///reference type.
    395418    template <class H, class CR = typename Digraph::template NodeMap<int> >
    396419    struct SetHeap
     
    412435    };
    413436    ///\brief \ref named-templ-param "Named parameter" for setting
    414     ///heap and cross reference types with automatic allocation
     437    ///heap and cross reference type with automatic allocation
    415438    ///
    416439    ///\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
     440    ///reference type. It can allocate the heap and the cross reference
     441    ///object if the cross reference's constructor waits for the digraph as
     442    ///parameter and the heap's constructor waits for the cross reference.
    426443    template <class H, class CR = typename Digraph::template NodeMap<int> >
    427444    struct SetStandardHeap
     
    493510
    494511    ///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.
     512    ///If you don't use this function before calling \ref run(),
     513    ///it will allocate one. The destructor deallocates this
     514    ///automatically allocated map, of course.
    499515    ///\return <tt> (*this) </tt>
    500516    Dijkstra &predMap(PredMap &m)
     
    511527
    512528    ///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.
     529    ///If you don't use this function before calling \ref run(),
     530    ///it will allocate one. The destructor deallocates this
     531    ///automatically allocated map, of course.
    517532    ///\return <tt> (*this) </tt>
    518533    Dijkstra &processedMap(ProcessedMap &m)
     
    530545    ///Sets the map that stores the distances of the nodes calculated by the
    531546    ///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.
     547    ///If you don't use this function before calling \ref run(),
     548    ///it will allocate one. The destructor deallocates this
     549    ///automatically allocated map, of course.
    536550    ///\return <tt> (*this) </tt>
    537551    Dijkstra &distMap(DistMap &m)
     
    548562
    549563    ///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.
     564    ///If you don't use this function before calling \ref run(),
     565    ///it will allocate one. The destructor deallocates this
     566    ///automatically allocated heap and cross reference, of course.
    555567    ///\return <tt> (*this) </tt>
    556568    Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
     
    579591  public:
    580592
    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.
     593    ///\name Execution control
     594    ///The simplest way to execute the algorithm is to use one of the
     595    ///member functions called \ref lemon::Dijkstra::run() "run()".
     596    ///\n
     597    ///If you need more control on the execution, first you must call
     598    ///\ref lemon::Dijkstra::init() "init()", then you can add several
     599    ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
     600    ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
     601    ///actual path computation.
    588602
    589603    ///@{
    590604
    591     ///\brief Initializes the internal data structures.
    592     ///
    593605    ///Initializes the internal data structures.
     606
     607    ///Initializes the internal data structures.
     608    ///
    594609    void init()
    595610    {
     
    667682    }
    668683
    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.
     684    ///\brief Returns \c false if there are nodes
     685    ///to be processed.
     686    ///
     687    ///Returns \c false if there are nodes
     688    ///to be processed in the priority heap.
    673689    bool emptyQueue() const { return _heap->empty(); }
    674690
    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.
     691    ///Returns the number of the nodes to be processed in the priority heap
     692
     693    ///Returns the number of the nodes to be processed in the priority heap.
     694    ///
    679695    int queueSize() const { return _heap->size(); }
    680696
     
    797813
    798814    ///\name Query Functions
    799     ///The results of the %Dijkstra algorithm can be obtained using these
     815    ///The result of the %Dijkstra algorithm can be obtained using these
    800816    ///functions.\n
    801     ///Either \ref run(Node) "run()" or \ref start() should be called
    802     ///before using them.
     817    ///Either \ref lemon::Dijkstra::run() "run()" or
     818    ///\ref lemon::Dijkstra::start() "start()" must be called before
     819    ///using them.
    803820
    804821    ///@{
     
    808825    ///Returns the shortest path to a node.
    809826    ///
    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.
     827    ///\warning \c t should be reachable from the root(s).
     828    ///
     829    ///\pre Either \ref run() or \ref start() must be called before
     830    ///using this function.
    814831    Path path(Node t) const { return Path(*G, *_pred, t); }
    815832
     
    818835    ///Returns the distance of a node from the root(s).
    819836    ///
    820     ///\warning If node \c v is not reached from the root(s), then
     837    ///\warning If node \c v is not reachable from the root(s), then
    821838    ///the return value of this function is undefined.
    822839    ///
    823     ///\pre Either \ref run(Node) "run()" or \ref init()
    824     ///must be called before using this function.
     840    ///\pre Either \ref run() or \ref start() must be called before
     841    ///using this function.
    825842    Value dist(Node v) const { return (*_dist)[v]; }
    826843
     
    829846    ///This function returns the 'previous arc' of the shortest path
    830847    ///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.
     848    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
     849    ///is not reachable from the root(s) or if \c v is a root.
    833850    ///
    834851    ///The shortest path tree used here is equal to the shortest path
    835852    ///tree used in \ref predNode().
    836853    ///
    837     ///\pre Either \ref run(Node) "run()" or \ref init()
    838     ///must be called before using this function.
     854    ///\pre Either \ref run() or \ref start() must be called before
     855    ///using this function.
    839856    Arc predArc(Node v) const { return (*_pred)[v]; }
    840857
     
    843860    ///This function returns the 'previous node' of the shortest path
    844861    ///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.
     862    ///from a shortest path from the root(s) to \c v. It is \c INVALID
     863    ///if \c v is not reachable from the root(s) or if \c v is a root.
    847864    ///
    848865    ///The shortest path tree used here is equal to the shortest path
    849866    ///tree used in \ref predArc().
    850867    ///
    851     ///\pre Either \ref run(Node) "run()" or \ref init()
    852     ///must be called before using this function.
     868    ///\pre Either \ref run() or \ref start() must be called before
     869    ///using this function.
    853870    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    854871                                  G->source((*_pred)[v]); }
     
    860877    ///of the nodes calculated by the algorithm.
    861878    ///
    862     ///\pre Either \ref run(Node) "run()" or \ref init()
     879    ///\pre Either \ref run() or \ref init()
    863880    ///must be called before using this function.
    864881    const DistMap &distMap() const { return *_dist;}
     
    870887    ///arcs, which form the shortest path tree.
    871888    ///
    872     ///\pre Either \ref run(Node) "run()" or \ref init()
     889    ///\pre Either \ref run() or \ref init()
    873890    ///must be called before using this function.
    874891    const PredMap &predMap() const { return *_pred;}
    875892
    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()
     893    ///Checks if a node is reachable from the root(s).
     894
     895    ///Returns \c true if \c v is reachable from the root(s).
     896    ///\pre Either \ref run() or \ref start()
    881897    ///must be called before using this function.
    882898    bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
     
    887903    ///Returns \c true if \c v is processed, i.e. the shortest
    888904    ///path to \c v has already found.
    889     ///
    890     ///\pre Either \ref run(Node) "run()" or \ref init()
     905    ///\pre Either \ref run() or \ref init()
    891906    ///must be called before using this function.
    892907    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
     
    897912    ///Returns the current distance of a node from the root(s).
    898913    ///It may be decreased in the following processes.
    899     ///
    900     ///\pre Either \ref run(Node) "run()" or \ref init()
     914    ///\pre Either \ref run() or \ref init()
    901915    ///must be called before using this function and
    902916    ///node \c v must be reached but not necessarily processed.
     
    10811095  /// This auxiliary class is created to implement the
    10821096  /// \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.
     1097  /// It does not have own \ref run() method, it uses the functions
     1098  /// and features of the plain \ref Dijkstra.
    10851099  ///
    10861100  /// This class should only be used through the \ref dijkstra() function,
     
    12771291  ///  bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
    12781292  ///\endcode
    1279   ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()"
     1293  ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
    12801294  ///to the end of the parameter list.
    12811295  ///\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

    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/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 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).
     
    541541    /// @{
    542542
     543    ///\name Initialization
     544    ///
     545    /// @{
     546
    543547    /// \brief Default constructor
    544548    ///
     
    689693    }
    690694
     695    /// \brief Returns a random real number the range [0, b)
     696    ///
     697    /// It returns a random real number from the range [0, b).
     698    template <typename Number>
     699    Number real(Number b) {
     700      return real<Number>() * b;
     701    }
     702
     703    /// \brief Returns a random real number from the range [a, b)
     704    ///
     705    /// It returns a random real number from the range [a, b).
     706    template <typename Number>
     707    Number real(Number a, Number b) {
     708      return real<Number>() * (b - a) + a;
     709    }
     710
     711    /// @}
     712
     713    ///\name Uniform distributions
     714    ///
     715    /// @{
     716
    691717    /// \brief Returns a random real number from the range [0, 1)
    692718    ///
     
    699725    ///
    700726    /// It returns a random real number from the range [0, b).
    701     double operator()(double b) {
    702       return real<double>() * b;
     727    template <typename Number>
     728    Number operator()(Number b) {
     729      return real<Number>() * b;
    703730    }
    704731
     
    706733    ///
    707734    /// It returns a random real number from the range [a, b).
    708     double operator()(double a, double b) {
    709       return real<double>() * (b - a) + a;
     735    template <typename Number>
     736    Number operator()(Number a, Number b) {
     737      return real<Number>() * (b - a) + a;
    710738    }
    711739
     
    743771      return _random_bits::IntConversion<Number, Word>::convert(core);
    744772    }
     773
     774    /// @}
    745775
    746776    unsigned int uinteger() {
     
    777807    ///\name Non-uniform distributions
    778808    ///
     809
    779810    ///@{
    780811
    781     /// \brief Returns a random bool with given probability of true result.
     812    /// \brief Returns a random bool
    782813    ///
    783814    /// It returns a random bool with given probability of true result.
     
    786817    }
    787818
    788     /// Standard normal (Gauss) distribution
    789 
    790     /// Standard normal (Gauss) distribution.
     819    /// Standard Gauss distribution
     820
     821    /// Standard Gauss distribution.
    791822    /// \note The Cartesian form of the Box-Muller
    792823    /// transformation is used to generate a random normal distribution.
     
    801832      return std::sqrt(-2*std::log(S)/S)*V1;
    802833    }
    803     /// Normal (Gauss) distribution with given mean and standard deviation
    804 
    805     /// Normal (Gauss) distribution with given mean and standard deviation.
     834    /// Gauss distribution with given mean and standard deviation
     835
     836    /// Gauss distribution with given mean and standard deviation.
    806837    /// \sa gauss()
    807838    double gauss(double mean,double std_dev)
    808839    {
    809840      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));
    850841    }
    851842
     
    953944    ///\name Two dimensional distributions
    954945    ///
     946
    955947    ///@{
    956948
     
    969961      return dim2::Point<double>(V1,V2);
    970962    }
    971     /// A kind of two dimensional normal (Gauss) distribution
     963    /// A kind of two dimensional Gauss distribution
    972964
    973965    /// 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 r236  
    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).
     
    11781178            if (nodes[nodes[jd].next].size < cmax) {
    11791179              pushLeft(nodes[jd].next, nodes[jd].left);
    1180               if (less(jd, nodes[jd].next) ||
    1181                   nodes[jd].item == nodes[pd].item) {
    1182                 nodes[nodes[jd].next].prio = nodes[jd].prio;
    1183                 nodes[nodes[jd].next].item = nodes[jd].item;
     1180              if (less(nodes[jd].left, nodes[jd].next)) {
     1181                nodes[nodes[jd].next].prio = nodes[nodes[jd].left].prio;
     1182                nodes[nodes[jd].next].item = nodes[nodes[jd].left].item;
    11841183              }
    11851184              popLeft(pd);
     
    11901189              popLeft(nodes[jd].next);
    11911190              pushRight(jd, ld);
    1192               if (less(ld, nodes[jd].left) ||
    1193                   nodes[ld].item == nodes[pd].item) {
     1191              if (less(ld, nodes[jd].left)) {
    11941192                nodes[jd].item = nodes[ld].item;
    1195                 nodes[jd].prio = nodes[ld].prio;
     1193                nodes[jd].prio = nodes[jd].prio;
    11961194              }
    11971195              if (nodes[nodes[jd].next].item == nodes[ld].item) {
     
    12221220            if (nodes[nodes[jd].prev].size < cmax) {
    12231221              pushRight(nodes[jd].prev, nodes[jd].right);
    1224               if (less(jd, nodes[jd].prev) ||
    1225                   nodes[jd].item == nodes[pd].item) {
    1226                 nodes[nodes[jd].prev].prio = nodes[jd].prio;
    1227                 nodes[nodes[jd].prev].item = nodes[jd].item;
     1222              if (less(nodes[jd].right, nodes[jd].prev)) {
     1223                nodes[nodes[jd].prev].prio = nodes[nodes[jd].right].prio;
     1224                nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item;
    12281225              }
    12291226              popRight(pd);
     
    12341231              popRight(nodes[jd].prev);
    12351232              pushLeft(jd, ld);
    1236               if (less(ld, nodes[jd].right) ||
    1237                   nodes[ld].item == nodes[pd].item) {
     1233              if (less(ld, nodes[jd].right)) {
    12381234                nodes[jd].item = nodes[ld].item;
    1239                 nodes[jd].prio = nodes[ld].prio;
     1235                nodes[jd].prio = nodes[jd].prio;
    12401236              }
    12411237              if (nodes[nodes[jd].prev].item == nodes[ld].item) {
     
    12551251      return comp(nodes[id].prio, nodes[jd].prio);
    12561252    }
     1253
     1254    bool equal(int id, int jd) const {
     1255      return !less(id, jd) && !less(jd, id);
     1256    }
     1257
    12571258
    12581259  public:
     
    14001401              push(new_id, right_id);
    14011402              pushRight(new_id, ~(classes[r].parent));
    1402 
    1403               if (less(~classes[r].parent, right_id)) {
    1404                 nodes[new_id].item = nodes[~classes[r].parent].item;
    1405                 nodes[new_id].prio = nodes[~classes[r].parent].prio;
    1406               } else {
    1407                 nodes[new_id].item = nodes[right_id].item;
    1408                 nodes[new_id].prio = nodes[right_id].prio;
    1409               }
     1403              setPrio(new_id);
    14101404
    14111405              id = nodes[id].parent;
     
    14471441              push(new_id, left_id);
    14481442              pushLeft(new_id, ~(classes[l].parent));
    1449 
    1450               if (less(~classes[l].parent, left_id)) {
    1451                 nodes[new_id].item = nodes[~classes[l].parent].item;
    1452                 nodes[new_id].prio = nodes[~classes[l].parent].prio;
    1453               } else {
    1454                 nodes[new_id].item = nodes[left_id].item;
    1455                 nodes[new_id].prio = nodes[left_id].prio;
    1456               }
     1443              setPrio(new_id);
    14571444
    14581445              id = nodes[id].parent;
  • 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

    r468 r464  
    55SET(TESTS
    66  bfs_test
    7   circulation_test
    87  counter_test
    98  dfs_test
     
    1211  dim_test
    1312  error_test
    14   graph_adaptor_test
    1513  graph_copy_test
    1614  graph_test
    1715  graph_utils_test
    18   hao_orlin_test
    1916  heap_test
    2017  kruskal_test
    2118  maps_test
    22   max_matching_test
    2319  radix_sort_test
     20  random_test
    2421  path_test
    25   preflow_test
    26   random_test
    27   suurballe_test
    2822  time_measure_test
    2923  unionfind_test)
  • test/Makefile.am

    r468 r464  
    44noinst_HEADERS += \
    55        test/graph_test.h \
    6         test/test_tools.h
     6        test/test_tools.h
    77
    88check_PROGRAMS += \
    99        test/bfs_test \
    10         test/circulation_test \
    11         test/counter_test \
     10        test/counter_test \
    1211        test/dfs_test \
    1312        test/digraph_test \
    1413        test/dijkstra_test \
    15         test/dim_test \
     14        test/dim_test \
    1615        test/error_test \
    17         test/graph_adaptor_test \
    1816        test/graph_copy_test \
    1917        test/graph_test \
    2018        test/graph_utils_test \
    21         test/hao_orlin_test \
    2219        test/heap_test \
    2320        test/kruskal_test \
    24         test/maps_test \
    25         test/max_matching_test \
    26         test/path_test \
    27         test/preflow_test \
     21        test/maps_test \
    2822        test/radix_sort_test \
    29         test/random_test \
    30         test/suurballe_test \
    31         test/test_tools_fail \
    32         test/test_tools_pass \
    33         test/time_measure_test \
     23        test/random_test \
     24        test/path_test \
     25        test/test_tools_fail \
     26        test/test_tools_pass \
     27        test/time_measure_test \
    3428        test/unionfind_test
    3529
     
    3832
    3933test_bfs_test_SOURCES = test/bfs_test.cc
    40 test_circulation_test_SOURCES = test/circulation_test.cc
    4134test_counter_test_SOURCES = test/counter_test.cc
    4235test_dfs_test_SOURCES = test/dfs_test.cc
     
    4538test_dim_test_SOURCES = test/dim_test.cc
    4639test_error_test_SOURCES = test/error_test.cc
    47 test_graph_adaptor_test_SOURCES = test/graph_adaptor_test.cc
    4840test_graph_copy_test_SOURCES = test/graph_copy_test.cc
    4941test_graph_test_SOURCES = test/graph_test.cc
     
    5143test_heap_test_SOURCES = test/heap_test.cc
    5244test_kruskal_test_SOURCES = test/kruskal_test.cc
    53 test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
    5445test_maps_test_SOURCES = test/maps_test.cc
    55 test_max_matching_test_SOURCES = test/max_matching_test.cc
    5646test_path_test_SOURCES = test/path_test.cc
    57 test_preflow_test_SOURCES = test/preflow_test.cc
    5847test_radix_sort_test_SOURCES = test/radix_sort_test.cc
    59 test_suurballe_test_SOURCES = test/suurballe_test.cc
    6048test_random_test_SOURCES = test/random_test.cc
    6149test_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 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).
     
    9090      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
    9191      ::SetStandardProcessedMap
    92       ::SetOperationTraits<DijkstraDefaultOperationTraits<VType> >
     92      ::SetOperationTraits<DijkstraWidestPathOperationTraits<VType> >
    9393      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
    9494      ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
  • 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

    r378 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     <$i > $TMP
    96     mv $TMP $i
    97 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.