Changes in doc/groups.dox [463:88ed40ad0d4f:318:1e2d6ca80793] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r463 r318 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 17 17 */ 18 18 19 namespace lemon {20 21 19 /** 22 20 @defgroup datas Data Structures … … 63 61 64 62 /** 65 @defgroup graph_adaptors Adaptor Classes for graphs66 @ingroup graphs67 \brief This group contains several adaptor classes for digraphs and graphs68 69 The main parts of LEMON are the different graph structures, generic70 graph algorithms, graph concepts which couple these, and graph71 adaptors. While the previous notions are more or less clear, the72 latter one needs further explanation. Graph adaptors are graph classes73 which serve for considering graph structures in different ways.74 75 A short example makes this much clearer. Suppose that we have an76 instance \c g of a directed graph type say ListDigraph and an algorithm77 \code78 template <typename Digraph>79 int algorithm(const Digraph&);80 \endcode81 is needed to run on the reverse oriented graph. It may be expensive82 (in time or in memory usage) to copy \c g with the reversed83 arcs. In this case, an adaptor class is used, which (according84 to LEMON digraph concepts) works as a digraph. The adaptor uses the85 original digraph structure and digraph operations when methods of the86 reversed oriented graph are called. This means that the adaptor have87 minor memory usage, and do not perform sophisticated algorithmic88 actions. The purpose of it is to give a tool for the cases when a89 graph have to be used in a specific alteration. If this alteration is90 obtained by a usual construction like filtering the arc-set or91 considering a new orientation, then an adaptor is worthwhile to use.92 To come back to the reverse oriented graph, in this situation93 \code94 template<typename Digraph> class ReverseDigraph;95 \endcode96 template class can be used. The code looks as follows97 \code98 ListDigraph g;99 ReverseDigraph<ListGraph> rg(g);100 int result = algorithm(rg);101 \endcode102 After running the algorithm, the original graph \c g is untouched.103 This techniques gives rise to an elegant code, and based on stable104 graph adaptors, complex algorithms can be implemented easily.105 106 In flow, circulation and bipartite matching problems, the residual107 graph is of particular importance. Combining an adaptor implementing108 this, shortest path algorithms and minimum mean cycle algorithms,109 a range of weighted and cardinality optimization algorithms can be110 obtained. For other examples, the interested user is referred to the111 detailed documentation of particular adaptors.112 113 The behavior of graph adaptors can be very different. Some of them keep114 capabilities of the original graph while in other cases this would be115 meaningless. This means that the concepts that they are models of depend116 on the graph adaptor, and the wrapped graph(s).117 If an arc of \c rg is deleted, this is carried out by deleting the118 corresponding arc of \c g, thus the adaptor modifies the original graph.119 120 But for a residual graph, this operation has no sense.121 Let us stand one more example here to simplify your work.122 RevGraphAdaptor has constructor123 \code124 ReverseDigraph(Digraph& digraph);125 \endcode126 This means that in a situation, when a <tt>const ListDigraph&</tt>127 reference to a graph is given, then it have to be instantiated with128 <tt>Digraph=const ListDigraph</tt>.129 \code130 int algorithm1(const ListDigraph& g) {131 RevGraphAdaptor<const ListDigraph> rg(g);132 return algorithm2(rg);133 }134 \endcode135 */136 137 /**138 63 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs 139 64 @ingroup graphs … … 164 89 165 90 This group describes maps that are specifically designed to assign 166 values to the nodes and arcs/edges of graphs. 167 168 If you are looking for the standard graph maps (\c NodeMap, \c ArcMap, 169 \c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts". 91 values to the nodes and arcs of graphs. 170 92 */ 171 93 … … 178 100 maps from other maps. 179 101 180 Most of them are \ref concepts::ReadMap "read-only maps".102 Most of them are \ref lemon::concepts::ReadMap "read-only maps". 181 103 They can make arithmetic and logical operations between one or two maps 182 104 (negation, shifting, addition, multiplication, logical 'and', 'or', … … 280 202 \brief Common graph search algorithms. 281 203 282 This group describes the common graph search algorithms , namely283 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).204 This group describes the common graph search algorithms like 205 Breadth-First Search (BFS) and Depth-First Search (DFS). 284 206 */ 285 207 … … 289 211 \brief Algorithms for finding shortest paths. 290 212 291 This group describes the algorithms for finding shortest paths in digraphs. 292 293 - \ref Dijkstra algorithm for finding shortest paths from a source node 294 when all arc lengths are non-negative. 295 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths 296 from a source node when arc lenghts can be either positive or negative, 297 but the digraph should not contain directed cycles with negative total 298 length. 299 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms 300 for solving the \e all-pairs \e shortest \e paths \e problem when arc 301 lenghts can be either positive or negative, but the digraph should 302 not contain directed cycles with negative total length. 303 - \ref Suurballe A successive shortest path algorithm for finding 304 arc-disjoint paths between two nodes having minimum total length. 213 This group describes the algorithms for finding shortest paths in graphs. 305 214 */ 306 215 … … 313 222 feasible circulations. 314 223 315 The \e maximum \e flow \e problem is to find a flow of maximum value between 316 a single source and a single target. Formally, there is a \f$G=(V,A)\f$ 317 digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and 318 \f$s, t \in V\f$ source and target nodes. 319 A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the 320 following optimization problem. 321 322 \f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f] 323 \f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a) 324 \qquad \forall v\in V\setminus\{s,t\} \f] 325 \f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f] 224 The maximum flow problem is to find a flow between a single source and 225 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$ capacity 227 function and given \f$s, t \in V\f$ source and target node. The 228 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] 326 234 327 235 LEMON contains several algorithms for solving maximum flow problems: 328 - \ref EdmondsKarp Edmonds-Karp algorithm.329 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.330 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.331 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.332 333 In most cases the \ref Preflow "Preflow" algorithm provides the334 fastest method for computing a maximum flow. All implementations335 provides functions to also query the minimum cut, which is the dual336 pro blem of the maximum flow.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 the 242 fastest method to compute the maximum flow. All impelementations 243 provides functions to query the minimum cut, which is the dual linear 244 programming problem of the maximum flow. 337 245 */ 338 246 … … 345 253 This group describes the algorithms for finding minimum cost flows and 346 254 circulations. 347 348 The \e minimum \e cost \e flow \e problem is to find a feasible flow of349 minimum total cost from a set of supply nodes to a set of demand nodes350 in a network with capacity constraints and arc costs.351 Formally, let \f$G=(V,A)\f$ be a digraph,352 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and353 upper bounds for the flow values on the arcs,354 \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow355 on the arcs, and356 \f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values357 of the nodes.358 A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of359 the following optimization problem.360 361 \f[ \min\sum_{a\in A} f(a) cost(a) \f]362 \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =363 supply(v) \qquad \forall v\in V \f]364 \f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]365 366 LEMON contains several algorithms for solving minimum cost flow problems:367 - \ref CycleCanceling Cycle-canceling algorithms.368 - \ref CapacityScaling Successive shortest path algorithm with optional369 capacity scaling.370 - \ref CostScaling Push-relabel and augment-relabel algorithms based on371 cost scaling.372 - \ref NetworkSimplex Primal network simplex algorithm with various373 pivot strategies.374 255 */ 375 256 … … 382 263 This group describes the algorithms for finding minimum cut in graphs. 383 264 384 The \e minimum \e cut \eproblem is to find a non-empty and non-complete385 \f$X\f$ subset of the nodes with minimum overall capacity on386 outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a387 \f$c ap:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum265 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 388 269 cut is the \f$X\f$ solution of the next optimization problem: 389 270 390 271 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} 391 \sum_{uv\in A, u\in X, v\not\in X}cap(uv)\f]272 \sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f] 392 273 393 274 LEMON contains several algorithms related to minimum cut problems: 394 275 395 - \ref HaoOrlin "Hao-Orlin algorithm" for calculatingminimum cut396 in directed graphs .397 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for398 calculat ing minimum cut in undirected graphs.399 - \ref GomoryHuTree "Gomory-Hu tree computation" for calculating400 all-pairs minimum cut in undirected graphs.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 401 282 402 283 If you want to find minimum cut just between two distinict nodes, 403 see the \ref max_flow "maximum flow problem".284 please see the \ref max_flow "Maximum Flow page". 404 285 */ 405 286 … … 440 321 graphs. The matching problems in bipartite graphs are generally 441 322 easier than in general graphs. The goal of the matching optimization 442 can be finding maximum cardinality, maximum weight or minimum cost323 can be the finding maximum cardinality, maximum weight or minimum cost 443 324 matching. The search can be constrained to find perfect or 444 325 maximum cardinality matching. 445 326 446 The matching algorithms implemented in LEMON: 447 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm 448 for calculating maximum cardinality matching in bipartite graphs. 449 - \ref PrBipartiteMatching Push-relabel algorithm 450 for calculating maximum cardinality matching in bipartite graphs. 451 - \ref MaxWeightedBipartiteMatching 452 Successive shortest path algorithm for calculating maximum weighted 453 matching and maximum weighted bipartite matching in bipartite graphs. 454 - \ref MinCostMaxBipartiteMatching 455 Successive shortest path algorithm for calculating minimum cost maximum 456 matching in bipartite graphs. 457 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating 458 maximum cardinality matching in general graphs. 459 - \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating 460 maximum weighted matching in general graphs. 461 - \ref MaxWeightedPerfectMatching 462 Edmond's blossom shrinking algorithm for calculating maximum weighted 463 perfect matching in general graphs. 327 LEMON contains the next algorithms: 328 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp 329 augmenting path algorithm for calculate maximum cardinality matching in 330 bipartite graphs 331 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel 332 algorithm for calculate maximum cardinality matching in bipartite graphs 333 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching" 334 Successive shortest path algorithm for calculate maximum weighted matching 335 and maximum weighted bipartite matching in bipartite graph 336 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching" 337 Successive shortest path algorithm for calculate minimum cost maximum 338 matching in bipartite graph 339 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm 340 for calculate maximum cardinality matching in general graph 341 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom 342 shrinking algorithm for calculate maximum weighted matching in general 343 graph 344 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching" 345 Edmond's blossom shrinking algorithm for calculate maximum weighted 346 perfect matching in general graph 464 347 465 348 \image html bipartite_matching.png … … 473 356 474 357 This group describes the algorithms for finding a minimum cost spanning 475 tree in a graph .358 tree in a graph 476 359 */ 477 360 … … 582 465 583 466 /** 584 @defgroup lemon_io LEMON Graph Format467 @defgroup lemon_io LEMON Input-Output 585 468 @ingroup io_group 586 469 \brief Reading and writing LEMON Graph Format. … … 597 480 This group describes general \c EPS drawing methods and special 598 481 graph exporting tools. 599 */600 601 /**602 @defgroup dimacs_group DIMACS format603 @ingroup io_group604 \brief Read and write files in DIMACS format605 606 Tools to read a digraph from or write it to a file in DIMACS format data.607 */608 609 /**610 @defgroup nauty_group NAUTY Format611 @ingroup io_group612 \brief Read \e Nauty format613 614 Tool to read graphs from \e Nauty format data.615 482 */ 616 483 … … 664 531 \anchor demoprograms 665 532 666 @defgroup demos Demo Programs533 @defgroup demos Demo programs 667 534 668 535 Some demo programs are listed here. Their full source codes can be found in … … 674 541 675 542 /** 676 @defgroup tools Standalone Utility Applications543 @defgroup tools Standalone utility applications 677 544 678 545 Some utility applications are listed here. … … 682 549 */ 683 550 684 }
Note: See TracChangeset
for help on using the changeset viewer.