Changeset 327:12626fc94ccf in lemon for doc/groups.dox
- Timestamp:
- 10/09/08 15:37:44 (16 years ago)
- Branch:
- 1.0
- Parents:
- 326:de38fca76780 (diff), 315:c175e387da19 (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
r314 r327 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 node-set50 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 Semi-Adaptor 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 light-weight 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 "Edmonds-Karp"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 non-empty and non-complete266 \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 "Hao-Orlin algorithm" to calculate minimum cut277 in directed graphs278 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to279 calculate minimum cut in undirected graphs280 - \ref lemon::GomoryHuTree "Gomory-Hu 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 "bi-edge-connected 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" Hopcroft-Karp329 augmenting path algorithm for calculate maximum cardinality matching in330 bipartite graphs331 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel332 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 … … 359 193 */ 360 194 361 /**362 @defgroup auxalg Auxiliary Algorithms363 195 @ingroup algs 364 \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 196 /** 416 197 @defgroup utils Tools and Utilities … … 459 240 460 241 This group describes the tools for importing and exporting graphs 461 and graph related data. Now it supports the \ref lgf-format462 "LEMON Graph Format", the \c DIMACS format and the encapsulated 242 and graph related data. Now it supports the LEMON format 243 and the encapsulated postscript (EPS) format. 463 244 postscript (EPS) format. 464 245 */ … … 520 301 */ 521 302 522 /**523 @defgroup map_concepts Map Concepts524 @ingroup concept525 \brief Skeleton and concept checking classes for maps526 303 527 304 This group describes the skeletons and concept checking classes of maps. 528 */529 530 305 /** 531 306 \anchor demoprograms … … 539 314 build the library. 540 315 */ 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
r325 r327 43 43 You are free to use the graph structure that fit your requirements 44 44 the best, most graph algorithms and auxiliary data structures can be used 45 with any graph structures. 45 with any graph structure. 46 47 <b>See also:</b> \ref graph_concepts "Graph Structure Concepts". 46 48 */ 47 49 … … 53 55 This group describes the map structures implemented in LEMON. 54 56 55 LEMON provides several special purpose maps that e.g. combine57 LEMON provides several special purpose maps and map adaptors that e.g. combine 56 58 new maps from existing ones. 59 60 <b>See also:</b> \ref map_concepts "Map Concepts". 57 61 */ 58 62 … … 65 69 values to the nodes and arcs of graphs. 66 70 */ 67 68 71 69 72 /** … … 83 86 algorithms. If a function type algorithm is called then the function 84 87 type map adaptors can be used comfortable. For example let's see the 85 usage of map adaptors with the \c digraphToEps() function.88 usage of map adaptors with the \c graphToEps() function. 86 89 \code 87 90 Color nodeColor(int deg) { … … 97 100 Digraph::NodeMap<int> degree_map(graph); 98 101 99 digraphToEps(graph, "graph.eps")102 graphToEps(graph, "graph.eps") 100 103 .coords(coords).scaleToA4().undirected() 101 104 .nodeColors(composeMap(functorToMap(nodeColor), degree_map)) … … 103 106 \endcode 104 107 The \c functorToMap() function makes an \c int to \c Color map from the 105 \ e nodeColor() function. The \c composeMap() compose the \edegree_map108 \c nodeColor() function. The \c composeMap() compose the \c degree_map 106 109 and the previously created map. The composed map is a proper function to 107 110 get the color of each node. … … 144 147 145 148 \sa lemon::concepts::Path 146 147 149 */ 148 150 … … 156 158 */ 157 159 158 159 160 /** 160 161 @defgroup algs Algorithms … … 172 173 173 174 This group describes the common graph search algorithms like 174 Breadth- first search (Bfs) and Depth-first search (Dfs).175 */ 176 177 /** 178 @defgroup shortest_path Shortest Path algorithms175 Breadth-First Search (BFS) and Depth-First Search (DFS). 176 */ 177 178 /** 179 @defgroup shortest_path Shortest Path Algorithms 179 180 @ingroup algs 180 181 \brief Algorithms for finding shortest paths. … … 184 185 185 186 /** 186 @defgroup spantree Minimum Spanning Tree algorithms187 @defgroup spantree Minimum Spanning Tree Algorithms 187 188 @ingroup algs 188 189 \brief Algorithms for finding a minimum cost spanning tree in a graph. … … 192 193 */ 193 194 195 @ingroup algs 194 196 /** 195 197 @defgroup utils Tools and Utilities … … 217 219 218 220 /** 219 @defgroup timecount Time measuring and Counting221 @defgroup timecount Time Measuring and Counting 220 222 @ingroup misc 221 223 \brief Simple tools for measuring the performance of algorithms. … … 240 242 and graph related data. Now it supports the LEMON format 241 243 and the encapsulated postscript (EPS) format. 244 postscript (EPS) format. 242 245 */ 243 246 … … 245 248 @defgroup lemon_io LEMON Input-Output 246 249 @ingroup io_group 247 \brief Reading and writing \ref lgf-format "LEMON Graph Format".250 \brief Reading and writing LEMON Graph Format. 248 251 249 252 This group describes methods for reading and writing … … 252 255 253 256 /** 254 @defgroup eps_io Postscript exporting257 @defgroup eps_io Postscript Exporting 255 258 @ingroup io_group 256 259 \brief General \c EPS drawer and graph exporter … … 259 262 graph exporting tools. 260 263 */ 261 262 264 263 265 /** … … 288 290 289 291 - Finally, They can serve as a skeleton of a new implementation of a concept. 290 291 */ 292 292 */ 293 293 294 294 /** … … 301 301 */ 302 302 303 304 This group describes the skeletons and concept checking classes of maps. 303 305 /** 304 306 \anchor demoprograms
Note: See TracChangeset
for help on using the changeset viewer.