Changeset 325:3a2e0692eaae in lemon for doc/groups.dox
 Timestamp:
 10/09/08 13:47:26 (12 years ago)
 Branch:
 1.0
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

doc/groups.dox
r236 r325 41 41 some graph features like arc/edge or node deletion. 42 42 43 Alteration of standard containers need a very limited number of44 operations, these together satisfy the everyday requirements.45 In the case of graph structures, different operations are needed which do46 not alter the physical graph, but gives another view. If some nodes or47 arcs have to be hidden or the reverse oriented graph have to be used, then48 this is the case. It also may happen that in a flow implementation49 the residual graph can be accessed by another algorithm, or a nodeset50 is to be shrunk for another algorithm.51 LEMON also provides a variety of graphs for these requirements called52 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only53 in conjunction with other graph representations.54 55 43 You are free to use the graph structure that fit your requirements 56 44 the best, most graph algorithms and auxiliary data structures can be used 57 45 with any graph structures. 58 */59 60 /**61 @defgroup semi_adaptors SemiAdaptor Classes for Graphs62 @ingroup graphs63 \brief Graph types between real graphs and graph adaptors.64 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 46 */ 69 47 … … 153 131 154 132 /** 155 @defgroup matrices Matrices156 @ingroup datas157 \brief Two dimensional data storages implemented in LEMON.158 159 This group describes two dimensional data storages implemented in LEMON.160 */161 162 /**163 133 @defgroup paths Path Structures 164 134 @ingroup datas … … 214 184 215 185 /** 216 @defgroup max_flow Maximum Flow algorithms217 @ingroup algs218 \brief Algorithms for finding maximum flows.219 220 This group describes the algorithms for finding maximum flows and221 feasible circulations.222 223 The maximum flow problem is to find a flow between a single source and224 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$225 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity226 function and given \f$s, t \in V\f$ source and target node. The227 maximum flow is the \f$f_a\f$ solution of the next optimization problem:228 229 \f[ 0 \le f_a \le c_a \f]230 \f[ \sum_{v\in\delta^{}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}231 \qquad \forall u \in V \setminus \{s,t\}\f]232 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv}  \sum_{v\in\delta^{}(s)}f_{vu}\f]233 234 LEMON contains several algorithms for solving maximum flow problems:235  \ref lemon::EdmondsKarp "EdmondsKarp"236  \ref lemon::Preflow "Goldberg's Preflow algorithm"237  \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"238  \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"239 240 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the241 fastest method to compute the maximum flow. All impelementations242 provides functions to query the minimum cut, which is the dual linear243 programming problem of the maximum flow.244 245 */246 247 /**248 @defgroup min_cost_flow Minimum Cost Flow algorithms249 @ingroup algs250 251 \brief Algorithms for finding minimum cost flows and circulations.252 253 This group describes the algorithms for finding minimum cost flows and254 circulations.255 */256 257 /**258 @defgroup min_cut Minimum Cut algorithms259 @ingroup algs260 261 \brief Algorithms for finding minimum cut in graphs.262 263 This group describes the algorithms for finding minimum cut in graphs.264 265 The minimum cut problem 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 minimum269 cut is the \f$X\f$ solution of the next optimization problem:270 271 \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]273 274 LEMON contains several algorithms related to minimum cut problems:275 276  \ref lemon::HaoOrlin "HaoOrlin algorithm" to calculate minimum cut277 in directed graphs278  \ref lemon::NagamochiIbaraki "NagamochiIbaraki algorithm" to279 calculate minimum cut in undirected graphs280  \ref lemon::GomoryHuTree "GomoryHu tree computation" to calculate all281 pairs minimum cut in undirected graphs282 283 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 /**289 @defgroup graph_prop Connectivity and other graph properties290 @ingroup algs291 \brief Algorithms for discovering the graph properties292 293 This group describes the algorithms for discovering the graph properties294 like connectivity, bipartiteness, euler property, simplicity etc.295 296 \image html edge_biconnected_components.png297 \image latex edge_biconnected_components.eps "biedgeconnected components" width=\textwidth298 */299 300 /**301 @defgroup planar Planarity embedding and drawing302 @ingroup algs303 \brief Algorithms for planarity checking, embedding and drawing304 305 This group describes the algorithms for planarity checking,306 embedding and drawing.307 308 \image html planar.png309 \image latex planar.eps "Plane graph" width=\textwidth310 */311 312 /**313 @defgroup matching Matching algorithms314 @ingroup algs315 \brief Algorithms for finding matchings in graphs and bipartite graphs.316 317 This group contains algorithm objects and functions to calculate318 matchings in graphs and bipartite graphs. The general matching problem is319 finding a subset of the arcs which does not shares common endpoints.320 321 There are several different algorithms for calculate matchings in322 graphs. The matching problems in bipartite graphs are generally323 easier than in general graphs. The goal of the matching optimization324 can be the finding maximum cardinality, maximum weight or minimum cost325 matching. The search can be constrained to find perfect or326 maximum cardinality matching.327 328 LEMON contains the next algorithms:329  \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" HopcroftKarp330 augmenting path algorithm for calculate maximum cardinality matching in331 bipartite graphs332  \ref lemon::PrBipartiteMatching "PrBipartiteMatching" PushRelabel333 algorithm for calculate maximum cardinality matching in bipartite graphs334  \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"335 Successive shortest path algorithm for calculate maximum weighted matching336 and maximum weighted bipartite matching in bipartite graph337  \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"338 Successive shortest path algorithm for calculate minimum cost maximum339 matching in bipartite graph340  \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm341 for calculate maximum cardinality matching in general graph342  \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom343 shrinking algorithm for calculate maximum weighted matching in general344 graph345  \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"346 Edmond's blossom shrinking algorithm for calculate maximum weighted347 perfect matching in general graph348 349 \image html bipartite_matching.png350 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth351 352 */353 354 /**355 186 @defgroup spantree Minimum Spanning Tree algorithms 356 187 @ingroup algs … … 361 192 */ 362 193 363 364 /**365 @defgroup auxalg Auxiliary algorithms366 @ingroup algs367 \brief Auxiliary algorithms implemented in LEMON.368 369 This group describes some algorithms implemented in LEMON370 in order to make it easier to implement complex algorithms.371 */372 373 /**374 @defgroup approx Approximation algorithms375 \brief Approximation algorithms.376 377 This group describes the approximation and heuristic algorithms378 implemented in LEMON.379 */380 381 /**382 @defgroup gen_opt_group General Optimization Tools383 \brief This group describes some general optimization frameworks384 implemented in LEMON.385 386 This group describes some general optimization frameworks387 implemented in LEMON.388 389 */390 391 /**392 @defgroup lp_group Lp and Mip solvers393 @ingroup gen_opt_group394 \brief Lp and Mip solver interfaces for LEMON.395 396 This group describes Lp and Mip solver interfaces for LEMON. The397 various LP solvers could be used in the same manner with this398 interface.399 400 */401 402 /**403 @defgroup lp_utils Tools for Lp and Mip solvers404 @ingroup lp_group405 \brief Helper tools to the Lp and Mip solvers.406 407 This group adds some helper tools to general optimization framework408 implemented in LEMON.409 */410 411 /**412 @defgroup metah Metaheuristics413 @ingroup gen_opt_group414 \brief Metaheuristics for LEMON library.415 416 This group describes some metaheuristic optimization tools.417 */418 419 194 /** 420 195 @defgroup utils Tools and Utilities … … 451 226 452 227 /** 453 @defgroup graphbits Tools for Graph Implementation454 @ingroup utils455 \brief Tools to make it easier to create graphs.456 457 This group describes the tools that makes it easier to create graphs and458 the maps that dynamically update with the graph changes.459 */460 461 /**462 228 @defgroup exceptions Exceptions 463 229 @ingroup utils … … 472 238 473 239 This group describes the tools for importing and exporting graphs 474 and graph related data. Now it supports the LEMON format , the475 \c DIMACS formatand the encapsulated postscript (EPS) format.240 and graph related data. Now it supports the LEMON format 241 and the encapsulated postscript (EPS) format. 476 242 */ 477 243 … … 535 301 */ 536 302 537 /*  Unused group538 @defgroup experimental Experimental Structures and Algorithms539 This group describes some Experimental structures and algorithms.540 The stuff here is subject to change.541 */542 543 303 /** 544 304 \anchor demoprograms … … 552 312 build the library. 553 313 */ 554 555 /**556 @defgroup tools Standalone utility applications557 558 Some utility applications are listed here.559 560 The standard compilation procedure (<tt>./configure;make</tt>) will compile561 them, as well.562 */563
Note: See TracChangeset
for help on using the changeset viewer.