Changeset 50:a34c58ff6e40 in lemon1.0
 Timestamp:
 01/08/08 04:26:27 (13 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

doc/groups.dox
r41 r50 19 19 /** 20 20 @defgroup datas Data Structures 21 This group describes the several graphstructures implemented in LEMON.21 This group describes the several data structures implemented in LEMON. 22 22 */ 23 23 … … 51 51 LEMON also provides a variety of graphs for these requirements called 52 52 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only 53 in conjunction with other graph representation .53 in conjunction with other graph representations. 54 54 55 55 You are free to use the graph structure that fit your requirements … … 59 59 60 60 /** 61 @defgroup semi_adaptors SemiAdaptor sClasses for Graphs61 @defgroup semi_adaptors SemiAdaptor Classes for Graphs 62 62 @ingroup graphs 63 63 \brief Graph types between real graphs and graph adaptors. 64 64 65 Graph types between real graphs and graph adaptors. These classes wrap 66 graphs to give new functionality as the adaptors do it. On the other 67 hand they are not lightweight structures as the adaptors.65 This group describes some graph types between real graphs and graph adaptors. 66 These classes wrap graphs to give new functionality as the adaptors do it. 67 On the other hand they are not lightweight structures as the adaptors. 68 68 */ 69 69 … … 71 71 @defgroup maps Maps 72 72 @ingroup datas 73 \brief Some special purpose map to make life easier. 74 75 LEMON provides several special maps that e.g. combine 73 \brief Map structures implemented in LEMON. 74 75 This group describes the map structures implemented in LEMON. 76 77 LEMON provides several special purpose maps that e.g. combine 76 78 new maps from existing ones. 77 79 */ … … 82 84 \brief Special GraphRelated Maps. 83 85 84 Th ese maps are specifically designed to assign values to the nodes and edges of85 graphs.86 This group describes maps that are specifically designed to assign 87 values to the nodes and edges of graphs. 86 88 */ 87 89 … … 92 94 \brief Tools to create new maps from existing ones 93 95 94 Map adaptors are used to create "implicit" maps from other maps. 96 This group describes map adaptors that are used to create "implicit" 97 maps from other maps. 95 98 96 99 Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can … … 99 102 of different Value type. 100 103 101 The typical usage of this classes is thepassing implicit maps to104 The typical usage of this classes is passing implicit maps to 102 105 algorithms. If a function type algorithm is called then the function 103 106 type map adaptors can be used comfortable. For example let's see the … … 128 131 The usage with class type algorithms is little bit harder. In this 129 132 case the function type map adaptors can not be used, because the 130 function map adaptors give back temporar ly objects.133 function map adaptors give back temporary objects. 131 134 \code 132 135 Graph graph; … … 154 157 @defgroup matrices Matrices 155 158 @ingroup datas 156 \brief Two dimensional data storages .157 158 T wo dimensional data storages.159 \brief Two dimensional data storages implemented in LEMON. 160 161 This group describes two dimensional data storages implemented in LEMON. 159 162 */ 160 163 … … 164 167 \brief Path structures implemented in LEMON. 165 168 166 LEMON provides flexible data structures 167 to work with paths. 168 169 All of them have similar interfaces , and itcan be copied easily with170 assignment operator and copy constructor. This makeit easy and169 This group describes the path structures implemented in LEMON. 170 171 LEMON provides flexible data structures to work with paths. 172 All of them have similar interfaces and they can be copied easily with 173 assignment operators and copy constructors. This makes it easy and 171 174 efficient to have e.g. the Dijkstra algorithm to store its result in 172 175 any kind of path structure. … … 179 182 @defgroup auxdat Auxiliary Data Structures 180 183 @ingroup datas 181 \brief Somedata structures implemented in LEMON.182 183 This group describes the data structures implemented in LEMON in184 \brief Auxiliary data structures implemented in LEMON. 185 186 This group describes some data structures implemented in LEMON in 184 187 order to make it easier to implement combinatorial algorithms. 185 188 */ … … 198 201 @defgroup search Graph Search 199 202 @ingroup algs 200 \brief This group contains the common graph 201 search algorithms. 202 203 This group contains the common graph 204 search algorithms like Bfs and Dfs. 203 \brief Common graph search algorithms. 204 205 This group describes the common graph search algorithms like 206 Breadthfirst search (Bfs) and Depthfirst search (Dfs). 205 207 */ 206 208 … … 208 210 @defgroup shortest_path Shortest Path algorithms 209 211 @ingroup algs 210 \brief This group describes the algorithms 211 for finding shortest paths. 212 213 This group describes the algorithms for finding shortest paths in 214 graphs. 215 212 \brief Algorithms for finding shortest paths. 213 214 This group describes the algorithms for finding shortest paths in graphs. 216 215 */ 217 216 … … 219 218 @defgroup max_flow Maximum Flow algorithms 220 219 @ingroup algs 221 \brief This group describes the algorithms for finding maximum flows.220 \brief Algorithms for finding maximum flows. 222 221 223 222 This group describes the algorithms for finding maximum flows and 224 223 feasible circulations. 225 224 226 The maximum flow problem is to find a flow between a single source and227 singletarget that is maximum. Formally, there is\f$G=(V,A)\f$225 The maximum flow problem is to find a flow between a single source and 226 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$ 228 227 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity 229 228 function and given \f$s, t \in V\f$ source and target node. The 230 maximum flow is the solution of the next optimization problem:229 maximum flow is the \f$f_a\f$ solution of the next optimization problem: 231 230 232 231 \f[ 0 \le f_a \le c_a \f] 233 \f[ \sum_{v\in\delta^{}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \q uadu \in V \setminus \{s,t\}\f]232 \f[ \sum_{v\in\delta^{}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \qquad \forall u \in V \setminus \{s,t\}\f] 234 233 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv}  \sum_{v\in\delta^{}(s)}f_{vu}\f] 235 234 236 The lemon contains several algorithms for solvemaximum flow problems:235 LEMON contains several algorithms for solving maximum flow problems: 237 236  \ref lemon::EdmondsKarp "EdmondsKarp" 238 237  \ref lemon::Preflow "Goldberg's Preflow algorithm" 239  \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic tree "238  \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees" 240 239  \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees" 241 240 242 In most cases the \ref lemon::Preflow " preflow" algorithm provides the241 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the 243 242 fastest method to compute the maximum flow. All impelementations 244 provides functions forquery the minimum cut, which is the dual linear245 programming prob elm of the maximum flow.243 provides functions to query the minimum cut, which is the dual linear 244 programming problem of the maximum flow. 246 245 247 246 */ … … 251 250 @ingroup algs 252 251 253 \brief This group describes the algorithms 254 for finding minimum cost flows and circulations. 252 \brief Algorithms for finding minimum cost flows and circulations. 255 253 256 254 This group describes the algorithms for finding minimum cost flows and … … 262 260 @ingroup algs 263 261 264 \brief This group describes the algorithms for finding minimum cut in 265 graphs. 262 \brief Algorithms for finding minimum cut in graphs. 266 263 267 264 This group describes the algorithms for finding minimum cut in graphs. … … 271 268 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an 272 269 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum 273 cut is the solution of the next optimization problem:270 cut is the \f$X\f$ solution of the next optimization problem: 274 271 275 272 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f] 276 273 277 The lemoncontains several algorithms related to minimum cut problems:278 279  \ref lemon::HaoOrlin "HaoOrlin algorithm" forcalculate minimum cut274 LEMON contains several algorithms related to minimum cut problems: 275 276  \ref lemon::HaoOrlin "HaoOrlin algorithm" to calculate minimum cut 280 277 in directed graphs 281  \ref lemon::NagamochiIbaraki "NagamochiIbaraki algorithm" for278  \ref lemon::NagamochiIbaraki "NagamochiIbaraki algorithm" to 282 279 calculate minimum cut in undirected graphs 283  \ref lemon::GomoryHuTree "GomoryHu tree computation" forcalculate all280  \ref lemon::GomoryHuTree "GomoryHu tree computation" to calculate all 284 281 pairs minimum cut in undirected graphs 285 282 … … 292 289 @defgroup graph_prop Connectivity and other graph properties 293 290 @ingroup algs 294 \brief This group describes the algorithms 295 for discover the graph properties 296 297 This group describes the algorithms for discover the graph properties 298 like connectivity, bipartiteness, euler property, simplicity, etc... 291 \brief Algorithms for discovering the graph properties 292 293 This group describes the algorithms for discovering the graph properties 294 like connectivity, bipartiteness, euler property, simplicity etc. 299 295 300 296 \image html edge_biconnected_components.png … … 305 301 @defgroup planar Planarity embedding and drawing 306 302 @ingroup algs 307 \brief This group contains algorithms for planarityembedding and drawing308 309 This group containsalgorithms for planarity checking, embedding and drawing.303 \brief Algorithms for planarity checking, embedding and drawing 304 305 This group describes the algorithms for planarity checking, embedding and drawing. 310 306 311 307 \image html planar.png … … 316 312 @defgroup matching Matching algorithms 317 313 @ingroup algs 318 \brief This group describes the algorithms 319 for find matchings in graphs and bipartite graphs. 320 321 This group provides some algorithm objects and function to calculate 314 \brief Algorithms for finding matchings in graphs and bipartite graphs. 315 316 This group contains algorithm objects and functions to calculate 322 317 matchings in graphs and bipartite graphs. The general matching problem is 323 318 finding a subset of the edges which does not shares common endpoints. … … 359 354 @defgroup spantree Minimum Spanning Tree algorithms 360 355 @ingroup algs 361 \brief This group contains the algorithms for finding a minimum cost spanning 356 \brief Algorithms for finding a minimum cost spanning tree in a graph. 357 358 This group describes the algorithms for finding a minimum cost spanning 362 359 tree in a graph 363 364 This group contains the algorithms for finding a minimum cost spanning365 tree in a graph366 360 */ 367 361 … … 370 364 @defgroup auxalg Auxiliary algorithms 371 365 @ingroup algs 372 \brief Somealgorithms implemented in LEMON.373 374 This group describes the algorithms in LEMON in order to make375 i t easier to implement complex algorithms.366 \brief Auxiliary algorithms implemented in LEMON. 367 368 This group describes some algorithms implemented in LEMON 369 in order to make it easier to implement complex algorithms. 376 370 */ 377 371 378 372 /** 379 373 @defgroup approx Approximation algorithms 380 \brief Approximation algorithms 381 382 Approximation and heuristic algorithms 374 \brief Approximation algorithms. 375 376 This group describes the approximation and heuristic algorithms 377 implemented in LEMON. 383 378 */ 384 379 … … 407 402 @defgroup lp_utils Tools for Lp and Mip solvers 408 403 @ingroup lp_group 409 \brief This group adds some helper tools to the Lp and Mip solvers 410 implemented in LEMON. 404 \brief Helper tools to the Lp and Mip solvers. 411 405 412 406 This group adds some helper tools to general optimization framework … … 419 413 \brief Metaheuristics for LEMON library. 420 414 421 This group contains some metaheuristic optimization tools.415 This group describes some metaheuristic optimization tools. 422 416 */ 423 417 424 418 /** 425 419 @defgroup utils Tools and Utilities 426 \brief Tools and Utilities for Programming in LEMON427 428 Tools and Utilities for Programming in LEMON420 \brief Tools and utilities for programming in LEMON 421 422 Tools and utilities for programming in LEMON. 429 423 */ 430 424 … … 432 426 @defgroup gutils Basic Graph Utilities 433 427 @ingroup utils 434 \brief This group describes some simple basic graph utilities.428 \brief Simple basic graph utilities. 435 429 436 430 This group describes some simple basic graph utilities. … … 440 434 @defgroup misc Miscellaneous Tools 441 435 @ingroup utils 442 Here you can find several useful tools for development, 436 \brief Tools for development, debugging and testing. 437 438 This group describes several useful tools for development, 443 439 debugging and testing. 444 440 */ 445 446 441 447 442 /** 448 443 @defgroup timecount Time measuring and Counting 449 444 @ingroup misc 450 Here you can find simple tools for measuring the performance 445 \brief Simple tools for measuring the performance of algorithms. 446 447 This group describes simple tools for measuring the performance 451 448 of algorithms. 452 449 */ … … 455 452 @defgroup graphbits Tools for Graph Implementation 456 453 @ingroup utils 457 \brief Tools to Make It Easier to Make Graphs.458 459 This group describes the tools that makes it easier to make graphs and454 \brief Tools to make it easier to create graphs. 455 456 This group describes the tools that makes it easier to create graphs and 460 457 the maps that dynamically update with the graph changes. 461 458 */ … … 464 461 @defgroup exceptions Exceptions 465 462 @ingroup utils 466 This group contains the exceptions thrown by LEMON library 463 \brief Exceptions defined in LEMON. 464 465 This group describes the exceptions defined in LEMON. 467 466 */ 468 467 469 468 /** 470 469 @defgroup io_group InputOutput 471 \brief SeveralGraph InputOutput methods472 473 Here you can findtools for importing and exporting graphs470 \brief Graph InputOutput methods 471 472 This group describes the tools for importing and exporting graphs 474 473 and graph related data. Now it supports the LEMON format, the 475 \c DIMACS format and the encapsulated postscript format.474 \c DIMACS format and the encapsulated postscript (EPS) format. 476 475 */ 477 476 … … 481 480 \brief Reading and writing LEMON format 482 481 483 Methods for reading and writing LEMON format. More about this 484 format you can findon the \ref graphiopage "Graph InputOutput"482 This group describes methods for reading and writing LEMON format. 483 You can find more about this format on the \ref graphiopage "Graph InputOutput" 485 484 tutorial pages. 486 485 */ … … 491 490 \brief Section readers and writers for lemon InputOutput. 492 491 493 Here you can find which section readers and writers can attachto494 the LemonReader andLemonWriter.492 This group describes section readers and writers that can be attached to 493 \ref LemonReader and \ref LemonWriter. 495 494 */ 496 495 … … 510 509 \brief General \c EPS drawer and graph exporter 511 510 512 This group contains general \c EPS drawing methods and special511 This group describes general \c EPS drawing methods and special 513 512 graph exporting tools. 514 513 */ … … 538 537 539 538  The concept descriptor classes also provide a <em>checker class</em> 540 that makes it possible check whether a certain implementation of a539 that makes it possible to check whether a certain implementation of a 541 540 concept indeed provides all the required features. 542 541 … … 551 550 \brief Skeleton and concept checking classes for graph structures 552 551 553 This group contains the skeletons and concept checking classes of LEMON's552 This group describes the skeletons and concept checking classes of LEMON's 554 553 graph structures and helper classes used to implement these. 555 554 */ … … 557 556 /*  Unused group 558 557 @defgroup experimental Experimental Structures and Algorithms 559 This group contains some Experimental structures and algorithms.558 This group describes some Experimental structures and algorithms. 560 559 The stuff here is subject to change. 561 560 */ … … 571 570 It order to compile them, use <tt>enabledemo</tt> configure option when 572 571 build the library. 573 574 572 */ 575 573 … … 581 579 The standard compilation procedure (<tt>./configure;make</tt>) will compile 582 580 them, as well. 583 584 */ 585 581 */ 582
Note: See TracChangeset
for help on using the changeset viewer.