Changeset 330:d3a7603026a2 in lemon
 Timestamp:
 10/10/08 11:52:08 (16 years ago)
 Branch:
 1.0
 Parents:
 329:2592532ee838 (diff), 318:1e2d6ca80793 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.  Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

doc/groups.dox
r318 r330 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 … … 58 46 59 47 <b>See also:</b> \ref graph_concepts "Graph Structure Concepts". 60 */61 62 /**63 @defgroup semi_adaptors SemiAdaptor Classes for Graphs64 @ingroup graphs65 \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.70 48 */ 71 49 … … 156 134 157 135 /** 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 136 @defgroup paths Path Structures 167 137 @ingroup datas … … 215 185 216 186 /** 217 @defgroup max_flow Maximum Flow Algorithms218 @ingroup algs219 \brief Algorithms for finding maximum flows.220 221 This group describes the algorithms for finding maximum flows and222 feasible circulations.223 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 directed 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. The228 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 the242 fastest method to compute the maximum flow. All impelementations243 provides functions to query the minimum cut, which is the dual linear244 programming problem of the maximum flow.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 @defgroup graph_prop Connectivity and Other Graph Properties289 @ingroup algs290 \brief Algorithms for discovering the graph properties291 292 This group describes the algorithms for discovering the graph properties293 like connectivity, bipartiteness, euler property, simplicity etc.294 295 \image html edge_biconnected_components.png296 \image latex edge_biconnected_components.eps "biedgeconnected components" width=\textwidth297 */298 299 /**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 @defgroup matching Matching Algorithms313 @ingroup algs314 \brief Algorithms for finding matchings in graphs and bipartite graphs.315 316 This group contains algorithm objects and functions to calculate317 matchings in graphs and bipartite graphs. The general matching problem is318 finding a subset of the arcs which does not shares common endpoints.319 320 There are several different algorithms for calculate matchings in321 graphs. The matching problems in bipartite graphs are generally322 easier than in general graphs. The goal of the matching optimization323 can be the finding maximum cardinality, maximum weight or minimum cost324 matching. The search can be constrained to find perfect or325 maximum cardinality matching.326 327 LEMON contains the next algorithms:328  \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" HopcroftKarp329 augmenting path algorithm for calculate maximum cardinality matching in330 bipartite graphs331  \ref lemon::PrBipartiteMatching "PrBipartiteMatching" PushRelabel332 algorithm for calculate maximum cardinality matching in bipartite graphs333  \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"334 Successive shortest path algorithm for calculate maximum weighted matching335 and maximum weighted bipartite matching in bipartite graph336  \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"337 Successive shortest path algorithm for calculate minimum cost maximum338 matching in bipartite graph339  \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm340 for calculate maximum cardinality matching in general graph341  \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom342 shrinking algorithm for calculate maximum weighted matching in general343 graph344  \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"345 Edmond's blossom shrinking algorithm for calculate maximum weighted346 perfect matching in general graph347 348 \image html bipartite_matching.png349 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth350 */351 352 /**353 187 @defgroup spantree Minimum Spanning Tree Algorithms 354 188 @ingroup algs … … 360 194 361 195 /** 362 @defgroup auxalg Auxiliary Algorithms363 @ingroup algs364 \brief Auxiliary algorithms implemented in LEMON.365 366 This group describes some algorithms implemented in LEMON367 in order to make it easier to implement complex algorithms.368 */369 370 /**371 @defgroup approx Approximation Algorithms372 @ingroup algs373 \brief Approximation algorithms.374 375 This group describes the approximation and heuristic algorithms376 implemented in LEMON.377 */378 379 /**380 @defgroup gen_opt_group General Optimization Tools381 \brief This group describes some general optimization frameworks382 implemented in LEMON.383 384 This group describes some general optimization frameworks385 implemented in LEMON.386 */387 388 /**389 @defgroup lp_group Lp and Mip Solvers390 @ingroup gen_opt_group391 \brief Lp and Mip solver interfaces for LEMON.392 393 This group describes Lp and Mip solver interfaces for LEMON. The394 various LP solvers could be used in the same manner with this395 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 */414 415 /**416 196 @defgroup utils Tools and Utilities 417 197 \brief Tools and utilities for programming in LEMON … … 459 239 460 240 This group describes the tools for importing and exporting graphs 461 and graph related data. Now it supports the \ref lgfformat462 "LEMON Graph Format", the \c DIMACS format and the encapsulated 241 and graph related data. Now it supports the LEMON format 242 and the encapsulated postscript (EPS) format. 463 243 postscript (EPS) format. 464 244 */ … … 524 304 @ingroup concept 525 305 \brief Skeleton and concept checking classes for maps 526 306 527 307 This group describes the skeletons and concept checking classes of maps. 528 308 */ … … 539 319 build the library. 540 320 */ 541 542 /**543 @defgroup tools Standalone utility applications544 545 Some utility applications are listed here.546 547 The standard compilation procedure (<tt>./configure;make</tt>) will compile548 them, as well.549 */550 
doc/groups.dox
r329 r330 136 136 @defgroup paths Path Structures 137 137 @ingroup datas 138 \brief Path structures implemented in LEMON.138 \brief %Path structures implemented in LEMON. 139 139 140 140 This group describes the path structures implemented in LEMON. … … 271 271 The purpose of the classes in this group is fourfold. 272 272 273  These classes contain the documentations of the concepts. In order273  These classes contain the documentations of the %concepts. In order 274 274 to avoid document multiplications, an implementation of a concept 275 275 simply refers to the corresponding concept class. 276 276 277 277  These classes declare every functions, <tt>typedef</tt>s etc. an 278 implementation of the concepts should provide, however completely278 implementation of the %concepts should provide, however completely 279 279 without implementations and real data structures behind the 280 280 interface. On the other hand they should provide nothing else. All
Note: See TracChangeset
for help on using the changeset viewer.