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@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 kpeter@50: This group describes 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@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@318: with any graph structure. kpeter@318: kpeter@318: See also: \ref graph_concepts "Graph Structure Concepts". 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@50: This group describes the map structures implemented in LEMON. kpeter@50: kpeter@318: LEMON provides several special purpose maps and map adaptors that e.g. combine alpar@40: new maps from existing ones. kpeter@318: kpeter@318: 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@50: This group describes maps that are specifically designed to assign kpeter@83: values to the nodes and arcs of graphs. 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@50: This group describes map adaptors that are used to create "implicit" kpeter@50: maps from other maps. alpar@40: kpeter@83: Most of them are \ref lemon::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@318: 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@318: 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@318: \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@40: @defgroup paths Path Structures alpar@40: @ingroup datas kpeter@325: \brief %Path structures implemented in LEMON. alpar@40: kpeter@50: This group describes 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@50: This group describes 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 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 kpeter@50: \brief Common graph search algorithms. alpar@40: alpar@209: This group describes the common graph search algorithms like kpeter@318: Breadth-First Search (BFS) and Depth-First Search (DFS). alpar@40: */ alpar@40: alpar@40: /** kpeter@318: @defgroup shortest_path Shortest Path Algorithms alpar@40: @ingroup algs kpeter@50: \brief Algorithms for finding shortest paths. alpar@40: kpeter@50: This group describes the algorithms for finding shortest paths in graphs. alpar@40: */ alpar@40: alpar@209: /** kpeter@318: @defgroup spantree Minimum Spanning Tree Algorithms alpar@40: @ingroup algs kpeter@50: \brief Algorithms for finding a minimum cost spanning tree in a graph. alpar@40: kpeter@50: This group describes the algorithms for finding a minimum cost spanning alpar@40: tree in a graph alpar@40: */ alpar@40: alpar@40: /** alpar@209: @defgroup utils Tools and Utilities kpeter@50: \brief Tools and utilities for programming in LEMON alpar@40: kpeter@50: Tools and utilities for programming in LEMON. alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup gutils Basic Graph Utilities alpar@40: @ingroup utils kpeter@50: \brief Simple basic graph utilities. alpar@40: 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 kpeter@50: \brief Tools for development, debugging and testing. kpeter@50: kpeter@50: This group describes several useful tools for development, alpar@40: debugging and testing. alpar@40: */ alpar@40: alpar@40: /** kpeter@318: @defgroup timecount Time Measuring and Counting alpar@40: @ingroup misc kpeter@50: \brief Simple tools for measuring the performance of algorithms. kpeter@50: kpeter@50: This group describes simple tools for measuring the performance alpar@40: of algorithms. alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup exceptions Exceptions alpar@40: @ingroup utils kpeter@50: \brief Exceptions defined in LEMON. kpeter@50: kpeter@50: This group describes the exceptions defined in LEMON. alpar@40: */ alpar@40: alpar@40: /** alpar@40: @defgroup io_group Input-Output kpeter@50: \brief Graph Input-Output methods alpar@40: alpar@209: This group describes the tools for importing and exporting graphs kpeter@302: and graph related data. Now it supports the LEMON format kpeter@302: and the encapsulated postscript (EPS) format. kpeter@318: postscript (EPS) format. alpar@40: */ alpar@40: alpar@40: /** ladanyi@236: @defgroup lemon_io LEMON Input-Output alpar@40: @ingroup io_group kpeter@318: \brief Reading and writing LEMON Graph Format. alpar@40: alpar@210: This group describes methods for reading and writing ladanyi@236: \ref lgf-format "LEMON Graph Format". alpar@40: */ alpar@40: alpar@40: /** kpeter@318: @defgroup eps_io Postscript Exporting alpar@40: @ingroup io_group alpar@40: \brief General \c EPS drawer and graph exporter alpar@40: kpeter@50: This group describes general \c EPS drawing methods and special alpar@209: graph exporting tools. 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@209: kpeter@325: - 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 kpeter@325: 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@50: This group describes 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@318: /** kpeter@318: @defgroup map_concepts Map Concepts kpeter@318: @ingroup concept kpeter@318: \brief Skeleton and concept checking classes for maps kpeter@323: kpeter@318: This group describes the skeletons and concept checking classes of maps. 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: */