Changes in / [475:8b56605db6a8:476:efec3c133e74] in lemon-main
- Files:
-
- 47 added
- 101 edited
Legend:
- Unmodified
- Added
- Removed
-
.hgignore
r298 r472 27 27 .deps/* 28 28 demo/*.eps 29 m4/libtool.m4 30 m4/ltoptions.m4 31 m4/ltsugar.m4 32 m4/ltversion.m4 33 m4/lt~obsolete.m4 29 34 30 35 syntax: regexp … … 35 40 ^autom4te.cache/.* 36 41 ^build-aux/.* 37 ^ objs.*/.*42 ^.*objs.*/.* 38 43 ^test/[a-z_]*$ 44 ^tools/[a-z-_]*$ 39 45 ^demo/.*_demo$ 40 ^ build/.*46 ^.*build.*/.* 41 47 ^doc/gen-images/.* 42 48 CMakeFiles -
CMakeLists.txt
r274 r473 10 10 INCLUDE(FindDoxygen) 11 11 INCLUDE(FindGhostscript) 12 FIND_PACKAGE(GLPK 4.33) 13 14 ADD_DEFINITIONS(-DHAVE_CONFIG_H) 15 16 IF(GLPK_FOUND) 17 SET(HAVE_LP TRUE) 18 SET(HAVE_MIP TRUE) 19 SET(HAVE_GLPK TRUE) 20 ENDIF(GLPK_FOUND) 12 21 13 22 ENABLE_TESTING() -
LICENSE
r107 r440 2 2 copyright/license. 3 3 4 Copyright (C) 2003-200 8Egervary Jeno Kombinatorikus Optimalizalasi4 Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi 5 5 Kutatocsoport (Egervary Combinatorial Optimization Research Group, 6 6 EGRES). -
Makefile.am
r321 r363 1 1 ACLOCAL_AMFLAGS = -I m4 2 3 AM_CXXFLAGS = $(WARNINGCXXFLAGS) 2 4 3 5 AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir) -
configure.ac
r310 r459 19 19 AC_CONFIG_SRCDIR([lemon/list_graph.h]) 20 20 AC_CONFIG_HEADERS([config.h lemon/config.h]) 21 22 lx_cmdline_cxxflags_set=${CXXFLAGS+set}23 21 24 22 dnl Do compilation tests using the C++ compiler. … … 47 45 48 46 dnl Set custom compiler flags when using g++. 49 if test x"$lx_cmdline_cxxflags_set" != x"set" -a"$GXX" = yes -a "$ICC" = no; then50 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"47 if test "$GXX" = yes -a "$ICC" = no; then 48 WARNINGCXXFLAGS="-Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas" 51 49 fi 50 AC_SUBST([WARNINGCXXFLAGS]) 52 51 53 52 dnl Checks for libraries. 54 #LX_CHECK_GLPK 55 #LX_CHECK_CPLEX 56 #LX_CHECK_SOPLEX 53 LX_CHECK_GLPK 54 LX_CHECK_CPLEX 55 LX_CHECK_SOPLEX 56 LX_CHECK_CLP 57 58 AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"]) 59 AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"]) 57 60 58 61 dnl Disable/enable building the demo programs. … … 114 117 echo 115 118 echo C++ compiler.................. : $CXX 116 echo C++ compiles flags............ : $ CXXFLAGS119 echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS 117 120 echo 118 #echo GLPK support.................. : $lx_glpk_found 119 #echo CPLEX support................. : $lx_cplex_found 120 #echo SOPLEX support................ : $lx_soplex_found 121 #echo 121 echo GLPK support.................. : $lx_glpk_found 122 echo CPLEX support................. : $lx_cplex_found 123 echo SOPLEX support................ : $lx_soplex_found 124 echo CLP support................... : $lx_clp_found 125 echo 122 126 echo Build demo programs........... : $enable_demo 123 127 echo Build additional tools........ : $enable_tools -
demo/CMakeLists.txt
r225 r474 1 INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR}) 1 INCLUDE_DIRECTORIES( 2 ${CMAKE_SOURCE_DIR} 3 ${CMAKE_BINARY_DIR} 4 ) 2 5 3 6 LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon) -
demo/arg_parser_demo.cc
r311 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
demo/graph_to_eps_demo.cc
r313 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 86 86 coords(coords). 87 87 title("Sample .eps figure"). 88 copyright("(C) 2003-200 8LEMON Project").88 copyright("(C) 2003-2009 LEMON Project"). 89 89 run(); 90 90 … … 93 93 coords(coords). 94 94 title("Sample .eps figure"). 95 copyright("(C) 2003-200 8LEMON Project").95 copyright("(C) 2003-2009 LEMON Project"). 96 96 absoluteNodeSizes().absoluteArcWidths(). 97 97 nodeScale(2).nodeSizes(sizes). … … 106 106 graphToEps(g,"graph_to_eps_demo_out_3_arr.eps"). 107 107 title("Sample .eps figure (with arrowheads)"). 108 copyright("(C) 2003-200 8LEMON Project").108 copyright("(C) 2003-2009 LEMON Project"). 109 109 absoluteNodeSizes().absoluteArcWidths(). 110 110 nodeColors(composeMap(palette,colors)). … … 133 133 graphToEps(g,"graph_to_eps_demo_out_4_par.eps"). 134 134 title("Sample .eps figure (parallel arcs)"). 135 copyright("(C) 2003-200 8LEMON Project").135 copyright("(C) 2003-2009 LEMON Project"). 136 136 absoluteNodeSizes().absoluteArcWidths(). 137 137 nodeShapes(shapes). … … 148 148 graphToEps(g,"graph_to_eps_demo_out_5_par_arr.eps"). 149 149 title("Sample .eps figure (parallel arcs and arrowheads)"). 150 copyright("(C) 2003-200 8LEMON Project").150 copyright("(C) 2003-2009 LEMON Project"). 151 151 absoluteNodeSizes().absoluteArcWidths(). 152 152 nodeScale(2).nodeSizes(sizes). … … 164 164 graphToEps(g,"graph_to_eps_demo_out_6_par_arr_a4.eps"). 165 165 title("Sample .eps figure (fits to A4)"). 166 copyright("(C) 2003-200 8LEMON Project").166 copyright("(C) 2003-2009 LEMON Project"). 167 167 scaleToA4(). 168 168 absoluteNodeSizes().absoluteArcWidths(). … … 194 194 scale(60). 195 195 title("Sample .eps figure (Palette demo)"). 196 copyright("(C) 2003-200 8LEMON Project").196 copyright("(C) 2003-2009 LEMON Project"). 197 197 coords(hcoords). 198 198 absoluteNodeSizes().absoluteArcWidths(). -
demo/lgf_demo.cc
r294 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
doc/CMakeLists.txt
r475 r476 15 15 COMMAND rm -rf gen-images 16 16 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 17 18 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 18 19 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 r367 67 67 ENABLED_SECTIONS = 68 68 MAX_INITIALIZER_LINES = 5 69 SHOW_USED_FILES = YES69 SHOW_USED_FILES = NO 70 70 SHOW_DIRECTORIES = YES 71 71 SHOW_FILES = YES -
doc/Makefile.am
r317 r337 15 15 16 16 DOC_EPS_IMAGES18 = \ 17 grid_graph.eps \ 17 18 nodeshape_0.eps \ 18 19 nodeshape_1.eps \ -
doc/coding_style.dox
r210 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
doc/dirs.dox
r318 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 72 72 \brief Auxiliary tools for implementation. 73 73 74 This directory contains some auxiliary classes for implementing graphs, 74 This directory contains some auxiliary classes for implementing graphs, 75 75 maps and some other classes. 76 76 As a user you typically don't have to deal with these files. -
doc/groups.dox
r318 r455 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 17 17 */ 18 18 19 namespace lemon { 20 19 21 /** 20 22 @defgroup datas Data Structures … … 61 63 62 64 /** 65 @defgroup graph_adaptors Adaptor Classes for Graphs 66 @ingroup graphs 67 \brief Adaptor classes for digraphs and graphs 68 69 This group contains several useful adaptor classes for digraphs and graphs. 70 71 The main parts of LEMON are the different graph structures, generic 72 graph algorithms, graph concepts, which couple them, and graph 73 adaptors. While the previous notions are more or less clear, the 74 latter one needs further explanation. Graph adaptors are graph classes 75 which serve for considering graph structures in different ways. 76 77 A short example makes this much clearer. Suppose that we have an 78 instance \c g of a directed graph type, say ListDigraph and an algorithm 79 \code 80 template <typename Digraph> 81 int algorithm(const Digraph&); 82 \endcode 83 is needed to run on the reverse oriented graph. It may be expensive 84 (in time or in memory usage) to copy \c g with the reversed 85 arcs. In this case, an adaptor class is used, which (according 86 to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph. 87 The adaptor uses the original digraph structure and digraph operations when 88 methods of the reversed oriented graph are called. This means that the adaptor 89 have minor memory usage, and do not perform sophisticated algorithmic 90 actions. The purpose of it is to give a tool for the cases when a 91 graph have to be used in a specific alteration. If this alteration is 92 obtained by a usual construction like filtering the node or the arc set or 93 considering a new orientation, then an adaptor is worthwhile to use. 94 To come back to the reverse oriented graph, in this situation 95 \code 96 template<typename Digraph> class ReverseDigraph; 97 \endcode 98 template class can be used. The code looks as follows 99 \code 100 ListDigraph g; 101 ReverseDigraph<ListDigraph> rg(g); 102 int result = algorithm(rg); 103 \endcode 104 During running the algorithm, the original digraph \c g is untouched. 105 This techniques give rise to an elegant code, and based on stable 106 graph adaptors, complex algorithms can be implemented easily. 107 108 In flow, circulation and matching problems, the residual 109 graph is of particular importance. Combining an adaptor implementing 110 this with shortest path algorithms or minimum mean cycle algorithms, 111 a range of weighted and cardinality optimization algorithms can be 112 obtained. For other examples, the interested user is referred to the 113 detailed documentation of particular adaptors. 114 115 The behavior of graph adaptors can be very different. Some of them keep 116 capabilities of the original graph while in other cases this would be 117 meaningless. This means that the concepts that they meet depend 118 on the graph adaptor, and the wrapped graph. 119 For example, if an arc of a reversed digraph is deleted, this is carried 120 out by deleting the corresponding arc of the original digraph, thus the 121 adaptor modifies the original digraph. 122 However in case of a residual digraph, this operation has no sense. 123 124 Let us stand one more example here to simplify your work. 125 ReverseDigraph has constructor 126 \code 127 ReverseDigraph(Digraph& digraph); 128 \endcode 129 This means that in a situation, when a <tt>const %ListDigraph&</tt> 130 reference to a graph is given, then it have to be instantiated with 131 <tt>Digraph=const %ListDigraph</tt>. 132 \code 133 int algorithm1(const ListDigraph& g) { 134 ReverseDigraph<const ListDigraph> rg(g); 135 return algorithm2(rg); 136 } 137 \endcode 138 */ 139 140 /** 63 141 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs 64 142 @ingroup graphs … … 89 167 90 168 This group describes maps that are specifically designed to assign 91 values to the nodes and arcs of graphs. 169 values to the nodes and arcs/edges of graphs. 170 171 If you are looking for the standard graph maps (\c NodeMap, \c ArcMap, 172 \c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts". 92 173 */ 93 174 … … 100 181 maps from other maps. 101 182 102 Most of them are \ref lemon::concepts::ReadMap "read-only maps".183 Most of them are \ref concepts::ReadMap "read-only maps". 103 184 They can make arithmetic and logical operations between one or two maps 104 185 (negation, shifting, addition, multiplication, logical 'and', 'or', … … 202 283 \brief Common graph search algorithms. 203 284 204 This group describes the common graph search algorithms like205 Breadth-First Search (BFS) and Depth-First Search (DFS).285 This group describes the common graph search algorithms, namely 286 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS). 206 287 */ 207 288 … … 211 292 \brief Algorithms for finding shortest paths. 212 293 213 This group describes the algorithms for finding shortest paths in graphs. 294 This group describes the algorithms for finding shortest paths in digraphs. 295 296 - \ref Dijkstra algorithm for finding shortest paths from a source node 297 when all arc lengths are non-negative. 298 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths 299 from a source node when arc lenghts can be either positive or negative, 300 but the digraph should not contain directed cycles with negative total 301 length. 302 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms 303 for solving the \e all-pairs \e shortest \e paths \e problem when arc 304 lenghts can be either positive or negative, but the digraph should 305 not contain directed cycles with negative total length. 306 - \ref Suurballe A successive shortest path algorithm for finding 307 arc-disjoint paths between two nodes having minimum total length. 214 308 */ 215 309 … … 222 316 feasible circulations. 223 317 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] 318 The \e maximum \e flow \e problem is to find a flow of maximum value between 319 a single source and a single target. Formally, there is a \f$G=(V,A)\f$ 320 digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and 321 \f$s, t \in V\f$ source and target nodes. 322 A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the 323 following optimization problem. 324 325 \f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f] 326 \f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a) 327 \qquad \forall v\in V\setminus\{s,t\} \f] 328 \f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f] 234 329 235 330 LEMON 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 the242 fastest method to compute the maximum flow. All impelementations243 provides functions to query the minimum cut, which is the dual linear244 pro gramming 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 336 In most cases the \ref Preflow "Preflow" algorithm provides the 337 fastest method for computing a maximum flow. All implementations 338 provides functions to also query the minimum cut, which is the dual 339 problem of the maximum flow. 245 340 */ 246 341 … … 253 348 This group describes the algorithms for finding minimum cost flows and 254 349 circulations. 350 351 The \e minimum \e cost \e flow \e problem is to find a feasible flow of 352 minimum total cost from a set of supply nodes to a set of demand nodes 353 in a network with capacity constraints and arc costs. 354 Formally, let \f$G=(V,A)\f$ be a digraph, 355 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and 356 upper bounds for the flow values on the arcs, 357 \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow 358 on the arcs, and 359 \f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values 360 of the nodes. 361 A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of 362 the following optimization problem. 363 364 \f[ \min\sum_{a\in A} f(a) cost(a) \f] 365 \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) = 366 supply(v) \qquad \forall v\in V \f] 367 \f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f] 368 369 LEMON contains several algorithms for solving minimum cost flow problems: 370 - \ref CycleCanceling Cycle-canceling algorithms. 371 - \ref CapacityScaling Successive shortest path algorithm with optional 372 capacity scaling. 373 - \ref CostScaling Push-relabel and augment-relabel algorithms based on 374 cost scaling. 375 - \ref NetworkSimplex Primal network simplex algorithm with various 376 pivot strategies. 255 377 */ 256 378 … … 263 385 This group describes the algorithms for finding minimum cut in graphs. 264 386 265 The minimum cutproblem is to find a non-empty and non-complete266 \f$X\f$ subset of the vertices with minimum overall capacity on267 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an268 \f$c _a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum387 The \e minimum \e cut \e problem is to find a non-empty and non-complete 388 \f$X\f$ subset of the nodes with minimum overall capacity on 389 outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a 390 \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum 269 391 cut is the \f$X\f$ solution of the next optimization problem: 270 392 271 393 \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] 273 395 274 396 LEMON contains several algorithms related to minimum cut problems: 275 397 276 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculateminimum cut277 in directed graphs 278 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to279 calculat e minimum cut in undirected graphs280 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all281 pairs minimum cut in undirected graphs398 - \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. 282 404 283 405 If you want to find minimum cut just between two distinict nodes, 284 please see the \ref max_flow "Maximum Flow page".406 see the \ref max_flow "maximum flow problem". 285 407 */ 286 408 … … 321 443 graphs. The matching problems in bipartite graphs are generally 322 444 easier than in general graphs. The goal of the matching optimization 323 can be thefinding maximum cardinality, maximum weight or minimum cost445 can be finding maximum cardinality, maximum weight or minimum cost 324 446 matching. The search can be constrained to find perfect or 325 447 maximum cardinality matching. 326 448 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 449 The matching algorithms implemented in LEMON: 450 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm 451 for calculating maximum cardinality matching in bipartite graphs. 452 - \ref PrBipartiteMatching Push-relabel algorithm 453 for calculating maximum cardinality matching in bipartite graphs. 454 - \ref MaxWeightedBipartiteMatching 455 Successive shortest path algorithm for calculating maximum weighted 456 matching and maximum weighted bipartite matching in bipartite graphs. 457 - \ref MinCostMaxBipartiteMatching 458 Successive shortest path algorithm for calculating minimum cost maximum 459 matching in bipartite graphs. 460 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating 461 maximum cardinality matching in general graphs. 462 - \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating 463 maximum weighted matching in general graphs. 464 - \ref MaxWeightedPerfectMatching 465 Edmond's blossom shrinking algorithm for calculating maximum weighted 466 perfect matching in general graphs. 347 467 348 468 \image html bipartite_matching.png … … 356 476 357 477 This group describes the algorithms for finding a minimum cost spanning 358 tree in a graph 478 tree in a graph. 359 479 */ 360 480 … … 465 585 466 586 /** 467 @defgroup lemon_io LEMON Input-Output587 @defgroup lemon_io LEMON Graph Format 468 588 @ingroup io_group 469 589 \brief Reading and writing LEMON Graph Format. … … 480 600 This group describes general \c EPS drawing methods and special 481 601 graph exporting tools. 602 */ 603 604 /** 605 @defgroup dimacs_group DIMACS format 606 @ingroup io_group 607 \brief Read and write files in DIMACS format 608 609 Tools to read a digraph from or write it to a file in DIMACS format data. 610 */ 611 612 /** 613 @defgroup nauty_group NAUTY Format 614 @ingroup io_group 615 \brief Read \e Nauty format 616 617 Tool to read graphs from \e Nauty format data. 482 618 */ 483 619 … … 531 667 \anchor demoprograms 532 668 533 @defgroup demos Demo programs669 @defgroup demos Demo Programs 534 670 535 671 Some demo programs are listed here. Their full source codes can be found in … … 541 677 542 678 /** 543 @defgroup tools Standalone utility applications679 @defgroup tools Standalone Utility Applications 544 680 545 681 Some utility applications are listed here. … … 549 685 */ 550 686 687 } -
doc/lgf.dox
r313 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
doc/license.dox
r209 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
doc/mainpage.dox
r314 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
doc/migration.dox
r314 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 26 26 27 27 Many of these changes adjusted automatically by the 28 <tt> script/lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual28 <tt>lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual 29 29 update are typeset <b>boldface</b>. 30 30 … … 54 54 55 55 \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 58 strings, comments etc. as well as in all LEMON specific identifiers. 59 So use the script carefully and make a backup copy of your source files 60 before applying the script to them.</b> 59 61 60 62 \section migration-lgf LGF tools -
doc/named-param.dox
r269 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
doc/namespaces.dox
r209 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
doc/template.h
r209 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/CMakeLists.txt
r225 r474 1 INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR}) 1 INCLUDE_DIRECTORIES( 2 ${CMAKE_SOURCE_DIR} 3 ${CMAKE_BINARY_DIR} 4 ) 2 5 3 ADD_LIBRARY(lemon 6 CONFIGURE_FILE( 7 ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake 8 ${CMAKE_CURRENT_BINARY_DIR}/config.h 9 ) 10 11 SET(LEMON_SOURCES 4 12 arg_parser.cc 5 13 base.cc 6 14 color.cc 15 lp_base.cc 16 lp_skeleton.cc 7 17 random.cc) 18 19 IF(HAVE_GLPK) 20 SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc) 21 INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR}) 22 IF(WIN32) 23 INSTALL(FILES ${GLPK_BIN_DIR}/glpk.dll DESTINATION bin) 24 INSTALL(FILES ${GLPK_BIN_DIR}/libltdl3.dll DESTINATION bin) 25 INSTALL(FILES ${GLPK_BIN_DIR}/zlib1.dll DESTINATION bin) 26 ENDIF(WIN32) 27 ENDIF(HAVE_GLPK) 28 29 ADD_LIBRARY(lemon ${LEMON_SOURCES}) 8 30 9 31 INSTALL( -
lemon/Makefile.am
r259 r469 8 8 9 9 lemon_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 14 16 15 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) 16 #lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS) 17 18 lemon_libemon_la_CXXFLAGS = \ 19 $(GLPK_CFLAGS) \ 20 $(CPLEX_CFLAGS) \ 21 $(SOPLEX_CXXFLAGS) \ 22 $(CLP_CXXFLAGS) 23 24 lemon_libemon_la_LDFLAGS = \ 25 $(GLPK_LIBS) \ 26 $(CPLEX_LIBS) \ 27 $(SOPLEX_LIBS) \ 28 $(CLP_LIBS) 29 30 if HAVE_GLPK 31 lemon_libemon_la_SOURCES += lemon/glpk.cc 32 endif 33 34 if HAVE_CPLEX 35 lemon_libemon_la_SOURCES += lemon/cplex.cc 36 endif 37 38 if HAVE_SOPLEX 39 lemon_libemon_la_SOURCES += lemon/soplex.cc 40 endif 41 42 if HAVE_CLP 43 lemon_libemon_la_SOURCES += lemon/clp.cc 44 endif 17 45 18 46 lemon_HEADERS += \ 19 lemon/arg_parser.h \ 47 lemon/adaptors.h \ 48 lemon/arg_parser.h \ 20 49 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 \ 24 55 lemon/concept_check.h \ 25 56 lemon/counter.h \ 26 57 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 \ 30 65 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 \ 32 71 lemon/kruskal.h \ 72 lemon/hao_orlin.h \ 33 73 lemon/lgf_reader.h \ 34 74 lemon/lgf_writer.h \ 35 75 lemon/list_graph.h \ 76 lemon/lp.h \ 77 lemon/lp_base.h \ 78 lemon/lp_skeleton.h \ 79 lemon/list_graph.h \ 36 80 lemon/maps.h \ 37 81 lemon/math.h \ 82 lemon/max_matching.h \ 83 lemon/nauty_reader.h \ 38 84 lemon/path.h \ 39 lemon/random.h \ 85 lemon/preflow.h \ 86 lemon/radix_sort.h \ 87 lemon/random.h \ 40 88 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 \ 43 93 lemon/unionfind.h 44 94 … … 47 97 lemon/bits/array_map.h \ 48 98 lemon/bits/base_extender.h \ 49 99 lemon/bits/bezier.h \ 50 100 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 \ 52 104 lemon/bits/graph_extender.h \ 53 105 lemon/bits/map_extender.h \ 54 106 lemon/bits/path_dump.h \ 107 lemon/bits/solver_bits.h \ 55 108 lemon/bits/traits.h \ 109 lemon/bits/variant.h \ 56 110 lemon/bits/vector_map.h 57 111 -
lemon/arg_parser.cc
r311 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/arg_parser.h
r311 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/assert.h
r290 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/base.cc
r220 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bfs.h
r301 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 120 120 /// 121 121 ///\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. 129 123 #ifdef DOXYGEN 130 124 template <typename GR, … … 152 146 typedef PredMapPath<Digraph, PredMap> Path; 153 147 154 ///The traits class.148 ///The \ref BfsDefaultTraits "traits class" of the algorithm. 155 149 typedef TR Traits; 156 150 … … 214 208 typedef Bfs Create; 215 209 216 ///\name Named template parameters210 ///\name Named Template Parameters 217 211 218 212 ///@{ … … 232 226 ///\ref named-templ-param "Named parameter" for setting 233 227 ///PredMap type. 228 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 234 229 template <class T> 235 230 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > { … … 251 246 ///\ref named-templ-param "Named parameter" for setting 252 247 ///DistMap type. 248 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 253 249 template <class T> 254 250 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > { … … 270 266 ///\ref named-templ-param "Named parameter" for setting 271 267 ///ReachedMap type. 268 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 272 269 template <class T> 273 270 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { … … 289 286 ///\ref named-templ-param "Named parameter" for setting 290 287 ///ProcessedMap type. 288 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 291 289 template <class T> 292 290 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { … … 341 339 342 340 ///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. 346 345 ///\return <tt> (*this) </tt> 347 346 Bfs &predMap(PredMap &m) … … 358 357 359 358 ///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. 363 363 ///\return <tt> (*this) </tt> 364 364 Bfs &reachedMap(ReachedMap &m) … … 375 375 376 376 ///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. 380 381 ///\return <tt> (*this) </tt> 381 382 Bfs &processedMap(ProcessedMap &m) … … 393 394 ///Sets the map that stores the distances of the nodes calculated by 394 395 ///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. 398 400 ///\return <tt> (*this) </tt> 399 401 Bfs &distMap(DistMap &m) … … 409 411 public: 410 412 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. 420 420 421 421 ///@{ 422 422 423 ///\brief Initializes the internal data structures. 424 /// 423 425 ///Initializes the internal data structures. 424 425 ///Initializes the internal data structures.426 ///427 426 void init() 428 427 { … … 558 557 } 559 558 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. 565 563 bool emptyQueue() const { return _queue_tail==_queue_head; } 566 564 567 565 ///Returns the number of the nodes to be processed. 568 566 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. 570 569 int queueSize() const { return _queue_head-_queue_tail; } 571 570 … … 732 731 733 732 ///\name Query Functions 734 ///The result of the %BFS algorithm can be obtained using these733 ///The results of the BFS algorithm can be obtained using these 735 734 ///functions.\n 736 ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()737 /// "start()" must be calledbefore using them.735 ///Either \ref run(Node) "run()" or \ref start() should be called 736 ///before using them. 738 737 739 738 ///@{ … … 743 742 ///Returns the shortest path to a node. 744 743 /// 745 ///\warning \c t should be reach ablefrom the root(s).746 /// 747 ///\pre Either \ref run( ) or \ref start() must be called before748 /// 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. 749 748 Path path(Node t) const { return Path(*G, *_pred, t); } 750 749 … … 753 752 ///Returns the distance of a node from the root(s). 754 753 /// 755 ///\warning If node \c v is not reach ablefrom the root(s), then754 ///\warning If node \c v is not reached from the root(s), then 756 755 ///the return value of this function is undefined. 757 756 /// 758 ///\pre Either \ref run( ) or \ref start() must be called before759 /// using this function.757 ///\pre Either \ref run(Node) "run()" or \ref init() 758 ///must be called before using this function. 760 759 int dist(Node v) const { return (*_dist)[v]; } 761 760 … … 764 763 ///This function returns the 'previous arc' of the shortest path 765 764 ///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 v767 ///is not reach ablefrom 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. 768 767 /// 769 768 ///The shortest path tree used here is equal to the shortest path 770 769 ///tree used in \ref predNode(). 771 770 /// 772 ///\pre Either \ref run( ) or \ref start() must be called before773 /// using this function.771 ///\pre Either \ref run(Node) "run()" or \ref init() 772 ///must be called before using this function. 774 773 Arc predArc(Node v) const { return (*_pred)[v];} 775 774 … … 778 777 ///This function returns the 'previous node' of the shortest path 779 778 ///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 INVALID781 ///if \c v is not reach ablefrom 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. 782 781 /// 783 782 ///The shortest path tree used here is equal to the shortest path 784 783 ///tree used in \ref predArc(). 785 784 /// 786 ///\pre Either \ref run( ) or \ref start() must be called before787 /// using this function.785 ///\pre Either \ref run(Node) "run()" or \ref init() 786 ///must be called before using this function. 788 787 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 789 788 G->source((*_pred)[v]); } … … 795 794 ///of the nodes calculated by the algorithm. 796 795 /// 797 ///\pre Either \ref run( )or \ref init()796 ///\pre Either \ref run(Node) "run()" or \ref init() 798 797 ///must be called before using this function. 799 798 const DistMap &distMap() const { return *_dist;} … … 805 804 ///arcs, which form the shortest path tree. 806 805 /// 807 ///\pre Either \ref run( )or \ref init()806 ///\pre Either \ref run(Node) "run()" or \ref init() 808 807 ///must be called before using this function. 809 808 const PredMap &predMap() const { return *_pred;} 810 809 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() 815 815 ///must be called before using this function. 816 816 bool reached(Node v) const { return (*_reached)[v]; } … … 958 958 /// This auxiliary class is created to implement the 959 959 /// \ref bfs() "function-type interface" of \ref Bfs algorithm. 960 /// It does not have own \ref run( ) method, it uses the functions961 /// 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. 962 962 /// 963 963 /// This class should only be used through the \ref bfs() function, … … 1179 1179 /// bool reached = bfs(g).path(p).dist(d).run(s,t); 1180 1180 ///\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()" 1182 1182 ///to the end of the parameter list. 1183 1183 ///\sa BfsWizard … … 1365 1365 typedef BfsVisit Create; 1366 1366 1367 /// \name Named template parameters1367 /// \name Named Template Parameters 1368 1368 1369 1369 ///@{ … … 1407 1407 /// 1408 1408 /// 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. 1412 1413 /// \return <tt> (*this) </tt> 1413 1414 BfsVisit &reachedMap(ReachedMap &m) { … … 1422 1423 public: 1423 1424 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. 1434 1432 1435 1433 /// @{ … … 1731 1729 1732 1730 /// \name Query Functions 1733 /// The result of the %BFS algorithm can be obtained using these1731 /// The results of the BFS algorithm can be obtained using these 1734 1732 /// functions.\n 1735 /// Either \ref lemon::BfsVisit::run() "run()" or1736 /// \ref lemon::BfsVisit::start() "start()" must be called before1737 /// using them. 1733 /// Either \ref run(Node) "run()" or \ref start() should be called 1734 /// before using them. 1735 1738 1736 ///@{ 1739 1737 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() 1744 1743 /// must be called before using this function. 1745 bool reached(Node v) { return (*_reached)[v]; }1744 bool reached(Node v) const { return (*_reached)[v]; } 1746 1745 1747 1746 ///@} -
lemon/bin_heap.h
r209 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bits/alteration_notifier.h
r314 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 36 36 // a container. 37 37 // 38 // The simple graph 's can be refered as two containers, onenode container39 // and one edge container. But they are not standard containersthey40 // does not store values directly they are just key continars for more41 // value containers which are thenode and edge maps.42 // 43 // The graph's node and edge sets can be changed as we add or erase38 // 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 44 44 // nodes and edges in the graph. LEMON would like to handle easily 45 45 // that the node and edge maps should contain values for all nodes or 46 46 // edges. If we want to check on every indicing if the map contains 47 47 // the current indicing key that cause a drawback in the performance 48 // in the library. We use another solution we notify all maps about48 // in the library. We use another solution: we notify all maps about 49 49 // an alteration in the graph, which cause only drawback on the 50 50 // alteration of the graph. 51 51 // 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. 56 57 // 57 58 // For the proper functonality of this class, we should notify it 58 // about each alteration in the container. The alterations have four type 59 // a s \e add(), \e erase(), \e build() and \e clear(). The \e add() and60 // \e erase() signalsthat only one or few items added or erased to or61 // from the graph. If all items are erased from the graph or from an empty62 // graph a new graph is buildedthen it can be signaled with the59 // 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 63 64 // clear() and build() members. Important rule that if we erase items 64 // from graph we should first signal the alteration and after that erase65 // from graphs we should first signal the alteration and after that erase 65 66 // them from the container, on the other way on item addition we should 66 67 // first extend the container and just after that signal the alteration. 67 68 // 68 69 // The alteration can be observed with a class inherited from the 69 // \eObserverBase nested class. The signals can be handled with70 // ObserverBase nested class. The signals can be handled with 70 71 // overriding the virtual functions defined in the base class. The 71 72 // observer base can be attached to the notifier with the 72 // \eattach() member and can be detached with detach() function. The73 // attach() member and can be detached with detach() function. The 73 74 // alteration handlers should not call any function which signals 74 75 // an other alteration in the same notifier and should not 75 76 // detach any observer from the notifier. 76 77 // 77 // Alteration observers try to be exception safe. If an \eadd() or78 // a \eclear() function throws an exception then the remaining78 // Alteration observers try to be exception safe. If an add() or 79 // a clear() function throws an exception then the remaining 79 80 // 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 throw82 // exception. Actullay, it can be throw only \ref ImmediateDetach83 // exceptionwhich detach the observer from the notifier.84 // 85 // There are some placewhen the alteration observing is not completly81 // 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 86 87 // reliable. If we want to carry out the node degree in the graph 87 // as in the \ref InDegMap and we use the reverse Edge that cause88 // as in the \ref InDegMap and we use the reverseArc(), then it cause 88 89 // unreliable functionality. Because the alteration observing signals 89 // only erasing and adding but not the reversing it will stores bad90 // degrees. The sub graph adaptors cannot signal the alterations because91 // just a setting in the filter map can modify the graph and this cannot92 // 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. 93 94 // 94 95 // \param _Container The container which is observed. … … 104 105 typedef _Item Item; 105 106 106 // \brief Exception which can be called from \eclear() and107 // \eerase().108 // 109 // From the \e clear() and \eerase() function only this107 // \brief Exception which can be called from clear() and 108 // erase(). 109 // 110 // From the clear() and erase() function only this 110 111 // exception is allowed to throw. The exception immediatly 111 112 // detaches the current observer from the notifier. Because the 112 // \e clear() and \eerase() should not throw other exceptions113 // clear() and erase() should not throw other exceptions 113 114 // it can be used to invalidate the observer. 114 115 struct ImmediateDetach {}; … … 122 123 // The observer interface contains some pure virtual functions 123 124 // 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. 126 126 // 127 127 // The build() and clear() members are to notify the observer -
lemon/bits/array_map.h
r314 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 37 37 // \brief Graph map based on the array storage. 38 38 // 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. 43 42 // 44 // The template parameters are the Graph the current Item type and43 // The template parameters are the Graph, the current Item type and 45 44 // the Value type of the map. 46 45 template <typename _Graph, typename _Item, typename _Value> … … 48 47 : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase { 49 48 public: 50 // The graph type of the maps.49 // The graph type. 51 50 typedef _Graph Graph; 52 // The item type of the map.51 // The item type. 53 52 typedef _Item Item; 54 53 // The reference map tag. 55 54 typedef True ReferenceMapTag; 56 55 57 // The key type of the map s.56 // The key type of the map. 58 57 typedef _Item Key; 59 58 // The value type of the map. … … 201 200 // \brief Adds a new key to the map. 202 201 // 203 // It adds a new key to the map. It called by the observer notifier202 // It adds a new key to the map. It is called by the observer notifier 204 203 // and it overrides the add() member function of the observer base. 205 204 virtual void add(const Key& key) { … … 229 228 // \brief Adds more new keys to the map. 230 229 // 231 // It adds more new keys to the map. It called by the observer notifier230 // It adds more new keys to the map. It is called by the observer notifier 232 231 // and it overrides the add() member function of the observer base. 233 232 virtual void add(const std::vector<Key>& keys) { … … 273 272 // \brief Erase a key from the map. 274 273 // 275 // Erase a key from the map. It called by the observer notifier274 // Erase a key from the map. It is called by the observer notifier 276 275 // and it overrides the erase() member function of the observer base. 277 276 virtual void erase(const Key& key) { … … 282 281 // \brief Erase more keys from the map. 283 282 // 284 // Erase more keys from the map. It called by the observer notifier283 // Erase more keys from the map. It is called by the observer notifier 285 284 // and it overrides the erase() member function of the observer base. 286 285 virtual void erase(const std::vector<Key>& keys) { … … 291 290 } 292 291 293 // \brief Build es the map.294 // 295 // It build es the map. Itcalled by the observer notifier292 // \brief Builds the map. 293 // 294 // It builds the map. It is called by the observer notifier 296 295 // and it overrides the build() member function of the observer base. 297 296 virtual void build() { … … 307 306 // \brief Clear the map. 308 307 // 309 // It erase all items from the map. It called by the observer notifier308 // It erase all items from the map. It is called by the observer notifier 310 309 // and it overrides the clear() member function of the observer base. 311 310 virtual void clear() { -
lemon/bits/base_extender.h
r314 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 31 31 //\ingroup digraphbits 32 32 //\file 33 //\brief Extenders for the digraph types33 //\brief Extenders for the graph types 34 34 namespace lemon { 35 35 -
lemon/bits/bezier.h
r314 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bits/default_map.h
r314 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bits/enable_if.h
r314 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bits/graph_extender.h
r314 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 30 30 //\ingroup graphbits 31 31 //\file 32 //\brief Extenders for the digraph types32 //\brief Extenders for the graph types 33 33 namespace lemon { 34 34 35 35 // \ingroup graphbits 36 36 // 37 // \brief Extender for the Digraphs37 // \brief Extender for the digraph implementations 38 38 template <typename Base> 39 39 class DigraphExtender : public Base { -
lemon/bits/map_extender.h
r314 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bits/path_dump.h
r209 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bits/traits.h
r314 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 219 219 220 220 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> 221 234 struct EdgeNumTagIndicator { 222 235 static const bool value = false; … … 232 245 233 246 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> 234 260 struct FindEdgeTagIndicator { 235 261 static const bool value = false; -
lemon/bits/vector_map.h
r314 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 39 39 // \brief Graph map based on the std::vector storage. 40 40 // 41 // The VectorMap template class is graph map structure what42 // automatically updates the map when a key is added to or erased from43 // the map. This map type uses thestd::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. 44 44 // 45 45 // \tparam _Graph The graph this map is attached to. … … 170 170 // \brief Adds a new key to the map. 171 171 // 172 // It adds a new key to the map. It called by the observer notifier172 // It adds a new key to the map. It is called by the observer notifier 173 173 // and it overrides the add() member function of the observer base. 174 174 virtual void add(const Key& key) { … … 181 181 // \brief Adds more new keys to the map. 182 182 // 183 // It adds more new keys to the map. It called by the observer notifier183 // It adds more new keys to the map. It is called by the observer notifier 184 184 // and it overrides the add() member function of the observer base. 185 185 virtual void add(const std::vector<Key>& keys) { … … 196 196 // \brief Erase a key from the map. 197 197 // 198 // Erase a key from the map. It called by the observer notifier198 // Erase a key from the map. It is called by the observer notifier 199 199 // and it overrides the erase() member function of the observer base. 200 200 virtual void erase(const Key& key) { … … 204 204 // \brief Erase more keys from the map. 205 205 // 206 // Erase more keys from the map. Itcalled by the observer notifier206 // It erases more keys from the map. It is called by the observer notifier 207 207 // and it overrides the erase() member function of the observer base. 208 208 virtual void erase(const std::vector<Key>& keys) { … … 212 212 } 213 213 214 // \brief Build esthe map.215 // 216 // It build es the map. Itcalled by the observer notifier214 // \brief Build the map. 215 // 216 // It builds the map. It is called by the observer notifier 217 217 // and it overrides the build() member function of the observer base. 218 218 virtual void build() { … … 224 224 // \brief Clear the map. 225 225 // 226 // It erase all items from the map. Itcalled by the observer notifier226 // It erases all items from the map. It is called by the observer notifier 227 227 // and it overrides the clear() member function of the observer base. 228 228 virtual void clear() { -
lemon/color.cc
r209 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/color.h
r313 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/concept_check.h
r285 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/concepts/digraph.h
r263 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/concepts/graph.h
r263 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/concepts/graph_components.h
r313 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/concepts/heap.h
r290 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/concepts/maps.h
r314 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/concepts/path.h
r281 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/config.h.in
r1 r459 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 1 7 /* Define to 1 if you have CPLEX. */ 2 8 #undef HAVE_CPLEX … … 4 10 /* Define to 1 if you have GLPK. */ 5 11 #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
r429 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/counter.h
r209 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/dfs.h
r319 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 120 120 /// 121 121 ///\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. 129 123 #ifdef DOXYGEN 130 124 template <typename GR, … … 152 146 typedef PredMapPath<Digraph, PredMap> Path; 153 147 154 ///The traits class.148 ///The \ref DfsDefaultTraits "traits class" of the algorithm. 155 149 typedef TR Traits; 156 150 … … 231 225 ///\ref named-templ-param "Named parameter" for setting 232 226 ///PredMap type. 227 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 233 228 template <class T> 234 229 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > { … … 250 245 ///\ref named-templ-param "Named parameter" for setting 251 246 ///DistMap type. 247 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 252 248 template <class T> 253 249 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > { … … 269 265 ///\ref named-templ-param "Named parameter" for setting 270 266 ///ReachedMap type. 267 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 271 268 template <class T> 272 269 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > { … … 288 285 ///\ref named-templ-param "Named parameter" for setting 289 286 ///ProcessedMap type. 287 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 290 288 template <class T> 291 289 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > { … … 339 337 340 338 ///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. 344 343 ///\return <tt> (*this) </tt> 345 344 Dfs &predMap(PredMap &m) … … 356 355 357 356 ///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. 361 361 ///\return <tt> (*this) </tt> 362 362 Dfs &reachedMap(ReachedMap &m) … … 373 373 374 374 ///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. 378 379 ///\return <tt> (*this) </tt> 379 380 Dfs &processedMap(ProcessedMap &m) … … 391 392 ///Sets the map that stores the distances of the nodes calculated by 392 393 ///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. 396 398 ///\return <tt> (*this) </tt> 397 399 Dfs &distMap(DistMap &m) … … 407 409 public: 408 410 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. 418 419 419 420 ///@{ 420 421 422 ///\brief Initializes the internal data structures. 423 /// 421 424 ///Initializes the internal data structures. 422 423 ///Initializes the internal data structures.424 ///425 425 void init() 426 426 { … … 439 439 ///Adds a new source node to the set of nodes to be processed. 440 440 /// 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.) 446 445 void addSource(Node s) 447 446 { … … 507 506 } 508 507 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). 514 512 bool emptyQueue() const { return _stack_head<0; } 515 513 516 514 ///Returns the number of the nodes to be processed. 517 515 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). 519 518 int queueSize() const { return _stack_head+1; } 520 519 … … 638 637 /// 639 638 ///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. 642 641 /// 643 642 ///\note <tt>d.run()</tt> is just a shortcut of the following code. … … 664 663 665 664 ///\name Query Functions 666 ///The result of the %DFS algorithm can be obtained using these665 ///The results of the DFS algorithm can be obtained using these 667 666 ///functions.\n 668 ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()669 /// "start()" must be calledbefore using them.667 ///Either \ref run(Node) "run()" or \ref start() should be called 668 ///before using them. 670 669 671 670 ///@{ … … 675 674 ///Returns the DFS path to a node. 676 675 /// 677 ///\warning \c t should be reach able from the root.678 /// 679 ///\pre Either \ref run( ) or \ref start() must be called before680 /// 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. 681 680 Path path(Node t) const { return Path(*G, *_pred, t); } 682 681 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 reach able from the root, then682 ///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 688 687 ///the return value of this function is undefined. 689 688 /// 690 ///\pre Either \ref run( ) or \ref start() must be called before691 /// using this function.689 ///\pre Either \ref run(Node) "run()" or \ref init() 690 ///must be called before using this function. 692 691 int dist(Node v) const { return (*_dist)[v]; } 693 692 … … 695 694 696 695 ///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 the698 ///root to \c v. It is \c INVALID 699 /// if \c v is not reachable from theroot(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. 700 699 /// 701 700 ///The %DFS tree used here is equal to the %DFS tree used in 702 701 ///\ref predNode(). 703 702 /// 704 ///\pre Either \ref run( ) or \ref start() must be called before using705 /// this function.703 ///\pre Either \ref run(Node) "run()" or \ref init() 704 ///must be called before using this function. 706 705 Arc predArc(Node v) const { return (*_pred)[v];} 707 706 … … 710 709 ///This function returns the 'previous node' of the %DFS 711 710 ///tree for the node \c v, i.e. it returns the last but one node 712 ///from a %DFS path from theroot to \c v. It is \c INVALID713 ///if \c v is not reach ablefrom 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. 714 713 /// 715 714 ///The %DFS tree used here is equal to the %DFS tree used in 716 715 ///\ref predArc(). 717 716 /// 718 ///\pre Either \ref run( ) or \ref start() must be called before719 /// using this function.717 ///\pre Either \ref run(Node) "run()" or \ref init() 718 ///must be called before using this function. 720 719 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 721 720 G->source((*_pred)[v]); } … … 727 726 ///distances of the nodes calculated by the algorithm. 728 727 /// 729 ///\pre Either \ref run( )or \ref init()728 ///\pre Either \ref run(Node) "run()" or \ref init() 730 729 ///must be called before using this function. 731 730 const DistMap &distMap() const { return *_dist;} … … 737 736 ///arcs, which form the DFS tree. 738 737 /// 739 ///\pre Either \ref run( )or \ref init()738 ///\pre Either \ref run(Node) "run()" or \ref init() 740 739 ///must be called before using this function. 741 740 const PredMap &predMap() const { return *_pred;} 742 741 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() 747 747 ///must be called before using this function. 748 748 bool reached(Node v) const { return (*_reached)[v]; } … … 890 890 /// This auxiliary class is created to implement the 891 891 /// \ref dfs() "function-type interface" of \ref Dfs algorithm. 892 /// It does not have own \ref run( ) method, it uses the functions893 /// 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. 894 894 /// 895 895 /// This class should only be used through the \ref dfs() function, … … 1111 1111 /// bool reached = dfs(g).path(p).dist(d).run(s,t); 1112 1112 ///\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()" 1115 1114 ///to the end of the parameter list. 1116 1115 ///\sa DfsWizard … … 1310 1309 typedef DfsVisit Create; 1311 1310 1312 /// \name Named template parameters1311 /// \name Named Template Parameters 1313 1312 1314 1313 ///@{ … … 1352 1351 /// 1353 1352 /// 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. 1357 1357 /// \return <tt> (*this) </tt> 1358 1358 DfsVisit &reachedMap(ReachedMap &m) { … … 1367 1367 public: 1368 1368 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. 1379 1377 1380 1378 /// @{ … … 1392 1390 } 1393 1391 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.) 1403 1400 void addSource(Node s) 1404 1401 { … … 1414 1411 } else { 1415 1412 _visitor->leave(s); 1413 _visitor->stop(s); 1416 1414 } 1417 1415 } … … 1590 1588 /// 1591 1589 /// 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. 1594 1592 /// 1595 1593 /// \note <tt>d.run()</tt> is just a shortcut of the following code. … … 1616 1614 1617 1615 /// \name Query Functions 1618 /// The result of the %DFS algorithm can be obtained using these1616 /// The results of the DFS algorithm can be obtained using these 1619 1617 /// functions.\n 1620 /// Either \ref lemon::DfsVisit::run() "run()" or1621 /// \ref lemon::DfsVisit::start() "start()" must be called before1622 /// using them. 1618 /// Either \ref run(Node) "run()" or \ref start() should be called 1619 /// before using them. 1620 1623 1621 ///@{ 1624 1622 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() 1629 1628 /// must be called before using this function. 1630 bool reached(Node v) { return (*_reached)[v]; }1629 bool reached(Node v) const { return (*_reached)[v]; } 1631 1630 1632 1631 ///@} -
lemon/dijkstra.h
r397 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 180 180 /// 181 181 ///\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 187 186 ///relatively time consuming process to compute the arc lengths if 188 187 ///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>". 196 189 #ifdef DOXYGEN 197 190 template <typename GR, typename LM, typename TR> … … 227 220 typedef typename TR::OperationTraits OperationTraits; 228 221 229 ///The traits class.222 ///The \ref DijkstraDefaultTraits "traits class" of the algorithm. 230 223 typedef TR Traits; 231 224 … … 309 302 ///\ref named-templ-param "Named parameter" for setting 310 303 ///PredMap type. 304 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 311 305 template <class T> 312 306 struct SetPredMap … … 329 323 ///\ref named-templ-param "Named parameter" for setting 330 324 ///DistMap type. 325 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 331 326 template <class T> 332 327 struct SetDistMap … … 349 344 ///\ref named-templ-param "Named parameter" for setting 350 345 ///ProcessedMap type. 346 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 351 347 template <class T> 352 348 struct SetProcessedMap … … 389 385 }; 390 386 ///\brief \ref named-templ-param "Named parameter" for setting 391 ///heap and cross reference type 387 ///heap and cross reference types 392 388 /// 393 389 ///\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 395 395 template <class H, class CR = typename Digraph::template NodeMap<int> > 396 396 struct SetHeap … … 412 412 }; 413 413 ///\brief \ref named-templ-param "Named parameter" for setting 414 ///heap and cross reference type with automatic allocation414 ///heap and cross reference types with automatic allocation 415 415 /// 416 416 ///\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 420 426 template <class H, class CR = typename Digraph::template NodeMap<int> > 421 427 struct SetStandardHeap … … 487 493 488 494 ///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. 492 499 ///\return <tt> (*this) </tt> 493 500 Dijkstra &predMap(PredMap &m) … … 504 511 505 512 ///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. 509 517 ///\return <tt> (*this) </tt> 510 518 Dijkstra &processedMap(ProcessedMap &m) … … 522 530 ///Sets the map that stores the distances of the nodes calculated by the 523 531 ///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. 527 536 ///\return <tt> (*this) </tt> 528 537 Dijkstra &distMap(DistMap &m) … … 539 548 540 549 ///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. 544 555 ///\return <tt> (*this) </tt> 545 556 Dijkstra &heap(Heap& hp, HeapCrossRef &cr) … … 568 579 public: 569 580 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. 579 588 580 589 ///@{ 581 590 591 ///\brief Initializes the internal data structures. 592 /// 582 593 ///Initializes the internal data structures. 583 584 ///Initializes the internal data structures.585 ///586 594 void init() 587 595 { … … 659 667 } 660 668 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. 666 673 bool emptyQueue() const { return _heap->empty(); } 667 674 668 ///Returns the number of the nodes to be processed in the priority heap669 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. 672 679 int queueSize() const { return _heap->size(); } 673 680 … … 790 797 791 798 ///\name Query Functions 792 ///The result of the %Dijkstra algorithm can be obtained using these799 ///The results of the %Dijkstra algorithm can be obtained using these 793 800 ///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. 797 803 798 804 ///@{ … … 802 808 ///Returns the shortest path to a node. 803 809 /// 804 ///\warning \c t should be reach ablefrom the root(s).805 /// 806 ///\pre Either \ref run( ) or \ref start() must be called before807 /// 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. 808 814 Path path(Node t) const { return Path(*G, *_pred, t); } 809 815 … … 812 818 ///Returns the distance of a node from the root(s). 813 819 /// 814 ///\warning If node \c v is not reach ablefrom the root(s), then820 ///\warning If node \c v is not reached from the root(s), then 815 821 ///the return value of this function is undefined. 816 822 /// 817 ///\pre Either \ref run( ) or \ref start() must be called before818 /// using this function.823 ///\pre Either \ref run(Node) "run()" or \ref init() 824 ///must be called before using this function. 819 825 Value dist(Node v) const { return (*_dist)[v]; } 820 826 … … 823 829 ///This function returns the 'previous arc' of the shortest path 824 830 ///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 v826 ///is not reach ablefrom 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. 827 833 /// 828 834 ///The shortest path tree used here is equal to the shortest path 829 835 ///tree used in \ref predNode(). 830 836 /// 831 ///\pre Either \ref run( ) or \ref start() must be called before832 /// using this function.837 ///\pre Either \ref run(Node) "run()" or \ref init() 838 ///must be called before using this function. 833 839 Arc predArc(Node v) const { return (*_pred)[v]; } 834 840 … … 837 843 ///This function returns the 'previous node' of the shortest path 838 844 ///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 INVALID840 ///if \c v is not reach ablefrom 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. 841 847 /// 842 848 ///The shortest path tree used here is equal to the shortest path 843 849 ///tree used in \ref predArc(). 844 850 /// 845 ///\pre Either \ref run( ) or \ref start() must be called before846 /// using this function.851 ///\pre Either \ref run(Node) "run()" or \ref init() 852 ///must be called before using this function. 847 853 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 848 854 G->source((*_pred)[v]); } … … 854 860 ///of the nodes calculated by the algorithm. 855 861 /// 856 ///\pre Either \ref run( )or \ref init()862 ///\pre Either \ref run(Node) "run()" or \ref init() 857 863 ///must be called before using this function. 858 864 const DistMap &distMap() const { return *_dist;} … … 864 870 ///arcs, which form the shortest path tree. 865 871 /// 866 ///\pre Either \ref run( )or \ref init()872 ///\pre Either \ref run(Node) "run()" or \ref init() 867 873 ///must be called before using this function. 868 874 const PredMap &predMap() const { return *_pred;} 869 875 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() 874 881 ///must be called before using this function. 875 882 bool reached(Node v) const { return (*_heap_cross_ref)[v] != … … 880 887 ///Returns \c true if \c v is processed, i.e. the shortest 881 888 ///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() 883 891 ///must be called before using this function. 884 892 bool processed(Node v) const { return (*_heap_cross_ref)[v] == … … 889 897 ///Returns the current distance of a node from the root(s). 890 898 ///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() 892 901 ///must be called before using this function and 893 902 ///node \c v must be reached but not necessarily processed. … … 1072 1081 /// This auxiliary class is created to implement the 1073 1082 /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm. 1074 /// It does not have own \ref run( ) method, it uses the functions1075 /// 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. 1076 1085 /// 1077 1086 /// This class should only be used through the \ref dijkstra() function, … … 1268 1277 /// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t); 1269 1278 ///\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()" 1271 1280 ///to the end of the parameter list. 1272 1281 ///\sa DijkstraWizard -
lemon/dim2.h
r314 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/error.h
r291 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/graph_to_eps.h
r313 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/kruskal.h
r220 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/lgf_reader.h
r319 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 871 871 readLine(); 872 872 } 873 line.putback(c); 873 if (readSuccess()) { 874 line.putback(c); 875 } 874 876 } 875 877 … … 1700 1702 readLine(); 1701 1703 } 1702 line.putback(c); 1704 if (readSuccess()) { 1705 line.putback(c); 1706 } 1703 1707 } 1704 1708 … … 2227 2231 readLine(); 2228 2232 } 2229 line.putback(c); 2233 if (readSuccess()) { 2234 line.putback(c); 2235 } 2230 2236 } 2231 2237 … … 2568 2574 readLine(); 2569 2575 } 2570 line.putback(c); 2576 if (readSuccess()) { 2577 line.putback(c); 2578 } 2571 2579 } 2572 2580 -
lemon/lgf_writer.h
r319 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/list_graph.h
r313 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 841 841 842 842 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; 845 845 } 846 846 -
lemon/maps.h
r314 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/math.h
r209 r470 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 56 56 const long double SQRT1_2 = 0.7071067811865475244008443621048490L; 57 57 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 } 58 67 59 68 /// @} -
lemon/path.h
r313 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/random.cc
r209 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/random.h
r377 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 541 541 /// @{ 542 542 543 ///\name Initialization544 ///545 /// @{546 547 543 /// \brief Default constructor 548 544 /// … … 693 689 } 694 690 695 /// @}696 697 ///\name Uniform distributions698 ///699 /// @{700 701 691 /// \brief Returns a random real number from the range [0, 1) 702 692 /// … … 753 743 return _random_bits::IntConversion<Number, Word>::convert(core); 754 744 } 755 756 /// @}757 745 758 746 unsigned int uinteger() { … … 789 777 ///\name Non-uniform distributions 790 778 /// 791 792 779 ///@{ 793 780 794 /// \brief Returns a random bool 781 /// \brief Returns a random bool with given probability of true result. 795 782 /// 796 783 /// It returns a random bool with given probability of true result. … … 799 786 } 800 787 801 /// Standard Gaussdistribution802 803 /// Standard Gaussdistribution.788 /// Standard normal (Gauss) distribution 789 790 /// Standard normal (Gauss) distribution. 804 791 /// \note The Cartesian form of the Box-Muller 805 792 /// transformation is used to generate a random normal distribution. … … 814 801 return std::sqrt(-2*std::log(S)/S)*V1; 815 802 } 816 /// Gaussdistribution with given mean and standard deviation817 818 /// Gaussdistribution 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. 819 806 /// \sa gauss() 820 807 double gauss(double mean,double std_dev) 821 808 { 822 809 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> ¶ms) 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)); 823 850 } 824 851 … … 926 953 ///\name Two dimensional distributions 927 954 /// 928 929 955 ///@{ 930 956 … … 943 969 return dim2::Point<double>(V1,V2); 944 970 } 945 /// A kind of two dimensional Gaussdistribution971 /// A kind of two dimensional normal (Gauss) distribution 946 972 947 973 /// This function provides a turning symmetric two-dimensional distribution. -
lemon/smart_graph.h
r313 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 68 68 69 69 typedef True NodeNumTag; 70 typedef True EdgeNumTag;70 typedef True ArcNumTag; 71 71 72 72 int nodeNum() const { return nodes.size(); } … … 306 306 nodes[b._id].first_out=nodes[n._id].first_out; 307 307 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 } 309 311 if(connect) addArc(n,b); 310 312 return b; … … 465 467 466 468 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; 469 471 } 470 472 … … 481 483 : nodes(), arcs() {} 482 484 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(); } 483 492 484 493 int maxNodeId() const { return nodes.size()-1; } … … 729 738 dir.push_back(arcFromId(n-1)); 730 739 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; 733 742 arcs.pop_back(); 734 743 arcs.pop_back(); -
lemon/time_measure.h
r314 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/tolerance.h
r280 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/unionfind.h
r438 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 1190 1190 popLeft(nodes[jd].next); 1191 1191 pushRight(jd, ld); 1192 if (less(ld, nodes[jd].left) || 1192 if (less(ld, nodes[jd].left) || 1193 1193 nodes[ld].item == nodes[pd].item) { 1194 1194 nodes[jd].item = nodes[ld].item; -
m4/lx_check_cplex.m4
r187 r457 63 63 if test x"$lx_cplex_found" = x"yes"; then 64 64 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.]) 65 69 AC_MSG_RESULT([yes]) 66 70 else -
m4/lx_check_glpk.m4
r187 r459 43 43 } 44 44 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 45 50 int main(int argc, char** argv) 46 51 { … … 61 66 if test x"$lx_glpk_found" = x"yes"; then 62 67 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.]) 63 72 AC_MSG_RESULT([yes]) 64 73 else -
m4/lx_check_soplex.m4
r187 r457 57 57 if test x"$lx_soplex_found" = x"yes"; then 58 58 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.]) 59 61 AC_MSG_RESULT([yes]) 60 62 else -
scripts/chg-len.py
r284 r422 2 2 3 3 import sys 4 import os 4 5 from mercurial import ui, hg 6 from mercurial import util 7 8 util.rcpath = lambda : [] 5 9 6 10 if len(sys.argv)>1 and sys.argv[1] in ["-h","--help"]: … … 10 14 """ 11 15 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])17 16 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]) 17 u = ui.ui() 18 r = hg.repository(u, ".") 19 N = r.changectx(".").rev() 20 lengths=[0]*(N+1) 21 for i in range(N+1): 22 p=r.changectx(i).parents() 23 if p[0]: 24 p0=lengths[p[0].rev()] 33 25 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()] 38 29 else: 39 lengths.append(max(lengths[par1],lengths[par2])+1) 40 print lengths[PAR] 30 p1=-1 31 lengths[i]=max(p0,p1)+1 32 print lengths[N] -
scripts/unify-sources.sh
r208 r396 4 4 HGROOT=`hg root` 5 5 6 function update_header() { 6 # file enumaration modes 7 8 function all_files() { 9 hg status -a -m -c | 10 cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' | 11 while read file; do echo $HGROOT/$file; done 12 } 13 14 function modified_files() { 15 hg status -a -m | 16 cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' | 17 while read file; do echo $HGROOT/$file; done 18 } 19 20 function changed_files() { 21 { 22 if [ -n "$HG_PARENT1" ] 23 then 24 hg status --rev $HG_PARENT1:$HG_NODE -a -m 25 fi 26 if [ -n "$HG_PARENT2" ] 27 then 28 hg status --rev $HG_PARENT2:$HG_NODE -a -m 29 fi 30 } | cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' | 31 sort | uniq | 32 while read file; do echo $HGROOT/$file; done 33 } 34 35 function given_files() { 36 for file in $GIVEN_FILES 37 do 38 echo $file 39 done 40 } 41 42 # actions 43 44 function update_action() { 45 if ! diff -q $1 $2 >/dev/null 46 then 47 echo -n " [$3 updated]" 48 rm $2 49 mv $1 $2 50 CHANGED=YES 51 fi 52 } 53 54 function update_warning() { 55 echo -n " [$2 warning]" 56 WARNED=YES 57 } 58 59 function update_init() { 60 echo Update source files... 61 TOTAL_FILES=0 62 CHANGED_FILES=0 63 WARNED_FILES=0 64 } 65 66 function update_done() { 67 echo $CHANGED_FILES out of $TOTAL_FILES files has been changed. 68 echo $WARNED_FILES out of $TOTAL_FILES files triggered warnings. 69 } 70 71 function update_begin() { 72 ((TOTAL_FILES++)) 73 CHANGED=NO 74 WARNED=NO 75 } 76 77 function update_end() { 78 if [ $CHANGED == YES ] 79 then 80 ((++CHANGED_FILES)) 81 fi 82 if [ $WARNED == YES ] 83 then 84 ((++WARNED_FILES)) 85 fi 86 } 87 88 function check_action() { 89 if [ "$3" == 'tabs' ] 90 then 91 PATTERN=$(echo -e '\t') 92 elif [ "$3" == 'trailing spaces' ] 93 then 94 PATTERN='\ +$' 95 else 96 PATTERN='*' 97 fi 98 99 if ! diff -q $1 $2 >/dev/null 100 then 101 if [ "$PATTERN" == '*' ] 102 then 103 diff $1 $2 | grep '^[0-9]' | sed "s|^\(.*\)c.*$|$2:\1: check failed: $3|g" | 104 sed "s/:\([0-9]*\),\([0-9]*\):\(.*\)$/:\1:\3 (until line \2)/g" 105 else 106 grep -n -E "$PATTERN" $2 | sed "s|^\([0-9]*\):.*$|$2:\1: check failed: $3|g" 107 fi 108 FAILED=YES 109 fi 110 } 111 112 function check_warning() { 113 if [ "$2" == 'long lines' ] 114 then 115 grep -n -E '.{81,}' $1 | sed "s|^\([0-9]*\):.*$|$1:\1: warning: $2|g" 116 else 117 echo "$1: warning: $2" 118 fi 119 WARNED=YES 120 } 121 122 function check_init() { 123 echo Check source files... 124 FAILED_FILES=0 125 WARNED_FILES=0 126 TOTAL_FILES=0 127 } 128 129 function check_done() { 130 echo $FAILED_FILES out of $TOTAL_FILES files has been failed. 131 echo $WARNED_FILES out of $TOTAL_FILES files triggered warnings. 132 133 if [ $WARNED_FILES -gt 0 -o $FAILED_FILES -gt 0 ] 134 then 135 if [ "$WARNING" == 'INTERACTIVE' ] 136 then 137 echo -n "Are the files with errors/warnings acceptable? (yes/no) " 138 while read answer 139 do 140 if [ "$answer" == 'yes' ] 141 then 142 return 0 143 elif [ "$answer" == 'no' ] 144 then 145 return 1 146 fi 147 echo -n "Are the files with errors/warnings acceptable? (yes/no) " 148 done 149 elif [ "$WARNING" == 'WERROR' ] 150 then 151 return 1 152 fi 153 fi 154 } 155 156 function check_begin() { 157 ((TOTAL_FILES++)) 158 FAILED=NO 159 WARNED=NO 160 } 161 162 function check_end() { 163 if [ $FAILED == YES ] 164 then 165 ((++FAILED_FILES)) 166 fi 167 if [ $WARNED == YES ] 168 then 169 ((++WARNED_FILES)) 170 fi 171 } 172 173 174 175 # checks 176 177 function header_check() { 178 if echo $1 | grep -q -E 'Makefile\.am$' 179 then 180 return 181 fi 182 7 183 TMP_FILE=`mktemp` 8 FILE_NAME=$19 184 10 185 (echo "/* -*- mode: C++; indent-tabs-mode: nil; -*- … … 26 201 */ 27 202 " 28 203 awk 'BEGIN { pm=0; } 29 204 pm==3 { print } 30 205 /\/\* / && pm==0 { pm=1;} … … 32 207 /\*\// && pm==1 { pm=2;} 33 208 ' $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 214 function tabs_check() { 215 if echo $1 | grep -q -v -E 'Makefile\.am$' 216 then 217 OLD_PATTERN=$(echo -e '\t') 218 NEW_PATTERN=' ' 219 else 220 OLD_PATTERN=' ' 221 NEW_PATTERN=$(echo -e '\t') 222 fi 43 223 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 229 function spaces_check() { 56 230 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 236 function 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 245 function process_file() { 246 if [ "$ACTION" == 'update' ] 247 then 248 echo -n " $ACTION $1..." 249 else 250 echo " $ACTION $1..." 251 fi 252 253 CHECKING="header tabs spaces long_lines" 254 255 "$ACTION"_begin $1 256 for check in $CHECKING 113 257 do 114 update_file $HGROOT/$i 115 ((TOTAL_FILES++)) 258 "$check"_check $1 116 259 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 267 function process_all { 268 "$ACTION"_init 269 while read file 120 270 do 121 update_file $i 122 ((TOTAL_FILES++)) 123 done 271 process_file $file 272 done < <($FILES) 273 "$ACTION"_done 274 } 275 276 while [ $# -gt 0 ] 277 do 278 279 if [ "$1" == '--help' ] || [ "$1" == '-h' ] 280 then 281 echo -n \ 282 "Usage: 283 $0 [OPTIONS] [files] 284 Options: 285 --dry-run|-n 286 Check the files, but do not modify them. 287 --interactive|-i 288 If --dry-run is specified and the checker emits warnings, 289 then the user is asked if the warnings should be considered 290 errors. 291 --werror|-w 292 Make all warnings into errors. 293 --all|-a 294 Check all source files in the repository. 295 --modified|-m 296 Check only the modified (and new) source files. This option is 297 useful to check the modification before making a commit. 298 --changed|-c 299 Check only the changed source files compared to the parent(s) of 300 the current hg node. This option is useful as hg hook script. 301 To automatically check all your changes before making a commit, 302 add the following section to the appropriate .hg/hgrc file. 303 304 [hooks] 305 pretxncommit.checksources = scripts/unify-sources.sh -c -n -i 306 307 --help|-h 308 Print this help message. 309 files 310 The files to check/unify. If no file names are given, the modified 311 source files will be checked/unified (just like using the 312 --modified|-m option). 313 " 314 exit 0 315 elif [ "$1" == '--dry-run' ] || [ "$1" == '-n' ] 316 then 317 [ -n "$ACTION" ] && echo "Conflicting action options" >&2 && exit 1 318 ACTION=check 319 elif [ "$1" == "--all" ] || [ "$1" == '-a' ] 320 then 321 [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1 322 FILES=all_files 323 elif [ "$1" == "--changed" ] || [ "$1" == '-c' ] 324 then 325 [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1 326 FILES=changed_files 327 elif [ "$1" == "--modified" ] || [ "$1" == '-m' ] 328 then 329 [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1 330 FILES=modified_files 331 elif [ "$1" == "--interactive" ] || [ "$1" == "-i" ] 332 then 333 [ -n "$WARNING" ] && echo "Conflicting warning options" >&2 && exit 1 334 WARNING='INTERACTIVE' 335 elif [ "$1" == "--werror" ] || [ "$1" == "-w" ] 336 then 337 [ -n "$WARNING" ] && echo "Conflicting warning options" >&2 && exit 1 338 WARNING='WERROR' 339 elif [ $(echo x$1 | cut -c 2) == '-' ] 340 then 341 echo "Invalid option $1" >&2 && exit 1 342 else 343 [ -n "$FILES" ] && echo "Invalid option $1" >&2 && exit 1 344 GIVEN_FILES=$@ 345 FILES=given_files 346 break 347 fi 348 349 shift 350 done 351 352 if [ -z $FILES ] 353 then 354 FILES=modified_files 124 355 fi 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 357 if [ -z $ACTION ] 358 then 359 ACTION=update 134 360 fi 361 362 process_all -
test/CMakeLists.txt
r225 r474 1 INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR}) 1 INCLUDE_DIRECTORIES( 2 ${CMAKE_SOURCE_DIR} 3 ${CMAKE_BINARY_DIR} 4 ) 5 6 IF(HAVE_GLPK) 7 INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR}) 8 ENDIF(HAVE_GLPK) 2 9 3 10 LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon) 4 11 5 12 SET(TESTS 13 adaptors_test 6 14 bfs_test 15 circulation_test 7 16 counter_test 8 17 dfs_test … … 10 19 dijkstra_test 11 20 dim_test 21 edge_set_test 12 22 error_test 13 23 graph_copy_test 14 24 graph_test 15 25 graph_utils_test 26 hao_orlin_test 16 27 heap_test 17 28 kruskal_test 18 29 maps_test 30 max_matching_test 31 path_test 32 preflow_test 33 radix_sort_test 19 34 random_test 20 path_test35 suurballe_test 21 36 time_measure_test 22 37 unionfind_test) 38 39 IF(HAVE_LP) 40 ADD_EXECUTABLE(lp_test lp_test.cc) 41 IF(HAVE_GLPK) 42 TARGET_LINK_LIBRARIES(lp_test lemon ${GLPK_LIBRARIES}) 43 ENDIF(HAVE_GLPK) 44 ADD_TEST(lp_test lp_test) 45 46 IF(WIN32 AND HAVE_GLPK) 47 GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION) 48 GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH) 49 ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD 50 COMMAND cmake -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH} 51 COMMAND cmake -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH} 52 COMMAND cmake -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH} 53 ) 54 ENDIF(WIN32 AND HAVE_GLPK) 55 ENDIF(HAVE_LP) 56 57 IF(HAVE_MIP) 58 ADD_EXECUTABLE(mip_test mip_test.cc) 59 IF(HAVE_GLPK) 60 TARGET_LINK_LIBRARIES(mip_test lemon ${GLPK_LIBRARIES}) 61 ENDIF(HAVE_GLPK) 62 ADD_TEST(mip_test mip_test) 63 64 IF(WIN32 AND HAVE_GLPK) 65 GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION) 66 GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH) 67 ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD 68 COMMAND cmake -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH} 69 COMMAND cmake -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH} 70 COMMAND cmake -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH} 71 ) 72 ENDIF(WIN32 AND HAVE_GLPK) 73 ENDIF(HAVE_MIP) 23 74 24 75 FOREACH(TEST_NAME ${TESTS}) -
test/Makefile.am
r228 r469 4 4 noinst_HEADERS += \ 5 5 test/graph_test.h \ 6 6 test/test_tools.h 7 7 8 8 check_PROGRAMS += \ 9 test/adaptors_test \ 9 10 test/bfs_test \ 10 test/counter_test \ 11 test/circulation_test \ 12 test/counter_test \ 11 13 test/dfs_test \ 12 14 test/digraph_test \ 13 15 test/dijkstra_test \ 14 test/dim_test \ 16 test/dim_test \ 17 test/edge_set_test \ 15 18 test/error_test \ 16 19 test/graph_copy_test \ 17 20 test/graph_test \ 18 21 test/graph_utils_test \ 22 test/hao_orlin_test \ 19 23 test/heap_test \ 20 24 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 \ 27 35 test/unionfind_test 36 37 if HAVE_LP 38 check_PROGRAMS += test/lp_test 39 endif HAVE_LP 40 if HAVE_MIP 41 check_PROGRAMS += test/mip_test 42 endif HAVE_MIP 28 43 29 44 TESTS += $(check_PROGRAMS) 30 45 XFAIL_TESTS += test/test_tools_fail$(EXEEXT) 31 46 47 test_adaptors_test_SOURCES = test/adaptors_test.cc 32 48 test_bfs_test_SOURCES = test/bfs_test.cc 49 test_circulation_test_SOURCES = test/circulation_test.cc 33 50 test_counter_test_SOURCES = test/counter_test.cc 34 51 test_dfs_test_SOURCES = test/dfs_test.cc … … 36 53 test_dijkstra_test_SOURCES = test/dijkstra_test.cc 37 54 test_dim_test_SOURCES = test/dim_test.cc 55 test_edge_set_test_SOURCES = test/edge_set_test.cc 38 56 test_error_test_SOURCES = test/error_test.cc 39 57 test_graph_copy_test_SOURCES = test/graph_copy_test.cc … … 42 60 test_heap_test_SOURCES = test/heap_test.cc 43 61 test_kruskal_test_SOURCES = test/kruskal_test.cc 62 test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc 63 test_lp_test_SOURCES = test/lp_test.cc 44 64 test_maps_test_SOURCES = test/maps_test.cc 65 test_mip_test_SOURCES = test/mip_test.cc 66 test_max_matching_test_SOURCES = test/max_matching_test.cc 45 67 test_path_test_SOURCES = test/path_test.cc 68 test_preflow_test_SOURCES = test/preflow_test.cc 69 test_radix_sort_test_SOURCES = test/radix_sort_test.cc 70 test_suurballe_test_SOURCES = test/suurballe_test.cc 46 71 test_random_test_SOURCES = test/random_test.cc 47 72 test_test_tools_fail_SOURCES = test/test_tools_fail.cc -
test/bfs_test.cc
r293 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/counter_test.cc
r209 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/dfs_test.cc
r293 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/digraph_test.cc
r228 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 20 20 #include <lemon/list_graph.h> 21 21 #include <lemon/smart_graph.h> 22 //#include <lemon/full_graph.h> 23 //#include <lemon/hypercube_graph.h> 22 #include <lemon/full_graph.h> 24 23 25 24 #include "test_tools.h" … … 30 29 31 30 template <class Digraph> 32 void checkDigraph () {31 void checkDigraphBuild() { 33 32 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 34 33 Digraph G; … … 59 58 checkGraphConArcList(G, 1); 60 59 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 62 64 checkGraphNodeList(G, 3); 63 65 checkGraphArcList(G, 4); … … 77 79 checkGraphNodeMap(G); 78 80 checkGraphArcMap(G); 79 80 } 81 81 } 82 83 template <class Digraph> 84 void checkDigraphSplit() { 85 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 86 87 Digraph G; 88 Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); 89 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1), 90 a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); 91 92 Node n4 = G.split(n2); 93 94 check(G.target(OutArcIt(G, n2)) == n4 && 95 G.source(InArcIt(G, n4)) == n2, 96 "Wrong split."); 97 98 checkGraphNodeList(G, 4); 99 checkGraphArcList(G, 5); 100 101 checkGraphOutArcList(G, n1, 1); 102 checkGraphOutArcList(G, n2, 1); 103 checkGraphOutArcList(G, n3, 0); 104 checkGraphOutArcList(G, n4, 3); 105 106 checkGraphInArcList(G, n1, 1); 107 checkGraphInArcList(G, n2, 1); 108 checkGraphInArcList(G, n3, 2); 109 checkGraphInArcList(G, n4, 1); 110 111 checkGraphConArcList(G, 5); 112 } 113 114 template <class Digraph> 115 void checkDigraphAlter() { 116 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 117 118 Digraph G; 119 Node n1 = G.addNode(), n2 = G.addNode(), 120 n3 = G.addNode(), n4 = G.addNode(); 121 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1), 122 a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3), 123 a5 = G.addArc(n2, n4); 124 125 checkGraphNodeList(G, 4); 126 checkGraphArcList(G, 5); 127 128 // Check changeSource() and changeTarget() 129 G.changeTarget(a4, n1); 130 131 checkGraphNodeList(G, 4); 132 checkGraphArcList(G, 5); 133 134 checkGraphOutArcList(G, n1, 1); 135 checkGraphOutArcList(G, n2, 1); 136 checkGraphOutArcList(G, n3, 0); 137 checkGraphOutArcList(G, n4, 3); 138 139 checkGraphInArcList(G, n1, 2); 140 checkGraphInArcList(G, n2, 1); 141 checkGraphInArcList(G, n3, 1); 142 checkGraphInArcList(G, n4, 1); 143 144 checkGraphConArcList(G, 5); 145 146 G.changeSource(a4, n3); 147 148 checkGraphNodeList(G, 4); 149 checkGraphArcList(G, 5); 150 151 checkGraphOutArcList(G, n1, 1); 152 checkGraphOutArcList(G, n2, 1); 153 checkGraphOutArcList(G, n3, 1); 154 checkGraphOutArcList(G, n4, 2); 155 156 checkGraphInArcList(G, n1, 2); 157 checkGraphInArcList(G, n2, 1); 158 checkGraphInArcList(G, n3, 1); 159 checkGraphInArcList(G, n4, 1); 160 161 checkGraphConArcList(G, 5); 162 163 // Check contract() 164 G.contract(n2, n4, false); 165 166 checkGraphNodeList(G, 3); 167 checkGraphArcList(G, 5); 168 169 checkGraphOutArcList(G, n1, 1); 170 checkGraphOutArcList(G, n2, 3); 171 checkGraphOutArcList(G, n3, 1); 172 173 checkGraphInArcList(G, n1, 2); 174 checkGraphInArcList(G, n2, 2); 175 checkGraphInArcList(G, n3, 1); 176 177 checkGraphConArcList(G, 5); 178 179 G.contract(n2, n1); 180 181 checkGraphNodeList(G, 2); 182 checkGraphArcList(G, 3); 183 184 checkGraphOutArcList(G, n2, 2); 185 checkGraphOutArcList(G, n3, 1); 186 187 checkGraphInArcList(G, n2, 2); 188 checkGraphInArcList(G, n3, 1); 189 190 checkGraphConArcList(G, 3); 191 } 192 193 template <class Digraph> 194 void checkDigraphErase() { 195 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 196 197 Digraph G; 198 Node n1 = G.addNode(), n2 = G.addNode(), 199 n3 = G.addNode(), n4 = G.addNode(); 200 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1), 201 a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1), 202 a5 = G.addArc(n2, n4); 203 204 // Check arc deletion 205 G.erase(a1); 206 207 checkGraphNodeList(G, 4); 208 checkGraphArcList(G, 4); 209 210 checkGraphOutArcList(G, n1, 0); 211 checkGraphOutArcList(G, n2, 1); 212 checkGraphOutArcList(G, n3, 1); 213 checkGraphOutArcList(G, n4, 2); 214 215 checkGraphInArcList(G, n1, 2); 216 checkGraphInArcList(G, n2, 0); 217 checkGraphInArcList(G, n3, 1); 218 checkGraphInArcList(G, n4, 1); 219 220 checkGraphConArcList(G, 4); 221 222 // Check node deletion 223 G.erase(n4); 224 225 checkGraphNodeList(G, 3); 226 checkGraphArcList(G, 1); 227 228 checkGraphOutArcList(G, n1, 0); 229 checkGraphOutArcList(G, n2, 0); 230 checkGraphOutArcList(G, n3, 1); 231 checkGraphOutArcList(G, n4, 0); 232 233 checkGraphInArcList(G, n1, 1); 234 checkGraphInArcList(G, n2, 0); 235 checkGraphInArcList(G, n3, 0); 236 checkGraphInArcList(G, n4, 0); 237 238 checkGraphConArcList(G, 1); 239 } 240 241 242 template <class Digraph> 243 void checkDigraphSnapshot() { 244 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 245 246 Digraph G; 247 Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); 248 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1), 249 a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); 250 251 typename Digraph::Snapshot snapshot(G); 252 253 Node n = G.addNode(); 254 G.addArc(n3, n); 255 G.addArc(n, n3); 256 257 checkGraphNodeList(G, 4); 258 checkGraphArcList(G, 6); 259 260 snapshot.restore(); 261 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 } 82 290 83 291 void checkConcepts() { … … 110 318 checkConcept<ClearableDigraphComponent<>, SmartDigraph>(); 111 319 } 112 // { // Checking FullDigraph 113 // checkConcept<Digraph, FullDigraph>(); 114 // } 115 // { // Checking HyperCubeDigraph 116 // checkConcept<Digraph, HyperCubeDigraph>(); 117 // } 320 { // Checking FullDigraph 321 checkConcept<Digraph, FullDigraph>(); 322 } 118 323 } 119 324 … … 168 373 } 169 374 375 void checkFullDigraph(int num) { 376 typedef FullDigraph Digraph; 377 DIGRAPH_TYPEDEFS(Digraph); 378 Digraph G(num); 379 380 checkGraphNodeList(G, num); 381 checkGraphArcList(G, num * num); 382 383 for (NodeIt n(G); n != INVALID; ++n) { 384 checkGraphOutArcList(G, n, num); 385 checkGraphInArcList(G, n, num); 386 } 387 388 checkGraphConArcList(G, num * num); 389 390 checkNodeIds(G); 391 checkArcIds(G); 392 checkGraphNodeMap(G); 393 checkGraphArcMap(G); 394 395 for (int i = 0; i < G.nodeNum(); ++i) { 396 check(G.index(G(i)) == i, "Wrong index"); 397 } 398 399 for (NodeIt s(G); s != INVALID; ++s) { 400 for (NodeIt t(G); t != INVALID; ++t) { 401 Arc a = G.arc(s, t); 402 check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup"); 403 } 404 } 405 } 406 170 407 void checkDigraphs() { 171 408 { // Checking ListDigraph 172 checkDigraph<ListDigraph>(); 409 checkDigraphBuild<ListDigraph>(); 410 checkDigraphSplit<ListDigraph>(); 411 checkDigraphAlter<ListDigraph>(); 412 checkDigraphErase<ListDigraph>(); 413 checkDigraphSnapshot<ListDigraph>(); 173 414 checkDigraphValidityErase<ListDigraph>(); 174 415 } 175 416 { // Checking SmartDigraph 176 checkDigraph<SmartDigraph>(); 417 checkDigraphBuild<SmartDigraph>(); 418 checkDigraphSplit<SmartDigraph>(); 419 checkDigraphSnapshot<SmartDigraph>(); 177 420 checkDigraphValidity<SmartDigraph>(); 421 } 422 { // Checking FullDigraph 423 checkFullDigraph(8); 178 424 } 179 425 } -
test/dijkstra_test.cc
r397 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/dim_test.cc
r253 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/error_test.cc
r277 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/graph_copy_test.cc
r282 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/graph_test.cc
r228 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 20 20 #include <lemon/list_graph.h> 21 21 #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> 24 25 25 26 #include "test_tools.h" … … 30 31 31 32 template <class Graph> 32 void checkGraph () {33 void checkGraphBuild() { 33 34 TEMPLATE_GRAPH_TYPEDEFS(Graph); 34 35 … … 36 37 checkGraphNodeList(G, 0); 37 38 checkGraphEdgeList(G, 0); 39 checkGraphArcList(G, 0); 38 40 39 41 Node … … 43 45 checkGraphNodeList(G, 3); 44 46 checkGraphEdgeList(G, 0); 47 checkGraphArcList(G, 0); 45 48 46 49 Edge e1 = G.addEdge(n1, n2); 47 50 check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1), 48 51 "Wrong edge"); 49 checkGraphNodeList(G, 3); 52 53 checkGraphNodeList(G, 3); 54 checkGraphEdgeList(G, 1); 50 55 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); 65 62 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); 70 69 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); 85 76 checkGraphConArcList(G, 6); 86 checkGraphConEdgeList(G, 3);87 77 88 78 checkArcDirections(G); … … 96 86 } 97 87 88 template <class Graph> 89 void checkGraphAlter() { 90 TEMPLATE_GRAPH_TYPEDEFS(Graph); 91 92 Graph G; 93 Node n1 = G.addNode(), n2 = G.addNode(), 94 n3 = G.addNode(), n4 = G.addNode(); 95 Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1), 96 e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4), 97 e5 = G.addEdge(n4, n3); 98 99 checkGraphNodeList(G, 4); 100 checkGraphEdgeList(G, 5); 101 checkGraphArcList(G, 10); 102 103 // Check changeU() and changeV() 104 if (G.u(e2) == n2) { 105 G.changeU(e2, n3); 106 } else { 107 G.changeV(e2, n3); 108 } 109 110 checkGraphNodeList(G, 4); 111 checkGraphEdgeList(G, 5); 112 checkGraphArcList(G, 10); 113 114 checkGraphIncEdgeArcLists(G, n1, 3); 115 checkGraphIncEdgeArcLists(G, n2, 2); 116 checkGraphIncEdgeArcLists(G, n3, 3); 117 checkGraphIncEdgeArcLists(G, n4, 2); 118 119 checkGraphConEdgeList(G, 5); 120 checkGraphConArcList(G, 10); 121 122 if (G.u(e2) == n1) { 123 G.changeU(e2, n2); 124 } else { 125 G.changeV(e2, n2); 126 } 127 128 checkGraphNodeList(G, 4); 129 checkGraphEdgeList(G, 5); 130 checkGraphArcList(G, 10); 131 132 checkGraphIncEdgeArcLists(G, n1, 2); 133 checkGraphIncEdgeArcLists(G, n2, 3); 134 checkGraphIncEdgeArcLists(G, n3, 3); 135 checkGraphIncEdgeArcLists(G, n4, 2); 136 137 checkGraphConEdgeList(G, 5); 138 checkGraphConArcList(G, 10); 139 140 // Check contract() 141 G.contract(n1, n4, false); 142 143 checkGraphNodeList(G, 3); 144 checkGraphEdgeList(G, 5); 145 checkGraphArcList(G, 10); 146 147 checkGraphIncEdgeArcLists(G, n1, 4); 148 checkGraphIncEdgeArcLists(G, n2, 3); 149 checkGraphIncEdgeArcLists(G, n3, 3); 150 151 checkGraphConEdgeList(G, 5); 152 checkGraphConArcList(G, 10); 153 154 G.contract(n2, n3); 155 156 checkGraphNodeList(G, 2); 157 checkGraphEdgeList(G, 3); 158 checkGraphArcList(G, 6); 159 160 checkGraphIncEdgeArcLists(G, n1, 4); 161 checkGraphIncEdgeArcLists(G, n2, 2); 162 163 checkGraphConEdgeList(G, 3); 164 checkGraphConArcList(G, 6); 165 } 166 167 template <class Graph> 168 void checkGraphErase() { 169 TEMPLATE_GRAPH_TYPEDEFS(Graph); 170 171 Graph G; 172 Node n1 = G.addNode(), n2 = G.addNode(), 173 n3 = G.addNode(), n4 = G.addNode(); 174 Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1), 175 e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4), 176 e5 = G.addEdge(n4, n3); 177 178 // Check edge deletion 179 G.erase(e2); 180 181 checkGraphNodeList(G, 4); 182 checkGraphEdgeList(G, 4); 183 checkGraphArcList(G, 8); 184 185 checkGraphIncEdgeArcLists(G, n1, 2); 186 checkGraphIncEdgeArcLists(G, n2, 2); 187 checkGraphIncEdgeArcLists(G, n3, 2); 188 checkGraphIncEdgeArcLists(G, n4, 2); 189 190 checkGraphConEdgeList(G, 4); 191 checkGraphConArcList(G, 8); 192 193 // Check node deletion 194 G.erase(n3); 195 196 checkGraphNodeList(G, 3); 197 checkGraphEdgeList(G, 2); 198 checkGraphArcList(G, 4); 199 200 checkGraphIncEdgeArcLists(G, n1, 2); 201 checkGraphIncEdgeArcLists(G, n2, 1); 202 checkGraphIncEdgeArcLists(G, n4, 1); 203 204 checkGraphConEdgeList(G, 2); 205 checkGraphConArcList(G, 4); 206 } 207 208 209 template <class Graph> 210 void checkGraphSnapshot() { 211 TEMPLATE_GRAPH_TYPEDEFS(Graph); 212 213 Graph G; 214 Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); 215 Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1), 216 e3 = G.addEdge(n2, n3); 217 218 checkGraphNodeList(G, 3); 219 checkGraphEdgeList(G, 3); 220 checkGraphArcList(G, 6); 221 222 typename Graph::Snapshot snapshot(G); 223 224 Node n = G.addNode(); 225 G.addEdge(n3, n); 226 G.addEdge(n, n3); 227 G.addEdge(n3, n2); 228 229 checkGraphNodeList(G, 4); 230 checkGraphEdgeList(G, 6); 231 checkGraphArcList(G, 12); 232 233 snapshot.restore(); 234 235 checkGraphNodeList(G, 3); 236 checkGraphEdgeList(G, 3); 237 checkGraphArcList(G, 6); 238 239 checkGraphIncEdgeArcLists(G, n1, 2); 240 checkGraphIncEdgeArcLists(G, n2, 3); 241 checkGraphIncEdgeArcLists(G, n3, 1); 242 243 checkGraphConEdgeList(G, 3); 244 checkGraphConArcList(G, 6); 245 246 checkNodeIds(G); 247 checkEdgeIds(G); 248 checkArcIds(G); 249 checkGraphNodeMap(G); 250 checkGraphEdgeMap(G); 251 checkGraphArcMap(G); 252 253 G.addNode(); 254 snapshot.save(G); 255 256 G.addEdge(G.addNode(), G.addNode()); 257 258 snapshot.restore(); 259 260 checkGraphNodeList(G, 4); 261 checkGraphEdgeList(G, 3); 262 checkGraphArcList(G, 6); 263 } 264 265 void checkFullGraph(int num) { 266 typedef FullGraph Graph; 267 GRAPH_TYPEDEFS(Graph); 268 269 Graph G(num); 270 checkGraphNodeList(G, num); 271 checkGraphEdgeList(G, num * (num - 1) / 2); 272 273 for (NodeIt n(G); n != INVALID; ++n) { 274 checkGraphOutArcList(G, n, num - 1); 275 checkGraphInArcList(G, n, num - 1); 276 checkGraphIncEdgeList(G, n, num - 1); 277 } 278 279 checkGraphConArcList(G, num * (num - 1)); 280 checkGraphConEdgeList(G, num * (num - 1) / 2); 281 282 checkArcDirections(G); 283 284 checkNodeIds(G); 285 checkArcIds(G); 286 checkEdgeIds(G); 287 checkGraphNodeMap(G); 288 checkGraphArcMap(G); 289 checkGraphEdgeMap(G); 290 291 292 for (int i = 0; i < G.nodeNum(); ++i) { 293 check(G.index(G(i)) == i, "Wrong index"); 294 } 295 296 for (NodeIt u(G); u != INVALID; ++u) { 297 for (NodeIt v(G); v != INVALID; ++v) { 298 Edge e = G.edge(u, v); 299 Arc a = G.arc(u, v); 300 if (u == v) { 301 check(e == INVALID, "Wrong edge lookup"); 302 check(a == INVALID, "Wrong arc lookup"); 303 } else { 304 check((G.u(e) == u && G.v(e) == v) || 305 (G.u(e) == v && G.v(e) == u), "Wrong edge lookup"); 306 check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup"); 307 } 308 } 309 } 310 } 311 98 312 void checkConcepts() { 99 313 { // Checking graph components … … 125 339 checkConcept<ClearableGraphComponent<>, SmartGraph>(); 126 340 } 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 } 135 350 } 136 351 … … 189 404 } 190 405 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 // } 406 void checkGridGraph(int width, int height) { 407 typedef GridGraph Graph; 408 GRAPH_TYPEDEFS(Graph); 409 Graph G(width, height); 410 411 check(G.width() == width, "Wrong column number"); 412 check(G.height() == height, "Wrong row number"); 413 414 for (int i = 0; i < width; ++i) { 415 for (int j = 0; j < height; ++j) { 416 check(G.col(G(i, j)) == i, "Wrong column"); 417 check(G.row(G(i, j)) == j, "Wrong row"); 418 check(G.pos(G(i, j)).x == i, "Wrong column"); 419 check(G.pos(G(i, j)).y == j, "Wrong row"); 420 } 421 } 422 423 for (int j = 0; j < height; ++j) { 424 for (int i = 0; i < width - 1; ++i) { 425 check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right"); 426 check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right"); 427 } 428 check(G.right(G(width - 1, j)) == INVALID, "Wrong right"); 429 } 430 431 for (int j = 0; j < height; ++j) { 432 for (int i = 1; i < width; ++i) { 433 check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left"); 434 check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left"); 435 } 436 check(G.left(G(0, j)) == INVALID, "Wrong left"); 437 } 438 439 for (int i = 0; i < width; ++i) { 440 for (int j = 0; j < height - 1; ++j) { 441 check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up"); 442 check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up"); 443 } 444 check(G.up(G(i, height - 1)) == INVALID, "Wrong up"); 445 } 446 447 for (int i = 0; i < width; ++i) { 448 for (int j = 1; j < height; ++j) { 449 check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down"); 450 check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down"); 451 } 452 check(G.down(G(i, 0)) == INVALID, "Wrong down"); 453 } 454 455 checkGraphNodeList(G, width * height); 456 checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height); 457 checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height)); 458 459 for (NodeIt n(G); n != INVALID; ++n) { 460 int nb = 4; 461 if (G.col(n) == 0) --nb; 462 if (G.col(n) == width - 1) --nb; 463 if (G.row(n) == 0) --nb; 464 if (G.row(n) == height - 1) --nb; 465 466 checkGraphOutArcList(G, n, nb); 467 checkGraphInArcList(G, n, nb); 468 checkGraphIncEdgeList(G, n, nb); 469 } 470 471 checkArcDirections(G); 472 473 checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height)); 474 checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height); 475 476 checkNodeIds(G); 477 checkArcIds(G); 478 checkEdgeIds(G); 479 checkGraphNodeMap(G); 480 checkGraphArcMap(G); 481 checkGraphEdgeMap(G); 482 483 } 484 485 void checkHypercubeGraph(int dim) { 486 GRAPH_TYPEDEFS(HypercubeGraph); 487 488 HypercubeGraph G(dim); 489 checkGraphNodeList(G, 1 << dim); 490 checkGraphEdgeList(G, dim * (1 << (dim-1))); 491 checkGraphArcList(G, dim * (1 << dim)); 492 493 Node n = G.nodeFromId(dim); 494 495 for (NodeIt n(G); n != INVALID; ++n) { 496 checkGraphIncEdgeList(G, n, dim); 497 for (IncEdgeIt e(G, n); e != INVALID; ++e) { 498 check( (G.u(e) == n && 499 G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) || 500 (G.v(e) == n && 501 G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))), 502 "Wrong edge or wrong dimension"); 503 } 504 505 checkGraphOutArcList(G, n, dim); 506 for (OutArcIt a(G, n); a != INVALID; ++a) { 507 check(G.source(a) == n && 508 G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))), 509 "Wrong arc or wrong dimension"); 510 } 511 512 checkGraphInArcList(G, n, dim); 513 for (InArcIt a(G, n); a != INVALID; ++a) { 514 check(G.target(a) == n && 515 G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))), 516 "Wrong arc or wrong dimension"); 517 } 518 } 519 520 checkGraphConArcList(G, (1 << dim) * dim); 521 checkGraphConEdgeList(G, dim * (1 << (dim-1))); 522 523 checkArcDirections(G); 524 525 checkNodeIds(G); 526 checkArcIds(G); 527 checkEdgeIds(G); 528 checkGraphNodeMap(G); 529 checkGraphArcMap(G); 530 checkGraphEdgeMap(G); 531 } 234 532 235 533 void checkGraphs() { 236 534 { // Checking ListGraph 237 checkGraph<ListGraph>(); 535 checkGraphBuild<ListGraph>(); 536 checkGraphAlter<ListGraph>(); 537 checkGraphErase<ListGraph>(); 538 checkGraphSnapshot<ListGraph>(); 238 539 checkGraphValidityErase<ListGraph>(); 239 540 } 240 541 { // Checking SmartGraph 241 checkGraph<SmartGraph>(); 542 checkGraphBuild<SmartGraph>(); 543 checkGraphSnapshot<SmartGraph>(); 242 544 checkGraphValidity<SmartGraph>(); 243 545 } 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 } 255 563 } 256 564 -
test/graph_test.h
r263 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 115 115 check(e==INVALID,"Wrong IncEdge list linking."); 116 116 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); 117 126 } 118 127 -
test/graph_utils_test.cc
r220 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/heap_test.cc
r293 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/kruskal_test.cc
r209 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/maps_test.cc
r210 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/path_test.cc
r209 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/random_test.cc
r209 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/test_tools.h
r209 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/test_tools_fail.cc
r209 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/test_tools_pass.cc
r209 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/time_measure_test.cc
r209 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/unionfind_test.cc
r209 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
tools/Makefile.am
r310 r385 1 1 if WANT_TOOLS 2 2 3 bin_PROGRAMS += 3 bin_PROGRAMS += \ 4 tools/dimacs-to-lgf 5 4 6 dist_bin_SCRIPTS += tools/lemon-0.x-to-1.x.sh 5 7 6 8 endif WANT_TOOLS 9 10 tools_dimacs_to_lgf_SOURCES = tools/dimacs-to-lgf.cc -
tools/lemon-0.x-to-1.x.sh
r310 r466 4 4 5 5 if [ $# -eq 0 -o x$1 = "x-h" -o x$1 = "x-help" -o x$1 = "x--help" ]; then 6 7 echo " $0 source-file"8 6 echo "Usage:" 7 echo " $0 source-file(s)" 8 exit 9 9 fi 10 10 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 11 for i in $@ 12 do 13 echo Update $i... 14 TMP=`mktemp` 15 sed -e "s/\<undirected graph\>/_gr_aph_label_/g"\ 16 -e "s/\<undirected graphs\>/_gr_aph_label_s/g"\ 17 -e "s/\<undirected edge\>/_ed_ge_label_/g"\ 18 -e "s/\<undirected edges\>/_ed_ge_label_s/g"\ 19 -e "s/\<directed graph\>/_digr_aph_label_/g"\ 20 -e "s/\<directed graphs\>/_digr_aph_label_s/g"\ 21 -e "s/\<directed edge\>/_ar_c_label_/g"\ 22 -e "s/\<directed edges\>/_ar_c_label_s/g"\ 23 -e "s/UGraph/_Gr_aph_label_/g"\ 24 -e "s/u[Gg]raph/_gr_aph_label_/g"\ 25 -e "s/\<Graph\>/_Digr_aph_label_/g"\ 26 -e "s/\<graph\>/_digr_aph_label_/g"\ 27 -e "s/\<Graphs\>/_Digr_aph_label_s/g"\ 28 -e "s/\<graphs\>/_digr_aph_label_s/g"\ 29 -e "s/_Graph/__Gr_aph_label_/g"\ 30 -e "s/\([Gg]\)raph\([a-z_]\)/_\1r_aph_label_\2/g"\ 31 -e "s/\([a-z_]\)graph/\1_gr_aph_label_/g"\ 32 -e "s/Graph/_Digr_aph_label_/g"\ 33 -e "s/graph/_digr_aph_label_/g"\ 34 -e "s/UEdge/_Ed_ge_label_/g"\ 35 -e "s/u[Ee]dge/_ed_ge_label_/g"\ 36 -e "s/IncEdgeIt/_In_cEd_geIt_label_/g"\ 37 -e "s/\<Edge\>/_Ar_c_label_/g"\ 38 -e "s/\<edge\>/_ar_c_label_/g"\ 39 -e "s/\<Edges\>/_Ar_c_label_s/g"\ 40 -e "s/\<edges\>/_ar_c_label_s/g"\ 41 -e "s/_Edge/__Ed_ge_label_/g"\ 42 -e "s/Edge\([a-z_]\)/_Ed_ge_label_\1/g"\ 43 -e "s/edge\([a-z_]\)/_ed_ge_label_\1/g"\ 44 -e "s/\([a-z_]\)edge/\1_ed_ge_label_/g"\ 45 -e "s/Edge/_Ar_c_label_/g"\ 46 -e "s/edge/_ar_c_label_/g"\ 47 -e "s/A[Nn]ode/_Re_d_label_/g"\ 48 -e "s/B[Nn]ode/_Blu_e_label_/g"\ 49 -e "s/A-[Nn]ode/_Re_d_label_/g"\ 50 -e "s/B-[Nn]ode/_Blu_e_label_/g"\ 51 -e "s/a[Nn]ode/_re_d_label_/g"\ 52 -e "s/b[Nn]ode/_blu_e_label_/g"\ 53 -e "s/\<UGRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__GR_APH_TY_PEDE_FS_label_\1/g"\ 54 -e "s/\<GRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__DIGR_APH_TY_PEDE_FS_label_\1/g"\ 55 -e "s/\<UGRAPH_TYPEDEFS\>/_GR_APH_TY_PEDE_FS_label_/g"\ 56 -e "s/\<GRAPH_TYPEDEFS\>/_DIGR_APH_TY_PEDE_FS_label_/g"\ 57 -e "s/_Digr_aph_label_/Digraph/g"\ 58 -e "s/_digr_aph_label_/digraph/g"\ 59 -e "s/_Gr_aph_label_/Graph/g"\ 60 -e "s/_gr_aph_label_/graph/g"\ 61 -e "s/_Ar_c_label_/Arc/g"\ 62 -e "s/_ar_c_label_/arc/g"\ 63 -e "s/_Ed_ge_label_/Edge/g"\ 64 -e "s/_ed_ge_label_/edge/g"\ 65 -e "s/_In_cEd_geIt_label_/IncEdgeIt/g"\ 66 -e "s/_Re_d_label_/Red/g"\ 67 -e "s/_Blu_e_label_/Blue/g"\ 68 -e "s/_re_d_label_/red/g"\ 69 -e "s/_blu_e_label_/blue/g"\ 70 -e "s/_GR_APH_TY_PEDE_FS_label_/GRAPH_TYPEDEFS/g"\ 71 -e "s/_DIGR_APH_TY_PEDE_FS_label_/DIGRAPH_TYPEDEFS/g"\ 72 -e "s/DigraphToEps/GraphToEps/g"\ 73 -e "s/digraphToEps/graphToEps/g"\ 74 -e "s/\<DefPredMap\>/SetPredMap/g"\ 75 -e "s/\<DefDistMap\>/SetDistMap/g"\ 76 -e "s/\<DefReachedMap\>/SetReachedMap/g"\ 77 -e "s/\<DefProcessedMap\>/SetProcessedMap/g"\ 78 -e "s/\<DefHeap\>/SetHeap/g"\ 79 -e "s/\<DefStandardHeap\>/SetStandradHeap/g"\ 80 -e "s/\<DefOperationTraits\>/SetOperationTraits/g"\ 81 -e "s/\<DefProcessedMapToBeDefaultMap\>/SetStandardProcessedMap/g"\ 82 -e "s/\<copyGraph\>/graphCopy/g"\ 83 -e "s/\<copyDigraph\>/digraphCopy/g"\ 84 -e "s/\<HyperCubeDigraph\>/HypercubeGraph/g"\ 85 -e "s/\<IntegerMap\>/RangeMap/g"\ 86 -e "s/\<integerMap\>/rangeMap/g"\ 87 -e "s/\<\([sS]\)tdMap\>/\1parseMap/g"\ 88 -e "s/\<\([Ff]\)unctorMap\>/\1unctorToMap/g"\ 89 -e "s/\<\([Mm]\)apFunctor\>/\1apToFunctor/g"\ 90 -e "s/\<\([Ff]\)orkWriteMap\>/\1orkMap/g"\ 91 -e "s/\<StoreBoolMap\>/LoggerBoolMap/g"\ 92 -e "s/\<storeBoolMap\>/loggerBoolMap/g"\ 93 -e "s/\<BoundingBox\>/Box/g"\ 94 -e "s/\<readNauty\>/readNautyGraph/g"\ 95 -e "s/\<RevDigraphAdaptor\>/ReverseDigraph/g"\ 96 -e "s/\<revDigraphAdaptor\>/reverseDigraph/g"\ 97 -e "s/\<SubDigraphAdaptor\>/SubDigraph/g"\ 98 -e "s/\<subDigraphAdaptor\>/subDigraph/g"\ 99 -e "s/\<SubGraphAdaptor\>/SubGraph/g"\ 100 -e "s/\<subGraphAdaptor\>/subGraph/g"\ 101 -e "s/\<NodeSubDigraphAdaptor\>/FilterNodes/g"\ 102 -e "s/\<nodeSubDigraphAdaptor\>/filterNodes/g"\ 103 -e "s/\<ArcSubDigraphAdaptor\>/FilterArcs/g"\ 104 -e "s/\<arcSubDigraphAdaptor\>/filterArcs/g"\ 105 -e "s/\<UndirDigraphAdaptor\>/Undirector/g"\ 106 -e "s/\<undirDigraphAdaptor\>/undirector/g"\ 107 -e "s/\<ResDigraphAdaptor\>/ResidualDigraph/g"\ 108 -e "s/\<resDigraphAdaptor\>/residualDigraph/g"\ 109 -e "s/\<SplitDigraphAdaptor\>/SplitNodes/g"\ 110 -e "s/\<splitDigraphAdaptor\>/splitNodes/g"\ 111 -e "s/\<SubGraphAdaptor\>/SubGraph/g"\ 112 -e "s/\<subGraphAdaptor\>/subGraph/g"\ 113 -e "s/\<NodeSubGraphAdaptor\>/FilterNodes/g"\ 114 -e "s/\<nodeSubGraphAdaptor\>/filterNodes/g"\ 115 -e "s/\<ArcSubGraphAdaptor\>/FilterEdges/g"\ 116 -e "s/\<arcSubGraphAdaptor\>/filterEdges/g"\ 117 -e "s/\<DirGraphAdaptor\>/Orienter/g"\ 118 -e "s/\<dirGraphAdaptor\>/orienter/g"\ 119 <$i > $TMP 120 mv $TMP $i 121 done
Note: See TracChangeset
for help on using the changeset viewer.