doc/groups.dox
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 05 Aug 2011 00:17:29 +0200
branch1.0
changeset 427 c59bdcc8e33e
parent 326 d3a7603026a2
permissions -rw-r--r--
Unify sources
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2011
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 /**
    20 @defgroup datas Data Structures
    21 This group describes the several data structures implemented in LEMON.
    22 */
    23 
    24 /**
    25 @defgroup graphs Graph Structures
    26 @ingroup datas
    27 \brief Graph structures implemented in LEMON.
    28 
    29 The implementation of combinatorial algorithms heavily relies on
    30 efficient graph implementations. LEMON offers data structures which are
    31 planned to be easily used in an experimental phase of implementation studies,
    32 and thereafter the program code can be made efficient by small modifications.
    33 
    34 The most efficient implementation of diverse applications require the
    35 usage of different physical graph implementations. These differences
    36 appear in the size of graph we require to handle, memory or time usage
    37 limitations or in the set of operations through which the graph can be
    38 accessed.  LEMON provides several physical graph structures to meet
    39 the diverging requirements of the possible users.  In order to save on
    40 running time or on memory usage, some structures may fail to provide
    41 some graph features like arc/edge or node deletion.
    42 
    43 You are free to use the graph structure that fit your requirements
    44 the best, most graph algorithms and auxiliary data structures can be used
    45 with any graph structure.
    46 
    47 <b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
    48 */
    49 
    50 /**
    51 @defgroup maps Maps
    52 @ingroup datas
    53 \brief Map structures implemented in LEMON.
    54 
    55 This group describes the map structures implemented in LEMON.
    56 
    57 LEMON provides several special purpose maps and map adaptors that e.g. combine
    58 new maps from existing ones.
    59 
    60 <b>See also:</b> \ref map_concepts "Map Concepts".
    61 */
    62 
    63 /**
    64 @defgroup graph_maps Graph Maps
    65 @ingroup maps
    66 \brief Special graph-related maps.
    67 
    68 This group describes maps that are specifically designed to assign
    69 values to the nodes and arcs of graphs.
    70 */
    71 
    72 /**
    73 \defgroup map_adaptors Map Adaptors
    74 \ingroup maps
    75 \brief Tools to create new maps from existing ones
    76 
    77 This group describes map adaptors that are used to create "implicit"
    78 maps from other maps.
    79 
    80 Most of them are \ref lemon::concepts::ReadMap "read-only maps".
    81 They can make arithmetic and logical operations between one or two maps
    82 (negation, shifting, addition, multiplication, logical 'and', 'or',
    83 'not' etc.) or e.g. convert a map to another one of different Value type.
    84 
    85 The typical usage of this classes is passing implicit maps to
    86 algorithms.  If a function type algorithm is called then the function
    87 type map adaptors can be used comfortable. For example let's see the
    88 usage of map adaptors with the \c graphToEps() function.
    89 \code
    90   Color nodeColor(int deg) {
    91     if (deg >= 2) {
    92       return Color(0.5, 0.0, 0.5);
    93     } else if (deg == 1) {
    94       return Color(1.0, 0.5, 1.0);
    95     } else {
    96       return Color(0.0, 0.0, 0.0);
    97     }
    98   }
    99 
   100   Digraph::NodeMap<int> degree_map(graph);
   101 
   102   graphToEps(graph, "graph.eps")
   103     .coords(coords).scaleToA4().undirected()
   104     .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
   105     .run();
   106 \endcode
   107 The \c functorToMap() function makes an \c int to \c Color map from the
   108 \c nodeColor() function. The \c composeMap() compose the \c degree_map
   109 and the previously created map. The composed map is a proper function to
   110 get the color of each node.
   111 
   112 The usage with class type algorithms is little bit harder. In this
   113 case the function type map adaptors can not be used, because the
   114 function map adaptors give back temporary objects.
   115 \code
   116   Digraph graph;
   117 
   118   typedef Digraph::ArcMap<double> DoubleArcMap;
   119   DoubleArcMap length(graph);
   120   DoubleArcMap speed(graph);
   121 
   122   typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
   123   TimeMap time(length, speed);
   124 
   125   Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
   126   dijkstra.run(source, target);
   127 \endcode
   128 We have a length map and a maximum speed map on the arcs of a digraph.
   129 The minimum time to pass the arc can be calculated as the division of
   130 the two maps which can be done implicitly with the \c DivMap template
   131 class. We use the implicit minimum time map as the length map of the
   132 \c Dijkstra algorithm.
   133 */
   134 
   135 /**
   136 @defgroup paths Path Structures
   137 @ingroup datas
   138 \brief %Path structures implemented in LEMON.
   139 
   140 This group describes the path structures implemented in LEMON.
   141 
   142 LEMON provides flexible data structures to work with paths.
   143 All of them have similar interfaces and they can be copied easily with
   144 assignment operators and copy constructors. This makes it easy and
   145 efficient to have e.g. the Dijkstra algorithm to store its result in
   146 any kind of path structure.
   147 
   148 \sa lemon::concepts::Path
   149 */
   150 
   151 /**
   152 @defgroup auxdat Auxiliary Data Structures
   153 @ingroup datas
   154 \brief Auxiliary data structures implemented in LEMON.
   155 
   156 This group describes some data structures implemented in LEMON in
   157 order to make it easier to implement combinatorial algorithms.
   158 */
   159 
   160 /**
   161 @defgroup algs Algorithms
   162 \brief This group describes the several algorithms
   163 implemented in LEMON.
   164 
   165 This group describes the several algorithms
   166 implemented in LEMON.
   167 */
   168 
   169 /**
   170 @defgroup search Graph Search
   171 @ingroup algs
   172 \brief Common graph search algorithms.
   173 
   174 This group describes the common graph search algorithms like
   175 Breadth-First Search (BFS) and Depth-First Search (DFS).
   176 */
   177 
   178 /**
   179 @defgroup shortest_path Shortest Path Algorithms
   180 @ingroup algs
   181 \brief Algorithms for finding shortest paths.
   182 
   183 This group describes the algorithms for finding shortest paths in graphs.
   184 */
   185 
   186 /**
   187 @defgroup spantree Minimum Spanning Tree Algorithms
   188 @ingroup algs
   189 \brief Algorithms for finding a minimum cost spanning tree in a graph.
   190 
   191 This group describes the algorithms for finding a minimum cost spanning
   192 tree in a graph
   193 */
   194 
   195 /**
   196 @defgroup utils Tools and Utilities
   197 \brief Tools and utilities for programming in LEMON
   198 
   199 Tools and utilities for programming in LEMON.
   200 */
   201 
   202 /**
   203 @defgroup gutils Basic Graph Utilities
   204 @ingroup utils
   205 \brief Simple basic graph utilities.
   206 
   207 This group describes some simple basic graph utilities.
   208 */
   209 
   210 /**
   211 @defgroup misc Miscellaneous Tools
   212 @ingroup utils
   213 \brief Tools for development, debugging and testing.
   214 
   215 This group describes several useful tools for development,
   216 debugging and testing.
   217 */
   218 
   219 /**
   220 @defgroup timecount Time Measuring and Counting
   221 @ingroup misc
   222 \brief Simple tools for measuring the performance of algorithms.
   223 
   224 This group describes simple tools for measuring the performance
   225 of algorithms.
   226 */
   227 
   228 /**
   229 @defgroup exceptions Exceptions
   230 @ingroup utils
   231 \brief Exceptions defined in LEMON.
   232 
   233 This group describes the exceptions defined in LEMON.
   234 */
   235 
   236 /**
   237 @defgroup io_group Input-Output
   238 \brief Graph Input-Output methods
   239 
   240 This group describes the tools for importing and exporting graphs
   241 and graph related data. Now it supports the LEMON format
   242 and the encapsulated postscript (EPS) format.
   243 postscript (EPS) format.
   244 */
   245 
   246 /**
   247 @defgroup lemon_io LEMON Input-Output
   248 @ingroup io_group
   249 \brief Reading and writing LEMON Graph Format.
   250 
   251 This group describes methods for reading and writing
   252 \ref lgf-format "LEMON Graph Format".
   253 */
   254 
   255 /**
   256 @defgroup eps_io Postscript Exporting
   257 @ingroup io_group
   258 \brief General \c EPS drawer and graph exporter
   259 
   260 This group describes general \c EPS drawing methods and special
   261 graph exporting tools.
   262 */
   263 
   264 /**
   265 @defgroup concept Concepts
   266 \brief Skeleton classes and concept checking classes
   267 
   268 This group describes the data/algorithm skeletons and concept checking
   269 classes implemented in LEMON.
   270 
   271 The purpose of the classes in this group is fourfold.
   272 
   273 - These classes contain the documentations of the %concepts. In order
   274   to avoid document multiplications, an implementation of a concept
   275   simply refers to the corresponding concept class.
   276 
   277 - These classes declare every functions, <tt>typedef</tt>s etc. an
   278   implementation of the %concepts should provide, however completely
   279   without implementations and real data structures behind the
   280   interface. On the other hand they should provide nothing else. All
   281   the algorithms working on a data structure meeting a certain concept
   282   should compile with these classes. (Though it will not run properly,
   283   of course.) In this way it is easily to check if an algorithm
   284   doesn't use any extra feature of a certain implementation.
   285 
   286 - The concept descriptor classes also provide a <em>checker class</em>
   287   that makes it possible to check whether a certain implementation of a
   288   concept indeed provides all the required features.
   289 
   290 - Finally, They can serve as a skeleton of a new implementation of a concept.
   291 */
   292 
   293 /**
   294 @defgroup graph_concepts Graph Structure Concepts
   295 @ingroup concept
   296 \brief Skeleton and concept checking classes for graph structures
   297 
   298 This group describes the skeletons and concept checking classes of LEMON's
   299 graph structures and helper classes used to implement these.
   300 */
   301 
   302 /**
   303 @defgroup map_concepts Map Concepts
   304 @ingroup concept
   305 \brief Skeleton and concept checking classes for maps
   306 
   307 This group describes the skeletons and concept checking classes of maps.
   308 */
   309 
   310 /**
   311 \anchor demoprograms
   312 
   313 @defgroup demos Demo programs
   314 
   315 Some demo programs are listed here. Their full source codes can be found in
   316 the \c demo subdirectory of the source tree.
   317 
   318 It order to compile them, use <tt>--enable-demo</tt> configure option when
   319 build the library.
   320 */