Changes in doc/groups.dox [318:1e2d6ca80793:844:c01a98ce01fd] in lemon
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

doc/groups.dox
r318 r844 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003200 85 * Copyright (C) 20032009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 17 17 */ 18 18 19 namespace lemon { 20 19 21 /** 20 22 @defgroup datas Data Structures 21 This group describes the several data structures implemented in LEMON.23 This group contains the several data structures implemented in LEMON. 22 24 */ 23 25 … … 61 63 62 64 /** 63 @defgroup semi_adaptors SemiAdaptor Classes for Graphs65 @defgroup graph_adaptors Adaptor Classes for Graphs 64 66 @ingroup graphs 65 \brief Graph types between real graphs and graph adaptors. 66 67 This group describes some graph types between real graphs and graph adaptors. 68 These classes wrap graphs to give new functionality as the adaptors do it. 69 On the other hand they are not lightweight structures as the adaptors. 67 \brief Adaptor classes for digraphs and graphs 68 69 This group contains several useful adaptor classes for digraphs and graphs. 70 71 The main parts of LEMON are the different graph structures, generic 72 graph algorithms, graph concepts, which couple them, and graph 73 adaptors. While the previous notions are more or less clear, the 74 latter one needs further explanation. Graph adaptors are graph classes 75 which serve for considering graph structures in different ways. 76 77 A short example makes this much clearer. Suppose that we have an 78 instance \c g of a directed graph type, say ListDigraph and an algorithm 79 \code 80 template <typename Digraph> 81 int algorithm(const Digraph&); 82 \endcode 83 is needed to run on the reverse oriented graph. It may be expensive 84 (in time or in memory usage) to copy \c g with the reversed 85 arcs. In this case, an adaptor class is used, which (according 86 to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph. 87 The adaptor uses the original digraph structure and digraph operations when 88 methods of the reversed oriented graph are called. This means that the adaptor 89 have minor memory usage, and do not perform sophisticated algorithmic 90 actions. The purpose of it is to give a tool for the cases when a 91 graph have to be used in a specific alteration. If this alteration is 92 obtained by a usual construction like filtering the node or the arc set or 93 considering a new orientation, then an adaptor is worthwhile to use. 94 To come back to the reverse oriented graph, in this situation 95 \code 96 template<typename Digraph> class ReverseDigraph; 97 \endcode 98 template class can be used. The code looks as follows 99 \code 100 ListDigraph g; 101 ReverseDigraph<ListDigraph> rg(g); 102 int result = algorithm(rg); 103 \endcode 104 During running the algorithm, the original digraph \c g is untouched. 105 This techniques give rise to an elegant code, and based on stable 106 graph adaptors, complex algorithms can be implemented easily. 107 108 In flow, circulation and matching problems, the residual 109 graph is of particular importance. Combining an adaptor implementing 110 this with shortest path algorithms or minimum mean cycle algorithms, 111 a range of weighted and cardinality optimization algorithms can be 112 obtained. For other examples, the interested user is referred to the 113 detailed documentation of particular adaptors. 114 115 The behavior of graph adaptors can be very different. Some of them keep 116 capabilities of the original graph while in other cases this would be 117 meaningless. This means that the concepts that they meet depend 118 on the graph adaptor, and the wrapped graph. 119 For example, if an arc of a reversed digraph is deleted, this is carried 120 out by deleting the corresponding arc of the original digraph, thus the 121 adaptor modifies the original digraph. 122 However in case of a residual digraph, this operation has no sense. 123 124 Let us stand one more example here to simplify your work. 125 ReverseDigraph has constructor 126 \code 127 ReverseDigraph(Digraph& digraph); 128 \endcode 129 This means that in a situation, when a <tt>const %ListDigraph&</tt> 130 reference to a graph is given, then it have to be instantiated with 131 <tt>Digraph=const %ListDigraph</tt>. 132 \code 133 int algorithm1(const ListDigraph& g) { 134 ReverseDigraph<const ListDigraph> rg(g); 135 return algorithm2(rg); 136 } 137 \endcode 70 138 */ 71 139 … … 75 143 \brief Map structures implemented in LEMON. 76 144 77 This group describes the map structures implemented in LEMON.145 This group contains the map structures implemented in LEMON. 78 146 79 147 LEMON provides several special purpose maps and map adaptors that e.g. combine … … 88 156 \brief Special graphrelated maps. 89 157 90 This group describes maps that are specifically designed to assign 91 values to the nodes and arcs of graphs. 158 This group contains maps that are specifically designed to assign 159 values to the nodes and arcs/edges of graphs. 160 161 If you are looking for the standard graph maps (\c NodeMap, \c ArcMap, 162 \c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts". 92 163 */ 93 164 … … 97 168 \brief Tools to create new maps from existing ones 98 169 99 This group describes map adaptors that are used to create "implicit"170 This group contains map adaptors that are used to create "implicit" 100 171 maps from other maps. 101 172 102 Most of them are \ref lemon::concepts::ReadMap "readonly maps".173 Most of them are \ref concepts::ReadMap "readonly maps". 103 174 They can make arithmetic and logical operations between one or two maps 104 175 (negation, shifting, addition, multiplication, logical 'and', 'or', … … 156 227 157 228 /** 158 @defgroup matrices Matrices159 @ingroup datas160 \brief Two dimensional data storages implemented in LEMON.161 162 This group describes two dimensional data storages implemented in LEMON.163 */164 165 /**166 229 @defgroup paths Path Structures 167 230 @ingroup datas 168 231 \brief %Path structures implemented in LEMON. 169 232 170 This group describes the path structures implemented in LEMON.233 This group contains the path structures implemented in LEMON. 171 234 172 235 LEMON provides flexible data structures to work with paths. … … 184 247 \brief Auxiliary data structures implemented in LEMON. 185 248 186 This group describes some data structures implemented in LEMON in249 This group contains some data structures implemented in LEMON in 187 250 order to make it easier to implement combinatorial algorithms. 188 251 */ … … 190 253 /** 191 254 @defgroup algs Algorithms 192 \brief This group describes the several algorithms255 \brief This group contains the several algorithms 193 256 implemented in LEMON. 194 257 195 This group describes the several algorithms258 This group contains the several algorithms 196 259 implemented in LEMON. 197 260 */ … … 202 265 \brief Common graph search algorithms. 203 266 204 This group describes the common graph search algorithms like205 BreadthFirst Search (BFS) and DepthFirst Search (DFS).267 This group contains the common graph search algorithms, namely 268 \e breadthfirst \e search (BFS) and \e depthfirst \e search (DFS). 206 269 */ 207 270 … … 211 274 \brief Algorithms for finding shortest paths. 212 275 213 This group describes the algorithms for finding shortest paths in graphs. 276 This group contains the algorithms for finding shortest paths in digraphs. 277 278  \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a 279 source node when all arc lengths are nonnegative. 280  \ref Suurballe A successive shortest path algorithm for finding 281 arcdisjoint paths between two nodes having minimum total length. 214 282 */ 215 283 … … 219 287 \brief Algorithms for finding maximum flows. 220 288 221 This group describes the algorithms for finding maximum flows and289 This group contains the algorithms for finding maximum flows and 222 290 feasible circulations. 223 291 224 The maximum flow problem is to find a flow between a single source and225 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$226 di rected graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity227 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]234 235 LEMON contains several algorithms for solving maximum flow problems: 236  \ref lemon::EdmondsKarp "EdmondsKarp" 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 f astest method to compute the maximum flow. All impelementations243 provides functions to query the minimum cut, which is the dual linear 244 programming problem of the maximum flow.245 */ 246 247 /** 248 @defgroup min_cost_flow Minimum Cost Flow Algorithms292 The \e maximum \e flow \e problem is to find a flow of maximum value between 293 a single source and a single target. Formally, there is a \f$G=(V,A)\f$ 294 digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and 295 \f$s, t \in V\f$ source and target nodes. 296 A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the 297 following optimization problem. 298 299 \f[ \max\sum_{sv\in A} f(sv)  \sum_{vs\in A} f(vs) \f] 300 \f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu) 301 \quad \forall u\in V\setminus\{s,t\} \f] 302 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] 303 304 \ref Preflow implements the preflow pushrelabel algorithm of Goldberg and 305 Tarjan for solving this problem. It also provides functions to query the 306 minimum cut, which is the dual problem of maximum flow. 307 308 309 \ref Circulation is a preflow pushrelabel algorithm implemented directly 310 for finding feasible circulations, which is a somewhat different problem, 311 but it is strongly related to maximum flow. 312 For more information, see \ref Circulation. 313 */ 314 315 /** 316 @defgroup min_cost_flow_algs Minimum Cost Flow Algorithms 249 317 @ingroup algs 250 318 251 319 \brief Algorithms for finding minimum cost flows and circulations. 252 320 253 This group describes the algorithms for finding minimum cost flows and 254 circulations. 321 This group contains the algorithms for finding minimum cost flows and 322 circulations. For more information about this problem and its dual 323 solution see \ref min_cost_flow "Minimum Cost Flow Problem". 324 325 \ref NetworkSimplex is an efficient implementation of the primal Network 326 Simplex algorithm for finding minimum cost flows. It also provides dual 327 solution (node potentials), if an optimal flow is found. 255 328 */ 256 329 … … 261 334 \brief Algorithms for finding minimum cut in graphs. 262 335 263 This group describes the algorithms for finding minimum cut in graphs.264 265 The minimum cutproblem is to find a nonempty and noncomplete266 \f$X\f$ subset of the vertices with minimum overall capacity on267 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an268 \f$c _a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum336 This group contains the algorithms for finding minimum cut in graphs. 337 338 The \e minimum \e cut \e problem is to find a nonempty and noncomplete 339 \f$X\f$ subset of the nodes with minimum overall capacity on 340 outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a 341 \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum 269 342 cut is the \f$X\f$ solution of the next optimization problem: 270 343 271 344 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} 272 \sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]345 \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f] 273 346 274 347 LEMON contains several algorithms related to minimum cut problems: 275 348 276  \ref lemon::HaoOrlin "HaoOrlin algorithm" to calculate minimum cut 277 in directed graphs 278  \ref lemon::NagamochiIbaraki "NagamochiIbaraki algorithm" to 279 calculate minimum cut in undirected graphs 280  \ref lemon::GomoryHuTree "GomoryHu tree computation" to calculate all 281 pairs minimum cut in undirected graphs 349  \ref HaoOrlin "HaoOrlin algorithm" for calculating minimum cut 350 in directed graphs. 351  \ref GomoryHu "GomoryHu tree computation" for calculating 352 allpairs minimum cut in undirected graphs. 282 353 283 354 If you want to find minimum cut just between two distinict nodes, 284 please see the \ref max_flow "Maximum Flow page".285 */ 286 287 /** 288 @defgroup graph_prop Connectivity and Other Graph Properties355 see the \ref max_flow "maximum flow problem". 356 */ 357 358 /** 359 @defgroup graph_properties Connectivity and Other Graph Properties 289 360 @ingroup algs 290 361 \brief Algorithms for discovering the graph properties 291 362 292 This group describes the algorithms for discovering the graph properties363 This group contains the algorithms for discovering the graph properties 293 364 like connectivity, bipartiteness, euler property, simplicity etc. 294 365 … … 298 369 299 370 /** 300 @defgroup planar Planarity Embedding and Drawing301 @ingroup algs302 \brief Algorithms for planarity checking, embedding and drawing303 304 This group describes the algorithms for planarity checking,305 embedding and drawing.306 307 \image html planar.png308 \image latex planar.eps "Plane graph" width=\textwidth309 */310 311 /**312 371 @defgroup matching Matching Algorithms 313 372 @ingroup algs 314 373 \brief Algorithms for finding matchings in graphs and bipartite graphs. 315 374 316 This group contains algorithm objects and functions to calculate317 matchings in graphs and bipartite graphs. The general matching problem is 318 finding a subset of the arcs which does not shares common endpoints.375 This group contains the algorithms for calculating matchings in graphs. 376 The general matching problem is finding a subset of the edges for which 377 each node has at most one incident edge. 319 378 320 379 There are several different algorithms for calculate matchings in 321 graphs. The matching problems in bipartite graphs are generally 322 easier than in general graphs. The goal of the matching optimization 323 can be the finding maximum cardinality, maximum weight or minimum cost 380 graphs. The goal of the matching optimization 381 can be finding maximum cardinality, maximum weight or minimum cost 324 382 matching. The search can be constrained to find perfect or 325 383 maximum cardinality matching. 326 384 327 LEMON contains the next algorithms: 328  \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" HopcroftKarp 329 augmenting path algorithm for calculate maximum cardinality matching in 330 bipartite graphs 331  \ref lemon::PrBipartiteMatching "PrBipartiteMatching" PushRelabel 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 385 The matching algorithms implemented in LEMON: 386  \ref MaxMatching Edmond's blossom shrinking algorithm for calculating 387 maximum cardinality matching in general graphs. 388  \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating 389 maximum weighted matching in general graphs. 390  \ref MaxWeightedPerfectMatching 391 Edmond's blossom shrinking algorithm for calculating maximum weighted 392 perfect matching in general graphs. 347 393 348 394 \image html bipartite_matching.png … … 353 399 @defgroup spantree Minimum Spanning Tree Algorithms 354 400 @ingroup algs 355 \brief Algorithms for finding a minimum cost spanning tree in a graph.356 357 This group describes the algorithms for finding aminimum cost spanning358 tree in a graph401 \brief Algorithms for finding minimum cost spanning trees and arborescences. 402 403 This group contains the algorithms for finding minimum cost spanning 404 trees and arborescences. 359 405 */ 360 406 … … 364 410 \brief Auxiliary algorithms implemented in LEMON. 365 411 366 This group describes some algorithms implemented in LEMON412 This group contains some algorithms implemented in LEMON 367 413 in order to make it easier to implement complex algorithms. 368 414 */ 369 415 370 416 /** 371 @defgroup approx Approximation Algorithms 372 @ingroup algs 373 \brief Approximation algorithms. 374 375 This group describes the approximation and heuristic algorithms 417 @defgroup gen_opt_group General Optimization Tools 418 \brief This group contains some general optimization frameworks 376 419 implemented in LEMON. 377 */ 378 379 /** 380 @defgroup gen_opt_group General Optimization Tools 381 \brief This group describes some general optimization frameworks 382 implemented in LEMON. 383 384 This group describes some general optimization frameworks 420 421 This group contains some general optimization frameworks 385 422 implemented in LEMON. 386 423 */ … … 391 428 \brief Lp and Mip solver interfaces for LEMON. 392 429 393 This group describes Lp and Mip solver interfaces for LEMON. The430 This group contains Lp and Mip solver interfaces for LEMON. The 394 431 various LP solvers could be used in the same manner with this 395 432 interface. 396 */397 398 /**399 @defgroup lp_utils Tools for Lp and Mip Solvers400 @ingroup lp_group401 \brief Helper tools to the Lp and Mip solvers.402 403 This group adds some helper tools to general optimization framework404 implemented in LEMON.405 */406 407 /**408 @defgroup metah Metaheuristics409 @ingroup gen_opt_group410 \brief Metaheuristics for LEMON library.411 412 This group describes some metaheuristic optimization tools.413 433 */ 414 434 … … 425 445 \brief Simple basic graph utilities. 426 446 427 This group describes some simple basic graph utilities.447 This group contains some simple basic graph utilities. 428 448 */ 429 449 … … 433 453 \brief Tools for development, debugging and testing. 434 454 435 This group describes several useful tools for development,455 This group contains several useful tools for development, 436 456 debugging and testing. 437 457 */ … … 442 462 \brief Simple tools for measuring the performance of algorithms. 443 463 444 This group describes simple tools for measuring the performance464 This group contains simple tools for measuring the performance 445 465 of algorithms. 446 466 */ … … 451 471 \brief Exceptions defined in LEMON. 452 472 453 This group describes the exceptions defined in LEMON.473 This group contains the exceptions defined in LEMON. 454 474 */ 455 475 … … 458 478 \brief Graph InputOutput methods 459 479 460 This group describes the tools for importing and exporting graphs480 This group contains the tools for importing and exporting graphs 461 481 and graph related data. Now it supports the \ref lgfformat 462 482 "LEMON Graph Format", the \c DIMACS format and the encapsulated … … 465 485 466 486 /** 467 @defgroup lemon_io LEMON InputOutput487 @defgroup lemon_io LEMON Graph Format 468 488 @ingroup io_group 469 489 \brief Reading and writing LEMON Graph Format. 470 490 471 This group describes methods for reading and writing491 This group contains methods for reading and writing 472 492 \ref lgfformat "LEMON Graph Format". 473 493 */ … … 478 498 \brief General \c EPS drawer and graph exporter 479 499 480 This group describes general \c EPS drawing methods and special500 This group contains general \c EPS drawing methods and special 481 501 graph exporting tools. 502 */ 503 504 /** 505 @defgroup dimacs_group DIMACS format 506 @ingroup io_group 507 \brief Read and write files in DIMACS format 508 509 Tools to read a digraph from or write it to a file in DIMACS format data. 510 */ 511 512 /** 513 @defgroup nauty_group NAUTY Format 514 @ingroup io_group 515 \brief Read \e Nauty format 516 517 Tool to read graphs from \e Nauty format data. 482 518 */ 483 519 … … 486 522 \brief Skeleton classes and concept checking classes 487 523 488 This group describes the data/algorithm skeletons and concept checking524 This group contains the data/algorithm skeletons and concept checking 489 525 classes implemented in LEMON. 490 526 … … 516 552 \brief Skeleton and concept checking classes for graph structures 517 553 518 This group describes the skeletons and concept checking classes of LEMON's554 This group contains the skeletons and concept checking classes of LEMON's 519 555 graph structures and helper classes used to implement these. 520 556 */ … … 525 561 \brief Skeleton and concept checking classes for maps 526 562 527 This group describes the skeletons and concept checking classes of maps.563 This group contains the skeletons and concept checking classes of maps. 528 564 */ 529 565 … … 531 567 \anchor demoprograms 532 568 533 @defgroup demos Demo programs569 @defgroup demos Demo Programs 534 570 535 571 Some demo programs are listed here. Their full source codes can be found in 536 572 the \c demo subdirectory of the source tree. 537 573 538 I t order to compile them, use <tt>enabledemo</tt> configure option when539 build the library.540 */ 541 542 /** 543 @defgroup tools Standalone utility applications574 In order to compile them, use the <tt>make demo</tt> or the 575 <tt>make check</tt> commands. 576 */ 577 578 /** 579 @defgroup tools Standalone Utility Applications 544 580 545 581 Some utility applications are listed here. … … 549 585 */ 550 586 587 }
Note: See TracChangeset
for help on using the changeset viewer.