alpar@40: /* -*- C++ -*- alpar@40: * alpar@40: * This file is a part of LEMON, a generic C++ optimization library alpar@40: * alpar@40: * Copyright (C) 2003-2008 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: alpar@40: /** alpar@40: @defgroup datas Data Structures alpar@40: This group describes the several graph 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@40: The implementation of combinatorial algorithms heavily relies on alpar@40: efficient graph implementations. LEMON offers data structures which are alpar@40: planned to be easily used in an experimental phase of implementation studies, alpar@40: 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 alpar@40: some graph features like edge or node deletion. alpar@40: alpar@40: Alteration of standard containers need a very limited number of alpar@40: operations, these together satisfy the everyday requirements. alpar@40: In the case of graph structures, different operations are needed which do alpar@40: not alter the physical graph, but gives another view. If some nodes or alpar@40: edges have to be hidden or the reverse oriented graph have to be used, then alpar@40: this is the case. It also may happen that in a flow implementation alpar@40: the residual graph can be accessed by another algorithm, or a node-set alpar@40: is to be shrunk for another algorithm. alpar@40: LEMON also provides a variety of graphs for these requirements called alpar@40: \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only alpar@40: in conjunction with other graph representation. 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 alpar@40: with any graph structures. alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup semi_adaptors Semi-Adaptors Classes for Graphs alpar@40: @ingroup graphs alpar@40: \brief Graph types between real graphs and graph adaptors. alpar@40: alpar@40: Graph types between real graphs and graph adaptors. These classes wrap alpar@40: graphs to give new functionality as the adaptors do it. On the other alpar@40: hand they are not light-weight structures as the adaptors. alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup maps Maps alpar@40: @ingroup datas alpar@40: \brief Some special purpose map to make life easier. alpar@40: alpar@40: LEMON provides several special maps that e.g. combine alpar@40: new maps from existing ones. alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup graph_maps Graph Maps alpar@40: @ingroup maps alpar@40: \brief Special Graph-Related Maps. alpar@40: alpar@40: These maps are specifically designed to assign values to the nodes and edges of alpar@40: graphs. alpar@40: */ 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: alpar@40: Map adaptors are used to create "implicit" maps from other maps. alpar@40: alpar@40: Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can alpar@40: make arithmetic operations between one or two maps (negation, scaling, alpar@40: addition, multiplication etc.) or e.g. convert a map to another one alpar@40: of different Value type. alpar@40: alpar@40: The typical usage of this classes is the 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 alpar@40: 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@40: alpar@40: Graph::NodeMap degree_map(graph); alpar@40: alpar@40: graphToEps(graph, "graph.eps") alpar@40: .coords(coords).scaleToA4().undirected() alpar@40: .nodeColors(composeMap(functorMap(nodeColor), degree_map)) alpar@40: .run(); alpar@40: \endcode alpar@40: The \c functorMap() function makes an \c int to \c Color map from the alpar@40: \e nodeColor() function. The \c composeMap() compose the \e degree_map alpar@40: and the previous created map. The composed map is proper function to alpar@40: get 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 alpar@40: function map adaptors give back temporarly objects. alpar@40: \code alpar@40: Graph graph; alpar@40: alpar@40: typedef Graph::EdgeMap DoubleEdgeMap; alpar@40: DoubleEdgeMap length(graph); alpar@40: DoubleEdgeMap speed(graph); alpar@40: alpar@40: typedef DivMap TimeMap; alpar@40: alpar@40: TimeMap time(length, speed); alpar@40: alpar@40: Dijkstra dijkstra(graph, time); alpar@40: dijkstra.run(source, target); alpar@40: \endcode alpar@40: alpar@40: We have a length map and a maximum speed map on a graph. The minimum alpar@40: time to pass the edge can be calculated as the division of the two alpar@40: 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 matrices Matrices alpar@40: @ingroup datas alpar@40: \brief Two dimensional data storages. alpar@40: alpar@40: Two dimensional data storages. alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup paths Path Structures alpar@40: @ingroup datas alpar@40: \brief Path structures implemented in LEMON. alpar@40: alpar@40: LEMON provides flexible data structures alpar@40: to work with paths. alpar@40: alpar@40: All of them have similar interfaces, and it can be copied easily with alpar@40: assignment operator and copy constructor. This make 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: /** alpar@40: @defgroup auxdat Auxiliary Data Structures alpar@40: @ingroup datas alpar@40: \brief Some data structures implemented in LEMON. alpar@40: alpar@40: This group describes the 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: /** alpar@40: @defgroup algs Algorithms alpar@40: \brief This group describes the several algorithms alpar@40: implemented in LEMON. alpar@40: alpar@40: This group describes the several algorithms alpar@40: implemented in LEMON. alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup search Graph Search alpar@40: @ingroup algs alpar@40: \brief This group contains the common graph alpar@40: search algorithms. alpar@40: alpar@40: This group contains the common graph alpar@40: search algorithms like Bfs and Dfs. alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup shortest_path Shortest Path algorithms alpar@40: @ingroup algs alpar@40: \brief This group describes the algorithms alpar@40: for finding shortest paths. alpar@40: alpar@40: This group describes the algorithms for finding shortest paths in alpar@40: graphs. alpar@40: alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup max_flow Maximum Flow algorithms alpar@40: @ingroup algs alpar@40: \brief This group describes the algorithms for finding maximum flows. alpar@40: alpar@40: This group describes the algorithms for finding maximum flows and alpar@40: feasible circulations. alpar@40: alpar@40: The maximum flow problem is to find a flow between a single-source and alpar@40: single-target that is maximum. Formally, there is \f$G=(V,A)\f$ alpar@40: directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity alpar@40: function and given \f$s, t \in V\f$ source and target node. The alpar@40: maximum flow is the solution of the next optimization problem: alpar@40: alpar@40: \f[ 0 \le f_a \le c_a \f] alpar@40: \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \quad u \in V \setminus \{s,t\}\f] alpar@40: \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f] alpar@40: alpar@40: The lemon contains several algorithms for solve maximum flow problems: alpar@40: - \ref lemon::EdmondsKarp "Edmonds-Karp" alpar@40: - \ref lemon::Preflow "Goldberg's Preflow algorithm" alpar@40: - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic tree" alpar@40: - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees" alpar@40: alpar@40: In most cases the \ref lemon::Preflow "preflow" algorithm provides the alpar@40: fastest method to compute the maximum flow. All impelementations alpar@40: provides functions for query the minimum cut, which is the dual linear alpar@40: programming probelm of the maximum flow. alpar@40: alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup min_cost_flow Minimum Cost Flow algorithms alpar@40: @ingroup algs alpar@40: alpar@40: \brief This group describes the algorithms alpar@40: for finding minimum cost flows and circulations. alpar@40: alpar@40: This group describes the algorithms for finding minimum cost flows and alpar@40: circulations. alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup min_cut Minimum Cut algorithms alpar@40: @ingroup algs alpar@40: alpar@40: \brief This group describes the algorithms for finding minimum cut in alpar@40: graphs. alpar@40: alpar@40: This group describes the algorithms for finding minimum cut in graphs. alpar@40: alpar@40: The minimum cut problem is to find a non-empty and non-complete alpar@40: \f$X\f$ subset of the vertices with minimum overall capacity on alpar@40: outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an alpar@40: \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum alpar@40: cut is the solution of the next optimization problem: alpar@40: alpar@40: \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f] alpar@40: alpar@40: The lemon contains several algorithms related to minimum cut problems: alpar@40: alpar@40: - \ref lemon::HaoOrlin "Hao-Orlin algorithm" for calculate minimum cut alpar@40: in directed graphs alpar@40: - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for alpar@40: calculate minimum cut in undirected graphs alpar@40: - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" for calculate all alpar@40: pairs minimum cut in undirected graphs alpar@40: alpar@40: If you want to find minimum cut just between two distinict nodes, alpar@40: please see the \ref max_flow "Maximum Flow page". alpar@40: alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup graph_prop Connectivity and other graph properties alpar@40: @ingroup algs alpar@40: \brief This group describes the algorithms alpar@40: for discover the graph properties alpar@40: alpar@40: This group describes the algorithms for discover the graph properties alpar@40: like connectivity, bipartiteness, euler property, simplicity, etc... alpar@40: alpar@40: \image html edge_biconnected_components.png alpar@40: \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup planar Planarity embedding and drawing alpar@40: @ingroup algs alpar@40: \brief This group contains algorithms for planarity embedding and drawing alpar@40: alpar@40: This group contains algorithms for planarity checking, embedding and drawing. alpar@40: alpar@40: \image html planar.png alpar@40: \image latex planar.eps "Plane graph" width=\textwidth alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup matching Matching algorithms alpar@40: @ingroup algs alpar@40: \brief This group describes the algorithms alpar@40: for find matchings in graphs and bipartite graphs. alpar@40: alpar@40: This group provides some algorithm objects and function to calculate alpar@40: matchings in graphs and bipartite graphs. The general matching problem is alpar@40: finding a subset of the edges which does not shares common endpoints. alpar@40: 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 alpar@40: can be the 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: alpar@40: Lemon contains the next algorithms: alpar@40: - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp alpar@40: augmenting path algorithm for calculate maximum cardinality matching in alpar@40: bipartite graphs alpar@40: - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel alpar@40: algorithm for calculate maximum cardinality matching in bipartite graphs alpar@40: - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching" alpar@40: Successive shortest path algorithm for calculate maximum weighted matching alpar@40: and maximum weighted bipartite matching in bipartite graph alpar@40: - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching" alpar@40: Successive shortest path algorithm for calculate minimum cost maximum alpar@40: matching in bipartite graph alpar@40: - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm alpar@40: for calculate maximum cardinality matching in general graph alpar@40: - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom alpar@40: shrinking algorithm for calculate maximum weighted matching in general alpar@40: graph alpar@40: - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching" alpar@40: Edmond's blossom shrinking algorithm for calculate maximum weighted alpar@40: perfect matching in general graph alpar@40: alpar@40: \image html bipartite_matching.png alpar@40: \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth alpar@40: alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup spantree Minimum Spanning Tree algorithms alpar@40: @ingroup algs alpar@40: \brief This group contains the algorithms for finding a minimum cost spanning alpar@40: tree in a graph alpar@40: alpar@40: This group contains the algorithms for finding a minimum cost spanning alpar@40: tree in a graph alpar@40: */ alpar@40: alpar@40: alpar@40: /** alpar@40: @defgroup auxalg Auxiliary algorithms alpar@40: @ingroup algs alpar@40: \brief Some algorithms implemented in LEMON. alpar@40: alpar@40: This group describes the algorithms in LEMON in order to make alpar@40: it easier to implement complex algorithms. alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup approx Approximation algorithms alpar@40: \brief Approximation algorithms alpar@40: alpar@40: Approximation and heuristic algorithms alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup gen_opt_group General Optimization Tools alpar@40: \brief This group describes some general optimization frameworks alpar@40: implemented in LEMON. alpar@40: alpar@40: This group describes some general optimization frameworks alpar@40: implemented in LEMON. alpar@40: alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup lp_group Lp and Mip solvers alpar@40: @ingroup gen_opt_group alpar@40: \brief Lp and Mip solver interfaces for LEMON. alpar@40: alpar@40: This group describes Lp and Mip solver interfaces for LEMON. The alpar@40: various LP solvers could be used in the same manner with this alpar@40: interface. alpar@40: alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup lp_utils Tools for Lp and Mip solvers alpar@40: @ingroup lp_group alpar@40: \brief This group adds some helper tools to the Lp and Mip solvers alpar@40: implemented in LEMON. 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: alpar@40: This group contains some metaheuristic optimization tools. alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup utils Tools and Utilities alpar@40: \brief Tools and Utilities for Programming in LEMON alpar@40: alpar@40: Tools and Utilities for Programming in LEMON alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup gutils Basic Graph Utilities alpar@40: @ingroup utils alpar@40: \brief This group describes some simple basic graph utilities. alpar@40: alpar@40: This group describes some simple basic graph utilities. alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup misc Miscellaneous Tools alpar@40: @ingroup utils alpar@40: Here you can find several useful tools for development, alpar@40: debugging and testing. alpar@40: */ alpar@40: alpar@40: alpar@40: /** alpar@40: @defgroup timecount Time measuring and Counting alpar@40: @ingroup misc alpar@40: Here you can find simple tools for measuring the performance alpar@40: of algorithms. alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup graphbits Tools for Graph Implementation alpar@40: @ingroup utils alpar@40: \brief Tools to Make It Easier to Make Graphs. alpar@40: alpar@40: This group describes the tools that makes it easier to make graphs and alpar@40: the maps that dynamically update with the graph changes. alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup exceptions Exceptions alpar@40: @ingroup utils alpar@40: This group contains the exceptions thrown by LEMON library alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup io_group Input-Output alpar@40: \brief Several Graph Input-Output methods alpar@40: alpar@40: Here you can find tools for importing and exporting graphs alpar@40: and graph related data. Now it supports the LEMON format, the alpar@40: \c DIMACS format and the encapsulated postscript format. alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup lemon_io Lemon Input-Output alpar@40: @ingroup io_group alpar@40: \brief Reading and writing LEMON format alpar@40: alpar@40: Methods for reading and writing LEMON format. More about this alpar@40: format you can find on the \ref graph-io-page "Graph Input-Output" alpar@40: tutorial pages. alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup section_io Section readers and writers alpar@40: @ingroup lemon_io alpar@40: \brief Section readers and writers for lemon Input-Output. alpar@40: alpar@40: Here you can find which section readers and writers can attach to alpar@40: the LemonReader and LemonWriter. alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup item_io Item Readers and Writers alpar@40: @ingroup lemon_io alpar@40: \brief Item readers and writers for lemon Input-Output. alpar@40: alpar@40: The Input-Output classes can handle more data type by example alpar@40: as map or attribute value. Each of these should be written and alpar@40: read some way. The module make possible to do this. alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup eps_io Postscript exporting alpar@40: @ingroup io_group alpar@40: \brief General \c EPS drawer and graph exporter alpar@40: alpar@40: This group contains general \c EPS drawing methods and special alpar@40: graph exporting tools. alpar@40: */ alpar@40: alpar@40: alpar@40: /** alpar@40: @defgroup concept Concepts alpar@40: \brief Skeleton classes and concept checking classes alpar@40: alpar@40: This group describes 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@40: alpar@40: - 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, typedefs etc. an alpar@40: 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 alpar@40: that makes it possible 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: 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: alpar@40: 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: alpar@40: /* --- Unused group alpar@40: @defgroup experimental Experimental Structures and Algorithms alpar@40: This group contains some Experimental structures and algorithms. alpar@40: The stuff here is subject to change. alpar@40: */ alpar@40: alpar@40: /** alpar@40: \anchor demoprograms alpar@40: alpar@40: @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: alpar@41: It order to compile them, use --enable-demo configure option when alpar@41: build the library. alpar@40: alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup tools Standalone utility applications alpar@40: alpar@40: Some utility applications are listed here. alpar@40: alpar@40: The standard compilation procedure (./configure;make) will compile alpar@40: them, as well. alpar@40: alpar@40: */ alpar@40: