alpar@2391: /* -*- C++ -*-
alpar@2391:  *
alpar@2391:  * This file is a part of LEMON, a generic C++ optimization library
alpar@2391:  *
alpar@2391:  * Copyright (C) 2003-2007
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@921: This group describes the several graph 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 
marci@1172: in conjunction with other graph representation. 
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: /**
deba@1866: @defgroup semi_adaptors Semi-Adaptors Classes for Graphs
deba@1866: @ingroup graphs
deba@1866: \brief Graph types between real graphs and graph adaptors.
deba@1866: 
alpar@2117: Graph types between real graphs and graph adaptors. These classes wrap
alpar@2117: graphs to give new functionality as the adaptors do it. On the other
alpar@2117: 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@1043: \brief Some special purpose map to make life easier.
alpar@1043: 
alpar@1043: LEMON provides several special 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@1402: These maps are specifically designed to assign values to the nodes and edges of
alpar@1402: 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@1402: Map adaptors are used to create "implicit" 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: 
deba@2489: The typical usage of this classes is the 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<int> 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
deba@2489: function map adaptors give back temporarly objects.
deba@2489: \code
deba@2489:   Graph graph;
deba@2489:   
deba@2489:   typedef Graph::EdgeMap<double> DoubleEdgeMap;
deba@2489:   DoubleEdgeMap length(graph);
deba@2489:   DoubleEdgeMap speed(graph);
deba@2489:   
deba@2489:   typedef DivMap<DoubleEdgeMap, DoubleEdgeMap> TimeMap;
deba@2489:   
deba@2489:   TimeMap time(length, speed);
deba@2489:   
deba@2489:   Dijkstra<Graph, TimeMap> 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@2072: \brief Two dimensional data storages.
alpar@2072: 
deba@2084: Two dimensional data storages.
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: 
deba@2084: LEMON provides flexible data structures
deba@2084: to work with paths.
deba@2084: 
deba@2489: All of them have similar interfaces, and it can be copied easily with
deba@2489: assignment operator and copy constructor. This make 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@921: \brief Some data structures implemented in LEMON.
alpar@406: 
alpar@921: This group describes the 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
deba@2376: \brief This group contains the common graph
deba@2376: search algorithms.
alpar@947: 
deba@2376: This group contains the common graph
deba@2376: search algorithms like Bfs and Dfs.
alpar@678: */
alpar@678: 
alpar@678: /**
deba@2376: @defgroup shortest_path Shortest Path algorithms
deba@2084: @ingroup algs
alpar@758: \brief This group describes the algorithms
deba@2376: for finding shortest paths.
deba@2060: 
deba@2376: This group describes the algorithms for finding shortest paths in
deba@2376: graphs.
deba@2376: 
deba@2376: */
deba@2376: 
deba@2376: /** 
deba@2376: @defgroup max_flow Maximum Flow algorithms 
deba@2376: @ingroup algs 
deba@2376: \brief This group describes the 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: 
deba@2514: The maximum flow problem is to find a flow between a single-source and
deba@2514: single-target that is maximum. Formally, there is \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
deba@2514: maximum flow is the solution of the next optimization problem:
deba@2514: 
deba@2514: \f[ 0 \le f_a \le c_a \f]
deba@2514: \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \quad 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: 
deba@2514: The lemon contains several algorithms for solve maximum flow problems:
deba@2514: - \ref lemon::EdmondsKarp "Edmonds-Karp" 
deba@2514: - \ref lemon::Preflow "Goldberg's Preflow algorithm"
deba@2514: - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic tree"
deba@2514: - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
deba@2514: 
deba@2514: In most cases the \ref lemon::Preflow "preflow" algorithm provides the
deba@2514: fastest method to compute the maximum flow. All impelementations
deba@2514: provides functions for query the minimum cut, which is the dual linear
deba@2514: programming probelm 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: 
deba@2376: \brief This group describes the algorithms
deba@2376: 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: 
deba@2530: \brief This group describes the algorithms for finding minimum cut in
deba@2530: 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
deba@2530: cut is the 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: 
deba@2530: The lemon contains several algorithms related to minimum cut problems:
deba@2530: 
deba@2530: - \ref lemon::HaoOrlin "Hao-Orlin algorithm" for calculate minimum cut
deba@2530:   in directed graphs  
deba@2530: - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
deba@2530:   calculate minimum cut in undirected graphs
deba@2530: - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" for 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
deba@1750: \brief This group describes the algorithms
deba@2429: for discover the graph properties
deba@2060: 
deba@2429: This group describes the algorithms for discover the graph properties
deba@2429: 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
deba@2500: \brief This group contains algorithms for planarity embedding and drawing
deba@2500: 
deba@2500: This group contains 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
deba@2042: \brief This group describes the algorithms
deba@2042: for find matchings in graphs and bipartite graphs.
deba@2060: 
deba@2060: This group provides some algorithm objects and function
deba@2060: to calculate matchings in graphs and bipartite graphs.
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@2117: \brief This group contains the algorithms for finding a minimum cost spanning
deba@2084: tree in a graph
deba@2084: 
alpar@2117: This group contains 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
deba@2084: \brief Some algorithms implemented in LEMON.
deba@2084: 
deba@2084: This group describes the algorithms in LEMON in order to make 
deba@2084: it easier to implement complex algorithms.
deba@2376: */
deba@2084: 
deba@2376: /**
deba@2376: @defgroup approx Approximation algorithms
deba@2376: \brief Approximation algorithms
deba@2376: 
deba@2376: Approximation and heuristic algorithms
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
deba@2370: \brief This group adds some helper tools to the Lp and Mip solvers
deba@2370: implemented in LEMON.
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: 
deba@2370: This group contains some metaheuristic optimization tools.
deba@2370: */
deba@2370: 
deba@2370: /**
deba@2376: @defgroup utils Tools and Utilities 
deba@2376: \brief Tools and Utilities for Programming in LEMON
deba@2376: 
deba@2376: Tools and Utilities for Programming in LEMON
deba@2376: */
deba@2376: 
deba@2376: /**
deba@2376: @defgroup gutils Basic Graph Utilities
deba@2376: @ingroup utils
deba@2376: \brief This group describes some 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@678: Here you can find several useful tools for development,
alpar@678: debugging and testing.
alpar@678: */
alpar@678: 
deba@2376: 
alpar@678: /**
alpar@1847: @defgroup timecount Time measuring and Counting
alpar@1847: @ingroup misc
alpar@1847: Here you can find 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
deba@2376: \brief Tools to Make It Easier to Make Graphs.
deba@2376: 
deba@2376: This group describes the tools that makes it easier to make 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
deba@2376: This group contains the exceptions thrown by LEMON library
deba@2376: */
deba@2376: 
deba@2376: /**
deba@2016: @defgroup io_group Input-Output
deba@2084: \brief Several Graph Input-Output methods
deba@2084: 
deba@2084: Here you can find tools for importing and exporting graphs 
deba@2084: and graph related data. Now it supports the LEMON format, the
alpar@2117: \c DIMACS format and the encapsulated postscript 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: 
deba@2084: Methods for reading and writing LEMON format. More about this
deba@2084: format you can find 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
deba@2016: \brief Section readers and writers for lemon Input-Output.
deba@2016: 
deba@2016: Here you can find which section readers and writers can attach to
deba@2016: the LemonReader and LemonWriter.
deba@2016: */
deba@2016: 
deba@2016: /**
deba@2016: @defgroup item_io Item Readers and Writers
deba@2084: @ingroup lemon_io
deba@2016: \brief Item readers and writers for lemon Input-Output.
deba@2016: 
deba@2016: The Input-Output classes can handle more data type by example
deba@2016: as map or attribute value. Each of these should be written and
deba@2016: read some way. The module make possible to do this.  
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@2117: This group contains 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, <tt>typedef</tt>s 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 <em>checker class</em>
alpar@2117:   that makes it possible 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: 
klao@1030: This group contains 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@678: This group contains 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: 
ladanyi@1639: The standard compilation procedure (<tt>./configure;make</tt>) will compile
ladanyi@1639: them, as well. 
alpar@1558: 
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 (<tt>./configure;make</tt>) will compile
deba@2491: them, as well. 
deba@2491: 
deba@2491: */
deba@2491: