COIN-OR::LEMON - Graph Library

Ignore:
Files:
23 added
30 edited

Legend:

Unmodified
Added
Removed
  • .hgignore

    r298 r400  
    3737^objs.*/.*
    3838^test/[a-z_]*$
     39^tools/[a-z-_]*$
    3940^demo/.*_demo$
    4041^build/.*
  • Makefile.am

    r321 r375  
    11ACLOCAL_AMFLAGS = -I m4
     2
     3AM_CXXFLAGS = $(WARNINGCXXFLAGS)
    24
    35AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)
  • configure.ac

    r310 r375  
    1919AC_CONFIG_SRCDIR([lemon/list_graph.h])
    2020AC_CONFIG_HEADERS([config.h lemon/config.h])
    21 
    22 lx_cmdline_cxxflags_set=${CXXFLAGS+set}
    2321
    2422dnl Do compilation tests using the C++ compiler.
     
    4745
    4846dnl Set custom compiler flags when using g++.
    49 if 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"
     47if 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"
    5149fi
     50AC_SUBST([WARNINGCXXFLAGS])
    5251
    5352dnl Checks for libraries.
     
    114113echo
    115114echo C++ compiler.................. : $CXX
    116 echo C++ compiles flags............ : $CXXFLAGS
     115echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
    117116echo
    118117#echo GLPK support.................. : $lx_glpk_found
  • doc/CMakeLists.txt

    r225 r347  
    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
    1617      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
    1718      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

    r316 r379  
    6767ENABLED_SECTIONS       =
    6868MAX_INITIALIZER_LINES  = 5
    69 SHOW_USED_FILES        = YES
     69SHOW_USED_FILES        = NO
    7070SHOW_DIRECTORIES       = YES
    7171SHOW_FILES             = YES
  • doc/Makefile.am

    r317 r349  
    1515
    1616DOC_EPS_IMAGES18 = \
     17        grid_graph.eps \
    1718        nodeshape_0.eps \
    1819        nodeshape_1.eps \
  • doc/groups.dox

    r318 r434  
    1717 */
    1818
     19namespace lemon {
     20
    1921/**
    2022@defgroup datas Data Structures
     
    6163
    6264/**
     65@defgroup graph_adaptors Adaptor Classes for graphs
     66@ingroup graphs
     67\brief This group contains several adaptor classes for digraphs and graphs
     68
     69The main parts of LEMON are the different graph structures, generic
     70graph algorithms, graph concepts which couple these, and graph
     71adaptors. While the previous notions are more or less clear, the
     72latter one needs further explanation. Graph adaptors are graph classes
     73which serve for considering graph structures in different ways.
     74
     75A short example makes this much clearer.  Suppose that we have an
     76instance \c g of a directed graph type say ListDigraph and an algorithm
     77\code
     78template <typename Digraph>
     79int algorithm(const Digraph&);
     80\endcode
     81is 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
     83arcs.  In this case, an adaptor class is used, which (according
     84to LEMON digraph concepts) works as a digraph.  The adaptor uses the
     85original digraph structure and digraph operations when methods of the
     86reversed oriented graph are called.  This means that the adaptor have
     87minor memory usage, and do not perform sophisticated algorithmic
     88actions.  The purpose of it is to give a tool for the cases when a
     89graph have to be used in a specific alteration.  If this alteration is
     90obtained by a usual construction like filtering the arc-set or
     91considering a new orientation, then an adaptor is worthwhile to use.
     92To come back to the reverse oriented graph, in this situation
     93\code
     94template<typename Digraph> class ReverseDigraph;
     95\endcode
     96template class can be used. The code looks as follows
     97\code
     98ListDigraph g;
     99ReverseDigraph<ListGraph> rg(g);
     100int result = algorithm(rg);
     101\endcode
     102After running the algorithm, the original graph \c g is untouched.
     103This techniques gives rise to an elegant code, and based on stable
     104graph adaptors, complex algorithms can be implemented easily.
     105
     106In flow, circulation and bipartite matching problems, the residual
     107graph is of particular importance. Combining an adaptor implementing
     108this, shortest path algorithms and minimum mean cycle algorithms,
     109a range of weighted and cardinality optimization algorithms can be
     110obtained. For other examples, the interested user is referred to the
     111detailed documentation of particular adaptors.
     112
     113The behavior of graph adaptors can be very different. Some of them keep
     114capabilities of the original graph while in other cases this would be
     115meaningless. This means that the concepts that they are models of depend
     116on the graph adaptor, and the wrapped graph(s).
     117If an arc of \c rg is deleted, this is carried out by deleting the
     118corresponding arc of \c g, thus the adaptor modifies the original graph.
     119
     120But for a residual graph, this operation has no sense.
     121Let us stand one more example here to simplify your work.
     122RevGraphAdaptor has constructor
     123\code
     124ReverseDigraph(Digraph& digraph);
     125\endcode
     126This means that in a situation, when a <tt>const ListDigraph&</tt>
     127reference to a graph is given, then it have to be instantiated with
     128<tt>Digraph=const ListDigraph</tt>.
     129\code
     130int algorithm1(const ListDigraph& g) {
     131  RevGraphAdaptor<const ListDigraph> rg(g);
     132  return algorithm2(rg);
     133}
     134\endcode
     135*/
     136
     137/**
    63138@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
    64139@ingroup graphs
     
    89164
    90165This group describes maps that are specifically designed to assign
    91 values to the nodes and arcs of graphs.
     166values to the nodes and arcs/edges of graphs.
     167
     168If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
     169\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
    92170*/
    93171
     
    100178maps from other maps.
    101179
    102 Most of them are \ref lemon::concepts::ReadMap "read-only maps".
     180Most of them are \ref concepts::ReadMap "read-only maps".
    103181They can make arithmetic and logical operations between one or two maps
    104182(negation, shifting, addition, multiplication, logical 'and', 'or',
     
    202280\brief Common graph search algorithms.
    203281
    204 This group describes the common graph search algorithms like
    205 Breadth-First Search (BFS) and Depth-First Search (DFS).
     282This group describes the common graph search algorithms, namely
     283\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
    206284*/
    207285
     
    211289\brief Algorithms for finding shortest paths.
    212290
    213 This group describes the algorithms for finding shortest paths in graphs.
     291This 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.
    214305*/
    215306
     
    222313feasible circulations.
    223314
    224 The maximum flow problem is to find a flow between a single source and
    225 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
    226 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
    227 function and given \f$s, t \in V\f$ source and target node. The
    228 maximum 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]
     315The \e maximum \e flow \e problem is to find a flow of maximum value between
     316a single source and a single target. Formally, there is a \f$G=(V,A)\f$
     317digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
     318\f$s, t \in V\f$ source and target nodes.
     319A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
     320following 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]
    234326
    235327LEMON contains several algorithms for solving maximum flow problems:
    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 
    241 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
    242 fastest method to compute the maximum flow. All impelementations
    243 provides functions to query the minimum cut, which is the dual linear
    244 programming problem of the maximum flow.
     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
     333In most cases the \ref Preflow "Preflow" algorithm provides the
     334fastest method for computing a maximum flow. All implementations
     335provides functions to also query the minimum cut, which is the dual
     336problem of the maximum flow.
    245337*/
    246338
     
    253345This group describes the algorithms for finding minimum cost flows and
    254346circulations.
     347
     348The \e minimum \e cost \e flow \e problem is to find a feasible flow of
     349minimum total cost from a set of supply nodes to a set of demand nodes
     350in a network with capacity constraints and arc costs.
     351Formally, let \f$G=(V,A)\f$ be a digraph,
     352\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
     353upper bounds for the flow values on the arcs,
     354\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
     355on the arcs, and
     356\f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
     357of the nodes.
     358A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
     359the 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
     366LEMON 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.
    255374*/
    256375
     
    263382This group describes the algorithms for finding minimum cut in graphs.
    264383
    265 The 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
    267 outgoing 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
     384The \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
     386outgoing 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
    269388cut is the \f$X\f$ solution of the next optimization problem:
    270389
    271390\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    272 \sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
     391    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
    273392
    274393LEMON contains several algorithms related to minimum cut problems:
    275394
    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
     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.
    282401
    283402If you want to find minimum cut just between two distinict nodes,
    284 please see the \ref max_flow "Maximum Flow page".
     403see the \ref max_flow "maximum flow problem".
    285404*/
    286405
     
    321440graphs.  The matching problems in bipartite graphs are generally
    322441easier than in general graphs. The goal of the matching optimization
    323 can be the finding maximum cardinality, maximum weight or minimum cost
     442can be finding maximum cardinality, maximum weight or minimum cost
    324443matching. The search can be constrained to find perfect or
    325444maximum cardinality matching.
    326445
    327 LEMON 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
     446The 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.
    347464
    348465\image html bipartite_matching.png
     
    356473
    357474This group describes the algorithms for finding a minimum cost spanning
    358 tree in a graph
     475tree in a graph.
    359476*/
    360477
     
    465582
    466583/**
    467 @defgroup lemon_io LEMON Input-Output
     584@defgroup lemon_io LEMON Graph Format
    468585@ingroup io_group
    469586\brief Reading and writing LEMON Graph Format.
     
    480597This group describes general \c EPS drawing methods and special
    481598graph 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
     606Tools 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
     614Tool to read graphs from \e Nauty format data.
    482615*/
    483616
     
    531664\anchor demoprograms
    532665
    533 @defgroup demos Demo programs
     666@defgroup demos Demo Programs
    534667
    535668Some demo programs are listed here. Their full source codes can be found in
     
    541674
    542675/**
    543 @defgroup tools Standalone utility applications
     676@defgroup tools Standalone Utility Applications
    544677
    545678Some utility applications are listed here.
     
    549682*/
    550683
     684}
  • doc/migration.dox

    r314 r355  
    2626
    2727Many of these changes adjusted automatically by the
    28 <tt>script/lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual
     28<tt>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>script/lemon-0.x-to-1.x.sh</tt> tool replaces all instances of
    57 the words \c graph, \c digraph, \c edge and \c arc, so it replaces them
    58 in strings, comments etc. as well as in all identifiers.</b>
     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
     58strings, comments etc. as well as in all LEMON specific identifiers.
     59So use the script carefully and make a backup copy of your source files
     60before applying the script to them.</b>
    5961
    6062\section migration-lgf LGF tools
  • lemon/Makefile.am

    r259 r434  
    1313        lemon/random.cc
    1414
    15 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
     15#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) $(AM_CXXFLAGS)
    1616#lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
    1717
    1818lemon_HEADERS += \
     19        lemon/adaptors.h \
    1920        lemon/arg_parser.h \
    2021        lemon/assert.h \
    2122        lemon/bfs.h \
    2223        lemon/bin_heap.h \
     24        lemon/circulation.h \
    2325        lemon/color.h \
    2426        lemon/concept_check.h \
     
    2830        lemon/dijkstra.h \
    2931        lemon/dim2.h \
     32        lemon/dimacs.h \
     33        lemon/elevator.h \
    3034        lemon/error.h \
     35        lemon/full_graph.h \
    3136        lemon/graph_to_eps.h \
     37        lemon/grid_graph.h \
     38        lemon/hypercube_graph.h \
    3239        lemon/kruskal.h \
     40        lemon/hao_orlin.h \
    3341        lemon/lgf_reader.h \
    3442        lemon/lgf_writer.h \
     
    3644        lemon/maps.h \
    3745        lemon/math.h \
     46        lemon/max_matching.h \
     47        lemon/nauty_reader.h \
    3848        lemon/path.h \
     49        lemon/preflow.h \
    3950        lemon/random.h \
    4051        lemon/smart_graph.h \
     52        lemon/suurballe.h \
    4153        lemon/time_measure.h \
    4254        lemon/tolerance.h \
     
    5062        lemon/bits/default_map.h \
    5163        lemon/bits/enable_if.h \
     64        lemon/bits/graph_adaptor_extender.h \
    5265        lemon/bits/graph_extender.h \
    5366        lemon/bits/map_extender.h \
    5467        lemon/bits/path_dump.h \
    5568        lemon/bits/traits.h \
     69        lemon/bits/variant.h \
    5670        lemon/bits/vector_map.h
    5771
  • lemon/bfs.h

    r301 r437  
    120120  ///
    121121  ///\tparam GR The type of the digraph the algorithm runs on.
    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.
     122  ///The default type is \ref ListDigraph.
    129123#ifdef DOXYGEN
    130124  template <typename GR,
     
    152146    typedef PredMapPath<Digraph, PredMap> Path;
    153147
    154     ///The traits class.
     148    ///The \ref BfsDefaultTraits "traits class" of the algorithm.
    155149    typedef TR Traits;
    156150
     
    214208    typedef Bfs Create;
    215209
    216     ///\name Named template parameters
     210    ///\name Named Template Parameters
    217211
    218212    ///@{
     
    232226    ///\ref named-templ-param "Named parameter" for setting
    233227    ///PredMap type.
     228    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    234229    template <class T>
    235230    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
     
    251246    ///\ref named-templ-param "Named parameter" for setting
    252247    ///DistMap type.
     248    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    253249    template <class T>
    254250    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
     
    270266    ///\ref named-templ-param "Named parameter" for setting
    271267    ///ReachedMap type.
     268    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    272269    template <class T>
    273270    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
     
    289286    ///\ref named-templ-param "Named parameter" for setting
    290287    ///ProcessedMap type.
     288    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    291289    template <class T>
    292290    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
     
    341339
    342340    ///Sets the map that stores the predecessor arcs.
    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.
     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.
    346345    ///\return <tt> (*this) </tt>
    347346    Bfs &predMap(PredMap &m)
     
    358357
    359358    ///Sets the map that indicates which nodes are reached.
    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.
     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.
    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(),
    378     ///it will allocate one. The destructor deallocates this
    379     ///automatically allocated map, of course.
     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.
    380381    ///\return <tt> (*this) </tt>
    381382    Bfs &processedMap(ProcessedMap &m)
     
    393394    ///Sets the map that stores the distances of the nodes calculated by
    394395    ///the algorithm.
    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.
     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.
    398400    ///\return <tt> (*this) </tt>
    399401    Bfs &distMap(DistMap &m)
     
    409411  public:
    410412
    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.
     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.
    420420
    421421    ///@{
    422422
     423    ///\brief Initializes the internal data structures.
     424    ///
    423425    ///Initializes the internal data structures.
    424 
    425     ///Initializes the internal data structures.
    426     ///
    427426    void init()
    428427    {
     
    558557    }
    559558
    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.
     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.
    565563    bool emptyQueue() const { return _queue_tail==_queue_head; }
    566564
    567565    ///Returns the number of the nodes to be processed.
    568566
    569     ///Returns the number of the nodes to be processed in the queue.
     567    ///Returns the number of the nodes to be processed
     568    ///in the queue.
    570569    int queueSize() const { return _queue_head-_queue_tail; }
    571570
     
    732731
    733732    ///\name Query Functions
    734     ///The result of the %BFS algorithm can be obtained using these
     733    ///The results of the BFS algorithm can be obtained using these
    735734    ///functions.\n
    736     ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
    737     ///"start()" must be called before using them.
     735    ///Either \ref run(Node) "run()" or \ref start() should be called
     736    ///before using them.
    738737
    739738    ///@{
     
    743742    ///Returns the shortest path to a node.
    744743    ///
    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.
     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.
    749748    Path path(Node t) const { return Path(*G, *_pred, t); }
    750749
     
    753752    ///Returns the distance of a node from the root(s).
    754753    ///
    755     ///\warning If node \c v is not reachable from the root(s), then
     754    ///\warning If node \c v is not reached from the root(s), then
    756755    ///the return value of this function is undefined.
    757756    ///
    758     ///\pre Either \ref run() or \ref start() must be called before
    759     ///using this function.
     757    ///\pre Either \ref run(Node) "run()" or \ref init()
     758    ///must be called before using this function.
    760759    int dist(Node v) const { return (*_dist)[v]; }
    761760
     
    764763    ///This function returns the 'previous arc' of the shortest path
    765764    ///tree for the node \c v, i.e. it returns the last arc of a
    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.
     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.
    768767    ///
    769768    ///The shortest path tree used here is equal to the shortest path
    770769    ///tree used in \ref predNode().
    771770    ///
    772     ///\pre Either \ref run() or \ref start() must be called before
    773     ///using this function.
     771    ///\pre Either \ref run(Node) "run()" or \ref init()
     772    ///must be called before using this function.
    774773    Arc predArc(Node v) const { return (*_pred)[v];}
    775774
     
    778777    ///This function returns the 'previous node' of the shortest path
    779778    ///tree for the node \c v, i.e. it returns the last but one node
    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.
     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.
    782781    ///
    783782    ///The shortest path tree used here is equal to the shortest path
    784783    ///tree used in \ref predArc().
    785784    ///
    786     ///\pre Either \ref run() or \ref start() must be called before
    787     ///using this function.
     785    ///\pre Either \ref run(Node) "run()" or \ref init()
     786    ///must be called before using this function.
    788787    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    789788                                  G->source((*_pred)[v]); }
     
    795794    ///of the nodes calculated by the algorithm.
    796795    ///
    797     ///\pre Either \ref run() or \ref init()
     796    ///\pre Either \ref run(Node) "run()" or \ref init()
    798797    ///must be called before using this function.
    799798    const DistMap &distMap() const { return *_dist;}
     
    805804    ///arcs, which form the shortest path tree.
    806805    ///
    807     ///\pre Either \ref run() or \ref init()
     806    ///\pre Either \ref run(Node) "run()" or \ref init()
    808807    ///must be called before using this function.
    809808    const PredMap &predMap() const { return *_pred;}
    810809
    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()
     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()
    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() method, it uses the functions
    961   /// and features of the plain \ref Bfs.
     960  /// It does not have own \ref run(Node) "run()" method, it uses the
     961  /// functions 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() "run()"
     1181  ///\warning Don't forget to put the \ref BfsWizard::run(Node) "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(),
    1410     /// it will allocate one. The destructor deallocates this
    1411     /// automatically allocated map, of course.
     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.
    14121413    /// \return <tt> (*this) </tt>
    14131414    BfsVisit &reachedMap(ReachedMap &m) {
     
    14221423  public:
    14231424
    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.
     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.
    14341432
    14351433    /// @{
     
    17311729
    17321730    /// \name Query Functions
    1733     /// The result of the %BFS algorithm can be obtained using these
     1731    /// The results of the BFS algorithm can be obtained using these
    17341732    /// functions.\n
    1735     /// Either \ref lemon::BfsVisit::run() "run()" or
    1736     /// \ref lemon::BfsVisit::start() "start()" must be called before
    1737     /// using them.
     1733    /// Either \ref run(Node) "run()" or \ref start() should be called
     1734    /// before using them.
     1735
    17381736    ///@{
    17391737
    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()
     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()
    17441743    /// must be called before using this function.
    1745     bool reached(Node v) { return (*_reached)[v]; }
     1744    bool reached(Node v) const { return (*_reached)[v]; }
    17461745
    17471746    ///@}
  • lemon/bits/alteration_notifier.h

    r314 r373  
    3636  // a container.
    3737  //
    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
     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
    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 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.
     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.
    5657  //
    5758  // For the proper functonality of this class, we should notify it
    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
     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
    6364  // clear() and build() members. Important rule that if we erase items
    64   // from graph we should first signal the alteration and after that erase
     65  // from graphs we should first signal the alteration and after that erase
    6566  // them from the container, on the other way on item addition we should
    6667  // first extend the container and just after that signal the alteration.
    6768  //
    6869  // The alteration can be observed with a class inherited from the
    69   // \e ObserverBase nested class. The signals can be handled with
     70  // ObserverBase nested class. The signals can be handled with
    7071  // overriding the virtual functions defined in the base class.  The
    7172  // observer base can be attached to the notifier with the
    72   // \e attach() member and can be detached with detach() function. The
     73  // attach() member and can be detached with detach() function. The
    7374  // alteration handlers should not call any function which signals
    7475  // an other alteration in the same notifier and should not
    7576  // detach any observer from the notifier.
    7677  //
    77   // Alteration observers try to be exception safe. If an \e add() or
    78   // a \e clear() function throws an exception then the remaining
     78  // Alteration observers try to be exception safe. If an add() or
     79  // a clear() function throws an exception then the remaining
    7980  // observeres will not be notified and the fulfilled additions will
    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
     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
    8687  // reliable. If we want to carry out the node degree in the graph
    87   // as in the \ref InDegMap and we use the reverseEdge that cause
     88  // as in the \ref InDegMap and we use the reverseArc(), then it cause
    8889  // unreliable functionality. Because the alteration observing signals
    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.
     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.
    9394  //
    9495  // \param _Container The container which is observed.
     
    104105    typedef _Item Item;
    105106
    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
     107    // \brief Exception which can be called from clear() and
     108    // erase().
     109    //
     110    // From the clear() and erase() function only this
    110111    // exception is allowed to throw. The exception immediatly
    111112    // detaches the current observer from the notifier. Because the
    112     // \e clear() and \e erase() should not throw other exceptions
     113    // clear() and erase() should not throw other exceptions
    113114    // it can be used to invalidate the observer.
    114115    struct ImmediateDetach {};
     
    122123    // The observer interface contains some pure virtual functions
    123124    // to override. The add() and erase() functions are
    124     // to notify the oberver when one item is added or
    125     // erased.
     125    // to notify the oberver when one item is added or erased.
    126126    //
    127127    // The build() and clear() members are to notify the observer
  • lemon/bits/array_map.h

    r314 r373  
    3737  // \brief Graph map based on the array storage.
    3838  //
    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.
     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.
    4342  //
    44   // The template parameters are the Graph the current Item type and
     43  // The template parameters are the Graph, the current Item type and
    4544  // the Value type of the map.
    4645  template <typename _Graph, typename _Item, typename _Value>
     
    4847    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    4948  public:
    50     // The graph type of the maps.
     49    // The graph type.
    5150    typedef _Graph Graph;
    52     // The item type of the map.
     51    // The item type.
    5352    typedef _Item Item;
    5453    // The reference map tag.
    5554    typedef True ReferenceMapTag;
    5655
    57     // The key type of the maps.
     56    // The key type of the map.
    5857    typedef _Item Key;
    5958    // The value type of the map.
     
    201200    // \brief Adds a new key to the map.
    202201    //
    203     // It adds a new key to the map. It called by the observer notifier
     202    // It adds a new key to the map. It is called by the observer notifier
    204203    // and it overrides the add() member function of the observer base.
    205204    virtual void add(const Key& key) {
     
    229228    // \brief Adds more new keys to the map.
    230229    //
    231     // It adds more new keys to the map. It called by the observer notifier
     230    // It adds more new keys to the map. It is called by the observer notifier
    232231    // and it overrides the add() member function of the observer base.
    233232    virtual void add(const std::vector<Key>& keys) {
     
    273272    // \brief Erase a key from the map.
    274273    //
    275     // Erase a key from the map. It called by the observer notifier
     274    // Erase a key from the map. It is called by the observer notifier
    276275    // and it overrides the erase() member function of the observer base.
    277276    virtual void erase(const Key& key) {
     
    282281    // \brief Erase more keys from the map.
    283282    //
    284     // Erase more keys from the map. It called by the observer notifier
     283    // Erase more keys from the map. It is called by the observer notifier
    285284    // and it overrides the erase() member function of the observer base.
    286285    virtual void erase(const std::vector<Key>& keys) {
     
    291290    }
    292291
    293     // \brief Buildes the map.
    294     //
    295     // It buildes the map. It called by the observer notifier
     292    // \brief Builds the map.
     293    //
     294    // It builds the map. It is called by the observer notifier
    296295    // and it overrides the build() member function of the observer base.
    297296    virtual void build() {
     
    307306    // \brief Clear the map.
    308307    //
    309     // It erase all items from the map. It called by the observer notifier
     308    // It erase all items from the map. It is called by the observer notifier
    310309    // and it overrides the clear() member function of the observer base.
    311310    virtual void clear() {
  • lemon/bits/base_extender.h

    r314 r373  
    3131//\ingroup digraphbits
    3232//\file
    33 //\brief Extenders for the digraph types
     33//\brief Extenders for the graph types
    3434namespace lemon {
    3535
  • lemon/bits/graph_extender.h

    r314 r373  
    3030//\ingroup graphbits
    3131//\file
    32 //\brief Extenders for the digraph types
     32//\brief Extenders for the graph types
    3333namespace lemon {
    3434
    3535  // \ingroup graphbits
    3636  //
    37   // \brief Extender for the Digraphs
     37  // \brief Extender for the digraph implementations
    3838  template <typename Base>
    3939  class DigraphExtender : public Base {
  • lemon/bits/traits.h

    r314 r372  
    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>
    221234  struct EdgeNumTagIndicator {
    222235    static const bool value = false;
     
    232245
    233246  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>
    234260  struct FindEdgeTagIndicator {
    235261    static const bool value = false;
  • lemon/bits/vector_map.h

    r314 r373  
    3939  // \brief Graph map based on the std::vector storage.
    4040  //
    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.
     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.
    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 called by the observer notifier
     172    // It adds a new key to the map. It is 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 called by the observer notifier
     183    // It adds more new keys to the map. It is 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 called by the observer notifier
     198    // Erase a key from the map. It is 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     // Erase more keys from the map. It called by the observer notifier
     206    // It erases more keys from the map. It is 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 Buildes the map.
    215     //
    216     // It buildes the map. It called by the observer notifier
     214    // \brief Build the map.
     215    //
     216    // It builds the map. It is 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 erase all items from the map. It called by the observer notifier
     226    // It erases all items from the map. It is called by the observer notifier
    227227    // and it overrides the clear() member function of the observer base.
    228228    virtual void clear() {
  • lemon/dfs.h

    r319 r438  
    120120  ///
    121121  ///\tparam GR The type of the digraph the algorithm runs on.
    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.
     122  ///The default type is \ref ListDigraph.
    129123#ifdef DOXYGEN
    130124  template <typename GR,
     
    152146    typedef PredMapPath<Digraph, PredMap> Path;
    153147
    154     ///The traits class.
     148    ///The \ref DfsDefaultTraits "traits class" of the algorithm.
    155149    typedef TR Traits;
    156150
     
    231225    ///\ref named-templ-param "Named parameter" for setting
    232226    ///PredMap type.
     227    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    233228    template <class T>
    234229    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
     
    250245    ///\ref named-templ-param "Named parameter" for setting
    251246    ///DistMap type.
     247    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    252248    template <class T>
    253249    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
     
    269265    ///\ref named-templ-param "Named parameter" for setting
    270266    ///ReachedMap type.
     267    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    271268    template <class T>
    272269    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
     
    288285    ///\ref named-templ-param "Named parameter" for setting
    289286    ///ProcessedMap type.
     287    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    290288    template <class T>
    291289    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
     
    339337
    340338    ///Sets the map that stores the predecessor arcs.
    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.
     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.
    344343    ///\return <tt> (*this) </tt>
    345344    Dfs &predMap(PredMap &m)
     
    356355
    357356    ///Sets the map that indicates which nodes are reached.
    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.
     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.
    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(),
    376     ///it will allocate one. The destructor deallocates this
    377     ///automatically allocated map, of course.
     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.
    378379    ///\return <tt> (*this) </tt>
    379380    Dfs &processedMap(ProcessedMap &m)
     
    391392    ///Sets the map that stores the distances of the nodes calculated by
    392393    ///the algorithm.
    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.
     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.
    396398    ///\return <tt> (*this) </tt>
    397399    Dfs &distMap(DistMap &m)
     
    407409  public:
    408410
    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.
     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.
    418419
    419420    ///@{
    420421
     422    ///\brief Initializes the internal data structures.
     423    ///
    421424    ///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     ///false results.)
    443     ///
    444     ///\warning Distances will be wrong (or at least strange) in case of
    445     ///multiple sources.
     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.)
    446445    void addSource(Node s)
    447446    {
     
    507506    }
    508507
    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).
     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).
    514512    bool emptyQueue() const { return _stack_head<0; }
    515513
    516514    ///Returns the number of the nodes to be processed.
    517515
    518     ///Returns the number of the nodes to be processed in the queue (stack).
     516    ///Returns the number of the nodes to be processed
     517    ///in the queue (stack).
    519518    int queueSize() const { return _stack_head+1; }
    520519
     
    638637    ///
    639638    ///The algorithm computes
    640     ///- the %DFS tree,
    641     ///- the distance of each node from the root in the %DFS tree.
     639    ///- the %DFS tree (forest),
     640    ///- the distance of each node from the root(s) in the %DFS tree.
    642641    ///
    643642    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
     
    664663
    665664    ///\name Query Functions
    666     ///The result of the %DFS algorithm can be obtained using these
     665    ///The results of the DFS algorithm can be obtained using these
    667666    ///functions.\n
    668     ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
    669     ///"start()" must be called before using them.
     667    ///Either \ref run(Node) "run()" or \ref start() should be called
     668    ///before using them.
    670669
    671670    ///@{
     
    675674    ///Returns the DFS path to a node.
    676675    ///
    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.
     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.
    681680    Path path(Node t) const { return Path(*G, *_pred, t); }
    682681
    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
     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
    688687    ///the return value of this function is undefined.
    689688    ///
    690     ///\pre Either \ref run() or \ref start() must be called before
    691     ///using this function.
     689    ///\pre Either \ref run(Node) "run()" or \ref init()
     690    ///must be called before using this function.
    692691    int dist(Node v) const { return (*_dist)[v]; }
    693692
     
    695694
    696695    ///This function returns the 'previous arc' of the %DFS tree for the
    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.
     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.
    700699    ///
    701700    ///The %DFS tree used here is equal to the %DFS tree used in
    702701    ///\ref predNode().
    703702    ///
    704     ///\pre Either \ref run() or \ref start() must be called before using
    705     ///this function.
     703    ///\pre Either \ref run(Node) "run()" or \ref init()
     704    ///must be called before using this function.
    706705    Arc predArc(Node v) const { return (*_pred)[v];}
    707706
     
    710709    ///This function returns the 'previous node' of the %DFS
    711710    ///tree for the node \c v, i.e. it returns the last but one node
    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.
     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.
    714713    ///
    715714    ///The %DFS tree used here is equal to the %DFS tree used in
    716715    ///\ref predArc().
    717716    ///
    718     ///\pre Either \ref run() or \ref start() must be called before
    719     ///using this function.
     717    ///\pre Either \ref run(Node) "run()" or \ref init()
     718    ///must be called before using this function.
    720719    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    721720                                  G->source((*_pred)[v]); }
     
    727726    ///distances of the nodes calculated by the algorithm.
    728727    ///
    729     ///\pre Either \ref run() or \ref init()
     728    ///\pre Either \ref run(Node) "run()" or \ref init()
    730729    ///must be called before using this function.
    731730    const DistMap &distMap() const { return *_dist;}
     
    737736    ///arcs, which form the DFS tree.
    738737    ///
    739     ///\pre Either \ref run() or \ref init()
     738    ///\pre Either \ref run(Node) "run()" or \ref init()
    740739    ///must be called before using this function.
    741740    const PredMap &predMap() const { return *_pred;}
    742741
    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()
     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()
    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() method, it uses the functions
    893   /// and features of the plain \ref Dfs.
     892  /// It does not have own \ref run(Node) "run()" method, it uses the
     893  /// functions 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 
    1114   ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
     1113  ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()"
    11151114  ///to the end of the parameter list.
    11161115  ///\sa DfsWizard
     
    13101309    typedef DfsVisit Create;
    13111310
    1312     /// \name Named template parameters
     1311    /// \name Named Template Parameters
    13131312
    13141313    ///@{
     
    13521351    ///
    13531352    /// Sets the map that indicates which nodes are reached.
    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.
     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.
    13571357    /// \return <tt> (*this) </tt>
    13581358    DfsVisit &reachedMap(ReachedMap &m) {
     
    13671367  public:
    13681368
    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.
     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.
    13791377
    13801378    /// @{
     
    13921390    }
    13931391
    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.
     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.)
    14031400    void addSource(Node s)
    14041401    {
     
    14141411          } else {
    14151412            _visitor->leave(s);
     1413            _visitor->stop(s);
    14161414          }
    14171415        }
     
    15901588    ///
    15911589    /// The algorithm computes
    1592     /// - the %DFS tree,
    1593     /// - the distance of each node from the root in the %DFS tree.
     1590    /// - the %DFS tree (forest),
     1591    /// - the distance of each node from the root(s) in the %DFS tree.
    15941592    ///
    15951593    /// \note <tt>d.run()</tt> is just a shortcut of the following code.
     
    16161614
    16171615    /// \name Query Functions
    1618     /// The result of the %DFS algorithm can be obtained using these
     1616    /// The results of the DFS algorithm can be obtained using these
    16191617    /// functions.\n
    1620     /// Either \ref lemon::DfsVisit::run() "run()" or
    1621     /// \ref lemon::DfsVisit::start() "start()" must be called before
    1622     /// using them.
     1618    /// Either \ref run(Node) "run()" or \ref start() should be called
     1619    /// before using them.
     1620
    16231621    ///@{
    16241622
    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()
     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()
    16291628    /// must be called before using this function.
    1630     bool reached(Node v) { return (*_reached)[v]; }
     1629    bool reached(Node v) const { return (*_reached)[v]; }
    16311630
    16321631    ///@}
  • lemon/dijkstra.h

    r412 r424  
    180180  ///
    181181  ///\tparam GR The type of the digraph the algorithm runs on.
    182   ///The default value is \ref ListDigraph.
    183   ///The value of GR is not used directly by \ref Dijkstra, it is only
    184   ///passed to \ref DijkstraDefaultTraits.
    185   ///\tparam LM A readable arc map that determines the lengths of the
    186   ///arcs. It is read once for each arc, so the map may involve in
     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
    187186  ///relatively time consuming process to compute the arc lengths if
    188187  ///it is necessary. The default map type is \ref
    189   ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
    190   ///The value of LM is not used directly by \ref Dijkstra, it is only
    191   ///passed to \ref DijkstraDefaultTraits.
    192   ///\tparam TR Traits class to set various data types used by the algorithm.
    193   ///The default traits class is \ref DijkstraDefaultTraits
    194   ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
    195   ///for the documentation of a Dijkstra traits class.
     188  ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
    196189#ifdef DOXYGEN
    197190  template <typename GR, typename LM, typename TR>
     
    227220    typedef typename TR::OperationTraits OperationTraits;
    228221
    229     ///The traits class.
     222    ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
    230223    typedef TR Traits;
    231224
     
    309302    ///\ref named-templ-param "Named parameter" for setting
    310303    ///PredMap type.
     304    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    311305    template <class T>
    312306    struct SetPredMap
     
    329323    ///\ref named-templ-param "Named parameter" for setting
    330324    ///DistMap type.
     325    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    331326    template <class T>
    332327    struct SetDistMap
     
    349344    ///\ref named-templ-param "Named parameter" for setting
    350345    ///ProcessedMap type.
     346    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    351347    template <class T>
    352348    struct SetProcessedMap
     
    389385    };
    390386    ///\brief \ref named-templ-param "Named parameter" for setting
    391     ///heap and cross reference type
     387    ///heap and cross reference types
    392388    ///
    393389    ///\ref named-templ-param "Named parameter" for setting heap and cross
    394     ///reference type.
     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
    395395    template <class H, class CR = typename Digraph::template NodeMap<int> >
    396396    struct SetHeap
     
    412412    };
    413413    ///\brief \ref named-templ-param "Named parameter" for setting
    414     ///heap and cross reference type with automatic allocation
     414    ///heap and cross reference types with automatic allocation
    415415    ///
    416416    ///\ref named-templ-param "Named parameter" for setting heap and cross
    417     ///reference type. It can allocate the heap and the cross reference
    418     ///object if the cross reference's constructor waits for the digraph as
    419     ///parameter and the heap's constructor waits for the cross reference.
     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
    420426    template <class H, class CR = typename Digraph::template NodeMap<int> >
    421427    struct SetStandardHeap
     
    487493
    488494    ///Sets the map that stores the predecessor arcs.
    489     ///If you don't use this function before calling \ref run(),
    490     ///it will allocate one. The destructor deallocates this
    491     ///automatically allocated map, of course.
     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.
    492499    ///\return <tt> (*this) </tt>
    493500    Dijkstra &predMap(PredMap &m)
     
    504511
    505512    ///Sets the map that indicates which nodes are processed.
    506     ///If you don't use this function before calling \ref run(),
    507     ///it will allocate one. The destructor deallocates this
    508     ///automatically allocated map, of course.
     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.
    509517    ///\return <tt> (*this) </tt>
    510518    Dijkstra &processedMap(ProcessedMap &m)
     
    522530    ///Sets the map that stores the distances of the nodes calculated by the
    523531    ///algorithm.
    524     ///If you don't use this function before calling \ref run(),
    525     ///it will allocate one. The destructor deallocates this
    526     ///automatically allocated map, of course.
     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.
    527536    ///\return <tt> (*this) </tt>
    528537    Dijkstra &distMap(DistMap &m)
     
    539548
    540549    ///Sets the heap and the cross reference used by algorithm.
    541     ///If you don't use this function before calling \ref run(),
    542     ///it will allocate one. The destructor deallocates this
    543     ///automatically allocated heap and cross reference, of course.
     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.
    544555    ///\return <tt> (*this) </tt>
    545556    Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
     
    568579  public:
    569580
    570     ///\name Execution control
    571     ///The simplest way to execute the algorithm is to use one of the
    572     ///member functions called \ref lemon::Dijkstra::run() "run()".
    573     ///\n
    574     ///If you need more control on the execution, first you must call
    575     ///\ref lemon::Dijkstra::init() "init()", then you can add several
    576     ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
    577     ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
    578     ///actual path computation.
     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.
    579588
    580589    ///@{
    581590
     591    ///\brief Initializes the internal data structures.
     592    ///
    582593    ///Initializes the internal data structures.
    583 
    584     ///Initializes the internal data structures.
    585     ///
    586594    void init()
    587595    {
     
    659667    }
    660668
    661     ///\brief Returns \c false if there are nodes
    662     ///to be processed.
    663     ///
    664     ///Returns \c false if there are nodes
    665     ///to be processed in the priority heap.
     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.
    666673    bool emptyQueue() const { return _heap->empty(); }
    667674
    668     ///Returns the number of the nodes to be processed in the priority heap
    669 
    670     ///Returns the number of the nodes to be processed in the priority heap.
    671     ///
     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.
    672679    int queueSize() const { return _heap->size(); }
    673680
     
    790797
    791798    ///\name Query Functions
    792     ///The result of the %Dijkstra algorithm can be obtained using these
     799    ///The results of the %Dijkstra algorithm can be obtained using these
    793800    ///functions.\n
    794     ///Either \ref lemon::Dijkstra::run() "run()" or
    795     ///\ref lemon::Dijkstra::start() "start()" must be called before
    796     ///using them.
     801    ///Either \ref run(Node) "run()" or \ref start() should be called
     802    ///before using them.
    797803
    798804    ///@{
     
    802808    ///Returns the shortest path to a node.
    803809    ///
    804     ///\warning \c t should be reachable from the root(s).
    805     ///
    806     ///\pre Either \ref run() or \ref start() must be called before
    807     ///using this function.
     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.
    808814    Path path(Node t) const { return Path(*G, *_pred, t); }
    809815
     
    812818    ///Returns the distance of a node from the root(s).
    813819    ///
    814     ///\warning If node \c v is not reachable from the root(s), then
     820    ///\warning If node \c v is not reached from the root(s), then
    815821    ///the return value of this function is undefined.
    816822    ///
    817     ///\pre Either \ref run() or \ref start() must be called before
    818     ///using this function.
     823    ///\pre Either \ref run(Node) "run()" or \ref init()
     824    ///must be called before using this function.
    819825    Value dist(Node v) const { return (*_dist)[v]; }
    820826
     
    823829    ///This function returns the 'previous arc' of the shortest path
    824830    ///tree for the node \c v, i.e. it returns the last arc of a
    825     ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
    826     ///is not reachable from the root(s) or if \c v is a root.
     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.
    827833    ///
    828834    ///The shortest path tree used here is equal to the shortest path
    829835    ///tree used in \ref predNode().
    830836    ///
    831     ///\pre Either \ref run() or \ref start() must be called before
    832     ///using this function.
     837    ///\pre Either \ref run(Node) "run()" or \ref init()
     838    ///must be called before using this function.
    833839    Arc predArc(Node v) const { return (*_pred)[v]; }
    834840
     
    837843    ///This function returns the 'previous node' of the shortest path
    838844    ///tree for the node \c v, i.e. it returns the last but one node
    839     ///from a shortest path from the root(s) to \c v. It is \c INVALID
    840     ///if \c v is not reachable from the root(s) or if \c v is a root.
     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.
    841847    ///
    842848    ///The shortest path tree used here is equal to the shortest path
    843849    ///tree used in \ref predArc().
    844850    ///
    845     ///\pre Either \ref run() or \ref start() must be called before
    846     ///using this function.
     851    ///\pre Either \ref run(Node) "run()" or \ref init()
     852    ///must be called before using this function.
    847853    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    848854                                  G->source((*_pred)[v]); }
     
    854860    ///of the nodes calculated by the algorithm.
    855861    ///
    856     ///\pre Either \ref run() or \ref init()
     862    ///\pre Either \ref run(Node) "run()" or \ref init()
    857863    ///must be called before using this function.
    858864    const DistMap &distMap() const { return *_dist;}
     
    864870    ///arcs, which form the shortest path tree.
    865871    ///
    866     ///\pre Either \ref run() or \ref init()
     872    ///\pre Either \ref run(Node) "run()" or \ref init()
    867873    ///must be called before using this function.
    868874    const PredMap &predMap() const { return *_pred;}
    869875
    870     ///Checks if a node is reachable from the root(s).
    871 
    872     ///Returns \c true if \c v is reachable from the root(s).
    873     ///\pre Either \ref run() or \ref start()
     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()
    874881    ///must be called before using this function.
    875882    bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
     
    880887    ///Returns \c true if \c v is processed, i.e. the shortest
    881888    ///path to \c v has already found.
    882     ///\pre Either \ref run() or \ref init()
     889    ///
     890    ///\pre Either \ref run(Node) "run()" or \ref init()
    883891    ///must be called before using this function.
    884892    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
     
    889897    ///Returns the current distance of a node from the root(s).
    890898    ///It may be decreased in the following processes.
    891     ///\pre Either \ref run() or \ref init()
     899    ///
     900    ///\pre Either \ref run(Node) "run()" or \ref init()
    892901    ///must be called before using this function and
    893902    ///node \c v must be reached but not necessarily processed.
     
    10721081  /// This auxiliary class is created to implement the
    10731082  /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
    1074   /// It does not have own \ref run() method, it uses the functions
    1075   /// and features of the plain \ref Dijkstra.
     1083  /// It does not have own \ref run(Node) "run()" method, it uses the
     1084  /// functions and features of the plain \ref Dijkstra.
    10761085  ///
    10771086  /// This class should only be used through the \ref dijkstra() function,
     
    12681277  ///  bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
    12691278  ///\endcode
    1270   ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
     1279  ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()"
    12711280  ///to the end of the parameter list.
    12721281  ///\sa DijkstraWizard
  • lemon/list_graph.h

    r313 r341  
    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/random.h

    r391 r392  
    541541    /// @{
    542542
    543     ///\name Initialization
    544     ///
    545     /// @{
    546 
    547543    /// \brief Default constructor
    548544    ///
     
    693689    }
    694690
    695     /// @}
    696 
    697     ///\name Uniform distributions
    698     ///
    699     /// @{
    700 
    701691    /// \brief Returns a random real number from the range [0, 1)
    702692    ///
     
    753743      return _random_bits::IntConversion<Number, Word>::convert(core);
    754744    }
    755 
    756     /// @}
    757745
    758746    unsigned int uinteger() {
     
    789777    ///\name Non-uniform distributions
    790778    ///
    791 
    792779    ///@{
    793780
    794     /// \brief Returns a random bool
     781    /// \brief Returns a random bool with given probability of true result.
    795782    ///
    796783    /// It returns a random bool with given probability of true result.
     
    799786    }
    800787
    801     /// Standard Gauss distribution
    802 
    803     /// Standard Gauss distribution.
     788    /// Standard normal (Gauss) distribution
     789
     790    /// Standard normal (Gauss) distribution.
    804791    /// \note The Cartesian form of the Box-Muller
    805792    /// transformation is used to generate a random normal distribution.
     
    814801      return std::sqrt(-2*std::log(S)/S)*V1;
    815802    }
    816     /// Gauss distribution with given mean and standard deviation
    817 
    818     /// Gauss distribution with given mean and standard deviation.
     803    /// Normal (Gauss) distribution with given mean and standard deviation
     804
     805    /// Normal (Gauss) distribution with given mean and standard deviation.
    819806    /// \sa gauss()
    820807    double gauss(double mean,double std_dev)
    821808    {
    822809      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));
    823850    }
    824851
     
    926953    ///\name Two dimensional distributions
    927954    ///
    928 
    929955    ///@{
    930956
     
    943969      return dim2::Point<double>(V1,V2);
    944970    }
    945     /// A kind of two dimensional Gauss distribution
     971    /// A kind of two dimensional normal (Gauss) distribution
    946972
    947973    /// This function provides a turning symmetric two-dimensional distribution.
  • lemon/smart_graph.h

    r313 r388  
    6868
    6969    typedef True NodeNumTag;
    70     typedef True EdgeNumTag;
     70    typedef True ArcNumTag;
    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].source=b._id;
     308      for(int i=nodes[b._id].first_out; i!=-1; i=arcs[i].next_out) {
     309        arcs[i].source=b._id;
     310      }
    309311      if(connect) addArc(n,b);
    310312      return b;
     
    465467
    466468    public:
    467       operator Edge() const { 
    468         return _id != -1 ? edgeFromId(_id / 2) : INVALID; 
     469      operator Edge() const {
     470        return _id != -1 ? edgeFromId(_id / 2) : INVALID;
    469471      }
    470472
     
    481483      : nodes(), arcs() {}
    482484
     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(); }
    483492
    484493    int maxNodeId() const { return nodes.size()-1; }
     
    729738        dir.push_back(arcFromId(n-1));
    730739        Parent::notifier(Arc()).erase(dir);
    731         nodes[arcs[n].target].first_out=arcs[n].next_out;
    732         nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
     740        nodes[arcs[n-1].target].first_out=arcs[n].next_out;
     741        nodes[arcs[n].target].first_out=arcs[n-1].next_out;
    733742        arcs.pop_back();
    734743        arcs.pop_back();
  • scripts/chg-len.py

    r284 r439  
    22
    33import sys
    4 import os
     4
     5from mercurial import ui, hg
     6from mercurial import util
     7
     8util.rcpath = lambda : []
    59
    610if len(sys.argv)>1 and sys.argv[1] in ["-h","--help"]:
     
    1014"""
    1115    exit(0)
    12 plist = os.popen("HGRCPATH='' hg parents --template='{rev}\n'").readlines()
    13 if len(plist)>1:
    14     print "You are in the process of merging"
    15     exit(1)
    16 PAR = int(plist[0])
    1716
    18 f = os.popen("HGRCPATH='' hg log -r 0:tip --template='{rev} {parents}\n'").\
    19     readlines()
    20 REV = -1
    21 lengths=[]
    22 for 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])
     17u = ui.ui()
     18r = hg.repository(u, ".")
     19N = r.changectx(".").rev()
     20lengths=[0]*(N+1)
     21for i in range(N+1):
     22    p=r.changectx(i).parents()
     23    if p[0]:
     24        p0=lengths[p[0].rev()]
    3325    else:
    34         par1 = int(s[1].split(":")[0])
    35         par2 = int(s[2].split(":")[0])
    36     if rev == 0:
    37         lengths.append(0)
     26        p0=-1
     27    if len(p)>1 and p[1]:
     28        p1=lengths[p[1].rev()]
    3829    else:
    39         lengths.append(max(lengths[par1],lengths[par2])+1)
    40 print lengths[PAR]
     30        p1=-1
     31    lengths[i]=max(p0,p1)+1
     32print lengths[N]
  • scripts/unify-sources.sh

    r208 r411  
    44HGROOT=`hg root`
    55
    6 function update_header() {
     6# file enumaration modes
     7
     8function 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
     14function 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
     20function 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
     35function given_files() {
     36    for file in $GIVEN_FILES
     37    do
     38        echo $file
     39    done
     40}
     41
     42# actions
     43
     44function 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
     54function update_warning() {
     55    echo -n " [$2 warning]"
     56    WARNED=YES
     57}
     58
     59function update_init() {
     60    echo Update source files...
     61    TOTAL_FILES=0
     62    CHANGED_FILES=0
     63    WARNED_FILES=0
     64}
     65
     66function 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
     71function update_begin() {
     72    ((TOTAL_FILES++))
     73    CHANGED=NO
     74    WARNED=NO
     75}
     76
     77function 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
     88function 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
     112function 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
     122function check_init() {
     123    echo Check source files...
     124    FAILED_FILES=0
     125    WARNED_FILES=0
     126    TOTAL_FILES=0
     127}
     128
     129function 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
     156function check_begin() {
     157    ((TOTAL_FILES++))
     158    FAILED=NO
     159    WARNED=NO
     160}
     161
     162function 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
     177function header_check() {
     178    if echo $1 | grep -q -E 'Makefile\.am$'
     179    then
     180        return
     181    fi
     182
    7183    TMP_FILE=`mktemp`
    8     FILE_NAME=$1
    9184
    10185    (echo "/* -*- mode: C++; indent-tabs-mode: nil; -*-
     
    26201 */
    27202"
    28         awk 'BEGIN { pm=0; }
     203    awk 'BEGIN { pm=0; }
    29204     pm==3 { print }
    30205     /\/\* / && pm==0 { pm=1;}
     
    32207     /\*\// && pm==1 { pm=2;}
    33208    ' $1
    34         ) >$TMP_FILE
    35 
    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
    40 }
    41 
    42 function update_tabs() {
     209    ) >$TMP_FILE
     210
     211    "$ACTION"_action "$TMP_FILE" "$1" header
     212}
     213
     214function 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
    43223    TMP_FILE=`mktemp`
    44     FILE_NAME=$1
    45 
    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
    53 }
    54 
    55 function remove_trailing_space() {
     224    cat $1 | sed -e "s/$OLD_PATTERN/$NEW_PATTERN/g" >$TMP_FILE
     225
     226    "$ACTION"_action "$TMP_FILE" "$1" 'tabs'
     227}
     228
     229function spaces_check() {
    56230    TMP_FILE=`mktemp`
    57     FILE_NAME=$1
    58 
    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
    66 }
    67 
    68 function long_line_test() {
    69     cat $1 |grep -q -E '.{81,}'
    70 }
    71 
    72 function 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 ]];
    81     then
    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++))
    104     fi
    105 }
    106 
    107 CHANGED_FILES=0
    108 TOTAL_FILES=0
    109 LONG_LINE_FILES=0
    110 if [ $# == 0 ]; then
    111     echo Update all source files...
    112     for i in `hg manifest|grep -E  '\.(cc|h|dox)$'`
     231    cat $1 | sed -e 's/ \+$//g' >$TMP_FILE
     232
     233    "$ACTION"_action "$TMP_FILE" "$1" 'trailing spaces'
     234}
     235
     236function long_lines_check() {
     237    if cat $1 | grep -q -E '.{81,}'
     238    then
     239        "$ACTION"_warning $1 'long lines'
     240    fi
     241}
     242
     243# process the file
     244
     245function 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
    113257    do
    114         update_file $HGROOT/$i
    115         ((TOTAL_FILES++))
     258        "$check"_check $1
    116259    done
    117     echo '  done.'
    118 else
    119     for i in $*
     260    "$ACTION"_end $1
     261    if [ "$ACTION" == 'update' ]
     262    then
     263        echo
     264    fi
     265}
     266
     267function process_all {
     268    "$ACTION"_init
     269    while read file
    120270    do
    121         update_file $i
    122         ((TOTAL_FILES++))
    123     done
     271        process_file $file
     272    done < <($FILES)
     273    "$ACTION"_done
     274}
     275
     276while [ $# -gt 0 ]
     277do
     278   
     279    if [ "$1" == '--help' ] || [ "$1" == '-h' ]
     280    then
     281        echo -n \
     282"Usage:
     283  $0 [OPTIONS] [files]
     284Options:
     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
     350done
     351
     352if [ -z $FILES ]
     353then
     354    FILES=modified_files
    124355fi
    125 echo $CHANGED_FILES out of $TOTAL_FILES files has been changed.
    126 if [[ $LONG_LINE_FILES -gt 1 ]]; then
    127     echo
    128     echo WARNING: $LONG_LINE_FILES files contains long lines!   
    129     echo
    130 elif [[ $LONG_LINE_FILES -gt 0 ]]; then
    131     echo
    132     echo WARNING: a file contains long lines!
    133     echo
     356
     357if [ -z $ACTION ]
     358then
     359    ACTION=update
    134360fi
     361
     362process_all
  • test/CMakeLists.txt

    r225 r443  
    55SET(TESTS
    66  bfs_test
     7  circulation_test
    78  counter_test
    89  dfs_test
     
    1112  dim_test
    1213  error_test
     14  graph_adaptor_test
    1315  graph_copy_test
    1416  graph_test
    1517  graph_utils_test
     18  hao_orlin_test
    1619  heap_test
    1720  kruskal_test
    1821  maps_test
     22  max_matching_test
     23  path_test
     24  preflow_test
    1925  random_test
    20   path_test
     26  suurballe_test
    2127  time_measure_test
    2228  unionfind_test)
  • test/Makefile.am

    r228 r443  
    88check_PROGRAMS += \
    99        test/bfs_test \
     10        test/circulation_test \
    1011        test/counter_test \
    1112        test/dfs_test \
     
    1415        test/dim_test \
    1516        test/error_test \
     17        test/graph_adaptor_test \
    1618        test/graph_copy_test \
    1719        test/graph_test \
    1820        test/graph_utils_test \
     21        test/hao_orlin_test \
    1922        test/heap_test \
    2023        test/kruskal_test \
    2124        test/maps_test \
     25        test/max_matching_test \
     26        test/path_test \
     27        test/preflow_test \
    2228        test/random_test \
    23         test/path_test \
     29        test/suurballe_test \
    2430        test/test_tools_fail \
    2531        test/test_tools_pass \
     
    3137
    3238test_bfs_test_SOURCES = test/bfs_test.cc
     39test_circulation_test_SOURCES = test/circulation_test.cc
    3340test_counter_test_SOURCES = test/counter_test.cc
    3441test_dfs_test_SOURCES = test/dfs_test.cc
     
    3744test_dim_test_SOURCES = test/dim_test.cc
    3845test_error_test_SOURCES = test/error_test.cc
     46test_graph_adaptor_test_SOURCES = test/graph_adaptor_test.cc
    3947test_graph_copy_test_SOURCES = test/graph_copy_test.cc
    4048test_graph_test_SOURCES = test/graph_test.cc
     
    4250test_heap_test_SOURCES = test/heap_test.cc
    4351test_kruskal_test_SOURCES = test/kruskal_test.cc
     52test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
    4453test_maps_test_SOURCES = test/maps_test.cc
     54test_max_matching_test_SOURCES = test/max_matching_test.cc
    4555test_path_test_SOURCES = test/path_test.cc
     56test_preflow_test_SOURCES = test/preflow_test.cc
     57test_suurballe_test_SOURCES = test/suurballe_test.cc
    4658test_random_test_SOURCES = test/random_test.cc
    4759test_test_tools_fail_SOURCES = test/test_tools_fail.cc
  • test/digraph_test.cc

    r228 r388  
    2020#include <lemon/list_graph.h>
    2121#include <lemon/smart_graph.h>
    22 //#include <lemon/full_graph.h>
    23 //#include <lemon/hypercube_graph.h>
     22#include <lemon/full_graph.h>
    2423
    2524#include "test_tools.h"
     
    3029
    3130template <class Digraph>
    32 void checkDigraph() {
     31void checkDigraphBuild() {
    3332  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    3433  Digraph G;
     
    5958  checkGraphConArcList(G, 1);
    6059
    61   Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
     60  Arc a2 = G.addArc(n2, n1),
     61      a3 = G.addArc(n2, n3),
     62      a4 = G.addArc(n2, n3);
     63
    6264  checkGraphNodeList(G, 3);
    6365  checkGraphArcList(G, 4);
     
    7779  checkGraphNodeMap(G);
    7880  checkGraphArcMap(G);
    79 
    80 }
    81 
     81}
     82
     83template <class Digraph>
     84void 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
     114template <class Digraph>
     115void 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
     193template <class Digraph>
     194void 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
     242template <class Digraph>
     243void 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
     262  checkGraphNodeList(G, 3);
     263  checkGraphArcList(G, 4);
     264
     265  checkGraphOutArcList(G, n1, 1);
     266  checkGraphOutArcList(G, n2, 3);
     267  checkGraphOutArcList(G, n3, 0);
     268
     269  checkGraphInArcList(G, n1, 1);
     270  checkGraphInArcList(G, n2, 1);
     271  checkGraphInArcList(G, n3, 2);
     272
     273  checkGraphConArcList(G, 4);
     274
     275  checkNodeIds(G);
     276  checkArcIds(G);
     277  checkGraphNodeMap(G);
     278  checkGraphArcMap(G);
     279
     280  G.addNode();
     281  snapshot.save(G);
     282
     283  G.addArc(G.addNode(), G.addNode());
     284
     285  snapshot.restore();
     286
     287  checkGraphNodeList(G, 4);
     288  checkGraphArcList(G, 4);
     289}
    82290
    83291void checkConcepts() {
     
    110318    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
    111319  }
    112 //  { // Checking FullDigraph
    113 //    checkConcept<Digraph, FullDigraph>();
    114 //  }
    115 //  { // Checking HyperCubeDigraph
    116 //    checkConcept<Digraph, HyperCubeDigraph>();
    117 //  }
     320  { // Checking FullDigraph
     321    checkConcept<Digraph, FullDigraph>();
     322  }
    118323}
    119324
     
    168373}
    169374
     375void 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
    170407void checkDigraphs() {
    171408  { // Checking ListDigraph
    172     checkDigraph<ListDigraph>();
     409    checkDigraphBuild<ListDigraph>();
     410    checkDigraphSplit<ListDigraph>();
     411    checkDigraphAlter<ListDigraph>();
     412    checkDigraphErase<ListDigraph>();
     413    checkDigraphSnapshot<ListDigraph>();
    173414    checkDigraphValidityErase<ListDigraph>();
    174415  }
    175416  { // Checking SmartDigraph
    176     checkDigraph<SmartDigraph>();
     417    checkDigraphBuild<SmartDigraph>();
     418    checkDigraphSplit<SmartDigraph>();
     419    checkDigraphSnapshot<SmartDigraph>();
    177420    checkDigraphValidity<SmartDigraph>();
     421  }
     422  { // Checking FullDigraph
     423    checkFullDigraph(8);
    178424  }
    179425}
  • test/graph_test.cc

    r228 r388  
    2020#include <lemon/list_graph.h>
    2121#include <lemon/smart_graph.h>
    22 // #include <lemon/full_graph.h>
    23 // #include <lemon/grid_graph.h>
     22#include <lemon/full_graph.h>
     23#include <lemon/grid_graph.h>
     24#include <lemon/hypercube_graph.h>
    2425
    2526#include "test_tools.h"
     
    3031
    3132template <class Graph>
    32 void checkGraph() {
     33void checkGraphBuild() {
    3334  TEMPLATE_GRAPH_TYPEDEFS(Graph);
    3435
     
    3637  checkGraphNodeList(G, 0);
    3738  checkGraphEdgeList(G, 0);
     39  checkGraphArcList(G, 0);
    3840
    3941  Node
     
    4345  checkGraphNodeList(G, 3);
    4446  checkGraphEdgeList(G, 0);
     47  checkGraphArcList(G, 0);
    4548
    4649  Edge e1 = G.addEdge(n1, n2);
    4750  check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
    4851        "Wrong edge");
    49   checkGraphNodeList(G, 3);
     52
     53  checkGraphNodeList(G, 3);
     54  checkGraphEdgeList(G, 1);
    5055  checkGraphArcList(G, 2);
    51   checkGraphEdgeList(G, 1);
    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 
     56
     57  checkGraphIncEdgeArcLists(G, n1, 1);
     58  checkGraphIncEdgeArcLists(G, n2, 1);
     59  checkGraphIncEdgeArcLists(G, n3, 0);
     60
     61  checkGraphConEdgeList(G, 1);
    6562  checkGraphConArcList(G, 2);
    66   checkGraphConEdgeList(G, 1);
    67 
    68   Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
    69   checkGraphNodeList(G, 3);
     63
     64  Edge e2 = G.addEdge(n2, n1),
     65       e3 = G.addEdge(n2, n3);
     66
     67  checkGraphNodeList(G, 3);
     68  checkGraphEdgeList(G, 3);
    7069  checkGraphArcList(G, 6);
    71   checkGraphEdgeList(G, 3);
    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 
     70
     71  checkGraphIncEdgeArcLists(G, n1, 2);
     72  checkGraphIncEdgeArcLists(G, n2, 3);
     73  checkGraphIncEdgeArcLists(G, n3, 1);
     74
     75  checkGraphConEdgeList(G, 3);
    8576  checkGraphConArcList(G, 6);
    86   checkGraphConEdgeList(G, 3);
    8777
    8878  checkArcDirections(G);
     
    9686}
    9787
     88template <class Graph>
     89void 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
     167template <class Graph>
     168void 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
     209template <class Graph>
     210void 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
     265void 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
    98312void checkConcepts() {
    99313  { // Checking graph components
     
    125339    checkConcept<ClearableGraphComponent<>, SmartGraph>();
    126340  }
    127 //  { // Checking FullGraph
    128 //    checkConcept<Graph, FullGraph>();
    129 //    checkGraphIterators<FullGraph>();
    130 //  }
    131 //  { // Checking GridGraph
    132 //    checkConcept<Graph, GridGraph>();
    133 //    checkGraphIterators<GridGraph>();
    134 //  }
     341  { // Checking FullGraph
     342    checkConcept<Graph, FullGraph>();
     343  }
     344  { // Checking GridGraph
     345    checkConcept<Graph, GridGraph>();
     346  }
     347  { // Checking HypercubeGraph
     348    checkConcept<Graph, HypercubeGraph>();
     349  }
    135350}
    136351
     
    189404}
    190405
    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 // }
     406void 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
     485void 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}
    234532
    235533void checkGraphs() {
    236534  { // Checking ListGraph
    237     checkGraph<ListGraph>();
     535    checkGraphBuild<ListGraph>();
     536    checkGraphAlter<ListGraph>();
     537    checkGraphErase<ListGraph>();
     538    checkGraphSnapshot<ListGraph>();
    238539    checkGraphValidityErase<ListGraph>();
    239540  }
    240541  { // Checking SmartGraph
    241     checkGraph<SmartGraph>();
     542    checkGraphBuild<SmartGraph>();
     543    checkGraphSnapshot<SmartGraph>();
    242544    checkGraphValidity<SmartGraph>();
    243545  }
    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 //   }
     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  }
    255563}
    256564
  • test/graph_test.h

    r263 r387  
    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);
    117126  }
    118127
  • tools/Makefile.am

    r310 r400  
    11if WANT_TOOLS
    22
    3 bin_PROGRAMS +=
     3bin_PROGRAMS += \
     4        tools/dimacs-to-lgf
     5
    46dist_bin_SCRIPTS += tools/lemon-0.x-to-1.x.sh
    57
    68endif WANT_TOOLS
     9
     10tools_dimacs_to_lgf_SOURCES = tools/dimacs-to-lgf.cc
  • tools/lemon-0.x-to-1.x.sh

    r310 r378  
    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"
    8         exit
     6    echo "Usage:"
     7    echo "  $0 source-file(s)"
     8    exit
    99fi
    1010
    11 TMP=`mktemp`
    12 
    13 sed     -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 
    127 mv $TMP $1
     11for i in $@
     12do
     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
     97done
Note: See TracChangeset for help on using the changeset viewer.