alpar@2391: /* -*- C++ -*- alpar@2391: * alpar@2391: * This file is a part of LEMON, a generic C++ optimization library alpar@2391: * alpar@2553: * Copyright (C) 2003-2008 alpar@2391: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@2391: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@2391: * alpar@2391: * Permission to use, modify and distribute this software is granted alpar@2391: * provided that this copyright notice appears in all copies. For alpar@2391: * precise terms see the accompanying LICENSE file. alpar@2391: * alpar@2391: * This software is provided "AS IS" with no warranty of any kind, alpar@2391: * express or implied, and with no claim as to its suitability for any alpar@2391: * purpose. alpar@2391: * alpar@2391: */ alpar@814: alpar@678: /** alpar@678: @defgroup datas Data Structures alpar@2566: This group describes the several data structures implemented in LEMON. alpar@678: */ alpar@430: alpar@678: /** alpar@678: @defgroup graphs Graph Structures alpar@678: @ingroup datas alpar@921: \brief Graph structures implemented in LEMON. alpar@430: marci@1172: The implementation of combinatorial algorithms heavily relies on marci@1172: efficient graph implementations. LEMON offers data structures which are marci@1172: planned to be easily used in an experimental phase of implementation studies, marci@1172: and thereafter the program code can be made efficient by small modifications. alpar@430: deba@2084: The most efficient implementation of diverse applications require the deba@2084: usage of different physical graph implementations. These differences deba@2084: appear in the size of graph we require to handle, memory or time usage deba@2084: limitations or in the set of operations through which the graph can be deba@2084: accessed. LEMON provides several physical graph structures to meet deba@2084: the diverging requirements of the possible users. In order to save on deba@2084: running time or on memory usage, some structures may fail to provide deba@2084: some graph features like edge or node deletion. marci@1172: marci@1172: Alteration of standard containers need a very limited number of marci@1172: operations, these together satisfy the everyday requirements. alpar@2117: In the case of graph structures, different operations are needed which do alpar@2006: not alter the physical graph, but gives another view. If some nodes or marci@1172: edges have to be hidden or the reverse oriented graph have to be used, then alpar@2117: this is the case. It also may happen that in a flow implementation alpar@2006: the residual graph can be accessed by another algorithm, or a node-set alpar@2006: is to be shrunk for another algorithm. marci@1172: LEMON also provides a variety of graphs for these requirements called alpar@1401: \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only alpar@2566: in conjunction with other graph representations. alpar@430: alpar@678: You are free to use the graph structure that fit your requirements alpar@678: the best, most graph algorithms and auxiliary data structures can be used marci@1172: with any graph structures. alpar@678: */ alpar@430: alpar@678: /** alpar@2566: @defgroup semi_adaptors Semi-Adaptor Classes for Graphs deba@1866: @ingroup graphs deba@1866: \brief Graph types between real graphs and graph adaptors. deba@1866: alpar@2566: This group describes some graph types between real graphs and graph adaptors. alpar@2566: These classes wrap graphs to give new functionality as the adaptors do it. alpar@2566: On the other hand they are not light-weight structures as the adaptors. deba@1866: */ deba@1866: deba@1866: /** alpar@1043: @defgroup maps Maps alpar@1043: @ingroup datas alpar@2566: \brief Map structures implemented in LEMON. alpar@1043: alpar@2566: This group describes the map structures implemented in LEMON. alpar@2566: alpar@2566: LEMON provides several special purpose maps that e.g. combine alpar@1043: new maps from existing ones. alpar@1043: */ alpar@1043: alpar@1402: /** alpar@1402: @defgroup graph_maps Graph Maps alpar@1402: @ingroup maps alpar@1402: \brief Special Graph-Related Maps. alpar@1402: alpar@2566: This group describes maps that are specifically designed to assign alpar@2566: values to the nodes and edges of graphs. alpar@1402: */ alpar@1402: alpar@1402: alpar@1402: /** alpar@1402: \defgroup map_adaptors Map Adaptors alpar@1402: \ingroup maps alpar@1402: \brief Tools to create new maps from existing ones alpar@1402: alpar@2566: This group describes map adaptors that are used to create "implicit" alpar@2566: maps from other maps. alpar@1402: alpar@2260: Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can alpar@2117: make arithmetic operations between one or two maps (negation, scaling, alpar@1402: addition, multiplication etc.) or e.g. convert a map to another one alpar@1402: of different Value type. deba@2489: alpar@2566: The typical usage of this classes is passing implicit maps to deba@2489: algorithms. If a function type algorithm is called then the function deba@2489: type map adaptors can be used comfortable. For example let's see the deba@2489: usage of map adaptors with the \c graphToEps() function: deba@2489: \code deba@2489: Color nodeColor(int deg) { deba@2489: if (deg >= 2) { deba@2489: return Color(0.5, 0.0, 0.5); deba@2489: } else if (deg == 1) { deba@2489: return Color(1.0, 0.5, 1.0); deba@2489: } else { deba@2489: return Color(0.0, 0.0, 0.0); deba@2489: } deba@2489: } deba@2489: deba@2489: Graph::NodeMap degree_map(graph); deba@2489: deba@2489: graphToEps(graph, "graph.eps") deba@2489: .coords(coords).scaleToA4().undirected() deba@2489: .nodeColors(composeMap(functorMap(nodeColor), degree_map)) deba@2489: .run(); deba@2489: \endcode deba@2489: The \c functorMap() function makes an \c int to \c Color map from the deba@2489: \e nodeColor() function. The \c composeMap() compose the \e degree_map deba@2489: and the previous created map. The composed map is proper function to deba@2489: get color of each node. deba@2489: deba@2489: The usage with class type algorithms is little bit harder. In this deba@2489: case the function type map adaptors can not be used, because the alpar@2566: function map adaptors give back temporary objects. deba@2489: \code deba@2489: Graph graph; deba@2489: deba@2489: typedef Graph::EdgeMap DoubleEdgeMap; deba@2489: DoubleEdgeMap length(graph); deba@2489: DoubleEdgeMap speed(graph); deba@2489: deba@2489: typedef DivMap TimeMap; deba@2489: deba@2489: TimeMap time(length, speed); deba@2489: deba@2489: Dijkstra dijkstra(graph, time); deba@2489: dijkstra.run(source, target); deba@2489: \endcode deba@2489: deba@2489: We have a length map and a maximum speed map on a graph. The minimum deba@2489: time to pass the edge can be calculated as the division of the two deba@2489: maps which can be done implicitly with the \c DivMap template deba@2489: class. We use the implicit minimum time map as the length map of the deba@2489: \c Dijkstra algorithm. alpar@1402: */ alpar@1402: alpar@1043: /** alpar@2072: @defgroup matrices Matrices alpar@2072: @ingroup datas alpar@2566: \brief Two dimensional data storages implemented in LEMON. alpar@2072: alpar@2566: This group describes two dimensional data storages implemented in LEMON. alpar@2072: */ alpar@2072: deba@2084: /** deba@2084: @defgroup paths Path Structures deba@2084: @ingroup datas deba@2084: \brief Path structures implemented in LEMON. deba@2084: alpar@2566: This group describes the path structures implemented in LEMON. deba@2084: alpar@2566: LEMON provides flexible data structures to work with paths. alpar@2566: All of them have similar interfaces and they can be copied easily with alpar@2566: assignment operators and copy constructors. This makes it easy and deba@2489: efficient to have e.g. the Dijkstra algorithm to store its result in deba@2489: any kind of path structure. deba@2084: alpar@2260: \sa lemon::concepts::Path deba@2084: deba@2084: */ alpar@2072: alpar@2072: /** alpar@678: @defgroup auxdat Auxiliary Data Structures alpar@678: @ingroup datas alpar@2566: \brief Auxiliary data structures implemented in LEMON. alpar@406: alpar@2566: This group describes some data structures implemented in LEMON in alpar@678: order to make it easier to implement combinatorial algorithms. alpar@678: */ alpar@406: alpar@785: alpar@785: /** deba@2084: @defgroup algs Algorithms deba@2084: \brief This group describes the several algorithms alpar@921: implemented in LEMON. alpar@947: deba@2084: This group describes the several algorithms alpar@947: implemented in LEMON. alpar@947: */ alpar@947: alpar@947: /** deba@2376: @defgroup search Graph Search deba@2084: @ingroup algs alpar@2566: \brief Common graph search algorithms. alpar@947: alpar@2566: This group describes the common graph search algorithms like alpar@2566: Breadth-first search (Bfs) and Depth-first search (Dfs). alpar@678: */ alpar@678: alpar@678: /** deba@2376: @defgroup shortest_path Shortest Path algorithms deba@2084: @ingroup algs alpar@2566: \brief Algorithms for finding shortest paths. deba@2060: alpar@2566: This group describes the algorithms for finding shortest paths in graphs. deba@2376: */ deba@2376: deba@2376: /** deba@2376: @defgroup max_flow Maximum Flow algorithms deba@2376: @ingroup algs alpar@2566: \brief Algorithms for finding maximum flows. deba@2376: deba@2377: This group describes the algorithms for finding maximum flows and deba@2377: feasible circulations. deba@2060: alpar@2566: The maximum flow problem is to find a flow between a single source and alpar@2566: a single target that is maximum. Formally, there is a \f$G=(V,A)\f$ deba@2514: directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity deba@2514: function and given \f$s, t \in V\f$ source and target node. The alpar@2566: maximum flow is the \f$f_a\f$ solution of the next optimization problem: deba@2514: deba@2514: \f[ 0 \le f_a \le c_a \f] alpar@2566: \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \qquad \forall u \in V \setminus \{s,t\}\f] deba@2514: \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f] deba@2514: alpar@2566: LEMON contains several algorithms for solving maximum flow problems: deba@2514: - \ref lemon::EdmondsKarp "Edmonds-Karp" deba@2514: - \ref lemon::Preflow "Goldberg's Preflow algorithm" alpar@2566: - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees" deba@2514: - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees" deba@2514: alpar@2566: In most cases the \ref lemon::Preflow "Preflow" algorithm provides the deba@2514: fastest method to compute the maximum flow. All impelementations alpar@2566: provides functions to query the minimum cut, which is the dual linear alpar@2566: programming problem of the maximum flow. deba@2514: alpar@678: */ alpar@678: alpar@678: /** deba@2376: @defgroup min_cost_flow Minimum Cost Flow algorithms deba@2376: @ingroup algs deba@2376: alpar@2566: \brief Algorithms for finding minimum cost flows and circulations. deba@2376: deba@2376: This group describes the algorithms for finding minimum cost flows and deba@2376: circulations. deba@2376: */ deba@2376: deba@2376: /** deba@2530: @defgroup min_cut Minimum Cut algorithms deba@2530: @ingroup algs deba@2376: alpar@2566: \brief Algorithms for finding minimum cut in graphs. deba@2530: deba@2530: This group describes the algorithms for finding minimum cut in graphs. deba@2530: deba@2530: The minimum cut problem is to find a non-empty and non-complete deba@2530: \f$X\f$ subset of the vertices with minimum overall capacity on deba@2530: outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an deba@2530: \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum alpar@2566: cut is the \f$X\f$ solution of the next optimization problem: deba@2530: deba@2530: \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f] deba@2530: alpar@2566: LEMON contains several algorithms related to minimum cut problems: deba@2530: alpar@2566: - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut deba@2530: in directed graphs alpar@2566: - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to deba@2530: calculate minimum cut in undirected graphs alpar@2566: - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all deba@2530: pairs minimum cut in undirected graphs deba@2530: deba@2530: If you want to find minimum cut just between two distinict nodes, deba@2530: please see the \ref max_flow "Maximum Flow page". deba@2530: deba@2376: */ deba@2376: deba@2376: /** deba@2429: @defgroup graph_prop Connectivity and other graph properties deba@2084: @ingroup algs alpar@2566: \brief Algorithms for discovering the graph properties deba@2060: alpar@2566: This group describes the algorithms for discovering the graph properties alpar@2566: like connectivity, bipartiteness, euler property, simplicity etc. deba@2060: deba@2060: \image html edge_biconnected_components.png deba@2060: \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth deba@1750: */ deba@1750: deba@1750: /** deba@2500: @defgroup planar Planarity embedding and drawing deba@2500: @ingroup algs alpar@2566: \brief Algorithms for planarity checking, embedding and drawing deba@2500: alpar@2566: This group describes the algorithms for planarity checking, embedding and drawing. deba@2500: deba@2500: \image html planar.png deba@2500: \image latex planar.eps "Plane graph" width=\textwidth deba@2500: */ deba@2500: deba@2500: /** deba@2376: @defgroup matching Matching algorithms deba@2084: @ingroup algs alpar@2566: \brief Algorithms for finding matchings in graphs and bipartite graphs. deba@2060: alpar@2566: This group contains algorithm objects and functions to calculate deba@2548: matchings in graphs and bipartite graphs. The general matching problem is deba@2548: finding a subset of the edges which does not shares common endpoints. deba@2548: deba@2548: There are several different algorithms for calculate matchings in deba@2548: graphs. The matching problems in bipartite graphs are generally deba@2548: easier than in general graphs. The goal of the matching optimization deba@2548: can be the finding maximum cardinality, maximum weight or minimum cost deba@2548: matching. The search can be constrained to find perfect or deba@2548: maximum cardinality matching. deba@2548: deba@2548: Lemon contains the next algorithms: deba@2548: - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp deba@2548: augmenting path algorithm for calculate maximum cardinality matching in deba@2548: bipartite graphs deba@2548: - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel deba@2548: algorithm for calculate maximum cardinality matching in bipartite graphs deba@2548: - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching" deba@2548: Successive shortest path algorithm for calculate maximum weighted matching deba@2548: and maximum weighted bipartite matching in bipartite graph deba@2548: - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching" deba@2548: Successive shortest path algorithm for calculate minimum cost maximum deba@2548: matching in bipartite graph deba@2548: - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm deba@2548: for calculate maximum cardinality matching in general graph deba@2548: - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom deba@2548: shrinking algorithm for calculate maximum weighted matching in general deba@2548: graph deba@2548: - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching" deba@2548: Edmond's blossom shrinking algorithm for calculate maximum weighted deba@2548: perfect matching in general graph deba@2060: deba@2060: \image html bipartite_matching.png deba@2060: \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth deba@2060: deba@2042: */ deba@2042: deba@2042: /** deba@2376: @defgroup spantree Minimum Spanning Tree algorithms deba@2084: @ingroup algs alpar@2566: \brief Algorithms for finding a minimum cost spanning tree in a graph. deba@2084: alpar@2566: This group describes the algorithms for finding a minimum cost spanning deba@2084: tree in a graph deba@2084: */ deba@2084: deba@2084: deba@2084: /** deba@2376: @defgroup auxalg Auxiliary algorithms deba@2084: @ingroup algs alpar@2566: \brief Auxiliary algorithms implemented in LEMON. deba@2084: alpar@2566: This group describes some algorithms implemented in LEMON alpar@2566: in order to make it easier to implement complex algorithms. deba@2376: */ deba@2084: deba@2376: /** deba@2376: @defgroup approx Approximation algorithms alpar@2566: \brief Approximation algorithms. deba@2376: alpar@2566: This group describes the approximation and heuristic algorithms alpar@2566: implemented in LEMON. deba@2084: */ deba@2084: deba@2084: /** deba@2084: @defgroup gen_opt_group General Optimization Tools deba@2084: \brief This group describes some general optimization frameworks deba@2084: implemented in LEMON. deba@2084: deba@2084: This group describes some general optimization frameworks deba@2084: implemented in LEMON. deba@2084: alpar@1151: */ alpar@1151: deba@2370: /** deba@2371: @defgroup lp_group Lp and Mip solvers deba@2370: @ingroup gen_opt_group deba@2370: \brief Lp and Mip solver interfaces for LEMON. deba@2370: deba@2370: This group describes Lp and Mip solver interfaces for LEMON. The deba@2370: various LP solvers could be used in the same manner with this deba@2370: interface. deba@2370: deba@2370: */ deba@2370: deba@2368: /** deba@2370: @defgroup lp_utils Tools for Lp and Mip solvers deba@2370: @ingroup lp_group alpar@2566: \brief Helper tools to the Lp and Mip solvers. deba@2368: deba@2368: This group adds some helper tools to general optimization framework deba@2368: implemented in LEMON. deba@2368: */ deba@2368: alpar@1151: /** deba@2370: @defgroup metah Metaheuristics deba@2370: @ingroup gen_opt_group deba@2370: \brief Metaheuristics for LEMON library. deba@2370: alpar@2566: This group describes some metaheuristic optimization tools. deba@2370: */ deba@2370: deba@2370: /** deba@2376: @defgroup utils Tools and Utilities alpar@2566: \brief Tools and utilities for programming in LEMON deba@2376: alpar@2566: Tools and utilities for programming in LEMON. deba@2376: */ deba@2376: deba@2376: /** deba@2376: @defgroup gutils Basic Graph Utilities deba@2376: @ingroup utils alpar@2566: \brief Simple basic graph utilities. deba@2376: deba@2376: This group describes some simple basic graph utilities. deba@2376: */ deba@2376: deba@2376: /** alpar@678: @defgroup misc Miscellaneous Tools deba@2376: @ingroup utils alpar@2566: \brief Tools for development, debugging and testing. alpar@2566: alpar@2566: This group describes several useful tools for development, alpar@678: debugging and testing. alpar@678: */ alpar@678: alpar@678: /** alpar@1847: @defgroup timecount Time measuring and Counting alpar@1847: @ingroup misc alpar@2566: \brief Simple tools for measuring the performance of algorithms. alpar@2566: alpar@2566: This group describes simple tools for measuring the performance alpar@1847: of algorithms. alpar@1847: */ alpar@1847: alpar@1847: /** deba@2376: @defgroup graphbits Tools for Graph Implementation deba@2376: @ingroup utils alpar@2566: \brief Tools to make it easier to create graphs. deba@2376: alpar@2566: This group describes the tools that makes it easier to create graphs and deba@2376: the maps that dynamically update with the graph changes. deba@2376: */ deba@2376: deba@2376: /** deba@2376: @defgroup exceptions Exceptions deba@2376: @ingroup utils alpar@2566: \brief Exceptions defined in LEMON. alpar@2566: alpar@2566: This group describes the exceptions defined in LEMON. deba@2376: */ deba@2376: deba@2376: /** deba@2016: @defgroup io_group Input-Output alpar@2566: \brief Graph Input-Output methods deba@2084: alpar@2566: This group describes the tools for importing and exporting graphs deba@2084: and graph related data. Now it supports the LEMON format, the alpar@2566: \c DIMACS format and the encapsulated postscript (EPS) format. deba@2084: */ deba@2084: deba@2084: /** deba@2084: @defgroup lemon_io Lemon Input-Output deba@2084: @ingroup io_group deba@2084: \brief Reading and writing LEMON format deba@2084: alpar@2566: This group describes methods for reading and writing LEMON format. alpar@2566: You can find more about this format on the \ref graph-io-page "Graph Input-Output" deba@2084: tutorial pages. alpar@1287: */ alpar@1287: alpar@1287: /** deba@2016: @defgroup section_io Section readers and writers deba@2084: @ingroup lemon_io alpar@2566: \brief Section readers and writers for LEMON Input-Output. deba@2016: alpar@2566: This group describes section reader and writer classes that can be alpar@2566: attached to \ref LemonReader and \ref LemonWriter. deba@2016: */ deba@2016: deba@2016: /** alpar@2566: @defgroup item_io Item readers and writers deba@2084: @ingroup lemon_io alpar@2566: \brief Item readers and writers for LEMON Input-Output. deba@2016: alpar@2566: This group describes reader and writer classes for various data types alpar@2566: (e.g. map or attribute values). These classes can be attached to alpar@2566: \ref LemonReader and \ref LemonWriter. deba@2016: */ deba@2016: deba@2016: /** deba@2084: @defgroup eps_io Postscript exporting deba@2084: @ingroup io_group alpar@2117: \brief General \c EPS drawer and graph exporter deba@2084: alpar@2566: This group describes general \c EPS drawing methods and special deba@2084: graph exporting tools. deba@2084: */ deba@2084: deba@2084: deba@2084: /** klao@1030: @defgroup concept Concepts klao@959: \brief Skeleton classes and concept checking classes alpar@794: klao@959: This group describes the data/algorithm skeletons and concept checking klao@1030: classes implemented in LEMON. klao@1030: alpar@2117: The purpose of the classes in this group is fourfold. alpar@2117: alpar@2117: - These classes contain the documentations of the concepts. In order alpar@2117: to avoid document multiplications, an implementation of a concept alpar@2117: simply refers to the corresponding concept class. klao@1030: alpar@2233: - These classes declare every functions, typedefs etc. an alpar@2117: implementation of the concepts should provide, however completely alpar@2117: without implementations and real data structures behind the alpar@2117: interface. On the other hand they should provide nothing else. All alpar@2117: the algorithms working on a data structure meeting a certain concept alpar@2117: should compile with these classes. (Though it will not run properly, alpar@2117: of course.) In this way it is easily to check if an algorithm alpar@2117: doesn't use any extra feature of a certain implementation. alpar@2117: alpar@2233: - The concept descriptor classes also provide a checker class alpar@2566: that makes it possible to check whether a certain implementation of a alpar@2117: concept indeed provides all the required features. alpar@2117: alpar@2117: - Finally, They can serve as a skeleton of a new implementation of a concept. klao@1030: alpar@794: */ alpar@794: deba@2084: klao@1030: /** klao@1030: @defgroup graph_concepts Graph Structure Concepts klao@1030: @ingroup concept klao@1030: \brief Skeleton and concept checking classes for graph structures klao@1030: alpar@2566: This group describes the skeletons and concept checking classes of LEMON's klao@1030: graph structures and helper classes used to implement these. klao@1030: */ alpar@794: alpar@1587: /* --- Unused group alpar@678: @defgroup experimental Experimental Structures and Algorithms alpar@2566: This group describes some Experimental structures and algorithms. alpar@678: The stuff here is subject to change. alpar@678: */ alpar@1151: alpar@1558: /** athos@1582: \anchor demoprograms athos@1582: alpar@1558: @defgroup demos Demo programs alpar@1558: alpar@1559: Some demo programs are listed here. Their full source codes can be found in alpar@1558: the \c demo subdirectory of the source tree. alpar@1558: alpar@2566: It order to compile them, use --enable-demo configure option when alpar@2566: build the library. alpar@1558: */ alpar@1558: deba@2491: /** deba@2491: @defgroup tools Standalone utility applications deba@2491: deba@2491: Some utility applications are listed here. deba@2491: deba@2491: The standard compilation procedure (./configure;make) will compile deba@2491: them, as well. deba@2491: */ deba@2491: