Changes in / [468:75a5df083951:467:ba49101c9b07] in lemon
- Files:
-
- 23 deleted
- 94 edited
Legend:
- Unmodified
- Added
- Removed
-
.hgignore
r400 r298 37 37 ^objs.*/.* 38 38 ^test/[a-z_]*$ 39 ^tools/[a-z-_]*$40 39 ^demo/.*_demo$ 41 40 ^build/.* -
LICENSE
r463 r107 2 2 copyright/license. 3 3 4 Copyright (C) 2003-200 9Egervary Jeno Kombinatorikus Optimalizalasi4 Copyright (C) 2003-2008 Egervary Jeno Kombinatorikus Optimalizalasi 5 5 Kutatocsoport (Egervary Combinatorial Optimization Research Group, 6 6 EGRES). -
Makefile.am
r375 r321 1 1 ACLOCAL_AMFLAGS = -I m4 2 3 AM_CXXFLAGS = $(WARNINGCXXFLAGS)4 2 5 3 AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir) -
configure.ac
r375 r310 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} 21 23 22 24 dnl Do compilation tests using the C++ compiler. … … 45 47 46 48 dnl Set custom compiler flags when using g++. 47 if test "$GXX" = yes -a "$ICC" = no; then48 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"49 if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes -a "$ICC" = no; then 50 CXXFLAGS="$CXXFLAGS -Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas" 49 51 fi 50 AC_SUBST([WARNINGCXXFLAGS])51 52 52 53 dnl Checks for libraries. … … 113 114 echo 114 115 echo C++ compiler.................. : $CXX 115 echo C++ compiles flags............ : $ WARNINGCXXFLAGS $CXXFLAGS116 echo C++ compiles flags............ : $CXXFLAGS 116 117 echo 117 118 #echo GLPK support.................. : $lx_glpk_found -
demo/arg_parser_demo.cc
r463 r311 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
demo/graph_to_eps_demo.cc
r463 r313 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 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 9LEMON Project").88 copyright("(C) 2003-2008 LEMON Project"). 89 89 run(); 90 90 … … 93 93 coords(coords). 94 94 title("Sample .eps figure"). 95 copyright("(C) 2003-200 9LEMON Project").95 copyright("(C) 2003-2008 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 9LEMON Project").108 copyright("(C) 2003-2008 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 9LEMON Project").135 copyright("(C) 2003-2008 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 9LEMON Project").150 copyright("(C) 2003-2008 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 9LEMON Project").166 copyright("(C) 2003-2008 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 9LEMON Project").196 copyright("(C) 2003-2008 LEMON Project"). 197 197 coords(hcoords). 198 198 absoluteNodeSizes().absoluteArcWidths(). -
demo/lgf_demo.cc
r463 r294 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
doc/CMakeLists.txt
r347 r225 14 14 COMMAND rm -rf gen-images 15 15 COMMAND mkdir gen-images 16 COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps17 16 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 17 COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps -
doc/Doxyfile.in
r379 r316 67 67 ENABLED_SECTIONS = 68 68 MAX_INITIALIZER_LINES = 5 69 SHOW_USED_FILES = NO69 SHOW_USED_FILES = YES 70 70 SHOW_DIRECTORIES = YES 71 71 SHOW_FILES = YES -
doc/Makefile.am
r349 r317 15 15 16 16 DOC_EPS_IMAGES18 = \ 17 grid_graph.eps \18 17 nodeshape_0.eps \ 19 18 nodeshape_1.eps \ -
doc/coding_style.dox
r463 r210 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
doc/dirs.dox
r463 r318 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 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
r463 r318 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 17 17 */ 18 18 19 namespace lemon {20 21 19 /** 22 20 @defgroup datas Data Structures … … 63 61 64 62 /** 65 @defgroup graph_adaptors Adaptor Classes for graphs66 @ingroup graphs67 \brief This group contains several adaptor classes for digraphs and graphs68 69 The main parts of LEMON are the different graph structures, generic70 graph algorithms, graph concepts which couple these, and graph71 adaptors. While the previous notions are more or less clear, the72 latter one needs further explanation. Graph adaptors are graph classes73 which serve for considering graph structures in different ways.74 75 A short example makes this much clearer. Suppose that we have an76 instance \c g of a directed graph type say ListDigraph and an algorithm77 \code78 template <typename Digraph>79 int algorithm(const Digraph&);80 \endcode81 is needed to run on the reverse oriented graph. It may be expensive82 (in time or in memory usage) to copy \c g with the reversed83 arcs. In this case, an adaptor class is used, which (according84 to LEMON digraph concepts) works as a digraph. The adaptor uses the85 original digraph structure and digraph operations when methods of the86 reversed oriented graph are called. This means that the adaptor have87 minor memory usage, and do not perform sophisticated algorithmic88 actions. The purpose of it is to give a tool for the cases when a89 graph have to be used in a specific alteration. If this alteration is90 obtained by a usual construction like filtering the arc-set or91 considering a new orientation, then an adaptor is worthwhile to use.92 To come back to the reverse oriented graph, in this situation93 \code94 template<typename Digraph> class ReverseDigraph;95 \endcode96 template class can be used. The code looks as follows97 \code98 ListDigraph g;99 ReverseDigraph<ListGraph> rg(g);100 int result = algorithm(rg);101 \endcode102 After running the algorithm, the original graph \c g is untouched.103 This techniques gives rise to an elegant code, and based on stable104 graph adaptors, complex algorithms can be implemented easily.105 106 In flow, circulation and bipartite matching problems, the residual107 graph is of particular importance. Combining an adaptor implementing108 this, shortest path algorithms and minimum mean cycle algorithms,109 a range of weighted and cardinality optimization algorithms can be110 obtained. For other examples, the interested user is referred to the111 detailed documentation of particular adaptors.112 113 The behavior of graph adaptors can be very different. Some of them keep114 capabilities of the original graph while in other cases this would be115 meaningless. This means that the concepts that they are models of depend116 on the graph adaptor, and the wrapped graph(s).117 If an arc of \c rg is deleted, this is carried out by deleting the118 corresponding arc of \c g, thus the adaptor modifies the original graph.119 120 But for a residual graph, this operation has no sense.121 Let us stand one more example here to simplify your work.122 RevGraphAdaptor has constructor123 \code124 ReverseDigraph(Digraph& digraph);125 \endcode126 This means that in a situation, when a <tt>const ListDigraph&</tt>127 reference to a graph is given, then it have to be instantiated with128 <tt>Digraph=const ListDigraph</tt>.129 \code130 int algorithm1(const ListDigraph& g) {131 RevGraphAdaptor<const ListDigraph> rg(g);132 return algorithm2(rg);133 }134 \endcode135 */136 137 /**138 63 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs 139 64 @ingroup graphs … … 164 89 165 90 This group describes maps that are specifically designed to assign 166 values to the nodes and arcs/edges of graphs. 167 168 If you are looking for the standard graph maps (\c NodeMap, \c ArcMap, 169 \c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts". 91 values to the nodes and arcs of graphs. 170 92 */ 171 93 … … 178 100 maps from other maps. 179 101 180 Most of them are \ref concepts::ReadMap "read-only maps".102 Most of them are \ref lemon::concepts::ReadMap "read-only maps". 181 103 They can make arithmetic and logical operations between one or two maps 182 104 (negation, shifting, addition, multiplication, logical 'and', 'or', … … 280 202 \brief Common graph search algorithms. 281 203 282 This group describes the common graph search algorithms , namely283 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).204 This group describes the common graph search algorithms like 205 Breadth-First Search (BFS) and Depth-First Search (DFS). 284 206 */ 285 207 … … 289 211 \brief Algorithms for finding shortest paths. 290 212 291 This group describes the algorithms for finding shortest paths in digraphs. 292 293 - \ref Dijkstra algorithm for finding shortest paths from a source node 294 when all arc lengths are non-negative. 295 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths 296 from a source node when arc lenghts can be either positive or negative, 297 but the digraph should not contain directed cycles with negative total 298 length. 299 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms 300 for solving the \e all-pairs \e shortest \e paths \e problem when arc 301 lenghts can be either positive or negative, but the digraph should 302 not contain directed cycles with negative total length. 303 - \ref Suurballe A successive shortest path algorithm for finding 304 arc-disjoint paths between two nodes having minimum total length. 213 This group describes the algorithms for finding shortest paths in graphs. 305 214 */ 306 215 … … 313 222 feasible circulations. 314 223 315 The \e maximum \e flow \e problem is to find a flow of maximum value between 316 a single source and a single target. Formally, there is a \f$G=(V,A)\f$ 317 digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and 318 \f$s, t \in V\f$ source and target nodes. 319 A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the 320 following optimization problem. 321 322 \f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f] 323 \f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a) 324 \qquad \forall v\in V\setminus\{s,t\} \f] 325 \f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f] 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] 326 234 327 235 LEMON contains several algorithms for solving maximum flow problems: 328 - \ref EdmondsKarp Edmonds-Karp algorithm.329 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.330 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.331 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.332 333 In most cases the \ref Preflow "Preflow" algorithm provides the334 fastest method for computing a maximum flow. All implementations335 provides functions to also query the minimum cut, which is the dual336 pro blem of the maximum flow.236 - \ref lemon::EdmondsKarp "Edmonds-Karp" 237 - \ref lemon::Preflow "Goldberg's Preflow algorithm" 238 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees" 239 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees" 240 241 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the 242 fastest method to compute the maximum flow. All impelementations 243 provides functions to query the minimum cut, which is the dual linear 244 programming problem of the maximum flow. 337 245 */ 338 246 … … 345 253 This group describes the algorithms for finding minimum cost flows and 346 254 circulations. 347 348 The \e minimum \e cost \e flow \e problem is to find a feasible flow of349 minimum total cost from a set of supply nodes to a set of demand nodes350 in a network with capacity constraints and arc costs.351 Formally, let \f$G=(V,A)\f$ be a digraph,352 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and353 upper bounds for the flow values on the arcs,354 \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow355 on the arcs, and356 \f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values357 of the nodes.358 A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of359 the following optimization problem.360 361 \f[ \min\sum_{a\in A} f(a) cost(a) \f]362 \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =363 supply(v) \qquad \forall v\in V \f]364 \f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]365 366 LEMON contains several algorithms for solving minimum cost flow problems:367 - \ref CycleCanceling Cycle-canceling algorithms.368 - \ref CapacityScaling Successive shortest path algorithm with optional369 capacity scaling.370 - \ref CostScaling Push-relabel and augment-relabel algorithms based on371 cost scaling.372 - \ref NetworkSimplex Primal network simplex algorithm with various373 pivot strategies.374 255 */ 375 256 … … 382 263 This group describes the algorithms for finding minimum cut in graphs. 383 264 384 The \e minimum \e cut \eproblem is to find a non-empty and non-complete385 \f$X\f$ subset of the nodes with minimum overall capacity on386 outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a387 \f$c ap:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum265 The minimum cut problem is to find a non-empty and non-complete 266 \f$X\f$ subset of the vertices with minimum overall capacity on 267 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an 268 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum 388 269 cut is the \f$X\f$ solution of the next optimization problem: 389 270 390 271 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} 391 \sum_{uv\in A, u\in X, v\not\in X}cap(uv)\f]272 \sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f] 392 273 393 274 LEMON contains several algorithms related to minimum cut problems: 394 275 395 - \ref HaoOrlin "Hao-Orlin algorithm" for calculatingminimum cut396 in directed graphs .397 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for398 calculat ing minimum cut in undirected graphs.399 - \ref GomoryHuTree "Gomory-Hu tree computation" for calculating400 all-pairs minimum cut in undirected graphs.276 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut 277 in directed graphs 278 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to 279 calculate minimum cut in undirected graphs 280 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all 281 pairs minimum cut in undirected graphs 401 282 402 283 If you want to find minimum cut just between two distinict nodes, 403 see the \ref max_flow "maximum flow problem".284 please see the \ref max_flow "Maximum Flow page". 404 285 */ 405 286 … … 440 321 graphs. The matching problems in bipartite graphs are generally 441 322 easier than in general graphs. The goal of the matching optimization 442 can be finding maximum cardinality, maximum weight or minimum cost323 can be the finding maximum cardinality, maximum weight or minimum cost 443 324 matching. The search can be constrained to find perfect or 444 325 maximum cardinality matching. 445 326 446 The matching algorithms implemented in LEMON: 447 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm 448 for calculating maximum cardinality matching in bipartite graphs. 449 - \ref PrBipartiteMatching Push-relabel algorithm 450 for calculating maximum cardinality matching in bipartite graphs. 451 - \ref MaxWeightedBipartiteMatching 452 Successive shortest path algorithm for calculating maximum weighted 453 matching and maximum weighted bipartite matching in bipartite graphs. 454 - \ref MinCostMaxBipartiteMatching 455 Successive shortest path algorithm for calculating minimum cost maximum 456 matching in bipartite graphs. 457 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating 458 maximum cardinality matching in general graphs. 459 - \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating 460 maximum weighted matching in general graphs. 461 - \ref MaxWeightedPerfectMatching 462 Edmond's blossom shrinking algorithm for calculating maximum weighted 463 perfect matching in general graphs. 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 464 347 465 348 \image html bipartite_matching.png … … 473 356 474 357 This group describes the algorithms for finding a minimum cost spanning 475 tree in a graph .358 tree in a graph 476 359 */ 477 360 … … 582 465 583 466 /** 584 @defgroup lemon_io LEMON Graph Format467 @defgroup lemon_io LEMON Input-Output 585 468 @ingroup io_group 586 469 \brief Reading and writing LEMON Graph Format. … … 597 480 This group describes general \c EPS drawing methods and special 598 481 graph exporting tools. 599 */600 601 /**602 @defgroup dimacs_group DIMACS format603 @ingroup io_group604 \brief Read and write files in DIMACS format605 606 Tools to read a digraph from or write it to a file in DIMACS format data.607 */608 609 /**610 @defgroup nauty_group NAUTY Format611 @ingroup io_group612 \brief Read \e Nauty format613 614 Tool to read graphs from \e Nauty format data.615 482 */ 616 483 … … 664 531 \anchor demoprograms 665 532 666 @defgroup demos Demo Programs533 @defgroup demos Demo programs 667 534 668 535 Some demo programs are listed here. Their full source codes can be found in … … 674 541 675 542 /** 676 @defgroup tools Standalone Utility Applications543 @defgroup tools Standalone utility applications 677 544 678 545 Some utility applications are listed here. … … 682 549 */ 683 550 684 } -
doc/lgf.dox
r463 r313 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
doc/license.dox
r463 r209 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
doc/mainpage.dox
r463 r314 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
doc/migration.dox
r463 r314 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 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> lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual28 <tt>script/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>lemon-0.x-to-1.x.sh</tt> script replaces the words \c graph, 57 \c ugraph, \c edge and \c uedge in your own identifiers and in 58 strings, comments etc. as well as in all LEMON specific identifiers. 59 So use the script carefully and make a backup copy of your source files 60 before applying the script to them.</b> 56 <b>The <tt>script/lemon-0.x-to-1.x.sh</tt> tool replaces all instances of 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> 61 59 62 60 \section migration-lgf LGF tools -
doc/named-param.dox
r463 r269 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
doc/namespaces.dox
r463 r209 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
doc/template.h
r463 r209 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/Makefile.am
r468 r464 8 8 9 9 lemon_libemon_la_SOURCES = \ 10 11 12 13 10 lemon/arg_parser.cc \ 11 lemon/base.cc \ 12 lemon/color.cc \ 13 lemon/random.cc 14 14 15 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) $(AM_CXXFLAGS)15 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) 16 16 #lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS) 17 17 18 18 lemon_HEADERS += \ 19 lemon/adaptors.h \ 20 lemon/arg_parser.h \ 19 lemon/arg_parser.h \ 21 20 lemon/assert.h \ 22 lemon/bfs.h \ 23 lemon/bin_heap.h \ 24 lemon/circulation.h \ 25 lemon/color.h \ 21 lemon/bfs.h \ 22 lemon/bin_heap.h \ 23 lemon/color.h \ 26 24 lemon/concept_check.h \ 27 25 lemon/counter.h \ 28 26 lemon/core.h \ 29 lemon/dfs.h \ 30 lemon/dijkstra.h \ 31 lemon/dim2.h \ 32 lemon/dimacs.h \ 33 lemon/elevator.h \ 27 lemon/dfs.h \ 28 lemon/dijkstra.h \ 29 lemon/dim2.h \ 34 30 lemon/error.h \ 35 lemon/full_graph.h \ 36 lemon/graph_to_eps.h \ 37 lemon/grid_graph.h \ 38 lemon/hypercube_graph.h \ 31 lemon/graph_to_eps.h \ 39 32 lemon/kruskal.h \ 40 lemon/hao_orlin.h \41 33 lemon/lgf_reader.h \ 42 34 lemon/lgf_writer.h \ … … 44 36 lemon/maps.h \ 45 37 lemon/math.h \ 46 lemon/max_matching.h \47 lemon/nauty_reader.h \48 38 lemon/path.h \ 49 lemon/preflow.h \50 39 lemon/radix_sort.h \ 51 40 lemon/random.h \ 52 41 lemon/smart_graph.h \ 53 lemon/suurballe.h \ 54 lemon/time_measure.h \ 55 lemon/tolerance.h \ 42 lemon/time_measure.h \ 43 lemon/tolerance.h \ 56 44 lemon/unionfind.h 57 45 … … 60 48 lemon/bits/array_map.h \ 61 49 lemon/bits/base_extender.h \ 62 50 lemon/bits/bezier.h \ 63 51 lemon/bits/default_map.h \ 64 lemon/bits/enable_if.h \ 65 lemon/bits/graph_adaptor_extender.h \ 52 lemon/bits/enable_if.h \ 66 53 lemon/bits/graph_extender.h \ 67 54 lemon/bits/map_extender.h \ 68 55 lemon/bits/path_dump.h \ 69 56 lemon/bits/traits.h \ 70 lemon/bits/variant.h \71 57 lemon/bits/vector_map.h 72 58 -
lemon/arg_parser.cc
r463 r311 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/arg_parser.h
r463 r311 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/assert.h
r463 r290 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/base.cc
r463 r220 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bfs.h
r463 r301 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 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 type is \ref ListDigraph. 122 ///The default value is \ref ListDigraph. The value of GR is not used 123 ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits. 124 ///\tparam TR Traits class to set various data types used by the algorithm. 125 ///The default traits class is 126 ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>". 127 ///See \ref BfsDefaultTraits for the documentation of 128 ///a Bfs traits class. 123 129 #ifdef DOXYGEN 124 130 template <typename GR, … … 146 152 typedef PredMapPath<Digraph, PredMap> Path; 147 153 148 ///The \ref BfsDefaultTraits "traits class" of the algorithm.154 ///The traits class. 149 155 typedef TR Traits; 150 156 … … 208 214 typedef Bfs Create; 209 215 210 ///\name Named Template Parameters216 ///\name Named template parameters 211 217 212 218 ///@{ … … 226 232 ///\ref named-templ-param "Named parameter" for setting 227 233 ///PredMap type. 228 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.229 234 template <class T> 230 235 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > { … … 246 251 ///\ref named-templ-param "Named parameter" for setting 247 252 ///DistMap type. 248 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.249 253 template <class T> 250 254 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > { … … 266 270 ///\ref named-templ-param "Named parameter" for setting 267 271 ///ReachedMap type. 268 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.269 272 template <class T> 270 273 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { … … 286 289 ///\ref named-templ-param "Named parameter" for setting 287 290 ///ProcessedMap type. 288 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.289 291 template <class T> 290 292 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { … … 339 341 340 342 ///Sets the map that stores the predecessor arcs. 341 ///If you don't use this function before calling \ref run(Node) "run()" 342 ///or \ref init(), an instance will be allocated automatically. 343 ///The destructor deallocates this automatically allocated map, 344 ///of course. 343 ///If you don't use this function before calling \ref run(), 344 ///it will allocate one. The destructor deallocates this 345 ///automatically allocated map, of course. 345 346 ///\return <tt> (*this) </tt> 346 347 Bfs &predMap(PredMap &m) … … 357 358 358 359 ///Sets the map that indicates which nodes are reached. 359 ///If you don't use this function before calling \ref run(Node) "run()" 360 ///or \ref init(), an instance will be allocated automatically. 361 ///The destructor deallocates this automatically allocated map, 362 ///of course. 360 ///If you don't use this function before calling \ref run(), 361 ///it will allocate one. The destructor deallocates this 362 ///automatically allocated map, of course. 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(Node) "run()" 378 ///or \ref init(), an instance will be allocated automatically. 379 ///The destructor deallocates this automatically allocated map, 380 ///of course. 377 ///If you don't use this function before calling \ref run(), 378 ///it will allocate one. The destructor deallocates this 379 ///automatically allocated map, of course. 381 380 ///\return <tt> (*this) </tt> 382 381 Bfs &processedMap(ProcessedMap &m) … … 394 393 ///Sets the map that stores the distances of the nodes calculated by 395 394 ///the algorithm. 396 ///If you don't use this function before calling \ref run(Node) "run()" 397 ///or \ref init(), an instance will be allocated automatically. 398 ///The destructor deallocates this automatically allocated map, 399 ///of course. 395 ///If you don't use this function before calling \ref run(), 396 ///it will allocate one. The destructor deallocates this 397 ///automatically allocated map, of course. 400 398 ///\return <tt> (*this) </tt> 401 399 Bfs &distMap(DistMap &m) … … 411 409 public: 412 410 413 ///\name Execution Control 414 ///The simplest way to execute the BFS algorithm is to use one of the 415 ///member functions called \ref run(Node) "run()".\n 416 ///If you need more control on the execution, first you have to call 417 ///\ref init(), then you can add several source nodes with 418 ///\ref addSource(). Finally the actual path computation can be 419 ///performed with one of the \ref start() functions. 411 ///\name Execution control 412 ///The simplest way to execute the algorithm is to use 413 ///one of the member functions called \ref lemon::Bfs::run() "run()". 414 ///\n 415 ///If you need more control on the execution, first you must call 416 ///\ref lemon::Bfs::init() "init()", then you can add several source 417 ///nodes with \ref lemon::Bfs::addSource() "addSource()". 418 ///Finally \ref lemon::Bfs::start() "start()" will perform the 419 ///actual path computation. 420 420 421 421 ///@{ 422 422 423 ///\brief Initializes the internal data structures.424 ///425 423 ///Initializes the internal data structures. 424 425 ///Initializes the internal data structures. 426 /// 426 427 void init() 427 428 { … … 557 558 } 558 559 559 ///Returns \c false if there are nodes to be processed. 560 561 ///Returns \c false if there are nodes to be processed 562 ///in the queue. 560 ///\brief Returns \c false if there are nodes 561 ///to be processed. 562 /// 563 ///Returns \c false if there are nodes 564 ///to be processed in the queue. 563 565 bool emptyQueue() const { return _queue_tail==_queue_head; } 564 566 565 567 ///Returns the number of the nodes to be processed. 566 568 567 ///Returns the number of the nodes to be processed 568 ///in the queue. 569 ///Returns the number of the nodes to be processed in the queue. 569 570 int queueSize() const { return _queue_head-_queue_tail; } 570 571 … … 731 732 732 733 ///\name Query Functions 733 ///The result s of theBFS algorithm can be obtained using these734 ///The result of the %BFS algorithm can be obtained using these 734 735 ///functions.\n 735 ///Either \ref run(Node) "run()" or \ref start() should be called736 /// before using them.736 ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start() 737 ///"start()" must be called before using them. 737 738 738 739 ///@{ … … 742 743 ///Returns the shortest path to a node. 743 744 /// 744 ///\warning \c t should be reach edfrom the root(s).745 /// 746 ///\pre Either \ref run( Node) "run()" or \ref init()747 /// must be called beforeusing this function.745 ///\warning \c t should be reachable from the root(s). 746 /// 747 ///\pre Either \ref run() or \ref start() must be called before 748 ///using this function. 748 749 Path path(Node t) const { return Path(*G, *_pred, t); } 749 750 … … 752 753 ///Returns the distance of a node from the root(s). 753 754 /// 754 ///\warning If node \c v is not reach edfrom the root(s), then755 ///\warning If node \c v is not reachable from the root(s), then 755 756 ///the return value of this function is undefined. 756 757 /// 757 ///\pre Either \ref run( Node) "run()" or \ref init()758 /// must be called beforeusing this function.758 ///\pre Either \ref run() or \ref start() must be called before 759 ///using this function. 759 760 int dist(Node v) const { return (*_dist)[v]; } 760 761 … … 763 764 ///This function returns the 'previous arc' of the shortest path 764 765 ///tree for the node \c v, i.e. it returns the last arc of a 765 ///shortest path from a rootto \c v. It is \c INVALID if \c v766 ///is not reach edfrom the root(s) or if \c v is a root.766 ///shortest path from the root(s) to \c v. It is \c INVALID if \c v 767 ///is not reachable from the root(s) or if \c v is a root. 767 768 /// 768 769 ///The shortest path tree used here is equal to the shortest path 769 770 ///tree used in \ref predNode(). 770 771 /// 771 ///\pre Either \ref run( Node) "run()" or \ref init()772 /// must be called beforeusing this function.772 ///\pre Either \ref run() or \ref start() must be called before 773 ///using this function. 773 774 Arc predArc(Node v) const { return (*_pred)[v];} 774 775 … … 777 778 ///This function returns the 'previous node' of the shortest path 778 779 ///tree for the node \c v, i.e. it returns the last but one node 779 ///from a shortest path from a rootto \c v. It is \c INVALID780 ///if \c v is not reach edfrom the root(s) or if \c v is a root.780 ///from a shortest path from the root(s) to \c v. It is \c INVALID 781 ///if \c v is not reachable from the root(s) or if \c v is a root. 781 782 /// 782 783 ///The shortest path tree used here is equal to the shortest path 783 784 ///tree used in \ref predArc(). 784 785 /// 785 ///\pre Either \ref run( Node) "run()" or \ref init()786 /// must be called beforeusing this function.786 ///\pre Either \ref run() or \ref start() must be called before 787 ///using this function. 787 788 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 788 789 G->source((*_pred)[v]); } … … 794 795 ///of the nodes calculated by the algorithm. 795 796 /// 796 ///\pre Either \ref run( Node) "run()"or \ref init()797 ///\pre Either \ref run() or \ref init() 797 798 ///must be called before using this function. 798 799 const DistMap &distMap() const { return *_dist;} … … 804 805 ///arcs, which form the shortest path tree. 805 806 /// 806 ///\pre Either \ref run( Node) "run()"or \ref init()807 ///\pre Either \ref run() or \ref init() 807 808 ///must be called before using this function. 808 809 const PredMap &predMap() const { return *_pred;} 809 810 810 ///Checks if a node is reached from the root(s). 811 812 ///Returns \c true if \c v is reached from the root(s). 813 /// 814 ///\pre Either \ref run(Node) "run()" or \ref init() 811 ///Checks if a node is reachable from the root(s). 812 813 ///Returns \c true if \c v is reachable from the root(s). 814 ///\pre Either \ref run() or \ref start() 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( Node) "run()" method, it uses the961 /// functionsand features of the plain \ref Bfs.960 /// It does not have own \ref run() method, it uses the functions 961 /// and features of the plain \ref Bfs. 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( Node) "run()"1181 ///\warning Don't forget to put the \ref BfsWizard::run() "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(Node) "run()" 1410 /// or \ref init(), an instance will be allocated automatically. 1411 /// The destructor deallocates this automatically allocated map, 1412 /// of course. 1409 /// If you don't use this function before calling \ref run(), 1410 /// it will allocate one. The destructor deallocates this 1411 /// automatically allocated map, of course. 1413 1412 /// \return <tt> (*this) </tt> 1414 1413 BfsVisit &reachedMap(ReachedMap &m) { … … 1423 1422 public: 1424 1423 1425 /// \name Execution Control 1426 /// The simplest way to execute the BFS algorithm is to use one of the 1427 /// member functions called \ref run(Node) "run()".\n 1428 /// If you need more control on the execution, first you have to call 1429 /// \ref init(), then you can add several source nodes with 1430 /// \ref addSource(). Finally the actual path computation can be 1431 /// performed with one of the \ref start() functions. 1424 /// \name Execution control 1425 /// The simplest way to execute the algorithm is to use 1426 /// one of the member functions called \ref lemon::BfsVisit::run() 1427 /// "run()". 1428 /// \n 1429 /// If you need more control on the execution, first you must call 1430 /// \ref lemon::BfsVisit::init() "init()", then you can add several 1431 /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()". 1432 /// Finally \ref lemon::BfsVisit::start() "start()" will perform the 1433 /// actual path computation. 1432 1434 1433 1435 /// @{ … … 1729 1731 1730 1732 /// \name Query Functions 1731 /// The result s of theBFS algorithm can be obtained using these1733 /// The result of the %BFS algorithm can be obtained using these 1732 1734 /// functions.\n 1733 /// Either \ref run(Node) "run()" or \ref start() should be called1734 /// before using them.1735 1735 /// Either \ref lemon::BfsVisit::run() "run()" or 1736 /// \ref lemon::BfsVisit::start() "start()" must be called before 1737 /// using them. 1736 1738 ///@{ 1737 1739 1738 /// \brief Checks if a node is reached from the root(s). 1739 /// 1740 /// Returns \c true if \c v is reached from the root(s). 1741 /// 1742 /// \pre Either \ref run(Node) "run()" or \ref init() 1740 /// \brief Checks if a node is reachable from the root(s). 1741 /// 1742 /// Returns \c true if \c v is reachable from the root(s). 1743 /// \pre Either \ref run() or \ref start() 1743 1744 /// must be called before using this function. 1744 bool reached(Node v) const{ return (*_reached)[v]; }1745 bool reached(Node v) { return (*_reached)[v]; } 1745 1746 1746 1747 ///@} -
lemon/bin_heap.h
r463 r209 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bits/alteration_notifier.h
r463 r314 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 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: anode container39 // and an edge container. But they do not store values directly,they40 // are just key continars for more value containers, which are the41 // node and edge maps.42 // 43 // The node and edge sets of the graphs can be changed as we add or erase38 // The simple graph's can be refered as two containers, one node container 39 // and one edge container. But they are not standard containers they 40 // does not store values directly they are just key continars for more 41 // value containers which are the node and edge maps. 42 // 43 // The graph's node and edge sets can be changed as we add or erase 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 a node or edge container. 53 // The first() and next() member functions make possible 54 // to iterate on the keys of the container. 55 // The id() function returns an integer id for each key. 56 // The maxId() function gives back an upper bound of the ids. 52 // This class provides an interface to the container. The \e first() and \e 53 // next() member functions make possible to iterate on the keys of the 54 // container. The \e id() function returns an integer id for each key. 55 // The \e maxId() function gives back an upper bound of the ids. 57 56 // 58 57 // For the proper functonality of this class, we should notify it 59 // about each alteration in the container. The alterations have four type :60 // a dd(), erase(), build() and clear(). The add() and61 // erase() signalthat only one or few items added or erased to or62 // from the graph. If all items are erased from the graph or if a new graph63 // is built from an empty graph,then it can be signaled with the58 // about each alteration in the container. The alterations have four type 59 // as \e add(), \e erase(), \e build() and \e clear(). The \e add() and 60 // \e erase() signals that only one or few items added or erased to or 61 // from the graph. If all items are erased from the graph or from an empty 62 // graph a new graph is builded then it can be signaled with the 64 63 // clear() and build() members. Important rule that if we erase items 65 // from graph swe should first signal the alteration and after that erase64 // from graph we should first signal the alteration and after that erase 66 65 // them from the container, on the other way on item addition we should 67 66 // first extend the container and just after that signal the alteration. 68 67 // 69 68 // The alteration can be observed with a class inherited from the 70 // ObserverBase nested class. The signals can be handled with69 // \e ObserverBase nested class. The signals can be handled with 71 70 // overriding the virtual functions defined in the base class. The 72 71 // observer base can be attached to the notifier with the 73 // attach() member and can be detached with detach() function. The72 // \e attach() member and can be detached with detach() function. The 74 73 // alteration handlers should not call any function which signals 75 74 // an other alteration in the same notifier and should not 76 75 // detach any observer from the notifier. 77 76 // 78 // Alteration observers try to be exception safe. If an add() or79 // a clear() function throws an exception then the remaining77 // Alteration observers try to be exception safe. If an \e add() or 78 // a \e clear() function throws an exception then the remaining 80 79 // observeres will not be notified and the fulfilled additions will 81 // be rolled back by calling the erase() or clear() functions.82 // Hence erase() and clear() should not throw exception.83 // Actullay, they can throw only \ref ImmediateDetach exception,84 // which detach the observer from the notifier.85 // 86 // There are some cases,when the alteration observing is not completly80 // be rolled back by calling the \e erase() or \e clear() 81 // functions. Thence the \e erase() and \e clear() should not throw 82 // exception. Actullay, it can be throw only \ref ImmediateDetach 83 // exception which detach the observer from the notifier. 84 // 85 // There are some place when the alteration observing is not completly 87 86 // reliable. If we want to carry out the node degree in the graph 88 // as in the \ref InDegMap and we use the reverse Arc(), then it cause87 // as in the \ref InDegMap and we use the reverseEdge that cause 89 88 // unreliable functionality. Because the alteration observing signals 90 // only erasing and adding but not the reversing ,it will stores bad91 // degrees. Apart form that the subgraph adaptors cannot even signal92 // the alterations because just a setting in the filter map can modify93 // the graph and this cannotbe watched in any way.89 // only erasing and adding but not the reversing it will stores bad 90 // degrees. The sub graph adaptors cannot signal the alterations because 91 // just a setting in the filter map can modify the graph and this cannot 92 // be watched in any way. 94 93 // 95 94 // \param _Container The container which is observed. … … 105 104 typedef _Item Item; 106 105 107 // \brief Exception which can be called from clear() and108 // erase().109 // 110 // From the clear() anderase() function only this106 // \brief Exception which can be called from \e clear() and 107 // \e erase(). 108 // 109 // From the \e clear() and \e erase() function only this 111 110 // exception is allowed to throw. The exception immediatly 112 111 // detaches the current observer from the notifier. Because the 113 // clear() anderase() should not throw other exceptions112 // \e clear() and \e erase() should not throw other exceptions 114 113 // it can be used to invalidate the observer. 115 114 struct ImmediateDetach {}; … … 123 122 // The observer interface contains some pure virtual functions 124 123 // to override. The add() and erase() functions are 125 // to notify the oberver when one item is added or erased. 124 // to notify the oberver when one item is added or 125 // erased. 126 126 // 127 127 // The build() and clear() members are to notify the observer -
lemon/bits/array_map.h
r463 r314 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 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 that automatically 40 // updates the map when a key is added to or erased from the graph. 41 // This map uses the allocators to implement the container functionality. 39 // The ArrayMap template class is graph map structure what 40 // automatically updates the map when a key is added to or erased from 41 // the map. This map uses the allocators to implement 42 // the container functionality. 42 43 // 43 // The template parameters are the Graph ,the current Item type and44 // The template parameters are the Graph the current Item type and 44 45 // the Value type of the map. 45 46 template <typename _Graph, typename _Item, typename _Value> … … 47 48 : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase { 48 49 public: 49 // The graph type .50 // The graph type of the maps. 50 51 typedef _Graph Graph; 51 // The item type .52 // The item type of the map. 52 53 typedef _Item Item; 53 54 // The reference map tag. 54 55 typedef True ReferenceMapTag; 55 56 56 // The key type of the map .57 // The key type of the maps. 57 58 typedef _Item Key; 58 59 // The value type of the map. … … 200 201 // \brief Adds a new key to the map. 201 202 // 202 // It adds a new key to the map. It iscalled by the observer notifier203 // It adds a new key to the map. It called by the observer notifier 203 204 // and it overrides the add() member function of the observer base. 204 205 virtual void add(const Key& key) { … … 228 229 // \brief Adds more new keys to the map. 229 230 // 230 // It adds more new keys to the map. It iscalled by the observer notifier231 // It adds more new keys to the map. It called by the observer notifier 231 232 // and it overrides the add() member function of the observer base. 232 233 virtual void add(const std::vector<Key>& keys) { … … 272 273 // \brief Erase a key from the map. 273 274 // 274 // Erase a key from the map. It iscalled by the observer notifier275 // Erase a key from the map. It called by the observer notifier 275 276 // and it overrides the erase() member function of the observer base. 276 277 virtual void erase(const Key& key) { … … 281 282 // \brief Erase more keys from the map. 282 283 // 283 // Erase more keys from the map. It iscalled by the observer notifier284 // Erase more keys from the map. It called by the observer notifier 284 285 // and it overrides the erase() member function of the observer base. 285 286 virtual void erase(const std::vector<Key>& keys) { … … 290 291 } 291 292 292 // \brief Build s the map.293 // 294 // It build s the map. It iscalled by the observer notifier293 // \brief Buildes the map. 294 // 295 // It buildes the map. It called by the observer notifier 295 296 // and it overrides the build() member function of the observer base. 296 297 virtual void build() { … … 306 307 // \brief Clear the map. 307 308 // 308 // It erase all items from the map. It iscalled by the observer notifier309 // It erase all items from the map. It called by the observer notifier 309 310 // and it overrides the clear() member function of the observer base. 310 311 virtual void clear() { -
lemon/bits/base_extender.h
r463 r314 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 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 graph types33 //\brief Extenders for the digraph types 34 34 namespace lemon { 35 35 -
lemon/bits/bezier.h
r463 r314 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bits/default_map.h
r463 r314 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bits/enable_if.h
r463 r314 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bits/graph_extender.h
r463 r314 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 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 graph types32 //\brief Extenders for the digraph types 33 33 namespace lemon { 34 34 35 35 // \ingroup graphbits 36 36 // 37 // \brief Extender for the digraph implementations37 // \brief Extender for the Digraphs 38 38 template <typename Base> 39 39 class DigraphExtender : public Base { -
lemon/bits/map_extender.h
r463 r314 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bits/path_dump.h
r463 r209 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bits/traits.h
r463 r314 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 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>::type229 > {230 static const bool value = true;231 };232 233 template <typename Graph, typename Enable = void>234 221 struct EdgeNumTagIndicator { 235 222 static const bool value = false; … … 245 232 246 233 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>::type255 > {256 static const bool value = true;257 };258 259 template <typename Graph, typename Enable = void>260 234 struct FindEdgeTagIndicator { 261 235 static const bool value = false; -
lemon/bits/vector_map.h
r463 r314 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 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 that automatically42 // updates the map when a key is added to or erased from the graph.43 // This map type usesstd::vector to store the values.41 // The VectorMap template class is graph map structure what 42 // automatically updates the map when a key is added to or erased from 43 // the map. This map type uses the std::vector to store the values. 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 iscalled by the observer notifier172 // It adds a new key to the map. It 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 iscalled by the observer notifier183 // It adds more new keys to the map. It 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 iscalled by the observer notifier198 // Erase a key from the map. It 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 // It erases more keys from the map. It iscalled by the observer notifier206 // Erase more keys from the map. It 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 the map.215 // 216 // It build s the map. It iscalled by the observer notifier214 // \brief Buildes the map. 215 // 216 // It buildes the map. It 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 s all items from the map. It iscalled by the observer notifier226 // It erase all items from the map. It 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
r463 r209 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/color.h
r463 r313 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/concept_check.h
r463 r285 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/concepts/digraph.h
r463 r263 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/concepts/graph.h
r463 r263 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/concepts/graph_components.h
r463 r313 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/concepts/heap.h
r463 r290 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/concepts/maps.h
r463 r314 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/concepts/path.h
r463 r281 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/core.h
r463 r319 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 1171 1171 /// Construct a new ConEdgeIt iterating on the edges that 1172 1172 /// connects nodes \c u and \c v. 1173 ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) , _u(u), _v(v){1174 Parent::operator=(findEdge(_graph, _u, _v));1173 ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) { 1174 Parent::operator=(findEdge(_graph, u, v)); 1175 1175 } 1176 1176 … … 1184 1184 /// It increments the iterator and gives back the next edge. 1185 1185 ConEdgeIt& operator++() { 1186 Parent::operator=(findEdge(_graph, _u, _v, *this)); 1186 Parent::operator=(findEdge(_graph, _graph.u(*this), 1187 _graph.v(*this), *this)); 1187 1188 return *this; 1188 1189 } 1189 1190 private: 1190 1191 const Graph& _graph; 1191 Node _u, _v;1192 1192 }; 1193 1193 -
lemon/counter.h
r463 r209 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/dfs.h
r463 r319 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 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 type is \ref ListDigraph. 122 ///The default value is \ref ListDigraph. The value of GR is not used 123 ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits. 124 ///\tparam TR Traits class to set various data types used by the algorithm. 125 ///The default traits class is 126 ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>". 127 ///See \ref DfsDefaultTraits for the documentation of 128 ///a Dfs traits class. 123 129 #ifdef DOXYGEN 124 130 template <typename GR, … … 146 152 typedef PredMapPath<Digraph, PredMap> Path; 147 153 148 ///The \ref DfsDefaultTraits "traits class" of the algorithm.154 ///The traits class. 149 155 typedef TR Traits; 150 156 … … 225 231 ///\ref named-templ-param "Named parameter" for setting 226 232 ///PredMap type. 227 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.228 233 template <class T> 229 234 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > { … … 245 250 ///\ref named-templ-param "Named parameter" for setting 246 251 ///DistMap type. 247 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.248 252 template <class T> 249 253 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > { … … 265 269 ///\ref named-templ-param "Named parameter" for setting 266 270 ///ReachedMap type. 267 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.268 271 template <class T> 269 272 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > { … … 285 288 ///\ref named-templ-param "Named parameter" for setting 286 289 ///ProcessedMap type. 287 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.288 290 template <class T> 289 291 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > { … … 337 339 338 340 ///Sets the map that stores the predecessor arcs. 339 ///If you don't use this function before calling \ref run(Node) "run()" 340 ///or \ref init(), an instance will be allocated automatically. 341 ///The destructor deallocates this automatically allocated map, 342 ///of course. 341 ///If you don't use this function before calling \ref run(), 342 ///it will allocate one. The destructor deallocates this 343 ///automatically allocated map, of course. 343 344 ///\return <tt> (*this) </tt> 344 345 Dfs &predMap(PredMap &m) … … 355 356 356 357 ///Sets the map that indicates which nodes are reached. 357 ///If you don't use this function before calling \ref run(Node) "run()" 358 ///or \ref init(), an instance will be allocated automatically. 359 ///The destructor deallocates this automatically allocated map, 360 ///of course. 358 ///If you don't use this function before calling \ref run(), 359 ///it will allocate one. The destructor deallocates this 360 ///automatically allocated map, of course. 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(Node) "run()" 376 ///or \ref init(), an instance will be allocated automatically. 377 ///The destructor deallocates this automatically allocated map, 378 ///of course. 375 ///If you don't use this function before calling \ref run(), 376 ///it will allocate one. The destructor deallocates this 377 ///automatically allocated map, of course. 379 378 ///\return <tt> (*this) </tt> 380 379 Dfs &processedMap(ProcessedMap &m) … … 392 391 ///Sets the map that stores the distances of the nodes calculated by 393 392 ///the algorithm. 394 ///If you don't use this function before calling \ref run(Node) "run()" 395 ///or \ref init(), an instance will be allocated automatically. 396 ///The destructor deallocates this automatically allocated map, 397 ///of course. 393 ///If you don't use this function before calling \ref run(), 394 ///it will allocate one. The destructor deallocates this 395 ///automatically allocated map, of course. 398 396 ///\return <tt> (*this) </tt> 399 397 Dfs &distMap(DistMap &m) … … 409 407 public: 410 408 411 ///\name Execution Control 412 ///The simplest way to execute the DFS algorithm is to use one of the 413 ///member functions called \ref run(Node) "run()".\n 414 ///If you need more control on the execution, first you have to call 415 ///\ref init(), then you can add a source node with \ref addSource() 416 ///and perform the actual computation with \ref start(). 417 ///This procedure can be repeated if there are nodes that have not 418 ///been reached. 409 ///\name Execution control 410 ///The simplest way to execute the algorithm is to use 411 ///one of the member functions called \ref lemon::Dfs::run() "run()". 412 ///\n 413 ///If you need more control on the execution, first you must call 414 ///\ref lemon::Dfs::init() "init()", then you can add a source node 415 ///with \ref lemon::Dfs::addSource() "addSource()". 416 ///Finally \ref lemon::Dfs::start() "start()" will perform the 417 ///actual path computation. 419 418 420 419 ///@{ 421 420 422 ///\brief Initializes the internal data structures.423 ///424 421 ///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 ///wrong results. (One of the outgoing arcs of all the source nodes 443 ///except for the last one will not be visited and distances will 444 ///also be wrong.) 441 ///\pre The stack must be empty. (Otherwise the algorithm gives 442 ///false results.) 443 /// 444 ///\warning Distances will be wrong (or at least strange) in case of 445 ///multiple sources. 445 446 void addSource(Node s) 446 447 { … … 506 507 } 507 508 508 ///Returns \c false if there are nodes to be processed. 509 510 ///Returns \c false if there are nodes to be processed 511 ///in the queue (stack). 509 ///\brief Returns \c false if there are nodes 510 ///to be processed. 511 /// 512 ///Returns \c false if there are nodes 513 ///to be processed in the queue (stack). 512 514 bool emptyQueue() const { return _stack_head<0; } 513 515 514 516 ///Returns the number of the nodes to be processed. 515 517 516 ///Returns the number of the nodes to be processed 517 ///in the queue (stack). 518 ///Returns the number of the nodes to be processed in the queue (stack). 518 519 int queueSize() const { return _stack_head+1; } 519 520 … … 637 638 /// 638 639 ///The algorithm computes 639 ///- the %DFS tree (forest),640 ///- the distance of each node from the root (s)in the %DFS tree.640 ///- the %DFS tree, 641 ///- the distance of each node from the root in the %DFS tree. 641 642 /// 642 643 ///\note <tt>d.run()</tt> is just a shortcut of the following code. … … 663 664 664 665 ///\name Query Functions 665 ///The result s of theDFS algorithm can be obtained using these666 ///The result of the %DFS algorithm can be obtained using these 666 667 ///functions.\n 667 ///Either \ref run(Node) "run()" or \ref start() should be called668 /// before using them.668 ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start() 669 ///"start()" must be called before using them. 669 670 670 671 ///@{ … … 674 675 ///Returns the DFS path to a node. 675 676 /// 676 ///\warning \c t should be reach ed from the root(s).677 /// 678 ///\pre Either \ref run( Node) "run()" or \ref init()679 /// must be called beforeusing this function.677 ///\warning \c t should be reachable from the root. 678 /// 679 ///\pre Either \ref run() or \ref start() must be called before 680 ///using this function. 680 681 Path path(Node t) const { return Path(*G, *_pred, t); } 681 682 682 ///The distance of a node from the root (s).683 684 ///Returns the distance of a node from the root (s).685 /// 686 ///\warning If node \c v is not reach ed from the root(s), then683 ///The distance of a node from the root. 684 685 ///Returns the distance of a node from the root. 686 /// 687 ///\warning If node \c v is not reachable from the root, then 687 688 ///the return value of this function is undefined. 688 689 /// 689 ///\pre Either \ref run( Node) "run()" or \ref init()690 /// must be called beforeusing this function.690 ///\pre Either \ref run() or \ref start() must be called before 691 ///using this function. 691 692 int dist(Node v) const { return (*_dist)[v]; } 692 693 … … 694 695 695 696 ///This function returns the 'previous arc' of the %DFS tree for the 696 ///node \c v, i.e. it returns the last arc of a %DFS path from a697 ///root to \c v. It is \c INVALID if \c v is not reached from the698 /// root(s) or if \c v is a root.697 ///node \c v, i.e. it returns the last arc of a %DFS path from the 698 ///root to \c v. It is \c INVALID 699 ///if \c v is not reachable from the root(s) or if \c v is a root. 699 700 /// 700 701 ///The %DFS tree used here is equal to the %DFS tree used in 701 702 ///\ref predNode(). 702 703 /// 703 ///\pre Either \ref run( Node) "run()" or \ref init()704 /// must be called before usingthis function.704 ///\pre Either \ref run() or \ref start() must be called before using 705 ///this function. 705 706 Arc predArc(Node v) const { return (*_pred)[v];} 706 707 … … 709 710 ///This function returns the 'previous node' of the %DFS 710 711 ///tree for the node \c v, i.e. it returns the last but one node 711 ///from a %DFS path from aroot to \c v. It is \c INVALID712 ///if \c v is not reach edfrom the root(s) or if \c v is a root.712 ///from a %DFS path from the root to \c v. It is \c INVALID 713 ///if \c v is not reachable from the root(s) or if \c v is a root. 713 714 /// 714 715 ///The %DFS tree used here is equal to the %DFS tree used in 715 716 ///\ref predArc(). 716 717 /// 717 ///\pre Either \ref run( Node) "run()" or \ref init()718 /// must be called beforeusing this function.718 ///\pre Either \ref run() or \ref start() must be called before 719 ///using this function. 719 720 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 720 721 G->source((*_pred)[v]); } … … 726 727 ///distances of the nodes calculated by the algorithm. 727 728 /// 728 ///\pre Either \ref run( Node) "run()"or \ref init()729 ///\pre Either \ref run() or \ref init() 729 730 ///must be called before using this function. 730 731 const DistMap &distMap() const { return *_dist;} … … 736 737 ///arcs, which form the DFS tree. 737 738 /// 738 ///\pre Either \ref run( Node) "run()"or \ref init()739 ///\pre Either \ref run() or \ref init() 739 740 ///must be called before using this function. 740 741 const PredMap &predMap() const { return *_pred;} 741 742 742 ///Checks if a node is reached from the root(s). 743 744 ///Returns \c true if \c v is reached from the root(s). 745 /// 746 ///\pre Either \ref run(Node) "run()" or \ref init() 743 ///Checks if a node is reachable from the root(s). 744 745 ///Returns \c true if \c v is reachable from the root(s). 746 ///\pre Either \ref run() or \ref start() 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( Node) "run()" method, it uses the893 /// functionsand features of the plain \ref Dfs.892 /// It does not have own \ref run() method, it uses the functions 893 /// and features of the plain \ref Dfs. 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 ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()" 1113 1114 ///\warning Don't forget to put the \ref DfsWizard::run() "run()" 1114 1115 ///to the end of the parameter list. 1115 1116 ///\sa DfsWizard … … 1309 1310 typedef DfsVisit Create; 1310 1311 1311 /// \name Named Template Parameters1312 /// \name Named template parameters 1312 1313 1313 1314 ///@{ … … 1351 1352 /// 1352 1353 /// Sets the map that indicates which nodes are reached. 1353 /// If you don't use this function before calling \ref run(Node) "run()" 1354 /// or \ref init(), an instance will be allocated automatically. 1355 /// The destructor deallocates this automatically allocated map, 1356 /// of course. 1354 /// If you don't use this function before calling \ref run(), 1355 /// it will allocate one. The destructor deallocates this 1356 /// automatically allocated map, of course. 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 DFS algorithm is to use one of the 1371 /// member functions called \ref run(Node) "run()".\n 1372 /// If you need more control on the execution, first you have to call 1373 /// \ref init(), then you can add a source node with \ref addSource() 1374 /// and perform the actual computation with \ref start(). 1375 /// This procedure can be repeated if there are nodes that have not 1376 /// been reached. 1369 /// \name Execution control 1370 /// The simplest way to execute the algorithm is to use 1371 /// one of the member functions called \ref lemon::DfsVisit::run() 1372 /// "run()". 1373 /// \n 1374 /// If you need more control on the execution, first you must call 1375 /// \ref lemon::DfsVisit::init() "init()", then you can add several 1376 /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()". 1377 /// Finally \ref lemon::DfsVisit::start() "start()" will perform the 1378 /// actual path computation. 1377 1379 1378 1380 /// @{ … … 1390 1392 } 1391 1393 1392 /// \brief Adds a new source node. 1393 /// 1394 /// Adds a new source node to the set of nodes to be processed. 1395 /// 1396 /// \pre The stack must be empty. Otherwise the algorithm gives 1397 /// wrong results. (One of the outgoing arcs of all the source nodes 1398 /// except for the last one will not be visited and distances will 1399 /// also be wrong.) 1394 ///Adds a new source node. 1395 1396 ///Adds a new source node to the set of nodes to be processed. 1397 /// 1398 ///\pre The stack must be empty. (Otherwise the algorithm gives 1399 ///false results.) 1400 /// 1401 ///\warning Distances will be wrong (or at least strange) in case of 1402 ///multiple sources. 1400 1403 void addSource(Node s) 1401 1404 { … … 1411 1414 } else { 1412 1415 _visitor->leave(s); 1413 _visitor->stop(s);1414 1416 } 1415 1417 } … … 1588 1590 /// 1589 1591 /// The algorithm computes 1590 /// - the %DFS tree (forest),1591 /// - the distance of each node from the root (s)in the %DFS tree.1592 /// - the %DFS tree, 1593 /// - the distance of each node from the root in the %DFS tree. 1592 1594 /// 1593 1595 /// \note <tt>d.run()</tt> is just a shortcut of the following code. … … 1614 1616 1615 1617 /// \name Query Functions 1616 /// The result s of theDFS algorithm can be obtained using these1618 /// The result of the %DFS algorithm can be obtained using these 1617 1619 /// functions.\n 1618 /// Either \ref run(Node) "run()" or \ref start() should be called1619 /// before using them.1620 1620 /// Either \ref lemon::DfsVisit::run() "run()" or 1621 /// \ref lemon::DfsVisit::start() "start()" must be called before 1622 /// using them. 1621 1623 ///@{ 1622 1624 1623 /// \brief Checks if a node is reached from the root(s). 1624 /// 1625 /// Returns \c true if \c v is reached from the root(s). 1626 /// 1627 /// \pre Either \ref run(Node) "run()" or \ref init() 1625 /// \brief Checks if a node is reachable from the root(s). 1626 /// 1627 /// Returns \c true if \c v is reachable from the root(s). 1628 /// \pre Either \ref run() or \ref start() 1628 1629 /// must be called before using this function. 1629 bool reached(Node v) const{ return (*_reached)[v]; }1630 bool reached(Node v) { return (*_reached)[v]; } 1630 1631 1631 1632 ///@} -
lemon/dijkstra.h
r463 r313 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 48 48 static Value plus(const Value& left, const Value& right) { 49 49 return left + right; 50 } 51 /// \brief Gives back true only if the first value is less than the second. 52 static bool less(const Value& left, const Value& right) { 53 return left < right; 54 } 55 }; 56 57 /// \brief Widest path operation traits for the Dijkstra algorithm class. 58 /// 59 /// This operation traits class defines all computational operations and 60 /// constants which are used in the Dijkstra algorithm for widest path 61 /// computation. 62 /// 63 /// \see DijkstraDefaultOperationTraits 64 template <typename Value> 65 struct DijkstraWidestPathOperationTraits { 66 /// \brief Gives back the maximum value of the type. 67 static Value zero() { 68 return std::numeric_limits<Value>::max(); 69 } 70 /// \brief Gives back the minimum of the given two elements. 71 static Value plus(const Value& left, const Value& right) { 72 return std::min(left, right); 50 73 } 51 74 /// \brief Gives back true only if the first value is less than the second. … … 180 203 /// 181 204 ///\tparam GR The type of the digraph the algorithm runs on. 182 ///The default type is \ref ListDigraph. 183 ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies 184 ///the lengths of the arcs. 185 ///It is read once for each arc, so the map may involve in 205 ///The default value is \ref ListDigraph. 206 ///The value of GR is not used directly by \ref Dijkstra, it is only 207 ///passed to \ref DijkstraDefaultTraits. 208 ///\tparam LM A readable arc map that determines the lengths of the 209 ///arcs. It is read once for each arc, so the map may involve in 186 210 ///relatively time consuming process to compute the arc lengths if 187 211 ///it is necessary. The default map type is \ref 188 ///concepts::Digraph::ArcMap "GR::ArcMap<int>". 212 ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>". 213 ///The value of LM is not used directly by \ref Dijkstra, it is only 214 ///passed to \ref DijkstraDefaultTraits. 215 ///\tparam TR Traits class to set various data types used by the algorithm. 216 ///The default traits class is \ref DijkstraDefaultTraits 217 ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits 218 ///for the documentation of a Dijkstra traits class. 189 219 #ifdef DOXYGEN 190 220 template <typename GR, typename LM, typename TR> … … 220 250 typedef typename TR::OperationTraits OperationTraits; 221 251 222 ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.252 ///The traits class. 223 253 typedef TR Traits; 224 254 … … 302 332 ///\ref named-templ-param "Named parameter" for setting 303 333 ///PredMap type. 304 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.305 334 template <class T> 306 335 struct SetPredMap … … 323 352 ///\ref named-templ-param "Named parameter" for setting 324 353 ///DistMap type. 325 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.326 354 template <class T> 327 355 struct SetDistMap … … 344 372 ///\ref named-templ-param "Named parameter" for setting 345 373 ///ProcessedMap type. 346 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.347 374 template <class T> 348 375 struct SetProcessedMap … … 385 412 }; 386 413 ///\brief \ref named-templ-param "Named parameter" for setting 387 ///heap and cross reference type s414 ///heap and cross reference type 388 415 /// 389 416 ///\ref named-templ-param "Named parameter" for setting heap and cross 390 ///reference types. If this named parameter is used, then external 391 ///heap and cross reference objects must be passed to the algorithm 392 ///using the \ref heap() function before calling \ref run(Node) "run()" 393 ///or \ref init(). 394 ///\sa SetStandardHeap 417 ///reference type. 395 418 template <class H, class CR = typename Digraph::template NodeMap<int> > 396 419 struct SetHeap … … 412 435 }; 413 436 ///\brief \ref named-templ-param "Named parameter" for setting 414 ///heap and cross reference type swith automatic allocation437 ///heap and cross reference type with automatic allocation 415 438 /// 416 439 ///\ref named-templ-param "Named parameter" for setting heap and cross 417 ///reference types with automatic allocation. 418 ///They should have standard constructor interfaces to be able to 419 ///automatically created by the algorithm (i.e. the digraph should be 420 ///passed to the constructor of the cross reference and the cross 421 ///reference should be passed to the constructor of the heap). 422 ///However external heap and cross reference objects could also be 423 ///passed to the algorithm using the \ref heap() function before 424 ///calling \ref run(Node) "run()" or \ref init(). 425 ///\sa SetHeap 440 ///reference type. It can allocate the heap and the cross reference 441 ///object if the cross reference's constructor waits for the digraph as 442 ///parameter and the heap's constructor waits for the cross reference. 426 443 template <class H, class CR = typename Digraph::template NodeMap<int> > 427 444 struct SetStandardHeap … … 493 510 494 511 ///Sets the map that stores the predecessor arcs. 495 ///If you don't use this function before calling \ref run(Node) "run()" 496 ///or \ref init(), an instance will be allocated automatically. 497 ///The destructor deallocates this automatically allocated map, 498 ///of course. 512 ///If you don't use this function before calling \ref run(), 513 ///it will allocate one. The destructor deallocates this 514 ///automatically allocated map, of course. 499 515 ///\return <tt> (*this) </tt> 500 516 Dijkstra &predMap(PredMap &m) … … 511 527 512 528 ///Sets the map that indicates which nodes are processed. 513 ///If you don't use this function before calling \ref run(Node) "run()" 514 ///or \ref init(), an instance will be allocated automatically. 515 ///The destructor deallocates this automatically allocated map, 516 ///of course. 529 ///If you don't use this function before calling \ref run(), 530 ///it will allocate one. The destructor deallocates this 531 ///automatically allocated map, of course. 517 532 ///\return <tt> (*this) </tt> 518 533 Dijkstra &processedMap(ProcessedMap &m) … … 530 545 ///Sets the map that stores the distances of the nodes calculated by the 531 546 ///algorithm. 532 ///If you don't use this function before calling \ref run(Node) "run()" 533 ///or \ref init(), an instance will be allocated automatically. 534 ///The destructor deallocates this automatically allocated map, 535 ///of course. 547 ///If you don't use this function before calling \ref run(), 548 ///it will allocate one. The destructor deallocates this 549 ///automatically allocated map, of course. 536 550 ///\return <tt> (*this) </tt> 537 551 Dijkstra &distMap(DistMap &m) … … 548 562 549 563 ///Sets the heap and the cross reference used by algorithm. 550 ///If you don't use this function before calling \ref run(Node) "run()" 551 ///or \ref init(), heap and cross reference instances will be 552 ///allocated automatically. 553 ///The destructor deallocates these automatically allocated objects, 554 ///of course. 564 ///If you don't use this function before calling \ref run(), 565 ///it will allocate one. The destructor deallocates this 566 ///automatically allocated heap and cross reference, of course. 555 567 ///\return <tt> (*this) </tt> 556 568 Dijkstra &heap(Heap& hp, HeapCrossRef &cr) … … 579 591 public: 580 592 581 ///\name Execution Control 582 ///The simplest way to execute the %Dijkstra algorithm is to use 583 ///one of the member functions called \ref run(Node) "run()".\n 584 ///If you need more control on the execution, first you have to call 585 ///\ref init(), then you can add several source nodes with 586 ///\ref addSource(). Finally the actual path computation can be 587 ///performed with one of the \ref start() functions. 593 ///\name Execution control 594 ///The simplest way to execute the algorithm is to use one of the 595 ///member functions called \ref lemon::Dijkstra::run() "run()". 596 ///\n 597 ///If you need more control on the execution, first you must call 598 ///\ref lemon::Dijkstra::init() "init()", then you can add several 599 ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()". 600 ///Finally \ref lemon::Dijkstra::start() "start()" will perform the 601 ///actual path computation. 588 602 589 603 ///@{ 590 604 591 ///\brief Initializes the internal data structures.592 ///593 605 ///Initializes the internal data structures. 606 607 ///Initializes the internal data structures. 608 /// 594 609 void init() 595 610 { … … 667 682 } 668 683 669 ///Returns \c false if there are nodes to be processed. 670 671 ///Returns \c false if there are nodes to be processed 672 ///in the priority heap. 684 ///\brief Returns \c false if there are nodes 685 ///to be processed. 686 /// 687 ///Returns \c false if there are nodes 688 ///to be processed in the priority heap. 673 689 bool emptyQueue() const { return _heap->empty(); } 674 690 675 ///Returns the number of the nodes to be processed .676 677 ///Returns the number of the nodes to be processed 678 /// in the priority heap.691 ///Returns the number of the nodes to be processed in the priority heap 692 693 ///Returns the number of the nodes to be processed in the priority heap. 694 /// 679 695 int queueSize() const { return _heap->size(); } 680 696 … … 797 813 798 814 ///\name Query Functions 799 ///The result sof the %Dijkstra algorithm can be obtained using these815 ///The result of the %Dijkstra algorithm can be obtained using these 800 816 ///functions.\n 801 ///Either \ref run(Node) "run()" or \ref start() should be called 802 ///before using them. 817 ///Either \ref lemon::Dijkstra::run() "run()" or 818 ///\ref lemon::Dijkstra::start() "start()" must be called before 819 ///using them. 803 820 804 821 ///@{ … … 808 825 ///Returns the shortest path to a node. 809 826 /// 810 ///\warning \c t should be reach edfrom the root(s).811 /// 812 ///\pre Either \ref run( Node) "run()" or \ref init()813 /// must be called beforeusing this function.827 ///\warning \c t should be reachable from the root(s). 828 /// 829 ///\pre Either \ref run() or \ref start() must be called before 830 ///using this function. 814 831 Path path(Node t) const { return Path(*G, *_pred, t); } 815 832 … … 818 835 ///Returns the distance of a node from the root(s). 819 836 /// 820 ///\warning If node \c v is not reach edfrom the root(s), then837 ///\warning If node \c v is not reachable from the root(s), then 821 838 ///the return value of this function is undefined. 822 839 /// 823 ///\pre Either \ref run( Node) "run()" or \ref init()824 /// must be called beforeusing this function.840 ///\pre Either \ref run() or \ref start() must be called before 841 ///using this function. 825 842 Value dist(Node v) const { return (*_dist)[v]; } 826 843 … … 829 846 ///This function returns the 'previous arc' of the shortest path 830 847 ///tree for the node \c v, i.e. it returns the last arc of a 831 ///shortest path from a rootto \c v. It is \c INVALID if \c v832 ///is not reach edfrom the root(s) or if \c v is a root.848 ///shortest path from the root(s) to \c v. It is \c INVALID if \c v 849 ///is not reachable from the root(s) or if \c v is a root. 833 850 /// 834 851 ///The shortest path tree used here is equal to the shortest path 835 852 ///tree used in \ref predNode(). 836 853 /// 837 ///\pre Either \ref run( Node) "run()" or \ref init()838 /// must be called beforeusing this function.854 ///\pre Either \ref run() or \ref start() must be called before 855 ///using this function. 839 856 Arc predArc(Node v) const { return (*_pred)[v]; } 840 857 … … 843 860 ///This function returns the 'previous node' of the shortest path 844 861 ///tree for the node \c v, i.e. it returns the last but one node 845 ///from a shortest path from a rootto \c v. It is \c INVALID846 ///if \c v is not reach edfrom the root(s) or if \c v is a root.862 ///from a shortest path from the root(s) to \c v. It is \c INVALID 863 ///if \c v is not reachable from the root(s) or if \c v is a root. 847 864 /// 848 865 ///The shortest path tree used here is equal to the shortest path 849 866 ///tree used in \ref predArc(). 850 867 /// 851 ///\pre Either \ref run( Node) "run()" or \ref init()852 /// must be called beforeusing this function.868 ///\pre Either \ref run() or \ref start() must be called before 869 ///using this function. 853 870 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 854 871 G->source((*_pred)[v]); } … … 860 877 ///of the nodes calculated by the algorithm. 861 878 /// 862 ///\pre Either \ref run( Node) "run()"or \ref init()879 ///\pre Either \ref run() or \ref init() 863 880 ///must be called before using this function. 864 881 const DistMap &distMap() const { return *_dist;} … … 870 887 ///arcs, which form the shortest path tree. 871 888 /// 872 ///\pre Either \ref run( Node) "run()"or \ref init()889 ///\pre Either \ref run() or \ref init() 873 890 ///must be called before using this function. 874 891 const PredMap &predMap() const { return *_pred;} 875 892 876 ///Checks if a node is reached from the root(s). 877 878 ///Returns \c true if \c v is reached from the root(s). 879 /// 880 ///\pre Either \ref run(Node) "run()" or \ref init() 893 ///Checks if a node is reachable from the root(s). 894 895 ///Returns \c true if \c v is reachable from the root(s). 896 ///\pre Either \ref run() or \ref start() 881 897 ///must be called before using this function. 882 898 bool reached(Node v) const { return (*_heap_cross_ref)[v] != … … 887 903 ///Returns \c true if \c v is processed, i.e. the shortest 888 904 ///path to \c v has already found. 889 /// 890 ///\pre Either \ref run(Node) "run()" or \ref init() 905 ///\pre Either \ref run() or \ref init() 891 906 ///must be called before using this function. 892 907 bool processed(Node v) const { return (*_heap_cross_ref)[v] == … … 897 912 ///Returns the current distance of a node from the root(s). 898 913 ///It may be decreased in the following processes. 899 /// 900 ///\pre Either \ref run(Node) "run()" or \ref init() 914 ///\pre Either \ref run() or \ref init() 901 915 ///must be called before using this function and 902 916 ///node \c v must be reached but not necessarily processed. … … 1081 1095 /// This auxiliary class is created to implement the 1082 1096 /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm. 1083 /// It does not have own \ref run( Node) "run()" method, it uses the1084 /// functionsand features of the plain \ref Dijkstra.1097 /// It does not have own \ref run() method, it uses the functions 1098 /// and features of the plain \ref Dijkstra. 1085 1099 /// 1086 1100 /// This class should only be used through the \ref dijkstra() function, … … 1277 1291 /// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t); 1278 1292 ///\endcode 1279 ///\warning Don't forget to put the \ref DijkstraWizard::run( Node) "run()"1293 ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()" 1280 1294 ///to the end of the parameter list. 1281 1295 ///\sa DijkstraWizard -
lemon/dim2.h
r463 r314 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/error.h
r463 r291 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/graph_to_eps.h
r463 r313 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/kruskal.h
r463 r220 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/lgf_reader.h
r463 r319 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 871 871 readLine(); 872 872 } 873 if (readSuccess()) { 874 line.putback(c); 875 } 873 line.putback(c); 876 874 } 877 875 … … 1702 1700 readLine(); 1703 1701 } 1704 if (readSuccess()) { 1705 line.putback(c); 1706 } 1702 line.putback(c); 1707 1703 } 1708 1704 … … 2231 2227 readLine(); 2232 2228 } 2233 if (readSuccess()) { 2234 line.putback(c); 2235 } 2229 line.putback(c); 2236 2230 } 2237 2231 … … 2574 2568 readLine(); 2575 2569 } 2576 if (readSuccess()) { 2577 line.putback(c); 2578 } 2570 line.putback(c); 2579 2571 } 2580 2572 -
lemon/lgf_writer.h
r463 r319 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/list_graph.h
r463 r313 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 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
r463 r314 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/math.h
r463 r209 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/path.h
r463 r313 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/random.cc
r463 r209 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/random.h
r463 r280 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 541 541 /// @{ 542 542 543 ///\name Initialization 544 /// 545 /// @{ 546 543 547 /// \brief Default constructor 544 548 /// … … 689 693 } 690 694 695 /// \brief Returns a random real number the range [0, b) 696 /// 697 /// It returns a random real number from the range [0, b). 698 template <typename Number> 699 Number real(Number b) { 700 return real<Number>() * b; 701 } 702 703 /// \brief Returns a random real number from the range [a, b) 704 /// 705 /// It returns a random real number from the range [a, b). 706 template <typename Number> 707 Number real(Number a, Number b) { 708 return real<Number>() * (b - a) + a; 709 } 710 711 /// @} 712 713 ///\name Uniform distributions 714 /// 715 /// @{ 716 691 717 /// \brief Returns a random real number from the range [0, 1) 692 718 /// … … 699 725 /// 700 726 /// It returns a random real number from the range [0, b). 701 double operator()(double b) { 702 return real<double>() * b; 727 template <typename Number> 728 Number operator()(Number b) { 729 return real<Number>() * b; 703 730 } 704 731 … … 706 733 /// 707 734 /// It returns a random real number from the range [a, b). 708 double operator()(double a, double b) { 709 return real<double>() * (b - a) + a; 735 template <typename Number> 736 Number operator()(Number a, Number b) { 737 return real<Number>() * (b - a) + a; 710 738 } 711 739 … … 743 771 return _random_bits::IntConversion<Number, Word>::convert(core); 744 772 } 773 774 /// @} 745 775 746 776 unsigned int uinteger() { … … 777 807 ///\name Non-uniform distributions 778 808 /// 809 779 810 ///@{ 780 811 781 /// \brief Returns a random bool with given probability of true result.812 /// \brief Returns a random bool 782 813 /// 783 814 /// It returns a random bool with given probability of true result. … … 786 817 } 787 818 788 /// Standard normal (Gauss)distribution789 790 /// Standard normal (Gauss)distribution.819 /// Standard Gauss distribution 820 821 /// Standard Gauss distribution. 791 822 /// \note The Cartesian form of the Box-Muller 792 823 /// transformation is used to generate a random normal distribution. … … 801 832 return std::sqrt(-2*std::log(S)/S)*V1; 802 833 } 803 /// Normal (Gauss)distribution with given mean and standard deviation804 805 /// Normal (Gauss)distribution with given mean and standard deviation.834 /// Gauss distribution with given mean and standard deviation 835 836 /// Gauss distribution with given mean and standard deviation. 806 837 /// \sa gauss() 807 838 double gauss(double mean,double std_dev) 808 839 { 809 840 return gauss()*std_dev+mean; 810 }811 812 /// Lognormal distribution813 814 /// Lognormal distribution. The parameters are the mean and the standard815 /// 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 distribution822 823 /// Lognormal distribution. The parameter is an <tt>std::pair</tt> of824 /// 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 deviation831 832 /// This function computes the lognormal parameters from mean and833 /// standard deviation. The return value can direcly be passed to834 /// 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 deviation844 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));850 841 } 851 842 … … 953 944 ///\name Two dimensional distributions 954 945 /// 946 955 947 ///@{ 956 948 … … 969 961 return dim2::Point<double>(V1,V2); 970 962 } 971 /// A kind of two dimensional normal (Gauss)distribution963 /// A kind of two dimensional Gauss distribution 972 964 973 965 /// This function provides a turning symmetric two-dimensional distribution. -
lemon/smart_graph.h
r463 r313 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 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 ArcNumTag;70 typedef True EdgeNumTag; 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].next_out) { 309 arcs[i].source=b._id; 310 } 308 for(int i=nodes[b._id].first_out;i!=-1;i++) arcs[i].source=b._id; 311 309 if(connect) addArc(n,b); 312 310 return b; … … 467 465 468 466 public: 469 operator Edge() const { 470 return _id != -1 ? edgeFromId(_id / 2) : INVALID; 467 operator Edge() const { 468 return _id != -1 ? edgeFromId(_id / 2) : INVALID; 471 469 } 472 470 … … 483 481 : nodes(), arcs() {} 484 482 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(); }492 483 493 484 int maxNodeId() const { return nodes.size()-1; } … … 738 729 dir.push_back(arcFromId(n-1)); 739 730 Parent::notifier(Arc()).erase(dir); 740 nodes[arcs[n -1].target].first_out=arcs[n].next_out;741 nodes[arcs[n ].target].first_out=arcs[n-1].next_out;731 nodes[arcs[n].target].first_out=arcs[n].next_out; 732 nodes[arcs[n-1].target].first_out=arcs[n-1].next_out; 742 733 arcs.pop_back(); 743 734 arcs.pop_back(); -
lemon/time_measure.h
r463 r314 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/tolerance.h
r463 r280 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/unionfind.h
r463 r236 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 1178 1178 if (nodes[nodes[jd].next].size < cmax) { 1179 1179 pushLeft(nodes[jd].next, nodes[jd].left); 1180 if (less(jd, nodes[jd].next) || 1181 nodes[jd].item == nodes[pd].item) { 1182 nodes[nodes[jd].next].prio = nodes[jd].prio; 1183 nodes[nodes[jd].next].item = nodes[jd].item; 1180 if (less(nodes[jd].left, nodes[jd].next)) { 1181 nodes[nodes[jd].next].prio = nodes[nodes[jd].left].prio; 1182 nodes[nodes[jd].next].item = nodes[nodes[jd].left].item; 1184 1183 } 1185 1184 popLeft(pd); … … 1190 1189 popLeft(nodes[jd].next); 1191 1190 pushRight(jd, ld); 1192 if (less(ld, nodes[jd].left) || 1193 nodes[ld].item == nodes[pd].item) { 1191 if (less(ld, nodes[jd].left)) { 1194 1192 nodes[jd].item = nodes[ld].item; 1195 nodes[jd].prio = nodes[ ld].prio;1193 nodes[jd].prio = nodes[jd].prio; 1196 1194 } 1197 1195 if (nodes[nodes[jd].next].item == nodes[ld].item) { … … 1222 1220 if (nodes[nodes[jd].prev].size < cmax) { 1223 1221 pushRight(nodes[jd].prev, nodes[jd].right); 1224 if (less(jd, nodes[jd].prev) || 1225 nodes[jd].item == nodes[pd].item) { 1226 nodes[nodes[jd].prev].prio = nodes[jd].prio; 1227 nodes[nodes[jd].prev].item = nodes[jd].item; 1222 if (less(nodes[jd].right, nodes[jd].prev)) { 1223 nodes[nodes[jd].prev].prio = nodes[nodes[jd].right].prio; 1224 nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item; 1228 1225 } 1229 1226 popRight(pd); … … 1234 1231 popRight(nodes[jd].prev); 1235 1232 pushLeft(jd, ld); 1236 if (less(ld, nodes[jd].right) || 1237 nodes[ld].item == nodes[pd].item) { 1233 if (less(ld, nodes[jd].right)) { 1238 1234 nodes[jd].item = nodes[ld].item; 1239 nodes[jd].prio = nodes[ ld].prio;1235 nodes[jd].prio = nodes[jd].prio; 1240 1236 } 1241 1237 if (nodes[nodes[jd].prev].item == nodes[ld].item) { … … 1255 1251 return comp(nodes[id].prio, nodes[jd].prio); 1256 1252 } 1253 1254 bool equal(int id, int jd) const { 1255 return !less(id, jd) && !less(jd, id); 1256 } 1257 1257 1258 1258 1259 public: … … 1400 1401 push(new_id, right_id); 1401 1402 pushRight(new_id, ~(classes[r].parent)); 1402 1403 if (less(~classes[r].parent, right_id)) { 1404 nodes[new_id].item = nodes[~classes[r].parent].item; 1405 nodes[new_id].prio = nodes[~classes[r].parent].prio; 1406 } else { 1407 nodes[new_id].item = nodes[right_id].item; 1408 nodes[new_id].prio = nodes[right_id].prio; 1409 } 1403 setPrio(new_id); 1410 1404 1411 1405 id = nodes[id].parent; … … 1447 1441 push(new_id, left_id); 1448 1442 pushLeft(new_id, ~(classes[l].parent)); 1449 1450 if (less(~classes[l].parent, left_id)) { 1451 nodes[new_id].item = nodes[~classes[l].parent].item; 1452 nodes[new_id].prio = nodes[~classes[l].parent].prio; 1453 } else { 1454 nodes[new_id].item = nodes[left_id].item; 1455 nodes[new_id].prio = nodes[left_id].prio; 1456 } 1443 setPrio(new_id); 1457 1444 1458 1445 id = nodes[id].parent; -
scripts/chg-len.py
r439 r284 2 2 3 3 import sys 4 5 from mercurial import ui, hg 6 from mercurial import util 7 8 util.rcpath = lambda : [] 4 import os 9 5 10 6 if len(sys.argv)>1 and sys.argv[1] in ["-h","--help"]: … … 14 10 """ 15 11 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]) 16 17 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()] 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]) 25 33 else: 26 p0=-1 27 if len(p)>1 and p[1]: 28 p1=lengths[p[1].rev()] 34 par1 = int(s[1].split(":")[0]) 35 par2 = int(s[2].split(":")[0]) 36 if rev == 0: 37 lengths.append(0) 29 38 else: 30 p1=-1 31 lengths[i]=max(p0,p1)+1 32 print lengths[N] 39 lengths.append(max(lengths[par1],lengths[par2])+1) 40 print lengths[PAR] -
scripts/unify-sources.sh
r411 r208 4 4 HGROOT=`hg root` 5 5 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 6 function update_header() { 183 7 TMP_FILE=`mktemp` 8 FILE_NAME=$1 184 9 185 10 (echo "/* -*- mode: C++; indent-tabs-mode: nil; -*- … … 201 26 */ 202 27 " 203 28 awk 'BEGIN { pm=0; } 204 29 pm==3 { print } 205 30 /\/\* / && pm==0 { pm=1;} … … 207 32 /\*\// && pm==1 { pm=2;} 208 33 ' $1 209 34 ) >$TMP_FILE 210 35 211 "$ACTION"_action "$TMP_FILE" "$1" header 36 HEADER_CH=`diff -q $TMP_FILE $FILE_NAME >/dev/null&&echo NO||echo YES` 37 38 rm $FILE_NAME 39 mv $TMP_FILE $FILE_NAME 212 40 } 213 41 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 42 function update_tabs() { 223 43 TMP_FILE=`mktemp` 224 cat $1 | sed -e "s/$OLD_PATTERN/$NEW_PATTERN/g" >$TMP_FILE44 FILE_NAME=$1 225 45 226 "$ACTION"_action "$TMP_FILE" "$1" 'tabs' 46 cat $1 | 47 sed -e 's/\t/ /g' >$TMP_FILE 48 49 TABS_CH=`diff -q $TMP_FILE $FILE_NAME >/dev/null&&echo NO||echo YES` 50 51 rm $FILE_NAME 52 mv $TMP_FILE $FILE_NAME 227 53 } 228 54 229 function spaces_check() {55 function remove_trailing_space() { 230 56 TMP_FILE=`mktemp` 231 cat $1 | sed -e 's/ \+$//g' >$TMP_FILE57 FILE_NAME=$1 232 58 233 "$ACTION"_action "$TMP_FILE" "$1" 'trailing spaces' 59 cat $1 | 60 sed -e 's/ \+$//g' >$TMP_FILE 61 62 SPACES_CH=`diff -q $TMP_FILE $FILE_NAME >/dev/null&&echo NO||echo YES` 63 64 rm $FILE_NAME 65 mv $TMP_FILE $FILE_NAME 234 66 } 235 67 236 function long_lines_check() { 237 if cat $1 | grep -q -E '.{81,}' 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 ]]; 238 81 then 239 "$ACTION"_warning $1 'long lines' 82 echo -n ' [header updated]' 83 CHANGED=YES; 84 fi 85 if [[ $TABS_CH = YES ]]; 86 then 87 echo -n ' [tabs removed]' 88 CHANGED=YES; 89 fi 90 if [[ $SPACES_CH = YES ]]; 91 then 92 echo -n ' [trailing spaces removed]' 93 CHANGED=YES; 94 fi 95 if long_line_test $1 ; 96 then 97 echo -n ' [LONG LINES]' 98 ((LONG_LINE_FILES++)) 99 fi 100 echo 101 if [[ $CHANGED = YES ]]; 102 then 103 ((CHANGED_FILES++)) 240 104 fi 241 105 } 242 106 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 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)$'` 257 113 do 258 "$check"_check $1 114 update_file $HGROOT/$i 115 ((TOTAL_FILES++)) 259 116 done 260 "$ACTION"_end $1 261 if [ "$ACTION" == 'update' ] 262 then 263 echo 264 fi 265 } 266 267 function process_all { 268 "$ACTION"_init 269 while read file 117 echo ' done.' 118 else 119 for i in $* 270 120 do 271 process_file $file 272 done < <($FILES) 273 "$ACTION"_done 274 } 275 276 while [ $# -gt 0 ] 277 do 278 279 if [ "$1" == '--help' ] || [ "$1" == '-h' ] 280 then 281 echo -n \ 282 "Usage: 283 $0 [OPTIONS] [files] 284 Options: 285 --dry-run|-n 286 Check the files, but do not modify them. 287 --interactive|-i 288 If --dry-run is specified and the checker emits warnings, 289 then the user is asked if the warnings should be considered 290 errors. 291 --werror|-w 292 Make all warnings into errors. 293 --all|-a 294 Check all source files in the repository. 295 --modified|-m 296 Check only the modified (and new) source files. This option is 297 useful to check the modification before making a commit. 298 --changed|-c 299 Check only the changed source files compared to the parent(s) of 300 the current hg node. This option is useful as hg hook script. 301 To automatically check all your changes before making a commit, 302 add the following section to the appropriate .hg/hgrc file. 303 304 [hooks] 305 pretxncommit.checksources = scripts/unify-sources.sh -c -n -i 306 307 --help|-h 308 Print this help message. 309 files 310 The files to check/unify. If no file names are given, the modified 311 source files will be checked/unified (just like using the 312 --modified|-m option). 313 " 314 exit 0 315 elif [ "$1" == '--dry-run' ] || [ "$1" == '-n' ] 316 then 317 [ -n "$ACTION" ] && echo "Conflicting action options" >&2 && exit 1 318 ACTION=check 319 elif [ "$1" == "--all" ] || [ "$1" == '-a' ] 320 then 321 [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1 322 FILES=all_files 323 elif [ "$1" == "--changed" ] || [ "$1" == '-c' ] 324 then 325 [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1 326 FILES=changed_files 327 elif [ "$1" == "--modified" ] || [ "$1" == '-m' ] 328 then 329 [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1 330 FILES=modified_files 331 elif [ "$1" == "--interactive" ] || [ "$1" == "-i" ] 332 then 333 [ -n "$WARNING" ] && echo "Conflicting warning options" >&2 && exit 1 334 WARNING='INTERACTIVE' 335 elif [ "$1" == "--werror" ] || [ "$1" == "-w" ] 336 then 337 [ -n "$WARNING" ] && echo "Conflicting warning options" >&2 && exit 1 338 WARNING='WERROR' 339 elif [ $(echo x$1 | cut -c 2) == '-' ] 340 then 341 echo "Invalid option $1" >&2 && exit 1 342 else 343 [ -n "$FILES" ] && echo "Invalid option $1" >&2 && exit 1 344 GIVEN_FILES=$@ 345 FILES=given_files 346 break 347 fi 348 349 shift 350 done 351 352 if [ -z $FILES ] 353 then 354 FILES=modified_files 121 update_file $i 122 ((TOTAL_FILES++)) 123 done 355 124 fi 356 357 if [ -z $ACTION ] 358 then 359 ACTION=update 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 360 134 fi 361 362 process_all -
test/CMakeLists.txt
r468 r464 5 5 SET(TESTS 6 6 bfs_test 7 circulation_test8 7 counter_test 9 8 dfs_test … … 12 11 dim_test 13 12 error_test 14 graph_adaptor_test15 13 graph_copy_test 16 14 graph_test 17 15 graph_utils_test 18 hao_orlin_test19 16 heap_test 20 17 kruskal_test 21 18 maps_test 22 max_matching_test23 19 radix_sort_test 20 random_test 24 21 path_test 25 preflow_test26 random_test27 suurballe_test28 22 time_measure_test 29 23 unionfind_test) -
test/Makefile.am
r468 r464 4 4 noinst_HEADERS += \ 5 5 test/graph_test.h \ 6 6 test/test_tools.h 7 7 8 8 check_PROGRAMS += \ 9 9 test/bfs_test \ 10 test/circulation_test \ 11 test/counter_test \ 10 test/counter_test \ 12 11 test/dfs_test \ 13 12 test/digraph_test \ 14 13 test/dijkstra_test \ 15 14 test/dim_test \ 16 15 test/error_test \ 17 test/graph_adaptor_test \18 16 test/graph_copy_test \ 19 17 test/graph_test \ 20 18 test/graph_utils_test \ 21 test/hao_orlin_test \22 19 test/heap_test \ 23 20 test/kruskal_test \ 24 test/maps_test \ 25 test/max_matching_test \ 26 test/path_test \ 27 test/preflow_test \ 21 test/maps_test \ 28 22 test/radix_sort_test \ 29 30 test/suurballe_test \31 32 33 23 test/random_test \ 24 test/path_test \ 25 test/test_tools_fail \ 26 test/test_tools_pass \ 27 test/time_measure_test \ 34 28 test/unionfind_test 35 29 … … 38 32 39 33 test_bfs_test_SOURCES = test/bfs_test.cc 40 test_circulation_test_SOURCES = test/circulation_test.cc41 34 test_counter_test_SOURCES = test/counter_test.cc 42 35 test_dfs_test_SOURCES = test/dfs_test.cc … … 45 38 test_dim_test_SOURCES = test/dim_test.cc 46 39 test_error_test_SOURCES = test/error_test.cc 47 test_graph_adaptor_test_SOURCES = test/graph_adaptor_test.cc48 40 test_graph_copy_test_SOURCES = test/graph_copy_test.cc 49 41 test_graph_test_SOURCES = test/graph_test.cc … … 51 43 test_heap_test_SOURCES = test/heap_test.cc 52 44 test_kruskal_test_SOURCES = test/kruskal_test.cc 53 test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc54 45 test_maps_test_SOURCES = test/maps_test.cc 55 test_max_matching_test_SOURCES = test/max_matching_test.cc56 46 test_path_test_SOURCES = test/path_test.cc 57 test_preflow_test_SOURCES = test/preflow_test.cc58 47 test_radix_sort_test_SOURCES = test/radix_sort_test.cc 59 test_suurballe_test_SOURCES = test/suurballe_test.cc60 48 test_random_test_SOURCES = test/random_test.cc 61 49 test_test_tools_fail_SOURCES = test/test_tools_fail.cc -
test/bfs_test.cc
r463 r293 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/counter_test.cc
r463 r209 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/dfs_test.cc
r463 r293 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/digraph_test.cc
r463 r228 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 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> 22 //#include <lemon/full_graph.h> 23 //#include <lemon/hypercube_graph.h> 23 24 24 25 #include "test_tools.h" … … 29 30 30 31 template <class Digraph> 31 void checkDigraph Build() {32 void checkDigraph() { 32 33 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 33 34 Digraph G; … … 58 59 checkGraphConArcList(G, 1); 59 60 60 Arc a2 = G.addArc(n2, n1), 61 a3 = G.addArc(n2, n3), 62 a4 = G.addArc(n2, n3); 63 64 checkGraphNodeList(G, 3); 65 checkGraphArcList(G, 4); 66 67 checkGraphOutArcList(G, n1, 1); 68 checkGraphOutArcList(G, n2, 3); 69 checkGraphOutArcList(G, n3, 0); 70 71 checkGraphInArcList(G, n1, 1); 72 checkGraphInArcList(G, n2, 1); 73 checkGraphInArcList(G, n3, 2); 74 75 checkGraphConArcList(G, 4); 76 77 checkNodeIds(G); 78 checkArcIds(G); 79 checkGraphNodeMap(G); 80 checkGraphArcMap(G); 81 } 82 83 template <class Digraph> 84 void checkDigraphSplit() { 85 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 86 87 Digraph G; 88 Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); 89 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1), 90 a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); 91 92 Node n4 = G.split(n2); 93 94 check(G.target(OutArcIt(G, n2)) == n4 && 95 G.source(InArcIt(G, n4)) == n2, 96 "Wrong split."); 97 98 checkGraphNodeList(G, 4); 99 checkGraphArcList(G, 5); 100 101 checkGraphOutArcList(G, n1, 1); 102 checkGraphOutArcList(G, n2, 1); 103 checkGraphOutArcList(G, n3, 0); 104 checkGraphOutArcList(G, n4, 3); 105 106 checkGraphInArcList(G, n1, 1); 107 checkGraphInArcList(G, n2, 1); 108 checkGraphInArcList(G, n3, 2); 109 checkGraphInArcList(G, n4, 1); 110 111 checkGraphConArcList(G, 5); 112 } 113 114 template <class Digraph> 115 void checkDigraphAlter() { 116 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 117 118 Digraph G; 119 Node n1 = G.addNode(), n2 = G.addNode(), 120 n3 = G.addNode(), n4 = G.addNode(); 121 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1), 122 a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3), 123 a5 = G.addArc(n2, n4); 124 125 checkGraphNodeList(G, 4); 126 checkGraphArcList(G, 5); 127 128 // Check changeSource() and changeTarget() 129 G.changeTarget(a4, n1); 130 131 checkGraphNodeList(G, 4); 132 checkGraphArcList(G, 5); 133 134 checkGraphOutArcList(G, n1, 1); 135 checkGraphOutArcList(G, n2, 1); 136 checkGraphOutArcList(G, n3, 0); 137 checkGraphOutArcList(G, n4, 3); 138 139 checkGraphInArcList(G, n1, 2); 140 checkGraphInArcList(G, n2, 1); 141 checkGraphInArcList(G, n3, 1); 142 checkGraphInArcList(G, n4, 1); 143 144 checkGraphConArcList(G, 5); 145 146 G.changeSource(a4, n3); 147 148 checkGraphNodeList(G, 4); 149 checkGraphArcList(G, 5); 150 151 checkGraphOutArcList(G, n1, 1); 152 checkGraphOutArcList(G, n2, 1); 153 checkGraphOutArcList(G, n3, 1); 154 checkGraphOutArcList(G, n4, 2); 155 156 checkGraphInArcList(G, n1, 2); 157 checkGraphInArcList(G, n2, 1); 158 checkGraphInArcList(G, n3, 1); 159 checkGraphInArcList(G, n4, 1); 160 161 checkGraphConArcList(G, 5); 162 163 // Check contract() 164 G.contract(n2, n4, false); 165 166 checkGraphNodeList(G, 3); 167 checkGraphArcList(G, 5); 168 169 checkGraphOutArcList(G, n1, 1); 170 checkGraphOutArcList(G, n2, 3); 171 checkGraphOutArcList(G, n3, 1); 172 173 checkGraphInArcList(G, n1, 2); 174 checkGraphInArcList(G, n2, 2); 175 checkGraphInArcList(G, n3, 1); 176 177 checkGraphConArcList(G, 5); 178 179 G.contract(n2, n1); 180 181 checkGraphNodeList(G, 2); 182 checkGraphArcList(G, 3); 183 184 checkGraphOutArcList(G, n2, 2); 185 checkGraphOutArcList(G, n3, 1); 186 187 checkGraphInArcList(G, n2, 2); 188 checkGraphInArcList(G, n3, 1); 189 190 checkGraphConArcList(G, 3); 191 } 192 193 template <class Digraph> 194 void checkDigraphErase() { 195 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 196 197 Digraph G; 198 Node n1 = G.addNode(), n2 = G.addNode(), 199 n3 = G.addNode(), n4 = G.addNode(); 200 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1), 201 a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1), 202 a5 = G.addArc(n2, n4); 203 204 // Check arc deletion 205 G.erase(a1); 206 207 checkGraphNodeList(G, 4); 208 checkGraphArcList(G, 4); 209 210 checkGraphOutArcList(G, n1, 0); 211 checkGraphOutArcList(G, n2, 1); 212 checkGraphOutArcList(G, n3, 1); 213 checkGraphOutArcList(G, n4, 2); 214 215 checkGraphInArcList(G, n1, 2); 216 checkGraphInArcList(G, n2, 0); 217 checkGraphInArcList(G, n3, 1); 218 checkGraphInArcList(G, n4, 1); 219 220 checkGraphConArcList(G, 4); 221 222 // Check node deletion 223 G.erase(n4); 224 225 checkGraphNodeList(G, 3); 226 checkGraphArcList(G, 1); 227 228 checkGraphOutArcList(G, n1, 0); 229 checkGraphOutArcList(G, n2, 0); 230 checkGraphOutArcList(G, n3, 1); 231 checkGraphOutArcList(G, n4, 0); 232 233 checkGraphInArcList(G, n1, 1); 234 checkGraphInArcList(G, n2, 0); 235 checkGraphInArcList(G, n3, 0); 236 checkGraphInArcList(G, n4, 0); 237 238 checkGraphConArcList(G, 1); 239 } 240 241 242 template <class Digraph> 243 void checkDigraphSnapshot() { 244 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 245 246 Digraph G; 247 Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); 248 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1), 249 a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); 250 251 typename Digraph::Snapshot snapshot(G); 252 253 Node n = G.addNode(); 254 G.addArc(n3, n); 255 G.addArc(n, n3); 256 257 checkGraphNodeList(G, 4); 258 checkGraphArcList(G, 6); 259 260 snapshot.restore(); 261 61 Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); 262 62 checkGraphNodeList(G, 3); 263 63 checkGraphArcList(G, 4); … … 278 78 checkGraphArcMap(G); 279 79 280 G.addNode(); 281 snapshot.save(G); 80 } 282 81 283 G.addArc(G.addNode(), G.addNode());284 285 snapshot.restore();286 287 checkGraphNodeList(G, 4);288 checkGraphArcList(G, 4);289 }290 82 291 83 void checkConcepts() { … … 318 110 checkConcept<ClearableDigraphComponent<>, SmartDigraph>(); 319 111 } 320 { // Checking FullDigraph 321 checkConcept<Digraph, FullDigraph>(); 322 } 112 // { // Checking FullDigraph 113 // checkConcept<Digraph, FullDigraph>(); 114 // } 115 // { // Checking HyperCubeDigraph 116 // checkConcept<Digraph, HyperCubeDigraph>(); 117 // } 323 118 } 324 119 … … 373 168 } 374 169 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 407 170 void checkDigraphs() { 408 171 { // Checking ListDigraph 409 checkDigraphBuild<ListDigraph>(); 410 checkDigraphSplit<ListDigraph>(); 411 checkDigraphAlter<ListDigraph>(); 412 checkDigraphErase<ListDigraph>(); 413 checkDigraphSnapshot<ListDigraph>(); 172 checkDigraph<ListDigraph>(); 414 173 checkDigraphValidityErase<ListDigraph>(); 415 174 } 416 175 { // Checking SmartDigraph 417 checkDigraphBuild<SmartDigraph>(); 418 checkDigraphSplit<SmartDigraph>(); 419 checkDigraphSnapshot<SmartDigraph>(); 176 checkDigraph<SmartDigraph>(); 420 177 checkDigraphValidity<SmartDigraph>(); 421 }422 { // Checking FullDigraph423 checkFullDigraph(8);424 178 } 425 179 } -
test/dijkstra_test.cc
r463 r293 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 90 90 ::SetProcessedMap<concepts::WriteMap<Node,bool> > 91 91 ::SetStandardProcessedMap 92 ::SetOperationTraits<Dijkstra DefaultOperationTraits<VType> >92 ::SetOperationTraits<DijkstraWidestPathOperationTraits<VType> > 93 93 ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > > 94 94 ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > > -
test/dim_test.cc
r463 r253 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/error_test.cc
r463 r277 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/graph_copy_test.cc
r463 r282 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/graph_test.cc
r463 r228 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 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> 24 #include <lemon/hypercube_graph.h> 22 // #include <lemon/full_graph.h> 23 // #include <lemon/grid_graph.h> 25 24 26 25 #include "test_tools.h" … … 31 30 32 31 template <class Graph> 33 void checkGraph Build() {32 void checkGraph() { 34 33 TEMPLATE_GRAPH_TYPEDEFS(Graph); 35 34 … … 37 36 checkGraphNodeList(G, 0); 38 37 checkGraphEdgeList(G, 0); 39 checkGraphArcList(G, 0);40 38 41 39 Node … … 45 43 checkGraphNodeList(G, 3); 46 44 checkGraphEdgeList(G, 0); 47 checkGraphArcList(G, 0);48 45 49 46 Edge e1 = G.addEdge(n1, n2); 50 47 check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1), 51 48 "Wrong edge"); 52 53 49 checkGraphNodeList(G, 3); 50 checkGraphArcList(G, 2); 54 51 checkGraphEdgeList(G, 1); 55 checkGraphArcList(G, 2); 56 57 checkGraphIncEdgeArcLists(G, n1, 1); 58 checkGraphIncEdgeArcLists(G, n2, 1); 59 checkGraphIncEdgeArcLists(G, n3, 0); 60 52 53 checkGraphOutArcList(G, n1, 1); 54 checkGraphOutArcList(G, n2, 1); 55 checkGraphOutArcList(G, n3, 0); 56 57 checkGraphInArcList(G, n1, 1); 58 checkGraphInArcList(G, n2, 1); 59 checkGraphInArcList(G, n3, 0); 60 61 checkGraphIncEdgeList(G, n1, 1); 62 checkGraphIncEdgeList(G, n2, 1); 63 checkGraphIncEdgeList(G, n3, 0); 64 65 checkGraphConArcList(G, 2); 61 66 checkGraphConEdgeList(G, 1); 62 checkGraphConArcList(G, 2); 63 64 Edge e2 = G.addEdge(n2, n1), 65 e3 = G.addEdge(n2, n3); 66 67 68 Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3); 67 69 checkGraphNodeList(G, 3); 70 checkGraphArcList(G, 6); 68 71 checkGraphEdgeList(G, 3); 69 checkGraphArcList(G, 6); 70 71 checkGraphIncEdgeArcLists(G, n1, 2); 72 checkGraphIncEdgeArcLists(G, n2, 3); 73 checkGraphIncEdgeArcLists(G, n3, 1); 74 72 73 checkGraphOutArcList(G, n1, 2); 74 checkGraphOutArcList(G, n2, 3); 75 checkGraphOutArcList(G, n3, 1); 76 77 checkGraphInArcList(G, n1, 2); 78 checkGraphInArcList(G, n2, 3); 79 checkGraphInArcList(G, n3, 1); 80 81 checkGraphIncEdgeList(G, n1, 2); 82 checkGraphIncEdgeList(G, n2, 3); 83 checkGraphIncEdgeList(G, n3, 1); 84 85 checkGraphConArcList(G, 6); 75 86 checkGraphConEdgeList(G, 3); 76 checkGraphConArcList(G, 6);77 87 78 88 checkArcDirections(G); … … 86 96 } 87 97 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 deletion179 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 deletion194 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 312 98 void checkConcepts() { 313 99 { // Checking graph components … … 339 125 checkConcept<ClearableGraphComponent<>, SmartGraph>(); 340 126 } 341 { // Checking FullGraph 342 checkConcept<Graph, FullGraph>(); 343 } 344 { // Checking GridGraph 345 checkConcept<Graph, GridGraph>(); 346 } 347 { // Checking HypercubeGraph 348 checkConcept<Graph, HypercubeGraph>(); 349 } 127 // { // Checking FullGraph 128 // checkConcept<Graph, FullGraph>(); 129 // checkGraphIterators<FullGraph>(); 130 // } 131 // { // Checking GridGraph 132 // checkConcept<Graph, GridGraph>(); 133 // checkGraphIterators<GridGraph>(); 134 // } 350 135 } 351 136 … … 404 189 } 405 190 406 void checkGridGraph(int width, int height) { 407 typedef GridGraph Graph; 408 GRAPH_TYPEDEFS(Graph); 409 Graph G(width, height); 410 411 check(G.width() == width, "Wrong column number"); 412 check(G.height() == height, "Wrong row number"); 413 414 for (int i = 0; i < width; ++i) { 415 for (int j = 0; j < height; ++j) { 416 check(G.col(G(i, j)) == i, "Wrong column"); 417 check(G.row(G(i, j)) == j, "Wrong row"); 418 check(G.pos(G(i, j)).x == i, "Wrong column"); 419 check(G.pos(G(i, j)).y == j, "Wrong row"); 420 } 421 } 422 423 for (int j = 0; j < height; ++j) { 424 for (int i = 0; i < width - 1; ++i) { 425 check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right"); 426 check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right"); 427 } 428 check(G.right(G(width - 1, j)) == INVALID, "Wrong right"); 429 } 430 431 for (int j = 0; j < height; ++j) { 432 for (int i = 1; i < width; ++i) { 433 check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left"); 434 check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left"); 435 } 436 check(G.left(G(0, j)) == INVALID, "Wrong left"); 437 } 438 439 for (int i = 0; i < width; ++i) { 440 for (int j = 0; j < height - 1; ++j) { 441 check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up"); 442 check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up"); 443 } 444 check(G.up(G(i, height - 1)) == INVALID, "Wrong up"); 445 } 446 447 for (int i = 0; i < width; ++i) { 448 for (int j = 1; j < height; ++j) { 449 check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down"); 450 check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down"); 451 } 452 check(G.down(G(i, 0)) == INVALID, "Wrong down"); 453 } 454 455 checkGraphNodeList(G, width * height); 456 checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height); 457 checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height)); 458 459 for (NodeIt n(G); n != INVALID; ++n) { 460 int nb = 4; 461 if (G.col(n) == 0) --nb; 462 if (G.col(n) == width - 1) --nb; 463 if (G.row(n) == 0) --nb; 464 if (G.row(n) == height - 1) --nb; 465 466 checkGraphOutArcList(G, n, nb); 467 checkGraphInArcList(G, n, nb); 468 checkGraphIncEdgeList(G, n, nb); 469 } 470 471 checkArcDirections(G); 472 473 checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height)); 474 checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height); 475 476 checkNodeIds(G); 477 checkArcIds(G); 478 checkEdgeIds(G); 479 checkGraphNodeMap(G); 480 checkGraphArcMap(G); 481 checkGraphEdgeMap(G); 482 483 } 484 485 void checkHypercubeGraph(int dim) { 486 GRAPH_TYPEDEFS(HypercubeGraph); 487 488 HypercubeGraph G(dim); 489 checkGraphNodeList(G, 1 << dim); 490 checkGraphEdgeList(G, dim * (1 << (dim-1))); 491 checkGraphArcList(G, dim * (1 << dim)); 492 493 Node n = G.nodeFromId(dim); 494 495 for (NodeIt n(G); n != INVALID; ++n) { 496 checkGraphIncEdgeList(G, n, dim); 497 for (IncEdgeIt e(G, n); e != INVALID; ++e) { 498 check( (G.u(e) == n && 499 G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) || 500 (G.v(e) == n && 501 G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))), 502 "Wrong edge or wrong dimension"); 503 } 504 505 checkGraphOutArcList(G, n, dim); 506 for (OutArcIt a(G, n); a != INVALID; ++a) { 507 check(G.source(a) == n && 508 G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))), 509 "Wrong arc or wrong dimension"); 510 } 511 512 checkGraphInArcList(G, n, dim); 513 for (InArcIt a(G, n); a != INVALID; ++a) { 514 check(G.target(a) == n && 515 G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))), 516 "Wrong arc or wrong dimension"); 517 } 518 } 519 520 checkGraphConArcList(G, (1 << dim) * dim); 521 checkGraphConEdgeList(G, dim * (1 << (dim-1))); 522 523 checkArcDirections(G); 524 525 checkNodeIds(G); 526 checkArcIds(G); 527 checkEdgeIds(G); 528 checkGraphNodeMap(G); 529 checkGraphArcMap(G); 530 checkGraphEdgeMap(G); 531 } 191 // void checkGridGraph(const GridGraph& g, int w, int h) { 192 // check(g.width() == w, "Wrong width"); 193 // check(g.height() == h, "Wrong height"); 194 195 // for (int i = 0; i < w; ++i) { 196 // for (int j = 0; j < h; ++j) { 197 // check(g.col(g(i, j)) == i, "Wrong col"); 198 // check(g.row(g(i, j)) == j, "Wrong row"); 199 // } 200 // } 201 202 // for (int i = 0; i < w; ++i) { 203 // for (int j = 0; j < h - 1; ++j) { 204 // check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down"); 205 // check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down"); 206 // } 207 // check(g.down(g(i, h - 1)) == INVALID, "Wrong down"); 208 // } 209 210 // for (int i = 0; i < w; ++i) { 211 // for (int j = 1; j < h; ++j) { 212 // check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up"); 213 // check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up"); 214 // } 215 // check(g.up(g(i, 0)) == INVALID, "Wrong up"); 216 // } 217 218 // for (int j = 0; j < h; ++j) { 219 // for (int i = 0; i < w - 1; ++i) { 220 // check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right"); 221 // check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right"); 222 // } 223 // check(g.right(g(w - 1, j)) == INVALID, "Wrong right"); 224 // } 225 226 // for (int j = 0; j < h; ++j) { 227 // for (int i = 1; i < w; ++i) { 228 // check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left"); 229 // check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left"); 230 // } 231 // check(g.left(g(0, j)) == INVALID, "Wrong left"); 232 // } 233 // } 532 234 533 235 void checkGraphs() { 534 236 { // Checking ListGraph 535 checkGraphBuild<ListGraph>(); 536 checkGraphAlter<ListGraph>(); 537 checkGraphErase<ListGraph>(); 538 checkGraphSnapshot<ListGraph>(); 237 checkGraph<ListGraph>(); 539 238 checkGraphValidityErase<ListGraph>(); 540 239 } 541 240 { // Checking SmartGraph 542 checkGraphBuild<SmartGraph>(); 543 checkGraphSnapshot<SmartGraph>(); 241 checkGraph<SmartGraph>(); 544 242 checkGraphValidity<SmartGraph>(); 545 243 } 546 { // Checking FullGraph 547 checkFullGraph(7); 548 checkFullGraph(8); 549 } 550 { // Checking GridGraph 551 checkGridGraph(5, 8); 552 checkGridGraph(8, 5); 553 checkGridGraph(5, 5); 554 checkGridGraph(0, 0); 555 checkGridGraph(1, 1); 556 } 557 { // Checking HypercubeGraph 558 checkHypercubeGraph(1); 559 checkHypercubeGraph(2); 560 checkHypercubeGraph(3); 561 checkHypercubeGraph(4); 562 } 244 // { // Checking FullGraph 245 // FullGraph g(5); 246 // checkGraphNodeList(g, 5); 247 // checkGraphEdgeList(g, 10); 248 // } 249 // { // Checking GridGraph 250 // GridGraph g(5, 6); 251 // checkGraphNodeList(g, 30); 252 // checkGraphEdgeList(g, 49); 253 // checkGridGraph(g, 5, 6); 254 // } 563 255 } 564 256 -
test/graph_test.h
r463 r263 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 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);126 117 } 127 118 -
test/graph_utils_test.cc
r463 r220 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/heap_test.cc
r463 r293 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/kruskal_test.cc
r463 r209 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/maps_test.cc
r463 r210 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/path_test.cc
r463 r209 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/random_test.cc
r463 r209 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/test_tools.h
r463 r209 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/test_tools_fail.cc
r463 r209 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/test_tools_pass.cc
r463 r209 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/time_measure_test.cc
r463 r209 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/unionfind_test.cc
r463 r209 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
tools/Makefile.am
r400 r310 1 1 if WANT_TOOLS 2 2 3 bin_PROGRAMS += \ 4 tools/dimacs-to-lgf 5 3 bin_PROGRAMS += 6 4 dist_bin_SCRIPTS += tools/lemon-0.x-to-1.x.sh 7 5 8 6 endif WANT_TOOLS 9 10 tools_dimacs_to_lgf_SOURCES = tools/dimacs-to-lgf.cc -
tools/lemon-0.x-to-1.x.sh
r378 r310 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(s)"8 6 echo "Usage:" 7 echo " $0 source-file" 8 exit 9 9 fi 10 10 11 for i in $@ 12 do 13 echo Update $i... 14 TMP=`mktemp` 15 sed -e "s/\<undirected graph\>/_gr_aph_label_/g"\ 16 -e "s/\<undirected graphs\>/_gr_aph_label_s/g"\ 17 -e "s/\<undirected edge\>/_ed_ge_label_/g"\ 18 -e "s/\<undirected edges\>/_ed_ge_label_s/g"\ 19 -e "s/\<directed graph\>/_digr_aph_label_/g"\ 20 -e "s/\<directed graphs\>/_digr_aph_label_s/g"\ 21 -e "s/\<directed edge\>/_ar_c_label_/g"\ 22 -e "s/\<directed edges\>/_ar_c_label_s/g"\ 23 -e "s/UGraph/_Gr_aph_label_/g"\ 24 -e "s/u[Gg]raph/_gr_aph_label_/g"\ 25 -e "s/\<Graph\>/_Digr_aph_label_/g"\ 26 -e "s/\<graph\>/_digr_aph_label_/g"\ 27 -e "s/\<Graphs\>/_Digr_aph_label_s/g"\ 28 -e "s/\<graphs\>/_digr_aph_label_s/g"\ 29 -e "s/_Graph/__Gr_aph_label_/g"\ 30 -e "s/\([Gg]\)raph\([a-z_]\)/_\1r_aph_label_\2/g"\ 31 -e "s/\([a-z_]\)graph/\1_gr_aph_label_/g"\ 32 -e "s/Graph/_Digr_aph_label_/g"\ 33 -e "s/graph/_digr_aph_label_/g"\ 34 -e "s/UEdge/_Ed_ge_label_/g"\ 35 -e "s/u[Ee]dge/_ed_ge_label_/g"\ 36 -e "s/IncEdgeIt/_In_cEd_geIt_label_/g"\ 37 -e "s/\<Edge\>/_Ar_c_label_/g"\ 38 -e "s/\<edge\>/_ar_c_label_/g"\ 39 -e "s/\<Edges\>/_Ar_c_label_s/g"\ 40 -e "s/\<edges\>/_ar_c_label_s/g"\ 41 -e "s/_Edge/__Ed_ge_label_/g"\ 42 -e "s/Edge\([a-z_]\)/_Ed_ge_label_\1/g"\ 43 -e "s/edge\([a-z_]\)/_ed_ge_label_\1/g"\ 44 -e "s/\([a-z_]\)edge/\1_ed_ge_label_/g"\ 45 -e "s/Edge/_Ar_c_label_/g"\ 46 -e "s/edge/_ar_c_label_/g"\ 47 -e "s/A[Nn]ode/_Re_d_label_/g"\ 48 -e "s/B[Nn]ode/_Blu_e_label_/g"\ 49 -e "s/A-[Nn]ode/_Re_d_label_/g"\ 50 -e "s/B-[Nn]ode/_Blu_e_label_/g"\ 51 -e "s/a[Nn]ode/_re_d_label_/g"\ 52 -e "s/b[Nn]ode/_blu_e_label_/g"\ 53 -e "s/\<UGRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__GR_APH_TY_PEDE_FS_label_\1/g"\ 54 -e "s/\<GRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__DIGR_APH_TY_PEDE_FS_label_\1/g"\ 55 -e "s/\<UGRAPH_TYPEDEFS\>/_GR_APH_TY_PEDE_FS_label_/g"\ 56 -e "s/\<GRAPH_TYPEDEFS\>/_DIGR_APH_TY_PEDE_FS_label_/g"\ 57 -e "s/_Digr_aph_label_/Digraph/g"\ 58 -e "s/_digr_aph_label_/digraph/g"\ 59 -e "s/_Gr_aph_label_/Graph/g"\ 60 -e "s/_gr_aph_label_/graph/g"\ 61 -e "s/_Ar_c_label_/Arc/g"\ 62 -e "s/_ar_c_label_/arc/g"\ 63 -e "s/_Ed_ge_label_/Edge/g"\ 64 -e "s/_ed_ge_label_/edge/g"\ 65 -e "s/_In_cEd_geIt_label_/IncEdgeIt/g"\ 66 -e "s/_Re_d_label_/Red/g"\ 67 -e "s/_Blu_e_label_/Blue/g"\ 68 -e "s/_re_d_label_/red/g"\ 69 -e "s/_blu_e_label_/blue/g"\ 70 -e "s/_GR_APH_TY_PEDE_FS_label_/GRAPH_TYPEDEFS/g"\ 71 -e "s/_DIGR_APH_TY_PEDE_FS_label_/DIGRAPH_TYPEDEFS/g"\ 72 -e "s/DigraphToEps/GraphToEps/g"\ 73 -e "s/digraphToEps/graphToEps/g"\ 74 -e "s/\<DefPredMap\>/SetPredMap/g"\ 75 -e "s/\<DefDistMap\>/SetDistMap/g"\ 76 -e "s/\<DefReachedMap\>/SetReachedMap/g"\ 77 -e "s/\<DefProcessedMap\>/SetProcessedMap/g"\ 78 -e "s/\<DefHeap\>/SetHeap/g"\ 79 -e "s/\<DefStandardHeap\>/SetStandradHeap/g"\ 80 -e "s/\<DefOperationTraits\>/SetOperationTraits/g"\ 81 -e "s/\<DefProcessedMapToBeDefaultMap\>/SetStandardProcessedMap/g"\ 82 -e "s/\<copyGraph\>/graphCopy/g"\ 83 -e "s/\<copyDigraph\>/digraphCopy/g"\ 84 -e "s/\<HyperCubeDigraph\>/HypercubeGraph/g"\ 85 -e "s/\<IntegerMap\>/RangeMap/g"\ 86 -e "s/\<integerMap\>/rangeMap/g"\ 87 -e "s/\<\([sS]\)tdMap\>/\1parseMap/g"\ 88 -e "s/\<\([Ff]\)unctorMap\>/\1unctorToMap/g"\ 89 -e "s/\<\([Mm]\)apFunctor\>/\1apToFunctor/g"\ 90 -e "s/\<\([Ff]\)orkWriteMap\>/\1orkMap/g"\ 91 -e "s/\<StoreBoolMap\>/LoggerBoolMap/g"\ 92 -e "s/\<storeBoolMap\>/loggerBoolMap/g"\ 93 -e "s/\<BoundingBox\>/Box/g"\ 94 -e "s/\<readNauty\>/readNautyGraph/g"\ 95 <$i > $TMP 96 mv $TMP $i 97 done 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
Note: See TracChangeset
for help on using the changeset viewer.