lemon-1.1: comparison doc/groups.dox

equal deleted inserted replaced

-:b9d685ecc24f
+:1a4b0b76efe6
-/* -*- C++ -*-
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
-* This file is a part of LEMON, a generic C++ optimization library
+* This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2008
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 /**
 @defgroup graphs Graph Structures
 @ingroup datas
 \brief Graph structures implemented in LEMON.
 The implementation of combinatorial algorithms heavily relies on
 efficient graph implementations. LEMON offers data structures which are
 planned to be easily used in an experimental phase of implementation studies,
 and thereafter the program code can be made efficient by small modifications.
 The most efficient implementation of diverse applications require the
 usage of different physical graph implementations. These differences
 appear in the size of graph we require to handle, memory or time usage
 limitations or in the set of operations through which the graph can be
 accessed.  LEMON provides several physical graph structures to meet
 the diverging requirements of the possible users.  In order to save on
 running time or on memory usage, some structures may fail to provide
 some graph features like arc/edge or node deletion.
 Alteration of standard containers need a very limited number of
 operations, these together satisfy the everyday requirements.
 In the case of graph structures, different operations are needed which do
 not alter the physical graph, but gives another view. If some nodes or
 arcs have to be hidden or the reverse oriented graph have to be used, then
 this is the case. It also may happen that in a flow implementation
 the residual graph can be accessed by another algorithm, or a node-set
 is to be shrunk for another algorithm.
 LEMON also provides a variety of graphs for these requirements called
 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
 in conjunction with other graph representations.
 You are free to use the graph structure that fit your requirements
 the best, most graph algorithms and auxiliary data structures can be used
 with any graph structures.
 */
 /**
 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs
 @ingroup graphs
 \brief Graph types between real graphs and graph adaptors.
 This group describes some graph types between real graphs and graph adaptors.
 These classes wrap graphs to give new functionality as the adaptors do it.
 On the other hand they are not light-weight structures as the adaptors.
 */
 /**
 @defgroup maps Maps
 @ingroup datas
 \brief Map structures implemented in LEMON.
 This group describes the map structures implemented in LEMON.
 LEMON provides several special purpose maps that e.g. combine
 new maps from existing ones.
 */
 /**
 @defgroup graph_maps Graph Maps
 @ingroup maps
 \brief Special graph-related maps.
 This group describes maps that are specifically designed to assign
 values to the nodes and arcs of graphs.
 return Color(1.0, 0.5, 1.0);
 } else {
 return Color(0.0, 0.0, 0.0);
 }
 }
 Digraph::NodeMap<int> degree_map(graph);
 digraphToEps(graph, "graph.eps")
 .coords(coords).scaleToA4().undirected()
 .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
 .run();
 \endcode
 The \c functorToMap() function makes an \c int to \c Color map from the
 \e nodeColor() function. The \c composeMap() compose the \e degree_map
 and the previously created map. The composed map is a proper function to
 get the color of each node.
 DoubleArcMap length(graph);
 DoubleArcMap speed(graph);
 typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
 TimeMap time(length, speed);
 Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
 dijkstra.run(source, target);
 \endcode
 We have a length map and a maximum speed map on the arcs of a digraph.
 The minimum time to pass the arc can be calculated as the division of
 class. We use the implicit minimum time map as the length map of the
 \c Dijkstra algorithm.
 */
 /**
 @defgroup matrices Matrices
 @ingroup datas
 \brief Two dimensional data storages implemented in LEMON.
 This group describes two dimensional data storages implemented in LEMON.
 */
 /**
 @defgroup search Graph Search
 @ingroup algs
 \brief Common graph search algorithms.
 This group describes the common graph search algorithms like
 Breadth-first search (Bfs) and Depth-first search (Dfs).
 */
 /**
 @defgroup shortest_path Shortest Path algorithms
 \brief Algorithms for finding shortest paths.
 This group describes the algorithms for finding shortest paths in graphs.
 */
 /**
 @defgroup max_flow Maximum Flow algorithms
 @ingroup algs
 \brief Algorithms for finding maximum flows.
 This group describes the algorithms for finding maximum flows and
 feasible circulations.
 \f[ 0 \le f_a \le c_a \f]
 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \qquad \forall u \in V \setminus \{s,t\}\f]
 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
 LEMON contains several algorithms for solving maximum flow problems:
 - \ref lemon::EdmondsKarp "Edmonds-Karp"
 - \ref lemon::Preflow "Goldberg's Preflow algorithm"
 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
 @ingroup algs
 \brief Algorithms for finding minimum cost flows and circulations.
 This group describes the algorithms for finding minimum cost flows and
 circulations.
 */
 /**
 @defgroup min_cut Minimum Cut algorithms
 @ingroup algs
 \brief Algorithms for finding minimum cut in graphs.
 This group describes the algorithms for finding minimum cut in graphs.
 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
 LEMON contains several algorithms related to minimum cut problems:
 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
 in directed graphs
 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
 calculate minimum cut in undirected graphs
 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
 pairs minimum cut in undirected graphs
 \image html planar.png
 \image latex planar.eps "Plane graph" width=\textwidth
 */
 /**
 @defgroup matching Matching algorithms
 @ingroup algs
 \brief Algorithms for finding matchings in graphs and bipartite graphs.
 This group contains algorithm objects and functions to calculate
 matchings in graphs and bipartite graphs. The general matching problem is
 finding a subset of the arcs which does not shares common endpoints.
 There are several different algorithms for calculate matchings in
 graphs.  The matching problems in bipartite graphs are generally
 easier than in general graphs. The goal of the matching optimization
 can be the finding maximum cardinality, maximum weight or minimum cost
 matching. The search can be constrained to find perfect or
 maximum cardinality matching.
 Lemon contains the next algorithms:
 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
 augmenting path algorithm for calculate maximum cardinality matching in
 bipartite graphs
 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
 algorithm for calculate maximum cardinality matching in bipartite graphs
 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
 Successive shortest path algorithm for calculate maximum weighted matching
 and maximum weighted bipartite matching in bipartite graph
 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
 Successive shortest path algorithm for calculate minimum cost maximum
 matching in bipartite graph
 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
 for calculate maximum cardinality matching in general graph
 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
 shrinking algorithm for calculate maximum weighted matching in general
 various LP solvers could be used in the same manner with this
 interface.
 */
 /**
 @defgroup lp_utils Tools for Lp and Mip solvers
 @ingroup lp_group
 \brief Helper tools to the Lp and Mip solvers.
 This group adds some helper tools to general optimization framework
 implemented in LEMON.
 This group describes some metaheuristic optimization tools.
 */
 /**
 @defgroup utils Tools and Utilities
 \brief Tools and utilities for programming in LEMON
 Tools and utilities for programming in LEMON.
 */
 /**
 @defgroup io_group Input-Output
 \brief Graph Input-Output methods
 This group describes the tools for importing and exporting graphs
 and graph related data. Now it supports the LEMON format, the
 \c DIMACS format and the encapsulated postscript (EPS) format.
 */
 /**
 @defgroup eps_io Postscript exporting
 @ingroup io_group
 \brief General \c EPS drawer and graph exporter
 This group describes general \c EPS drawing methods and special
 graph exporting tools.
 */
 /**
 @defgroup concept Concepts
 This group describes the data/algorithm skeletons and concept checking
 classes implemented in LEMON.
 The purpose of the classes in this group is fourfold.
 - These classes contain the documentations of the concepts. In order
 to avoid document multiplications, an implementation of a concept
 simply refers to the corresponding concept class.
 - These classes declare every functions, <tt>typedef</tt>s etc. an
 */
 /**
 @defgroup tools Standalone utility applications
 Some utility applications are listed here.
 The standard compilation procedure (<tt>./configure;make</tt>) will compile
 them, as well.
 */

changeset 209	765619b7cbb2
parent 192	7bf5f97d574f
child 210	81cfc04531e8