Changeset 209:765619b7cbb2 in lemon-main for doc/groups.dox
- Timestamp:
- 07/13/08 20:51:02 (16 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r192 r209 1 /* -*- C++-*-1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 2003-2008 … … 27 27 \brief Graph structures implemented in LEMON. 28 28 29 The implementation of combinatorial algorithms heavily relies on 30 efficient graph implementations. LEMON offers data structures which are 31 planned to be easily used in an experimental phase of implementation studies, 32 and thereafter the program code can be made efficient by small modifications. 29 The implementation of combinatorial algorithms heavily relies on 30 efficient graph implementations. LEMON offers data structures which are 31 planned to be easily used in an experimental phase of implementation studies, 32 and thereafter the program code can be made efficient by small modifications. 33 33 34 34 The most efficient implementation of diverse applications require the … … 41 41 some graph features like arc/edge or node deletion. 42 42 43 Alteration of standard containers need a very limited number of 44 operations, these together satisfy the everyday requirements. 45 In the case of graph structures, different operations are needed which do 46 not alter the physical graph, but gives another view. If some nodes or 43 Alteration of standard containers need a very limited number of 44 operations, these together satisfy the everyday requirements. 45 In the case of graph structures, different operations are needed which do 46 not alter the physical graph, but gives another view. If some nodes or 47 47 arcs have to be hidden or the reverse oriented graph have to be used, then 48 this is the case. It also may happen that in a flow implementation 49 the residual graph can be accessed by another algorithm, or a node-set 50 is to be shrunk for another algorithm. 51 LEMON also provides a variety of graphs for these requirements called 52 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only 53 in conjunction with other graph representations. 48 this is the case. It also may happen that in a flow implementation 49 the residual graph can be accessed by another algorithm, or a node-set 50 is to be shrunk for another algorithm. 51 LEMON also provides a variety of graphs for these requirements called 52 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only 53 in conjunction with other graph representations. 54 54 55 55 You are free to use the graph structure that fit your requirements 56 56 the best, most graph algorithms and auxiliary data structures can be used 57 with any graph structures. 57 with any graph structures. 58 58 */ 59 59 … … 64 64 65 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. 66 These classes wrap graphs to give new functionality as the adaptors do it. 67 67 On the other hand they are not light-weight structures as the adaptors. 68 68 */ 69 69 70 70 /** 71 @defgroup maps Maps 71 @defgroup maps Maps 72 72 @ingroup datas 73 73 \brief Map structures implemented in LEMON. … … 80 80 81 81 /** 82 @defgroup graph_maps Graph Maps 82 @defgroup graph_maps Graph Maps 83 83 @ingroup maps 84 84 \brief Special graph-related maps. … … 116 116 } 117 117 } 118 118 119 119 Digraph::NodeMap<int> degree_map(graph); 120 120 121 121 digraphToEps(graph, "graph.eps") 122 122 .coords(coords).scaleToA4().undirected() 123 123 .nodeColors(composeMap(functorToMap(nodeColor), degree_map)) 124 124 .run(); 125 \endcode 125 \endcode 126 126 The \c functorToMap() function makes an \c int to \c Color map from the 127 127 \e nodeColor() function. The \c composeMap() compose the \e degree_map … … 141 141 typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap; 142 142 TimeMap time(length, speed); 143 143 144 144 Dijkstra<Digraph, TimeMap> dijkstra(graph, time); 145 145 dijkstra.run(source, target); … … 153 153 154 154 /** 155 @defgroup matrices Matrices 155 @defgroup matrices Matrices 156 156 @ingroup datas 157 157 \brief Two dimensional data storages implemented in LEMON. … … 201 201 \brief Common graph search algorithms. 202 202 203 This group describes the common graph search algorithms like 203 This group describes the common graph search algorithms like 204 204 Breadth-first search (Bfs) and Depth-first search (Dfs). 205 205 */ … … 213 213 */ 214 214 215 /** 216 @defgroup max_flow Maximum Flow algorithms 217 @ingroup algs 215 /** 216 @defgroup max_flow Maximum Flow algorithms 217 @ingroup algs 218 218 \brief Algorithms for finding maximum flows. 219 219 … … 232 232 233 233 LEMON contains several algorithms for solving maximum flow problems: 234 - \ref lemon::EdmondsKarp "Edmonds-Karp" 234 - \ref lemon::EdmondsKarp "Edmonds-Karp" 235 235 - \ref lemon::Preflow "Goldberg's Preflow algorithm" 236 236 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees" … … 251 251 252 252 This group describes the algorithms for finding minimum cost flows and 253 circulations. 254 */ 255 256 /** 257 @defgroup min_cut Minimum Cut algorithms 258 @ingroup algs 253 circulations. 254 */ 255 256 /** 257 @defgroup min_cut Minimum Cut algorithms 258 @ingroup algs 259 259 260 260 \brief Algorithms for finding minimum cut in graphs. … … 273 273 274 274 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut 275 in directed graphs 275 in directed graphs 276 276 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to 277 277 calculate minimum cut in undirected graphs … … 308 308 309 309 /** 310 @defgroup matching Matching algorithms 310 @defgroup matching Matching algorithms 311 311 @ingroup algs 312 312 \brief Algorithms for finding matchings in graphs and bipartite graphs. … … 315 315 matchings in graphs and bipartite graphs. The general matching problem is 316 316 finding a subset of the arcs which does not shares common endpoints. 317 317 318 318 There are several different algorithms for calculate matchings in 319 319 graphs. The matching problems in bipartite graphs are generally … … 324 324 325 325 Lemon contains the next algorithms: 326 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp 327 augmenting path algorithm for calculate maximum cardinality matching in 326 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp 327 augmenting path algorithm for calculate maximum cardinality matching in 328 328 bipartite graphs 329 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel 330 algorithm for calculate maximum cardinality matching in bipartite graphs 331 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching" 332 Successive shortest path algorithm for calculate maximum weighted matching 329 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel 330 algorithm for calculate maximum cardinality matching in bipartite graphs 331 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching" 332 Successive shortest path algorithm for calculate maximum weighted matching 333 333 and maximum weighted bipartite matching in bipartite graph 334 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching" 335 Successive shortest path algorithm for calculate minimum cost maximum 334 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching" 335 Successive shortest path algorithm for calculate minimum cost maximum 336 336 matching in bipartite graph 337 337 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm … … 397 397 */ 398 398 399 /** 400 @defgroup lp_utils Tools for Lp and Mip solvers 399 /** 400 @defgroup lp_utils Tools for Lp and Mip solvers 401 401 @ingroup lp_group 402 402 \brief Helper tools to the Lp and Mip solvers. … … 415 415 416 416 /** 417 @defgroup utils Tools and Utilities 417 @defgroup utils Tools and Utilities 418 418 \brief Tools and utilities for programming in LEMON 419 419 … … 468 468 \brief Graph Input-Output methods 469 469 470 This group describes the tools for importing and exporting graphs 470 This group describes the tools for importing and exporting graphs 471 471 and graph related data. Now it supports the LEMON format, the 472 472 \c DIMACS format and the encapsulated postscript (EPS) format. … … 487 487 488 488 This group describes general \c EPS drawing methods and special 489 graph exporting tools. 489 graph exporting tools. 490 490 */ 491 491 … … 499 499 500 500 The purpose of the classes in this group is fourfold. 501 501 502 502 - These classes contain the documentations of the concepts. In order 503 503 to avoid document multiplications, an implementation of a concept … … 552 552 @defgroup tools Standalone utility applications 553 553 554 Some utility applications are listed here. 554 Some utility applications are listed here. 555 555 556 556 The standard compilation procedure (<tt>./configure;make</tt>) will compile 557 them, as well. 558 */ 559 557 them, as well. 558 */ 559
Note: See TracChangeset
for help on using the changeset viewer.