alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@40:  *
alpar@209:  * This file is a part of LEMON, a generic C++ optimization library.
alpar@40:  *
alpar@1092:  * Copyright (C) 2003-2013
alpar@40:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@40:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@40:  *
alpar@40:  * Permission to use, modify and distribute this software is granted
alpar@40:  * provided that this copyright notice appears in all copies. For
alpar@40:  * precise terms see the accompanying LICENSE file.
alpar@40:  *
alpar@40:  * This software is provided "AS IS" with no warranty of any kind,
alpar@40:  * express or implied, and with no claim as to its suitability for any
alpar@40:  * purpose.
alpar@40:  *
alpar@40:  */
alpar@40: 
kpeter@406: namespace lemon {
kpeter@406: 
alpar@40: /**
alpar@40: @defgroup datas Data Structures
kpeter@559: This group contains the several data structures implemented in LEMON.
alpar@40: */
alpar@40: 
alpar@40: /**
alpar@40: @defgroup graphs Graph Structures
alpar@40: @ingroup datas
alpar@40: \brief Graph structures implemented in LEMON.
alpar@40: 
alpar@209: The implementation of combinatorial algorithms heavily relies on
alpar@209: efficient graph implementations. LEMON offers data structures which are
alpar@209: planned to be easily used in an experimental phase of implementation studies,
alpar@209: and thereafter the program code can be made efficient by small modifications.
alpar@40: 
alpar@40: The most efficient implementation of diverse applications require the
alpar@40: usage of different physical graph implementations. These differences
alpar@40: appear in the size of graph we require to handle, memory or time usage
alpar@40: limitations or in the set of operations through which the graph can be
alpar@40: accessed.  LEMON provides several physical graph structures to meet
alpar@40: the diverging requirements of the possible users.  In order to save on
alpar@40: running time or on memory usage, some structures may fail to provide
kpeter@83: some graph features like arc/edge or node deletion.
alpar@40: 
alpar@209: Alteration of standard containers need a very limited number of
alpar@209: operations, these together satisfy the everyday requirements.
alpar@209: In the case of graph structures, different operations are needed which do
alpar@209: not alter the physical graph, but gives another view. If some nodes or
kpeter@83: arcs have to be hidden or the reverse oriented graph have to be used, then
alpar@209: this is the case. It also may happen that in a flow implementation
alpar@209: the residual graph can be accessed by another algorithm, or a node-set
alpar@209: is to be shrunk for another algorithm.
alpar@209: LEMON also provides a variety of graphs for these requirements called
alpar@209: \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
alpar@209: in conjunction with other graph representations.
alpar@40: 
alpar@40: You are free to use the graph structure that fit your requirements
alpar@40: the best, most graph algorithms and auxiliary data structures can be used
kpeter@314: with any graph structure.
kpeter@314: 
kpeter@314: <b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
alpar@40: */
alpar@40: 
alpar@40: /**
kpeter@451: @defgroup graph_adaptors Adaptor Classes for Graphs
deba@416: @ingroup graphs
kpeter@451: \brief Adaptor classes for digraphs and graphs
kpeter@451: 
kpeter@451: This group contains several useful adaptor classes for digraphs and graphs.
deba@416: 
deba@416: The main parts of LEMON are the different graph structures, generic
kpeter@451: graph algorithms, graph concepts, which couple them, and graph
deba@416: adaptors. While the previous notions are more or less clear, the
deba@416: latter one needs further explanation. Graph adaptors are graph classes
deba@416: which serve for considering graph structures in different ways.
deba@416: 
deba@416: A short example makes this much clearer.  Suppose that we have an
kpeter@451: instance \c g of a directed graph type, say ListDigraph and an algorithm
deba@416: \code
deba@416: template <typename Digraph>
deba@416: int algorithm(const Digraph&);
deba@416: \endcode
deba@416: is needed to run on the reverse oriented graph.  It may be expensive
deba@416: (in time or in memory usage) to copy \c g with the reversed
deba@416: arcs.  In this case, an adaptor class is used, which (according
kpeter@451: to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
kpeter@451: The adaptor uses the original digraph structure and digraph operations when
kpeter@451: methods of the reversed oriented graph are called.  This means that the adaptor
kpeter@451: have minor memory usage, and do not perform sophisticated algorithmic
deba@416: actions.  The purpose of it is to give a tool for the cases when a
deba@416: graph have to be used in a specific alteration.  If this alteration is
kpeter@451: obtained by a usual construction like filtering the node or the arc set or
deba@416: considering a new orientation, then an adaptor is worthwhile to use.
deba@416: To come back to the reverse oriented graph, in this situation
deba@416: \code
deba@416: template<typename Digraph> class ReverseDigraph;
deba@416: \endcode
deba@416: template class can be used. The code looks as follows
deba@416: \code
deba@416: ListDigraph g;
kpeter@451: ReverseDigraph<ListDigraph> rg(g);
deba@416: int result = algorithm(rg);
deba@416: \endcode
kpeter@451: During running the algorithm, the original digraph \c g is untouched.
kpeter@451: This techniques give rise to an elegant code, and based on stable
deba@416: graph adaptors, complex algorithms can be implemented easily.
deba@416: 
kpeter@451: In flow, circulation and matching problems, the residual
deba@416: graph is of particular importance. Combining an adaptor implementing
kpeter@451: this with shortest path algorithms or minimum mean cycle algorithms,
deba@416: a range of weighted and cardinality optimization algorithms can be
deba@416: obtained. For other examples, the interested user is referred to the
deba@416: detailed documentation of particular adaptors.
deba@416: 
kpeter@1050: Since the adaptor classes conform to the \ref graph_concepts "graph concepts",
kpeter@1050: an adaptor can even be applied to another one.
kpeter@1050: The following image illustrates a situation when a \ref SubDigraph adaptor
kpeter@1050: is applied on a digraph and \ref Undirector is applied on the subgraph.
kpeter@1050: 
kpeter@1050: \image html adaptors2.png
kpeter@1050: \image latex adaptors2.eps "Using graph adaptors" width=\textwidth
kpeter@1050: 
deba@416: The behavior of graph adaptors can be very different. Some of them keep
deba@416: capabilities of the original graph while in other cases this would be
kpeter@451: meaningless. This means that the concepts that they meet depend
kpeter@451: on the graph adaptor, and the wrapped graph.
kpeter@451: For example, if an arc of a reversed digraph is deleted, this is carried
kpeter@451: out by deleting the corresponding arc of the original digraph, thus the
kpeter@451: adaptor modifies the original digraph.
kpeter@451: However in case of a residual digraph, this operation has no sense.
deba@416: 
deba@416: Let us stand one more example here to simplify your work.
kpeter@451: ReverseDigraph has constructor
deba@416: \code
deba@416: ReverseDigraph(Digraph& digraph);
deba@416: \endcode
kpeter@451: This means that in a situation, when a <tt>const %ListDigraph&</tt>
deba@416: reference to a graph is given, then it have to be instantiated with
kpeter@451: <tt>Digraph=const %ListDigraph</tt>.
deba@416: \code
deba@416: int algorithm1(const ListDigraph& g) {
kpeter@451:   ReverseDigraph<const ListDigraph> rg(g);
deba@416:   return algorithm2(rg);
deba@416: }
deba@416: \endcode
deba@416: */
deba@416: 
deba@416: /**
alpar@209: @defgroup maps Maps
alpar@40: @ingroup datas
kpeter@50: \brief Map structures implemented in LEMON.
alpar@40: 
kpeter@559: This group contains the map structures implemented in LEMON.
kpeter@50: 
kpeter@314: LEMON provides several special purpose maps and map adaptors that e.g. combine
alpar@40: new maps from existing ones.
kpeter@314: 
kpeter@314: <b>See also:</b> \ref map_concepts "Map Concepts".
alpar@40: */
alpar@40: 
alpar@40: /**
alpar@209: @defgroup graph_maps Graph Maps
alpar@40: @ingroup maps
kpeter@83: \brief Special graph-related maps.
alpar@40: 
kpeter@559: This group contains maps that are specifically designed to assign
kpeter@406: values to the nodes and arcs/edges of graphs.
kpeter@406: 
kpeter@406: If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
kpeter@406: \c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
alpar@40: */
alpar@40: 
alpar@40: /**
alpar@40: \defgroup map_adaptors Map Adaptors
alpar@40: \ingroup maps
alpar@40: \brief Tools to create new maps from existing ones
alpar@40: 
kpeter@559: This group contains map adaptors that are used to create "implicit"
kpeter@50: maps from other maps.
alpar@40: 
kpeter@406: Most of them are \ref concepts::ReadMap "read-only maps".
kpeter@83: They can make arithmetic and logical operations between one or two maps
kpeter@83: (negation, shifting, addition, multiplication, logical 'and', 'or',
kpeter@83: 'not' etc.) or e.g. convert a map to another one of different Value type.
alpar@40: 
kpeter@50: The typical usage of this classes is passing implicit maps to
alpar@40: algorithms.  If a function type algorithm is called then the function
alpar@40: type map adaptors can be used comfortable. For example let's see the
kpeter@314: usage of map adaptors with the \c graphToEps() function.
alpar@40: \code
alpar@40:   Color nodeColor(int deg) {
alpar@40:     if (deg >= 2) {
alpar@40:       return Color(0.5, 0.0, 0.5);
alpar@40:     } else if (deg == 1) {
alpar@40:       return Color(1.0, 0.5, 1.0);
alpar@40:     } else {
alpar@40:       return Color(0.0, 0.0, 0.0);
alpar@40:     }
alpar@40:   }
alpar@209: 
kpeter@83:   Digraph::NodeMap<int> degree_map(graph);
alpar@209: 
kpeter@314:   graphToEps(graph, "graph.eps")
alpar@40:     .coords(coords).scaleToA4().undirected()
kpeter@83:     .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
alpar@40:     .run();
alpar@209: \endcode
kpeter@83: The \c functorToMap() function makes an \c int to \c Color map from the
kpeter@314: \c nodeColor() function. The \c composeMap() compose the \c degree_map
kpeter@83: and the previously created map. The composed map is a proper function to
kpeter@83: get the color of each node.
alpar@40: 
alpar@40: The usage with class type algorithms is little bit harder. In this
alpar@40: case the function type map adaptors can not be used, because the
kpeter@50: function map adaptors give back temporary objects.
alpar@40: \code
kpeter@83:   Digraph graph;
kpeter@83: 
kpeter@83:   typedef Digraph::ArcMap<double> DoubleArcMap;
kpeter@83:   DoubleArcMap length(graph);
kpeter@83:   DoubleArcMap speed(graph);
kpeter@83: 
kpeter@83:   typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
alpar@40:   TimeMap time(length, speed);
alpar@209: 
kpeter@83:   Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
alpar@40:   dijkstra.run(source, target);
alpar@40: \endcode
kpeter@83: We have a length map and a maximum speed map on the arcs of a digraph.
kpeter@83: The minimum time to pass the arc can be calculated as the division of
kpeter@83: the two maps which can be done implicitly with the \c DivMap template
alpar@40: class. We use the implicit minimum time map as the length map of the
alpar@40: \c Dijkstra algorithm.
alpar@40: */
alpar@40: 
alpar@40: /**
alpar@40: @defgroup paths Path Structures
alpar@40: @ingroup datas
kpeter@318: \brief %Path structures implemented in LEMON.
alpar@40: 
kpeter@559: This group contains the path structures implemented in LEMON.
alpar@40: 
kpeter@50: LEMON provides flexible data structures to work with paths.
kpeter@50: All of them have similar interfaces and they can be copied easily with
kpeter@50: assignment operators and copy constructors. This makes it easy and
alpar@40: efficient to have e.g. the Dijkstra algorithm to store its result in
alpar@40: any kind of path structure.
alpar@40: 
kpeter@710: \sa \ref concepts::Path "Path concept"
kpeter@710: */
kpeter@710: 
kpeter@710: /**
kpeter@710: @defgroup heaps Heap Structures
kpeter@710: @ingroup datas
kpeter@710: \brief %Heap structures implemented in LEMON.
kpeter@710: 
kpeter@710: This group contains the heap structures implemented in LEMON.
kpeter@710: 
kpeter@710: LEMON provides several heap classes. They are efficient implementations
kpeter@710: of the abstract data type \e priority \e queue. They store items with
kpeter@710: specified values called \e priorities in such a way that finding and
kpeter@710: removing the item with minimum priority are efficient.
kpeter@710: The basic operations are adding and erasing items, changing the priority
kpeter@710: of an item, etc.
kpeter@710: 
kpeter@710: Heaps are crucial in several algorithms, such as Dijkstra and Prim.
kpeter@710: The heap implementations have the same interface, thus any of them can be
kpeter@710: used easily in such algorithms.
kpeter@710: 
kpeter@710: \sa \ref concepts::Heap "Heap concept"
kpeter@710: */
kpeter@710: 
kpeter@710: /**
alpar@40: @defgroup auxdat Auxiliary Data Structures
alpar@40: @ingroup datas
kpeter@50: \brief Auxiliary data structures implemented in LEMON.
alpar@40: 
kpeter@559: This group contains some data structures implemented in LEMON in
alpar@40: order to make it easier to implement combinatorial algorithms.
alpar@40: */
alpar@40: 
alpar@40: /**
kpeter@714: @defgroup geomdat Geometric Data Structures
kpeter@714: @ingroup auxdat
kpeter@714: \brief Geometric data structures implemented in LEMON.
kpeter@714: 
kpeter@714: This group contains geometric data structures implemented in LEMON.
kpeter@714: 
kpeter@714:  - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
kpeter@714:    vector with the usual operations.
kpeter@714:  - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
kpeter@714:    rectangular bounding box of a set of \ref lemon::dim2::Point
kpeter@714:    "dim2::Point"'s.
kpeter@714: */
kpeter@714: 
kpeter@714: /**
kpeter@714: @defgroup matrices Matrices
kpeter@714: @ingroup auxdat
kpeter@714: \brief Two dimensional data storages implemented in LEMON.
kpeter@714: 
kpeter@714: This group contains two dimensional data storages implemented in LEMON.
kpeter@714: */
kpeter@714: 
kpeter@714: /**
alpar@40: @defgroup algs Algorithms
kpeter@559: \brief This group contains the several algorithms
alpar@40: implemented in LEMON.
alpar@40: 
kpeter@559: This group contains the several algorithms
alpar@40: implemented in LEMON.
alpar@40: */
alpar@40: 
alpar@40: /**
alpar@40: @defgroup search Graph Search
alpar@40: @ingroup algs
kpeter@50: \brief Common graph search algorithms.
alpar@40: 
kpeter@559: This group contains the common graph search algorithms, namely
kpeter@755: \e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
alpar@1053: \cite clrs01algorithms.
alpar@40: */
alpar@40: 
alpar@40: /**
kpeter@314: @defgroup shortest_path Shortest Path Algorithms
alpar@40: @ingroup algs
kpeter@50: \brief Algorithms for finding shortest paths.
alpar@40: 
kpeter@755: This group contains the algorithms for finding shortest paths in digraphs
alpar@1053: \cite clrs01algorithms.
kpeter@406: 
kpeter@406:  - \ref Dijkstra algorithm for finding shortest paths from a source node
kpeter@406:    when all arc lengths are non-negative.
kpeter@406:  - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
kpeter@406:    from a source node when arc lenghts can be either positive or negative,
kpeter@406:    but the digraph should not contain directed cycles with negative total
kpeter@406:    length.
kpeter@406:  - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
kpeter@406:    for solving the \e all-pairs \e shortest \e paths \e problem when arc
kpeter@406:    lenghts can be either positive or negative, but the digraph should
kpeter@406:    not contain directed cycles with negative total length.
kpeter@406:  - \ref Suurballe A successive shortest path algorithm for finding
kpeter@406:    arc-disjoint paths between two nodes having minimum total length.
alpar@40: */
alpar@40: 
alpar@209: /**
kpeter@714: @defgroup spantree Minimum Spanning Tree Algorithms
kpeter@714: @ingroup algs
kpeter@714: \brief Algorithms for finding minimum cost spanning trees and arborescences.
kpeter@714: 
kpeter@714: This group contains the algorithms for finding minimum cost spanning
alpar@1053: trees and arborescences \cite clrs01algorithms.
kpeter@714: */
kpeter@714: 
kpeter@714: /**
kpeter@314: @defgroup max_flow Maximum Flow Algorithms
alpar@209: @ingroup algs
kpeter@50: \brief Algorithms for finding maximum flows.
alpar@40: 
kpeter@559: This group contains the algorithms for finding maximum flows and
alpar@1053: feasible circulations \cite clrs01algorithms, \cite amo93networkflows.
alpar@40: 
kpeter@406: The \e maximum \e flow \e problem is to find a flow of maximum value between
kpeter@406: a single source and a single target. Formally, there is a \f$G=(V,A)\f$
kpeter@609: digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
kpeter@406: \f$s, t \in V\f$ source and target nodes.
kpeter@609: A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
kpeter@406: following optimization problem.
alpar@40: 
kpeter@609: \f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
kpeter@609: \f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
kpeter@609:     \quad \forall u\in V\setminus\{s,t\} \f]
kpeter@609: \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
alpar@40: 
kpeter@50: LEMON contains several algorithms for solving maximum flow problems:
kpeter@755: - \ref EdmondsKarp Edmonds-Karp algorithm
alpar@1053:   \cite edmondskarp72theoretical.
kpeter@755: - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
alpar@1053:   \cite goldberg88newapproach.
kpeter@755: - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
alpar@1053:   \cite dinic70algorithm, \cite sleator83dynamic.
kpeter@755: - \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
alpar@1053:   \cite goldberg88newapproach, \cite sleator83dynamic.
alpar@40: 
kpeter@755: In most cases the \ref Preflow algorithm provides the
kpeter@406: fastest method for computing a maximum flow. All implementations
kpeter@651: also provide functions to query the minimum cut, which is the dual
kpeter@651: problem of maximum flow.
kpeter@651: 
deba@869: \ref Circulation is a preflow push-relabel algorithm implemented directly
kpeter@651: for finding feasible circulations, which is a somewhat different problem,
kpeter@651: but it is strongly related to maximum flow.
kpeter@651: For more information, see \ref Circulation.
alpar@40: */
alpar@40: 
alpar@40: /**
kpeter@663: @defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
alpar@40: @ingroup algs
alpar@40: 
kpeter@50: \brief Algorithms for finding minimum cost flows and circulations.
alpar@40: 
kpeter@609: This group contains the algorithms for finding minimum cost flows and
alpar@1053: circulations \cite amo93networkflows. For more information about this
kpeter@1049: problem and its dual solution, see: \ref min_cost_flow
kpeter@755: "Minimum Cost Flow Problem".
kpeter@406: 
kpeter@663: LEMON contains several algorithms for this problem.
kpeter@609:  - \ref NetworkSimplex Primal Network Simplex algorithm with various
alpar@1053:    pivot strategies \cite dantzig63linearprog, \cite kellyoneill91netsimplex.
kpeter@813:  - \ref CostScaling Cost Scaling algorithm based on push/augment and
alpar@1053:    relabel operations \cite goldberg90approximation, \cite goldberg97efficient,
alpar@1053:    \cite bunnagel98efficient.
kpeter@813:  - \ref CapacityScaling Capacity Scaling algorithm based on the successive
alpar@1053:    shortest path method \cite edmondskarp72theoretical.
kpeter@813:  - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
alpar@1053:    strongly polynomial \cite klein67primal, \cite goldberg89cyclecanceling.
kpeter@609: 
kpeter@919: In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
kpeter@1003: implementations.
kpeter@1003: \ref NetworkSimplex is usually the fastest on relatively small graphs (up to
kpeter@1003: several thousands of nodes) and on dense graphs, while \ref CostScaling is
kpeter@1003: typically more efficient on large graphs (e.g. hundreds of thousands of
kpeter@1003: nodes or above), especially if they are sparse.
kpeter@1003: However, other algorithms could be faster in special cases.
kpeter@609: For example, if the total supply and/or capacities are rather small,
alpar@1093: \ref CapacityScaling is usually the fastest algorithm
alpar@1093: (without effective scaling).
kpeter@1002: 
kpeter@1002: These classes are intended to be used with integer-valued input data
kpeter@1002: (capacities, supply values, and costs), except for \ref CapacityScaling,
kpeter@1002: which is capable of handling real-valued arc costs (other numerical
kpeter@1002: data are required to be integer).
kpeter@1051: 
alpar@1092: For more details about these implementations and for a comprehensive
alpar@1053: experimental study, see the paper \cite KiralyKovacs12MCF.
kpeter@1051: It also compares these codes to other publicly available
kpeter@1051: minimum cost flow solvers.
alpar@40: */
alpar@40: 
alpar@40: /**
kpeter@314: @defgroup min_cut Minimum Cut Algorithms
alpar@209: @ingroup algs
alpar@40: 
kpeter@50: \brief Algorithms for finding minimum cut in graphs.
alpar@40: 
kpeter@559: This group contains the algorithms for finding minimum cut in graphs.
alpar@40: 
kpeter@406: The \e minimum \e cut \e problem is to find a non-empty and non-complete
kpeter@406: \f$X\f$ subset of the nodes with minimum overall capacity on
kpeter@406: outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
kpeter@406: \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
kpeter@50: cut is the \f$X\f$ solution of the next optimization problem:
alpar@40: 
alpar@210: \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
kpeter@713:     \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
alpar@40: 
kpeter@50: LEMON contains several algorithms related to minimum cut problems:
alpar@40: 
kpeter@406: - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
kpeter@406:   in directed graphs.
kpeter@406: - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
kpeter@406:   calculating minimum cut in undirected graphs.
kpeter@559: - \ref GomoryHu "Gomory-Hu tree computation" for calculating
kpeter@406:   all-pairs minimum cut in undirected graphs.
alpar@40: 
alpar@40: If you want to find minimum cut just between two distinict nodes,
kpeter@406: see the \ref max_flow "maximum flow problem".
alpar@40: */
alpar@40: 
alpar@40: /**
kpeter@768: @defgroup min_mean_cycle Minimum Mean Cycle Algorithms
alpar@40: @ingroup algs
kpeter@768: \brief Algorithms for finding minimum mean cycles.
alpar@40: 
kpeter@771: This group contains the algorithms for finding minimum mean cycles
alpar@1053: \cite amo93networkflows, \cite karp78characterization.
alpar@40: 
kpeter@768: The \e minimum \e mean \e cycle \e problem is to find a directed cycle
kpeter@768: of minimum mean length (cost) in a digraph.
kpeter@768: The mean length of a cycle is the average length of its arcs, i.e. the
kpeter@768: ratio between the total length of the cycle and the number of arcs on it.
alpar@40: 
kpeter@768: This problem has an important connection to \e conservative \e length
kpeter@768: \e functions, too. A length function on the arcs of a digraph is called
kpeter@768: conservative if and only if there is no directed cycle of negative total
kpeter@768: length. For an arbitrary length function, the negative of the minimum
kpeter@768: cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
kpeter@768: arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
kpeter@768: function.
alpar@40: 
kpeter@768: LEMON contains three algorithms for solving the minimum mean cycle problem:
alpar@1053: - \ref KarpMmc Karp's original algorithm \cite karp78characterization.
kpeter@879: - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
alpar@1053:   version of Karp's algorithm \cite hartmann93finding.
kpeter@879: - \ref HowardMmc Howard's policy iteration algorithm
alpar@1053:   \cite dasdan98minmeancycle, \cite dasdan04experimental.
alpar@40: 
kpeter@919: In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
kpeter@879: most efficient one, though the best known theoretical bound on its running
kpeter@879: time is exponential.
kpeter@879: Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
kpeter@1080: run in time O(nm) and use space O(n<sup>2</sup>+m).
alpar@40: */
alpar@40: 
alpar@40: /**
kpeter@314: @defgroup matching Matching Algorithms
alpar@40: @ingroup algs
kpeter@50: \brief Algorithms for finding matchings in graphs and bipartite graphs.
alpar@40: 
kpeter@590: This group contains the algorithms for calculating
alpar@40: matchings in graphs and bipartite graphs. The general matching problem is
kpeter@590: finding a subset of the edges for which each node has at most one incident
kpeter@590: edge.
alpar@209: 
alpar@40: There are several different algorithms for calculate matchings in
alpar@40: graphs.  The matching problems in bipartite graphs are generally
alpar@40: easier than in general graphs. The goal of the matching optimization
kpeter@406: can be finding maximum cardinality, maximum weight or minimum cost
alpar@40: matching. The search can be constrained to find perfect or
alpar@40: maximum cardinality matching.
alpar@40: 
kpeter@406: The matching algorithms implemented in LEMON:
kpeter@406: - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
kpeter@406:   for calculating maximum cardinality matching in bipartite graphs.
kpeter@406: - \ref PrBipartiteMatching Push-relabel algorithm
kpeter@406:   for calculating maximum cardinality matching in bipartite graphs.
kpeter@406: - \ref MaxWeightedBipartiteMatching
kpeter@406:   Successive shortest path algorithm for calculating maximum weighted
kpeter@406:   matching and maximum weighted bipartite matching in bipartite graphs.
kpeter@406: - \ref MinCostMaxBipartiteMatching
kpeter@406:   Successive shortest path algorithm for calculating minimum cost maximum
kpeter@406:   matching in bipartite graphs.
kpeter@406: - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
kpeter@406:   maximum cardinality matching in general graphs.
kpeter@406: - \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
kpeter@406:   maximum weighted matching in general graphs.
kpeter@406: - \ref MaxWeightedPerfectMatching
kpeter@406:   Edmond's blossom shrinking algorithm for calculating maximum weighted
kpeter@406:   perfect matching in general graphs.
deba@869: - \ref MaxFractionalMatching Push-relabel algorithm for calculating
deba@869:   maximum cardinality fractional matching in general graphs.
deba@869: - \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating
deba@869:   maximum weighted fractional matching in general graphs.
deba@869: - \ref MaxWeightedPerfectFractionalMatching
deba@869:   Augmenting path algorithm for calculating maximum weighted
deba@869:   perfect fractional matching in general graphs.
alpar@40: 
alpar@865: \image html matching.png
alpar@873: \image latex matching.eps "Min Cost Perfect Matching" width=\textwidth
alpar@40: */
alpar@40: 
alpar@40: /**
kpeter@714: @defgroup graph_properties Connectivity and Other Graph Properties
alpar@40: @ingroup algs
kpeter@714: \brief Algorithms for discovering the graph properties
alpar@40: 
kpeter@714: This group contains the algorithms for discovering the graph properties
kpeter@714: like connectivity, bipartiteness, euler property, simplicity etc.
kpeter@714: 
kpeter@714: \image html connected_components.png
kpeter@714: \image latex connected_components.eps "Connected components" width=\textwidth
kpeter@714: */
kpeter@714: 
kpeter@714: /**
alpar@1142: @defgroup graph_isomorphism Graph Isomorphism
alpar@1142: @ingroup algs
alpar@1142: \brief Algorithms for testing (sub)graph isomorphism
alpar@1142: 
alpar@1142: This group contains algorithms for finding isomorph copies of a
alpar@1142: given graph in another one, or simply check whether two graphs are isomorphic.
alpar@1142: 
alpar@1142: The formal definition of subgraph isomorphism is as follows.
alpar@1142: 
alpar@1142: We are given two graphs, \f$G_1=(V_1,E_1)\f$ and \f$G_2=(V_2,E_2)\f$. A
alpar@1142: function \f$f:V_1\longrightarrow V_2\f$ is called \e mapping or \e
alpar@1142: embedding if \f$f(u)\neq f(v)\f$ whenever \f$u\neq v\f$.
alpar@1142: 
alpar@1142: The standard <em>Subgraph Isomorphism Problem (SIP)</em> looks for a
alpar@1142: mapping with the property that whenever \f$(u,v)\in E_1\f$, then
alpar@1142: \f$(f(u),f(v))\in E_2\f$.
alpar@1142: 
alpar@1142: In case of <em>Induced Subgraph Isomorphism Problem (ISIP)</em> one
alpar@1142: also requires that if \f$(u,v)\not\in E_1\f$, then \f$(f(u),f(v))\not\in
alpar@1142: E_2\f$
alpar@1142: 
alpar@1142: In addition, the graph nodes may be \e labeled, i.e. we are given two
alpar@1142: node labelings \f$l_1:V_1\longrightarrow L\f$ and \f$l_2:V_2\longrightarrow
alpar@1142: L\f$ and we require that \f$l_1(u)=l_2(f(u))\f$ holds for all nodes \f$u \in
kpeter@1152: G_1\f$.
alpar@1142: 
alpar@1142: */
alpar@1142: 
alpar@1142: /**
kpeter@919: @defgroup planar Planar Embedding and Drawing
kpeter@714: @ingroup algs
kpeter@714: \brief Algorithms for planarity checking, embedding and drawing
kpeter@714: 
kpeter@714: This group contains the algorithms for planarity checking,
kpeter@714: embedding and drawing.
kpeter@714: 
kpeter@714: \image html planar.png
kpeter@714: \image latex planar.eps "Plane graph" width=\textwidth
kpeter@714: */
alpar@1092: 
kpeter@1032: /**
kpeter@1032: @defgroup tsp Traveling Salesman Problem
kpeter@1032: @ingroup algs
kpeter@1032: \brief Algorithms for the symmetric traveling salesman problem
kpeter@1032: 
kpeter@1032: This group contains basic heuristic algorithms for the the symmetric
kpeter@1032: \e traveling \e salesman \e problem (TSP).
kpeter@1032: Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
kpeter@1032: the problem is to find a shortest possible tour that visits each node exactly
kpeter@1032: once (i.e. the minimum cost Hamiltonian cycle).
kpeter@1032: 
kpeter@1034: These TSP algorithms are intended to be used with a \e metric \e cost
kpeter@1034: \e function, i.e. the edge costs should satisfy the triangle inequality.
kpeter@1034: Otherwise the algorithms could yield worse results.
kpeter@1032: 
kpeter@1032: LEMON provides five well-known heuristics for solving symmetric TSP:
kpeter@1032:  - \ref NearestNeighborTsp Neareast neighbor algorithm
kpeter@1032:  - \ref GreedyTsp Greedy algorithm
kpeter@1032:  - \ref InsertionTsp Insertion heuristic (with four selection methods)
kpeter@1032:  - \ref ChristofidesTsp Christofides algorithm
kpeter@1032:  - \ref Opt2Tsp 2-opt algorithm
kpeter@1032: 
kpeter@1036: \ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest
kpeter@1036: solution methods. Furthermore, \ref InsertionTsp is usually quite effective.
kpeter@1036: 
kpeter@1036: \ref ChristofidesTsp is somewhat slower, but it has the best guaranteed
kpeter@1036: approximation factor: 3/2.
kpeter@1036: 
kpeter@1036: \ref Opt2Tsp usually provides the best results in practice, but
kpeter@1036: it is the slowest method. It can also be used to improve given tours,
kpeter@1036: for example, the results of other algorithms.
kpeter@1036: 
kpeter@1032: \image html tsp.png
kpeter@1032: \image latex tsp.eps "Traveling salesman problem" width=\textwidth
kpeter@1032: */
kpeter@714: 
kpeter@714: /**
kpeter@904: @defgroup approx_algs Approximation Algorithms
kpeter@714: @ingroup algs
kpeter@714: \brief Approximation algorithms.
kpeter@714: 
kpeter@714: This group contains the approximation and heuristic algorithms
kpeter@714: implemented in LEMON.
kpeter@904: 
kpeter@904: <b>Maximum Clique Problem</b>
kpeter@904:   - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
kpeter@904:     Grosso, Locatelli, and Pullan.
alpar@40: */
alpar@40: 
alpar@40: /**
kpeter@314: @defgroup auxalg Auxiliary Algorithms
alpar@40: @ingroup algs
kpeter@50: \brief Auxiliary algorithms implemented in LEMON.
alpar@40: 
kpeter@559: This group contains some algorithms implemented in LEMON
kpeter@50: in order to make it easier to implement complex algorithms.
alpar@40: */
alpar@40: 
alpar@40: /**
alpar@40: @defgroup gen_opt_group General Optimization Tools
kpeter@559: \brief This group contains some general optimization frameworks
alpar@40: implemented in LEMON.
alpar@40: 
kpeter@559: This group contains some general optimization frameworks
alpar@40: implemented in LEMON.
alpar@40: */
alpar@40: 
alpar@40: /**
kpeter@755: @defgroup lp_group LP and MIP Solvers
alpar@40: @ingroup gen_opt_group
kpeter@755: \brief LP and MIP solver interfaces for LEMON.
alpar@40: 
kpeter@755: This group contains LP and MIP solver interfaces for LEMON.
kpeter@755: Various LP solvers could be used in the same manner with this
kpeter@755: high-level interface.
kpeter@755: 
alpar@1053: The currently supported solvers are \cite glpk, \cite clp, \cite cbc,
alpar@1053: \cite cplex, \cite soplex.
alpar@40: */
alpar@40: 
alpar@209: /**
kpeter@314: @defgroup lp_utils Tools for Lp and Mip Solvers
alpar@40: @ingroup lp_group
kpeter@50: \brief Helper tools to the Lp and Mip solvers.
alpar@40: 
alpar@40: This group adds some helper tools to general optimization framework
alpar@40: implemented in LEMON.
alpar@40: */
alpar@40: 
alpar@40: /**
alpar@40: @defgroup metah Metaheuristics
alpar@40: @ingroup gen_opt_group
alpar@40: \brief Metaheuristics for LEMON library.
alpar@40: 
kpeter@559: This group contains some metaheuristic optimization tools.
alpar@40: */
alpar@40: 
alpar@40: /**
alpar@209: @defgroup utils Tools and Utilities
kpeter@50: \brief Tools and utilities for programming in LEMON
alpar@40: 
kpeter@50: Tools and utilities for programming in LEMON.
alpar@40: */
alpar@40: 
alpar@40: /**
alpar@40: @defgroup gutils Basic Graph Utilities
alpar@40: @ingroup utils
kpeter@50: \brief Simple basic graph utilities.
alpar@40: 
kpeter@559: This group contains some simple basic graph utilities.
alpar@40: */
alpar@40: 
alpar@40: /**
alpar@40: @defgroup misc Miscellaneous Tools
alpar@40: @ingroup utils
kpeter@50: \brief Tools for development, debugging and testing.
kpeter@50: 
kpeter@559: This group contains several useful tools for development,
alpar@40: debugging and testing.
alpar@40: */
alpar@40: 
alpar@40: /**
kpeter@314: @defgroup timecount Time Measuring and Counting
alpar@40: @ingroup misc
kpeter@50: \brief Simple tools for measuring the performance of algorithms.
kpeter@50: 
kpeter@559: This group contains simple tools for measuring the performance
alpar@40: of algorithms.
alpar@40: */
alpar@40: 
alpar@40: /**
alpar@40: @defgroup exceptions Exceptions
alpar@40: @ingroup utils
kpeter@50: \brief Exceptions defined in LEMON.
kpeter@50: 
kpeter@559: This group contains the exceptions defined in LEMON.
alpar@40: */
alpar@40: 
alpar@40: /**
alpar@40: @defgroup io_group Input-Output
kpeter@50: \brief Graph Input-Output methods
alpar@40: 
kpeter@559: This group contains the tools for importing and exporting graphs
kpeter@314: and graph related data. Now it supports the \ref lgf-format
kpeter@314: "LEMON Graph Format", the \c DIMACS format and the encapsulated
kpeter@314: postscript (EPS) format.
alpar@40: */
alpar@40: 
alpar@40: /**
kpeter@351: @defgroup lemon_io LEMON Graph Format
alpar@40: @ingroup io_group
kpeter@314: \brief Reading and writing LEMON Graph Format.
alpar@40: 
kpeter@559: This group contains methods for reading and writing
ladanyi@236: \ref lgf-format "LEMON Graph Format".
alpar@40: */
alpar@40: 
alpar@40: /**
kpeter@314: @defgroup eps_io Postscript Exporting
alpar@40: @ingroup io_group
alpar@40: \brief General \c EPS drawer and graph exporter
alpar@40: 
kpeter@559: This group contains general \c EPS drawing methods and special
alpar@209: graph exporting tools.
kpeter@1050: 
kpeter@1050: \image html graph_to_eps.png
alpar@40: */
alpar@40: 
alpar@40: /**
kpeter@714: @defgroup dimacs_group DIMACS Format
kpeter@388: @ingroup io_group
kpeter@388: \brief Read and write files in DIMACS format
kpeter@388: 
kpeter@388: Tools to read a digraph from or write it to a file in DIMACS format data.
kpeter@388: */
kpeter@388: 
kpeter@388: /**
kpeter@351: @defgroup nauty_group NAUTY Format
kpeter@351: @ingroup io_group
kpeter@351: \brief Read \e Nauty format
kpeter@388: 
kpeter@351: Tool to read graphs from \e Nauty format data.
kpeter@351: */
kpeter@351: 
kpeter@351: /**
alpar@40: @defgroup concept Concepts
alpar@40: \brief Skeleton classes and concept checking classes
alpar@40: 
kpeter@559: This group contains the data/algorithm skeletons and concept checking
alpar@40: classes implemented in LEMON.
alpar@40: 
alpar@40: The purpose of the classes in this group is fourfold.
alpar@209: 
kpeter@318: - These classes contain the documentations of the %concepts. In order
alpar@40:   to avoid document multiplications, an implementation of a concept
alpar@40:   simply refers to the corresponding concept class.
alpar@40: 
alpar@40: - These classes declare every functions, <tt>typedef</tt>s etc. an
kpeter@318:   implementation of the %concepts should provide, however completely
alpar@40:   without implementations and real data structures behind the
alpar@40:   interface. On the other hand they should provide nothing else. All
alpar@40:   the algorithms working on a data structure meeting a certain concept
alpar@40:   should compile with these classes. (Though it will not run properly,
alpar@40:   of course.) In this way it is easily to check if an algorithm
alpar@40:   doesn't use any extra feature of a certain implementation.
alpar@40: 
alpar@40: - The concept descriptor classes also provide a <em>checker class</em>
kpeter@50:   that makes it possible to check whether a certain implementation of a
alpar@40:   concept indeed provides all the required features.
alpar@40: 
alpar@40: - Finally, They can serve as a skeleton of a new implementation of a concept.
alpar@40: */
alpar@40: 
alpar@40: /**
alpar@40: @defgroup graph_concepts Graph Structure Concepts
alpar@40: @ingroup concept
alpar@40: \brief Skeleton and concept checking classes for graph structures
alpar@40: 
kpeter@735: This group contains the skeletons and concept checking classes of
kpeter@735: graph structures.
alpar@40: */
alpar@40: 
kpeter@314: /**
kpeter@314: @defgroup map_concepts Map Concepts
kpeter@314: @ingroup concept
kpeter@314: \brief Skeleton and concept checking classes for maps
kpeter@314: 
kpeter@559: This group contains the skeletons and concept checking classes of maps.
alpar@40: */
alpar@40: 
alpar@40: /**
kpeter@714: @defgroup tools Standalone Utility Applications
kpeter@714: 
kpeter@714: Some utility applications are listed here.
kpeter@714: 
kpeter@714: The standard compilation procedure (<tt>./configure;make</tt>) will compile
kpeter@714: them, as well.
kpeter@714: */
kpeter@714: 
kpeter@714: /**
alpar@40: \anchor demoprograms
alpar@40: 
kpeter@406: @defgroup demos Demo Programs
alpar@40: 
alpar@40: Some demo programs are listed here. Their full source codes can be found in
alpar@40: the \c demo subdirectory of the source tree.
alpar@40: 
ladanyi@564: In order to compile them, use the <tt>make demo</tt> or the
ladanyi@564: <tt>make check</tt> commands.
alpar@40: */
alpar@40: 
kpeter@406: }