Changes in doc/groups.dox [236:da953e387d31:320:12626fc94ccf] in lemon-1.0
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r236 r320 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 57 with any graph structures. 58 */ 59 60 /** 61 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs 62 @ingroup graphs 63 \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 light-weight structures as the adaptors. 45 with any graph structure. 46 47 <b>See also:</b> \ref graph_concepts "Graph Structure Concepts". 68 48 */ 69 49 … … 75 55 This group describes the map structures implemented in LEMON. 76 56 77 LEMON provides several special purpose maps that e.g. combine57 LEMON provides several special purpose maps and map adaptors that e.g. combine 78 58 new maps from existing ones. 59 60 <b>See also:</b> \ref map_concepts "Map Concepts". 79 61 */ 80 62 … … 87 69 values to the nodes and arcs of graphs. 88 70 */ 89 90 71 91 72 /** … … 105 86 algorithms. If a function type algorithm is called then the function 106 87 type map adaptors can be used comfortable. For example let's see the 107 usage of map adaptors with the \c digraphToEps() function.88 usage of map adaptors with the \c graphToEps() function. 108 89 \code 109 90 Color nodeColor(int deg) { … … 119 100 Digraph::NodeMap<int> degree_map(graph); 120 101 121 digraphToEps(graph, "graph.eps")102 graphToEps(graph, "graph.eps") 122 103 .coords(coords).scaleToA4().undirected() 123 104 .nodeColors(composeMap(functorToMap(nodeColor), degree_map)) … … 125 106 \endcode 126 107 The \c functorToMap() function makes an \c int to \c Color map from the 127 \ e nodeColor() function. The \c composeMap() compose the \edegree_map108 \c nodeColor() function. The \c composeMap() compose the \c degree_map 128 109 and the previously created map. The composed map is a proper function to 129 110 get the color of each node. … … 153 134 154 135 /** 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 136 @defgroup paths Path Structures 164 137 @ingroup datas … … 174 147 175 148 \sa lemon::concepts::Path 176 177 149 */ 178 150 … … 186 158 */ 187 159 188 189 160 /** 190 161 @defgroup algs Algorithms … … 202 173 203 174 This group describes the common graph search algorithms like 204 Breadth- first search (Bfs) and Depth-first search (Dfs).205 */ 206 207 /** 208 @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 209 180 @ingroup algs 210 181 \brief Algorithms for finding shortest paths. … … 214 185 215 186 /** 216 @defgroup max_flow Maximum Flow algorithms 217 @ingroup algs 218 \brief Algorithms for finding maximum flows. 219 220 This group describes the algorithms for finding maximum flows and 221 feasible circulations. 222 223 The maximum flow problem is to find a flow between a single source and 224 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$ capacity 226 function and given \f$s, t \in V\f$ source and target node. The 227 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 "Edmonds-Karp" 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 the 241 fastest method to compute the maximum flow. All impelementations 242 provides functions to query the minimum cut, which is the dual linear 243 programming problem of the maximum flow. 244 245 */ 246 247 /** 248 @defgroup min_cost_flow Minimum Cost Flow algorithms 249 @ingroup algs 250 251 \brief Algorithms for finding minimum cost flows and circulations. 252 253 This group describes the algorithms for finding minimum cost flows and 254 circulations. 255 */ 256 257 /** 258 @defgroup min_cut Minimum Cut algorithms 259 @ingroup algs 260 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-complete 266 \f$X\f$ subset of the vertices with minimum overall capacity on 267 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an 268 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum 269 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 cut 277 in directed graphs 278 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to 279 calculate minimum cut in undirected graphs 280 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all 281 pairs minimum cut in undirected graphs 282 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 properties 290 @ingroup algs 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. 295 296 \image html edge_biconnected_components.png 297 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth 298 */ 299 300 /** 301 @defgroup planar Planarity embedding and drawing 302 @ingroup algs 303 \brief Algorithms for planarity checking, embedding and drawing 304 305 This group describes the algorithms for planarity checking, 306 embedding and drawing. 307 308 \image html planar.png 309 \image latex planar.eps "Plane graph" width=\textwidth 310 */ 311 312 /** 313 @defgroup matching Matching algorithms 314 @ingroup algs 315 \brief Algorithms for finding matchings in graphs and bipartite graphs. 316 317 This group contains algorithm objects and functions to calculate 318 matchings in graphs and bipartite graphs. The general matching problem is 319 finding a subset of the arcs which does not shares common endpoints. 320 321 There are several different algorithms for calculate matchings in 322 graphs. The matching problems in bipartite graphs are generally 323 easier than in general graphs. The goal of the matching optimization 324 can be the finding maximum cardinality, maximum weight or minimum cost 325 matching. The search can be constrained to find perfect or 326 maximum cardinality matching. 327 328 LEMON contains the next algorithms: 329 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp 330 augmenting path algorithm for calculate maximum cardinality matching in 331 bipartite graphs 332 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel 333 algorithm for calculate maximum cardinality matching in bipartite graphs 334 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching" 335 Successive shortest path algorithm for calculate maximum weighted matching 336 and maximum weighted bipartite matching in bipartite graph 337 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching" 338 Successive shortest path algorithm for calculate minimum cost maximum 339 matching in bipartite graph 340 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm 341 for calculate maximum cardinality matching in general graph 342 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom 343 shrinking algorithm for calculate maximum weighted matching in general 344 graph 345 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching" 346 Edmond's blossom shrinking algorithm for calculate maximum weighted 347 perfect matching in general graph 348 349 \image html bipartite_matching.png 350 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth 351 352 */ 353 354 /** 355 @defgroup spantree Minimum Spanning Tree algorithms 187 @defgroup spantree Minimum Spanning Tree Algorithms 356 188 @ingroup algs 357 189 \brief Algorithms for finding a minimum cost spanning tree in a graph. … … 361 193 */ 362 194 363 364 /**365 @defgroup auxalg Auxiliary algorithms366 195 @ingroup algs 367 \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 196 /** 420 197 @defgroup utils Tools and Utilities … … 442 219 443 220 /** 444 @defgroup timecount Time measuring and Counting221 @defgroup timecount Time Measuring and Counting 445 222 @ingroup misc 446 223 \brief Simple tools for measuring the performance of algorithms. … … 448 225 This group describes simple tools for measuring the performance 449 226 of algorithms. 450 */451 452 /**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 227 */ 460 228 … … 472 240 473 241 This group describes the tools for importing and exporting graphs 474 and graph related data. Now it supports the LEMON format, the 475 \c DIMACS format and the encapsulated postscript (EPS) format. 242 and graph related data. Now it supports the LEMON format 243 and the encapsulated postscript (EPS) format. 244 postscript (EPS) format. 476 245 */ 477 246 … … 479 248 @defgroup lemon_io LEMON Input-Output 480 249 @ingroup io_group 481 \brief Reading and writing \ref lgf-format "LEMON Graph Format".250 \brief Reading and writing LEMON Graph Format. 482 251 483 252 This group describes methods for reading and writing … … 486 255 487 256 /** 488 @defgroup eps_io Postscript exporting257 @defgroup eps_io Postscript Exporting 489 258 @ingroup io_group 490 259 \brief General \c EPS drawer and graph exporter … … 493 262 graph exporting tools. 494 263 */ 495 496 264 497 265 /** … … 522 290 523 291 - Finally, They can serve as a skeleton of a new implementation of a concept. 524 525 */ 526 292 */ 527 293 528 294 /** … … 535 301 */ 536 302 537 /* --- Unused group 538 @defgroup experimental Experimental Structures and Algorithms 539 This group describes some Experimental structures and algorithms. 540 The stuff here is subject to change. 541 */ 542 303 304 This group describes the skeletons and concept checking classes of maps. 543 305 /** 544 306 \anchor demoprograms … … 552 314 build the library. 553 315 */ 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.