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@463: * Copyright (C) 2003-2009 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@422: namespace lemon { kpeter@422: alpar@40: /** alpar@40: @defgroup datas Data Structures kpeter@606: 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: See also: \ref graph_concepts "Graph Structure Concepts". alpar@40: */ alpar@40: alpar@40: /** kpeter@474: @defgroup graph_adaptors Adaptor Classes for Graphs deba@432: @ingroup graphs kpeter@474: \brief Adaptor classes for digraphs and graphs kpeter@474: kpeter@474: This group contains several useful adaptor classes for digraphs and graphs. deba@432: deba@432: The main parts of LEMON are the different graph structures, generic kpeter@474: graph algorithms, graph concepts, which couple them, and graph deba@432: adaptors. While the previous notions are more or less clear, the deba@432: latter one needs further explanation. Graph adaptors are graph classes deba@432: which serve for considering graph structures in different ways. deba@432: deba@432: A short example makes this much clearer. Suppose that we have an kpeter@474: instance \c g of a directed graph type, say ListDigraph and an algorithm deba@432: \code deba@432: template deba@432: int algorithm(const Digraph&); deba@432: \endcode deba@432: is needed to run on the reverse oriented graph. It may be expensive deba@432: (in time or in memory usage) to copy \c g with the reversed deba@432: arcs. In this case, an adaptor class is used, which (according kpeter@474: to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph. kpeter@474: The adaptor uses the original digraph structure and digraph operations when kpeter@474: methods of the reversed oriented graph are called. This means that the adaptor kpeter@474: have minor memory usage, and do not perform sophisticated algorithmic deba@432: actions. The purpose of it is to give a tool for the cases when a deba@432: graph have to be used in a specific alteration. If this alteration is kpeter@474: obtained by a usual construction like filtering the node or the arc set or deba@432: considering a new orientation, then an adaptor is worthwhile to use. deba@432: To come back to the reverse oriented graph, in this situation deba@432: \code deba@432: template class ReverseDigraph; deba@432: \endcode deba@432: template class can be used. The code looks as follows deba@432: \code deba@432: ListDigraph g; kpeter@474: ReverseDigraph rg(g); deba@432: int result = algorithm(rg); deba@432: \endcode kpeter@474: During running the algorithm, the original digraph \c g is untouched. kpeter@474: This techniques give rise to an elegant code, and based on stable deba@432: graph adaptors, complex algorithms can be implemented easily. deba@432: kpeter@474: In flow, circulation and matching problems, the residual deba@432: graph is of particular importance. Combining an adaptor implementing kpeter@474: this with shortest path algorithms or minimum mean cycle algorithms, deba@432: a range of weighted and cardinality optimization algorithms can be deba@432: obtained. For other examples, the interested user is referred to the deba@432: detailed documentation of particular adaptors. deba@432: deba@432: The behavior of graph adaptors can be very different. Some of them keep deba@432: capabilities of the original graph while in other cases this would be kpeter@474: meaningless. This means that the concepts that they meet depend kpeter@474: on the graph adaptor, and the wrapped graph. kpeter@474: For example, if an arc of a reversed digraph is deleted, this is carried kpeter@474: out by deleting the corresponding arc of the original digraph, thus the kpeter@474: adaptor modifies the original digraph. kpeter@474: However in case of a residual digraph, this operation has no sense. deba@432: deba@432: Let us stand one more example here to simplify your work. kpeter@474: ReverseDigraph has constructor deba@432: \code deba@432: ReverseDigraph(Digraph& digraph); deba@432: \endcode kpeter@474: This means that in a situation, when a const %ListDigraph& deba@432: reference to a graph is given, then it have to be instantiated with kpeter@474: Digraph=const %ListDigraph. deba@432: \code deba@432: int algorithm1(const ListDigraph& g) { kpeter@474: ReverseDigraph rg(g); deba@432: return algorithm2(rg); deba@432: } deba@432: \endcode deba@432: */ deba@432: deba@432: /** kpeter@50: @defgroup semi_adaptors Semi-Adaptor Classes for Graphs alpar@40: @ingroup graphs alpar@40: \brief Graph types between real graphs and graph adaptors. alpar@40: kpeter@606: This group contains some graph types between real graphs and graph adaptors. alpar@209: These classes wrap graphs to give new functionality as the adaptors do it. kpeter@50: On the other hand they are not light-weight structures as the adaptors. alpar@40: */ alpar@40: alpar@40: /** alpar@209: @defgroup maps Maps alpar@40: @ingroup datas kpeter@50: \brief Map structures implemented in LEMON. alpar@40: kpeter@606: 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: See also: \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@606: This group contains maps that are specifically designed to assign kpeter@422: values to the nodes and arcs/edges of graphs. kpeter@422: kpeter@422: If you are looking for the standard graph maps (\c NodeMap, \c ArcMap, kpeter@422: \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@606: This group contains map adaptors that are used to create "implicit" kpeter@50: maps from other maps. alpar@40: kpeter@422: 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 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 DoubleArcMap; kpeter@83: DoubleArcMap length(graph); kpeter@83: DoubleArcMap speed(graph); kpeter@83: kpeter@83: typedef DivMap TimeMap; alpar@40: TimeMap time(length, speed); alpar@209: kpeter@83: Dijkstra 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@209: @defgroup matrices Matrices alpar@40: @ingroup datas kpeter@50: \brief Two dimensional data storages implemented in LEMON. alpar@40: kpeter@606: This group contains two dimensional data storages implemented in LEMON. 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@606: 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: alpar@40: \sa lemon::concepts::Path alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup auxdat Auxiliary Data Structures alpar@40: @ingroup datas kpeter@50: \brief Auxiliary data structures implemented in LEMON. alpar@40: kpeter@606: 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: /** alpar@40: @defgroup algs Algorithms kpeter@606: \brief This group contains the several algorithms alpar@40: implemented in LEMON. alpar@40: kpeter@606: 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@606: This group contains the common graph search algorithms, namely kpeter@422: \e breadth-first \e search (BFS) and \e depth-first \e search (DFS). 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@606: This group contains the algorithms for finding shortest paths in digraphs. kpeter@422: kpeter@422: - \ref Dijkstra algorithm for finding shortest paths from a source node kpeter@422: when all arc lengths are non-negative. kpeter@422: - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths kpeter@422: from a source node when arc lenghts can be either positive or negative, kpeter@422: but the digraph should not contain directed cycles with negative total kpeter@422: length. kpeter@422: - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms kpeter@422: for solving the \e all-pairs \e shortest \e paths \e problem when arc kpeter@422: lenghts can be either positive or negative, but the digraph should kpeter@422: not contain directed cycles with negative total length. kpeter@422: - \ref Suurballe A successive shortest path algorithm for finding kpeter@422: arc-disjoint paths between two nodes having minimum total length. alpar@40: */ alpar@40: alpar@209: /** kpeter@314: @defgroup max_flow Maximum Flow Algorithms alpar@209: @ingroup algs kpeter@50: \brief Algorithms for finding maximum flows. alpar@40: kpeter@606: This group contains the algorithms for finding maximum flows and alpar@40: feasible circulations. alpar@40: kpeter@422: The \e maximum \e flow \e problem is to find a flow of maximum value between kpeter@422: a single source and a single target. Formally, there is a \f$G=(V,A)\f$ kpeter@656: digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and kpeter@422: \f$s, t \in V\f$ source and target nodes. kpeter@656: A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the kpeter@422: following optimization problem. alpar@40: kpeter@656: \f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f] kpeter@656: \f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu) kpeter@656: \quad \forall u\in V\setminus\{s,t\} \f] kpeter@656: \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@422: - \ref EdmondsKarp Edmonds-Karp algorithm. kpeter@422: - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm. kpeter@422: - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. kpeter@422: - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees. alpar@40: kpeter@422: In most cases the \ref Preflow "Preflow" algorithm provides the kpeter@422: fastest method for computing a maximum flow. All implementations kpeter@698: also provide functions to query the minimum cut, which is the dual kpeter@698: problem of maximum flow. kpeter@698: kpeter@698: \ref Circulation is a preflow push-relabel algorithm implemented directly kpeter@698: for finding feasible circulations, which is a somewhat different problem, kpeter@698: but it is strongly related to maximum flow. kpeter@698: For more information, see \ref Circulation. alpar@40: */ alpar@40: alpar@40: /** kpeter@314: @defgroup min_cost_flow Minimum Cost Flow Algorithms alpar@40: @ingroup algs alpar@40: kpeter@50: \brief Algorithms for finding minimum cost flows and circulations. alpar@40: kpeter@656: This group contains the algorithms for finding minimum cost flows and alpar@209: circulations. kpeter@422: kpeter@422: The \e minimum \e cost \e flow \e problem is to find a feasible flow of kpeter@422: minimum total cost from a set of supply nodes to a set of demand nodes kpeter@656: in a network with capacity constraints (lower and upper bounds) kpeter@656: and arc costs. kpeter@687: Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$, kpeter@687: \f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and kpeter@656: upper bounds for the flow values on the arcs, for which kpeter@687: \f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$, kpeter@687: \f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow kpeter@687: on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the kpeter@656: signed supply values of the nodes. kpeter@656: If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$ kpeter@656: supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with kpeter@656: \f$-sup(u)\f$ demand. kpeter@687: A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution kpeter@656: of the following optimization problem. kpeter@422: kpeter@656: \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f] kpeter@656: \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq kpeter@656: sup(u) \quad \forall u\in V \f] kpeter@656: \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] kpeter@422: kpeter@656: The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be kpeter@656: zero or negative in order to have a feasible solution (since the sum kpeter@656: of the expressions on the left-hand side of the inequalities is zero). kpeter@656: It means that the total demand must be greater or equal to the total kpeter@656: supply and all the supplies have to be carried out from the supply nodes, kpeter@656: but there could be demands that are not satisfied. kpeter@656: If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand kpeter@656: constraints have to be satisfied with equality, i.e. all demands kpeter@656: have to be satisfied and all supplies have to be used. kpeter@656: kpeter@656: If you need the opposite inequalities in the supply/demand constraints kpeter@656: (i.e. the total demand is less than the total supply and all the demands kpeter@656: have to be satisfied while there could be supplies that are not used), kpeter@656: then you could easily transform the problem to the above form by reversing kpeter@656: the direction of the arcs and taking the negative of the supply values kpeter@656: (e.g. using \ref ReverseDigraph and \ref NegMap adaptors). kpeter@656: However \ref NetworkSimplex algorithm also supports this form directly kpeter@656: for the sake of convenience. kpeter@656: kpeter@656: A feasible solution for this problem can be found using \ref Circulation. kpeter@656: kpeter@656: Note that the above formulation is actually more general than the usual kpeter@656: definition of the minimum cost flow problem, in which strict equalities kpeter@656: are required in the supply/demand contraints, i.e. kpeter@656: kpeter@656: \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) = kpeter@656: sup(u) \quad \forall u\in V. \f] kpeter@656: kpeter@656: However if the sum of the supply values is zero, then these two problems kpeter@656: are equivalent. So if you need the equality form, you have to ensure this kpeter@656: additional contraint for the algorithms. kpeter@656: kpeter@656: The dual solution of the minimum cost flow problem is represented by node kpeter@656: potentials \f$\pi: V\rightarrow\mathbf{Z}\f$. kpeter@687: An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem kpeter@656: is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$ kpeter@656: node potentials the following \e complementary \e slackness optimality kpeter@656: conditions hold. kpeter@656: kpeter@656: - For all \f$uv\in A\f$ arcs: kpeter@656: - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$; kpeter@656: - if \f$lower(uv)typedefs 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 checker class 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@606: This group contains the skeletons and concept checking classes of LEMON's alpar@40: graph structures and helper classes used to implement these. 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@606: This group contains the skeletons and concept checking classes of maps. alpar@40: */ alpar@40: alpar@40: /** alpar@40: \anchor demoprograms alpar@40: kpeter@422: @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@611: In order to compile them, use the make demo or the ladanyi@611: make check commands. alpar@40: */ alpar@40: alpar@40: /** kpeter@422: @defgroup tools Standalone Utility Applications alpar@40: alpar@209: Some utility applications are listed here. alpar@40: alpar@40: The standard compilation procedure (./configure;make) will compile alpar@209: them, as well. alpar@40: */ alpar@40: kpeter@422: }