COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
47 added
101 edited

Legend:

Unmodified
Added
Removed

  • .hgignore

    r298 r495  
    2727.deps/*
    2828demo/*.eps
     29m4/libtool.m4
     30m4/ltoptions.m4
     31m4/ltsugar.m4
     32m4/ltversion.m4
     33m4/lt~obsolete.m4
    2934
    3035syntax: regexp
    … …  
    3540^autom4te.cache/.*
    3641^build-aux/.*
    37 ^objs.*/.*
     42^.*objs.*/.*
    3843^test/[a-z_]*$
     44^tools/[a-z-_]*$
    3945^demo/.*_demo$
    40 ^build/.*
     46^.*build.*/.*
    4147^doc/gen-images/.*
    4248CMakeFiles

  • CMakeLists.txt

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

  • LICENSE

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

  • Makefile.am

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

  • configure.ac

    r310 r482  
    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.
    54 #LX_CHECK_GLPK
    55 #LX_CHECK_CPLEX
    56 #LX_CHECK_SOPLEX
     53LX_CHECK_GLPK
     54LX_CHECK_CPLEX
     55LX_CHECK_SOPLEX
     56LX_CHECK_CLP
     57
     58AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
     59AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
    5760
    5861dnl Disable/enable building the demo programs.
    … …  
    114117echo
    115118echo C++ compiler.................. : $CXX
    116 echo C++ compiles flags............ : $CXXFLAGS
     119echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
    117120echo
    118 #echo GLPK support.................. : $lx_glpk_found
    119 #echo CPLEX support................. : $lx_cplex_found
    120 #echo SOPLEX support................ : $lx_soplex_found
    121 #echo
     121echo GLPK support.................. : $lx_glpk_found
     122echo CPLEX support................. : $lx_cplex_found
     123echo SOPLEX support................ : $lx_soplex_found
     124echo CLP support................... : $lx_clp_found
     125echo
    122126echo Build demo programs........... : $enable_demo
    123127echo Build additional tools........ : $enable_tools

  • demo/CMakeLists.txt

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

  • demo/arg_parser_demo.cc

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

  • demo/graph_to_eps_demo.cc

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

  • demo/lgf_demo.cc

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

  • doc/CMakeLists.txt

    r497 r553  
    1515      COMMAND rm -rf gen-images
    1616      COMMAND mkdir gen-images
     17      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
    1718      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
    1819      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/coding_style.dox

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

  • doc/dirs.dox

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

  • doc/groups.dox

    r318 r478  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    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 Adaptor classes for digraphs and graphs
     68
     69This group contains several useful adaptor classes for digraphs and graphs.
     70
     71The main parts of LEMON are the different graph structures, generic
     72graph algorithms, graph concepts, which couple them, and graph
     73adaptors. While the previous notions are more or less clear, the
     74latter one needs further explanation. Graph adaptors are graph classes
     75which serve for considering graph structures in different ways.
     76
     77A short example makes this much clearer.  Suppose that we have an
     78instance \c g of a directed graph type, say ListDigraph and an algorithm
     79\code
     80template <typename Digraph>
     81int algorithm(const Digraph&);
     82\endcode
     83is needed to run on the reverse oriented graph.  It may be expensive
     84(in time or in memory usage) to copy \c g with the reversed
     85arcs.  In this case, an adaptor class is used, which (according
     86to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
     87The adaptor uses the original digraph structure and digraph operations when
     88methods of the reversed oriented graph are called.  This means that the adaptor
     89have minor memory usage, and do not perform sophisticated algorithmic
     90actions.  The purpose of it is to give a tool for the cases when a
     91graph have to be used in a specific alteration.  If this alteration is
     92obtained by a usual construction like filtering the node or the arc set or
     93considering a new orientation, then an adaptor is worthwhile to use.
     94To come back to the reverse oriented graph, in this situation
     95\code
     96template<typename Digraph> class ReverseDigraph;
     97\endcode
     98template class can be used. The code looks as follows
     99\code
     100ListDigraph g;
     101ReverseDigraph<ListDigraph> rg(g);
     102int result = algorithm(rg);
     103\endcode
     104During running the algorithm, the original digraph \c g is untouched.
     105This techniques give rise to an elegant code, and based on stable
     106graph adaptors, complex algorithms can be implemented easily.
     107
     108In flow, circulation and matching problems, the residual
     109graph is of particular importance. Combining an adaptor implementing
     110this with shortest path algorithms or minimum mean cycle algorithms,
     111a range of weighted and cardinality optimization algorithms can be
     112obtained. For other examples, the interested user is referred to the
     113detailed documentation of particular adaptors.
     114
     115The behavior of graph adaptors can be very different. Some of them keep
     116capabilities of the original graph while in other cases this would be
     117meaningless. This means that the concepts that they meet depend
     118on the graph adaptor, and the wrapped graph.
     119For example, if an arc of a reversed digraph is deleted, this is carried
     120out by deleting the corresponding arc of the original digraph, thus the
     121adaptor modifies the original digraph.
     122However in case of a residual digraph, this operation has no sense.
     123
     124Let us stand one more example here to simplify your work.
     125ReverseDigraph has constructor
     126\code
     127ReverseDigraph(Digraph& digraph);
     128\endcode
     129This means that in a situation, when a <tt>const %ListDigraph&</tt>
     130reference to a graph is given, then it have to be instantiated with
     131<tt>Digraph=const %ListDigraph</tt>.
     132\code
     133int algorithm1(const ListDigraph& g) {
     134  ReverseDigraph<const ListDigraph> rg(g);
     135  return algorithm2(rg);
     136}
     137\endcode
     138*/
     139
     140/**
    63141@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
    64142@ingroup graphs
    … …  
    89167
    90168This group describes maps that are specifically designed to assign
    91 values to the nodes and arcs of graphs.
     169values to the nodes and arcs/edges of graphs.
     170
     171If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
     172\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
    92173*/
    93174
    … …  
    100181maps from other maps.
    101182
    102 Most of them are \ref lemon::concepts::ReadMap "read-only maps".
     183Most of them are \ref concepts::ReadMap "read-only maps".
    103184They can make arithmetic and logical operations between one or two maps
    104185(negation, shifting, addition, multiplication, logical 'and', 'or',
    … …  
    202283\brief Common graph search algorithms.
    203284
    204 This group describes the common graph search algorithms like
    205 Breadth-First Search (BFS) and Depth-First Search (DFS).
     285This group describes the common graph search algorithms, namely
     286\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
    206287*/
    207288
    … …  
    211292\brief Algorithms for finding shortest paths.
    212293
    213 This group describes the algorithms for finding shortest paths in graphs.
     294This group describes the algorithms for finding shortest paths in digraphs.
     295
     296 - \ref Dijkstra algorithm for finding shortest paths from a source node
     297   when all arc lengths are non-negative.
     298 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
     299   from a source node when arc lenghts can be either positive or negative,
     300   but the digraph should not contain directed cycles with negative total
     301   length.
     302 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
     303   for solving the \e all-pairs \e shortest \e paths \e problem when arc
     304   lenghts can be either positive or negative, but the digraph should
     305   not contain directed cycles with negative total length.
     306 - \ref Suurballe A successive shortest path algorithm for finding
     307   arc-disjoint paths between two nodes having minimum total length.
    214308*/
    215309
    … …  
    222316feasible circulations.
    223317
    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]
     318The \e maximum \e flow \e problem is to find a flow of maximum value between
     319a single source and a single target. Formally, there is a \f$G=(V,A)\f$
     320digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
     321\f$s, t \in V\f$ source and target nodes.
     322A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
     323following optimization problem.
     324
     325\f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
     326\f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
     327    \qquad \forall v\in V\setminus\{s,t\} \f]
     328\f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
    234329
    235330LEMON 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.
     331- \ref EdmondsKarp Edmonds-Karp algorithm.
     332- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
     333- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
     334- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
     335
     336In most cases the \ref Preflow "Preflow" algorithm provides the
     337fastest method for computing a maximum flow. All implementations
     338provides functions to also query the minimum cut, which is the dual
     339problem of the maximum flow.
    245340*/
    246341
    … …  
    253348This group describes the algorithms for finding minimum cost flows and
    254349circulations.
     350
     351The \e minimum \e cost \e flow \e problem is to find a feasible flow of
     352minimum total cost from a set of supply nodes to a set of demand nodes
     353in a network with capacity constraints and arc costs.
     354Formally, let \f$G=(V,A)\f$ be a digraph,
     355\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
     356upper bounds for the flow values on the arcs,
     357\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
     358on the arcs, and
     359\f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
     360of the nodes.
     361A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
     362the following optimization problem.
     363
     364\f[ \min\sum_{a\in A} f(a) cost(a) \f]
     365\f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
     366    supply(v) \qquad \forall v\in V \f]
     367\f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
     368
     369LEMON contains several algorithms for solving minimum cost flow problems:
     370 - \ref CycleCanceling Cycle-canceling algorithms.
     371 - \ref CapacityScaling Successive shortest path algorithm with optional
     372   capacity scaling.
     373 - \ref CostScaling Push-relabel and augment-relabel algorithms based on
     374   cost scaling.
     375 - \ref NetworkSimplex Primal network simplex algorithm with various
     376   pivot strategies.
    255377*/
    256378
    … …  
    263385This group describes the algorithms for finding minimum cut in graphs.
    264386
    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
     387The \e minimum \e cut \e problem is to find a non-empty and non-complete
     388\f$X\f$ subset of the nodes with minimum overall capacity on
     389outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
     390\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
    269391cut is the \f$X\f$ solution of the next optimization problem:
    270392
    271393\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]
     394    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
    273395
    274396LEMON contains several algorithms related to minimum cut problems:
    275397
    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
     398- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
     399  in directed graphs.
     400- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
     401  calculating minimum cut in undirected graphs.
     402- \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
     403  all-pairs minimum cut in undirected graphs.
    282404
    283405If you want to find minimum cut just between two distinict nodes,
    284 please see the \ref max_flow "Maximum Flow page".
     406see the \ref max_flow "maximum flow problem".
    285407*/
    286408
    … …  
    321443graphs.  The matching problems in bipartite graphs are generally
    322444easier than in general graphs. The goal of the matching optimization
    323 can be the finding maximum cardinality, maximum weight or minimum cost
     445can be finding maximum cardinality, maximum weight or minimum cost
    324446matching. The search can be constrained to find perfect or
    325447maximum cardinality matching.
    326448
    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
     449The matching algorithms implemented in LEMON:
     450- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
     451  for calculating maximum cardinality matching in bipartite graphs.
     452- \ref PrBipartiteMatching Push-relabel algorithm
     453  for calculating maximum cardinality matching in bipartite graphs.
     454- \ref MaxWeightedBipartiteMatching
     455  Successive shortest path algorithm for calculating maximum weighted
     456  matching and maximum weighted bipartite matching in bipartite graphs.
     457- \ref MinCostMaxBipartiteMatching
     458  Successive shortest path algorithm for calculating minimum cost maximum
     459  matching in bipartite graphs.
     460- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
     461  maximum cardinality matching in general graphs.
     462- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
     463  maximum weighted matching in general graphs.
     464- \ref MaxWeightedPerfectMatching
     465  Edmond's blossom shrinking algorithm for calculating maximum weighted
     466  perfect matching in general graphs.
    347467
    348468\image html bipartite_matching.png
    … …  
    356476
    357477This group describes the algorithms for finding a minimum cost spanning
    358 tree in a graph
     478tree in a graph.
    359479*/
    360480
    … …  
    465585
    466586/**
    467 @defgroup lemon_io LEMON Input-Output
     587@defgroup lemon_io LEMON Graph Format
    468588@ingroup io_group
    469589\brief Reading and writing LEMON Graph Format.
    … …  
    480600This group describes general \c EPS drawing methods and special
    481601graph exporting tools.
     602*/
     603
     604/**
     605@defgroup dimacs_group DIMACS format
     606@ingroup io_group
     607\brief Read and write files in DIMACS format
     608
     609Tools to read a digraph from or write it to a file in DIMACS format data.
     610*/
     611
     612/**
     613@defgroup nauty_group NAUTY Format
     614@ingroup io_group
     615\brief Read \e Nauty format
     616
     617Tool to read graphs from \e Nauty format data.
    482618*/
    483619
    … …  
    531667\anchor demoprograms
    532668
    533 @defgroup demos Demo programs
     669@defgroup demos Demo Programs
    534670
    535671Some demo programs are listed here. Their full source codes can be found in
    … …  
    541677
    542678/**
    543 @defgroup tools Standalone utility applications
     679@defgroup tools Standalone Utility Applications
    544680
    545681Some utility applications are listed here.
    … …  
    549685*/
    550686
     687}

  • doc/lgf.dox

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

  • doc/license.dox

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

  • doc/mainpage.dox

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

  • doc/migration.dox

    r314 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    2626
    2727Many of these changes adjusted automatically by the
    28 <tt>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

  • doc/named-param.dox

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

  • doc/namespaces.dox

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

  • doc/template.h

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

  • lemon/CMakeLists.txt

    r225 r498  
    1 INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
     1INCLUDE_DIRECTORIES(
     2  ${CMAKE_SOURCE_DIR}
     3  ${CMAKE_BINARY_DIR}
     4)
    25
    3 ADD_LIBRARY(lemon
     6CONFIGURE_FILE(
     7  ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake
     8  ${CMAKE_CURRENT_BINARY_DIR}/config.h
     9)
     10
     11SET(LEMON_SOURCES
    412  arg_parser.cc
    513  base.cc
    614  color.cc
     15  lp_base.cc
     16  lp_skeleton.cc
    717  random.cc)
     18
     19IF(HAVE_GLPK)
     20  SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc)
     21  INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR})
     22  IF(WIN32)
     23    INSTALL(FILES ${GLPK_BIN_DIR}/glpk.dll DESTINATION bin)
     24    INSTALL(FILES ${GLPK_BIN_DIR}/libltdl3.dll DESTINATION bin)
     25    INSTALL(FILES ${GLPK_BIN_DIR}/zlib1.dll DESTINATION bin)
     26  ENDIF(WIN32)
     27ENDIF(HAVE_GLPK)
     28
     29ADD_LIBRARY(lemon ${LEMON_SOURCES})
    830
    931INSTALL(

  • lemon/Makefile.am

    r259 r492  
    88
    99lemon_libemon_la_SOURCES = \
    10         lemon/arg_parser.cc \
    11         lemon/base.cc \
    12         lemon/color.cc \
    13         lemon/random.cc
     10        lemon/arg_parser.cc \
     11        lemon/base.cc \
     12        lemon/color.cc \
     13        lemon/lp_base.cc \
     14        lemon/lp_skeleton.cc \
     15        lemon/random.cc
    1416
    15 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
    16 #lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
     17
     18lemon_libemon_la_CXXFLAGS = \
     19        $(GLPK_CFLAGS) \
     20        $(CPLEX_CFLAGS) \
     21        $(SOPLEX_CXXFLAGS) \
     22        $(CLP_CXXFLAGS)
     23
     24lemon_libemon_la_LDFLAGS = \
     25        $(GLPK_LIBS) \
     26        $(CPLEX_LIBS) \
     27        $(SOPLEX_LIBS) \
     28        $(CLP_LIBS)
     29
     30if HAVE_GLPK
     31lemon_libemon_la_SOURCES += lemon/glpk.cc
     32endif
     33
     34if HAVE_CPLEX
     35lemon_libemon_la_SOURCES += lemon/cplex.cc
     36endif
     37
     38if HAVE_SOPLEX
     39lemon_libemon_la_SOURCES += lemon/soplex.cc
     40endif
     41
     42if HAVE_CLP
     43lemon_libemon_la_SOURCES += lemon/clp.cc
     44endif
    1745
    1846lemon_HEADERS += \
    19         lemon/arg_parser.h \
     47        lemon/adaptors.h \
     48        lemon/arg_parser.h \
    2049        lemon/assert.h \
    21         lemon/bfs.h \
    22         lemon/bin_heap.h \
    23         lemon/color.h \
     50        lemon/bfs.h \
     51        lemon/bin_heap.h \
     52        lemon/circulation.h \
     53        lemon/clp.h \
     54        lemon/color.h \
    2455        lemon/concept_check.h \
    25         lemon/counter.h \
     56        lemon/counter.h \
    2657        lemon/core.h \
    27         lemon/dfs.h \
    28         lemon/dijkstra.h \
    29         lemon/dim2.h \
     58        lemon/cplex.h \
     59        lemon/dfs.h \
     60        lemon/dijkstra.h \
     61        lemon/dim2.h \
     62        lemon/dimacs.h \
     63        lemon/edge_set.h \
     64        lemon/elevator.h \
    3065        lemon/error.h \
    31         lemon/graph_to_eps.h \
     66        lemon/full_graph.h \
     67        lemon/glpk.h \
     68        lemon/graph_to_eps.h \
     69        lemon/grid_graph.h \
     70        lemon/hypercube_graph.h \
    3271        lemon/kruskal.h \
     72        lemon/hao_orlin.h \
    3373        lemon/lgf_reader.h \
    3474        lemon/lgf_writer.h \
    3575        lemon/list_graph.h \
     76        lemon/lp.h \
     77        lemon/lp_base.h \
     78        lemon/lp_skeleton.h \
     79        lemon/list_graph.h \
    3680        lemon/maps.h \
    3781        lemon/math.h \
     82        lemon/max_matching.h \
     83        lemon/nauty_reader.h \
    3884        lemon/path.h \
    39         lemon/random.h \
     85        lemon/preflow.h \
     86        lemon/radix_sort.h \
     87        lemon/random.h \
    4088        lemon/smart_graph.h \
    41         lemon/time_measure.h \
    42         lemon/tolerance.h \
     89        lemon/soplex.h \
     90        lemon/suurballe.h \
     91        lemon/time_measure.h \
     92        lemon/tolerance.h \
    4393        lemon/unionfind.h
    4494
    … …  
    4797        lemon/bits/array_map.h \
    4898        lemon/bits/base_extender.h \
    49         lemon/bits/bezier.h \
     99        lemon/bits/bezier.h \
    50100        lemon/bits/default_map.h \
    51         lemon/bits/enable_if.h \
     101        lemon/bits/edge_set_extender.h \
     102        lemon/bits/enable_if.h \
     103        lemon/bits/graph_adaptor_extender.h \
    52104        lemon/bits/graph_extender.h \
    53105        lemon/bits/map_extender.h \
    54106        lemon/bits/path_dump.h \
     107        lemon/bits/solver_bits.h \
    55108        lemon/bits/traits.h \
     109        lemon/bits/variant.h \
    56110        lemon/bits/vector_map.h
    57111

  • lemon/arg_parser.cc

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

  • lemon/arg_parser.h

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

  • lemon/assert.h

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

  • lemon/base.cc

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

  • lemon/bfs.h

    r301 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    120120  ///
    121121  ///\tparam GR The type of the digraph the algorithm runs on.
    122   ///The default 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/bin_heap.h

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

  • lemon/bits/alteration_notifier.h

    r314 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    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 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    3737  // \brief Graph map based on the array storage.
    3838  //
    39   // The ArrayMap template class is graph map structure 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 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    3131//\ingroup digraphbits
    3232//\file
    33 //\brief Extenders for the digraph types
     33//\brief Extenders for the graph types
    3434namespace lemon {
    3535

  • lemon/bits/bezier.h

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

  • lemon/bits/default_map.h

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

  • lemon/bits/enable_if.h

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

  • lemon/bits/graph_extender.h

    r314 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    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/map_extender.h

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

  • lemon/bits/path_dump.h

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

  • lemon/bits/traits.h

    r314 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    219219
    220220  template <typename Graph, typename Enable = void>
     221  struct ArcNumTagIndicator {
     222    static const bool value = false;
     223  };
     224
     225  template <typename Graph>
     226  struct ArcNumTagIndicator<
     227    Graph,
     228    typename enable_if<typename Graph::ArcNumTag, void>::type
     229  > {
     230    static const bool value = true;
     231  };
     232
     233  template <typename Graph, typename Enable = void>
    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 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    3939  // \brief Graph map based on the std::vector storage.
    4040  //
    41   // The VectorMap template class is graph map structure 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/color.cc

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

  • lemon/color.h

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

  • lemon/concept_check.h

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

  • lemon/concepts/digraph.h

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

  • lemon/concepts/graph.h

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

  • lemon/concepts/graph_components.h

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

  • lemon/concepts/heap.h

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

  • lemon/concepts/maps.h

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

  • lemon/concepts/path.h

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

  • lemon/config.h.in

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

  • lemon/core.h

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

  • lemon/counter.h

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

  • lemon/dfs.h

    r319 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    120120  ///
    121121  ///\tparam GR The type of the digraph the algorithm runs on.
    122   ///The default 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 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    180180  ///
    181181  ///\tparam GR The type of the digraph the algorithm runs on.
    182   ///The default 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/dim2.h

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

  • lemon/error.h

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

  • lemon/graph_to_eps.h

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

  • lemon/kruskal.h

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

  • lemon/lgf_reader.h

    r319 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    871871        readLine();
    872872      }
    873       line.putback(c);
     873      if (readSuccess()) {
     874        line.putback(c);
     875      }
    874876    }
    875877
    … …  
    17001702        readLine();
    17011703      }
    1702       line.putback(c);
     1704      if (readSuccess()) {
     1705        line.putback(c);
     1706      }
    17031707    }
    17041708
    … …  
    22272231        readLine();
    22282232      }
    2229       line.putback(c);
     2233      if (readSuccess()) {
     2234        line.putback(c);
     2235      }
    22302236    }
    22312237
    … …  
    25682574        readLine();
    25692575      }
    2570       line.putback(c);
     2576      if (readSuccess()) {
     2577        line.putback(c);
     2578      }
    25712579    }
    25722580

  • lemon/lgf_writer.h

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

  • lemon/list_graph.h

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

  • lemon/maps.h

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

  • lemon/math.h

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

  • lemon/path.h

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

  • lemon/random.cc

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

  • lemon/random.h

    r391 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    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 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    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();

  • lemon/time_measure.h

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

  • lemon/tolerance.h

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

  • lemon/unionfind.h

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

  • m4/lx_check_cplex.m4

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

  • m4/lx_check_glpk.m4

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

  • m4/lx_check_soplex.m4

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

  • 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 r498  
    1 INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
     1INCLUDE_DIRECTORIES(
     2  ${CMAKE_SOURCE_DIR}
     3  ${CMAKE_BINARY_DIR}
     4)
     5
     6IF(HAVE_GLPK)
     7  INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR})
     8ENDIF(HAVE_GLPK)
    29
    310LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
    411
    512SET(TESTS
     13  adaptors_test
    614  bfs_test
     15  circulation_test
    716  counter_test
    817  dfs_test
    … …  
    1019  dijkstra_test
    1120  dim_test
     21  edge_set_test
    1222  error_test
    1323  graph_copy_test
    1424  graph_test
    1525  graph_utils_test
     26  hao_orlin_test
    1627  heap_test
    1728  kruskal_test
    1829  maps_test
     30  max_matching_test
     31  path_test
     32  preflow_test
     33  radix_sort_test
    1934  random_test
    20   path_test
     35  suurballe_test
    2136  time_measure_test
    2237  unionfind_test)
     38
     39IF(HAVE_LP)
     40  ADD_EXECUTABLE(lp_test lp_test.cc)
     41  IF(HAVE_GLPK)
     42    TARGET_LINK_LIBRARIES(lp_test lemon ${GLPK_LIBRARIES})
     43  ENDIF(HAVE_GLPK)
     44  ADD_TEST(lp_test lp_test)
     45
     46  IF(WIN32 AND HAVE_GLPK)
     47    GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION)
     48    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
     49    ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD
     50      COMMAND cmake -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}
     51      COMMAND cmake -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}
     52      COMMAND cmake -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}
     53    )
     54  ENDIF(WIN32 AND HAVE_GLPK)
     55ENDIF(HAVE_LP)
     56
     57IF(HAVE_MIP)
     58  ADD_EXECUTABLE(mip_test mip_test.cc)
     59  IF(HAVE_GLPK)
     60    TARGET_LINK_LIBRARIES(mip_test lemon ${GLPK_LIBRARIES})
     61  ENDIF(HAVE_GLPK)
     62  ADD_TEST(mip_test mip_test)
     63
     64  IF(WIN32 AND HAVE_GLPK)
     65    GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION)
     66    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
     67    ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD
     68      COMMAND cmake -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}
     69      COMMAND cmake -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}
     70      COMMAND cmake -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}
     71    )
     72  ENDIF(WIN32 AND HAVE_GLPK)
     73ENDIF(HAVE_MIP)
    2374
    2475FOREACH(TEST_NAME ${TESTS})

  • test/Makefile.am

    r228 r492  
    44noinst_HEADERS += \
    55        test/graph_test.h \
    6         test/test_tools.h
     6        test/test_tools.h
    77
    88check_PROGRAMS += \
     9        test/adaptors_test \
    910        test/bfs_test \
    10         test/counter_test \
     11        test/circulation_test \
     12        test/counter_test \
    1113        test/dfs_test \
    1214        test/digraph_test \
    1315        test/dijkstra_test \
    14         test/dim_test \
     16        test/dim_test \
     17        test/edge_set_test \
    1518        test/error_test \
    1619        test/graph_copy_test \
    1720        test/graph_test \
    1821        test/graph_utils_test \
     22        test/hao_orlin_test \
    1923        test/heap_test \
    2024        test/kruskal_test \
    21         test/maps_test \
    22         test/random_test \
    23         test/path_test \
    24         test/test_tools_fail \
    25         test/test_tools_pass \
    26         test/time_measure_test \
     25        test/maps_test \
     26        test/max_matching_test \
     27        test/path_test \
     28        test/preflow_test \
     29        test/radix_sort_test \
     30        test/random_test \
     31        test/suurballe_test \
     32        test/test_tools_fail \
     33        test/test_tools_pass \
     34        test/time_measure_test \
    2735        test/unionfind_test
     36
     37if HAVE_LP
     38check_PROGRAMS += test/lp_test
     39endif HAVE_LP
     40if HAVE_MIP
     41check_PROGRAMS += test/mip_test
     42endif HAVE_MIP
    2843
    2944TESTS += $(check_PROGRAMS)
    3045XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
    3146
     47test_adaptors_test_SOURCES = test/adaptors_test.cc
    3248test_bfs_test_SOURCES = test/bfs_test.cc
     49test_circulation_test_SOURCES = test/circulation_test.cc
    3350test_counter_test_SOURCES = test/counter_test.cc
    3451test_dfs_test_SOURCES = test/dfs_test.cc
    … …  
    3653test_dijkstra_test_SOURCES = test/dijkstra_test.cc
    3754test_dim_test_SOURCES = test/dim_test.cc
     55test_edge_set_test_SOURCES = test/edge_set_test.cc
    3856test_error_test_SOURCES = test/error_test.cc
    3957test_graph_copy_test_SOURCES = test/graph_copy_test.cc
    … …  
    4260test_heap_test_SOURCES = test/heap_test.cc
    4361test_kruskal_test_SOURCES = test/kruskal_test.cc
     62test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
     63test_lp_test_SOURCES = test/lp_test.cc
    4464test_maps_test_SOURCES = test/maps_test.cc
     65test_mip_test_SOURCES = test/mip_test.cc
     66test_max_matching_test_SOURCES = test/max_matching_test.cc
    4567test_path_test_SOURCES = test/path_test.cc
     68test_preflow_test_SOURCES = test/preflow_test.cc
     69test_radix_sort_test_SOURCES = test/radix_sort_test.cc
     70test_suurballe_test_SOURCES = test/suurballe_test.cc
    4671test_random_test_SOURCES = test/random_test.cc
    4772test_test_tools_fail_SOURCES = test/test_tools_fail.cc

  • test/bfs_test.cc

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

  • test/counter_test.cc

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

  • test/dfs_test.cc

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

  • test/digraph_test.cc

    r228 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    2020#include <lemon/list_graph.h>
    2121#include <lemon/smart_graph.h>
    22 //#include <lemon/full_graph.h>
    23 //#include <lemon/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/dijkstra_test.cc

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

  • test/dim_test.cc

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

  • test/error_test.cc

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

  • test/graph_copy_test.cc

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

  • test/graph_test.cc

    r228 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    2020#include <lemon/list_graph.h>
    2121#include <lemon/smart_graph.h>
    22 // #include <lemon/full_graph.h>
    23 // #include <lemon/grid_graph.h>
     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 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    115115    check(e==INVALID,"Wrong IncEdge list linking.");
    116116    check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
     117  }
     118
     119  template <class Graph>
     120  void checkGraphIncEdgeArcLists(const Graph &G, typename Graph::Node n,
     121                                 int cnt)
     122  {
     123    checkGraphIncEdgeList(G, n, cnt);
     124    checkGraphOutArcList(G, n, cnt);
     125    checkGraphInArcList(G, n, cnt);
    117126  }
    118127

  • test/graph_utils_test.cc

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

  • test/heap_test.cc

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

  • test/kruskal_test.cc

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

  • test/maps_test.cc

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

  • test/path_test.cc

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

  • test/random_test.cc

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

  • test/test_tools.h

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

  • test/test_tools_fail.cc

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

  • test/test_tools_pass.cc

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

  • test/time_measure_test.cc

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

  • test/unionfind_test.cc

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

  • 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 r489  
    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        -e "s/\<RevDigraphAdaptor\>/ReverseDigraph/g"\
     96        -e "s/\<revDigraphAdaptor\>/reverseDigraph/g"\
     97        -e "s/\<SubDigraphAdaptor\>/SubDigraph/g"\
     98        -e "s/\<subDigraphAdaptor\>/subDigraph/g"\
     99        -e "s/\<SubGraphAdaptor\>/SubGraph/g"\
     100        -e "s/\<subGraphAdaptor\>/subGraph/g"\
     101        -e "s/\<NodeSubDigraphAdaptor\>/FilterNodes/g"\
     102        -e "s/\<nodeSubDigraphAdaptor\>/filterNodes/g"\
     103        -e "s/\<ArcSubDigraphAdaptor\>/FilterArcs/g"\
     104        -e "s/\<arcSubDigraphAdaptor\>/filterArcs/g"\
     105        -e "s/\<UndirDigraphAdaptor\>/Undirector/g"\
     106        -e "s/\<undirDigraphAdaptor\>/undirector/g"\
     107        -e "s/\<ResDigraphAdaptor\>/ResidualDigraph/g"\
     108        -e "s/\<resDigraphAdaptor\>/residualDigraph/g"\
     109        -e "s/\<SplitDigraphAdaptor\>/SplitNodes/g"\
     110        -e "s/\<splitDigraphAdaptor\>/splitNodes/g"\
     111        -e "s/\<SubGraphAdaptor\>/SubGraph/g"\
     112        -e "s/\<subGraphAdaptor\>/subGraph/g"\
     113        -e "s/\<NodeSubGraphAdaptor\>/FilterNodes/g"\
     114        -e "s/\<nodeSubGraphAdaptor\>/filterNodes/g"\
     115        -e "s/\<ArcSubGraphAdaptor\>/FilterEdges/g"\
     116        -e "s/\<arcSubGraphAdaptor\>/filterEdges/g"\
     117        -e "s/\<DirGraphAdaptor\>/Orienter/g"\
     118        -e "s/\<dirGraphAdaptor\>/orienter/g"\
     119    <$i > $TMP
     120    mv $TMP $i
     121done
Note: See TracChangeset for help on using the changeset viewer.