doc/groups.dox
author Alpar Juttner <alpar@cs.elte.hu>
Thu, 09 Oct 2008 13:52:01 +0100
branch1.0
changeset 303 de38fca76780
parent 236 da953e387d31
child 320 12626fc94ccf
permissions -rw-r--r--
Merge
     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-2008
     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 structures.
    46 */
    47 
    48 /**
    49 @defgroup maps Maps
    50 @ingroup datas
    51 \brief Map structures implemented in LEMON.
    52 
    53 This group describes the map structures implemented in LEMON.
    54 
    55 LEMON provides several special purpose maps that e.g. combine
    56 new maps from existing ones.
    57 */
    58 
    59 /**
    60 @defgroup graph_maps Graph Maps
    61 @ingroup maps
    62 \brief Special graph-related maps.
    63 
    64 This group describes maps that are specifically designed to assign
    65 values to the nodes and arcs of graphs.
    66 */
    67 
    68 
    69 /**
    70 \defgroup map_adaptors Map Adaptors
    71 \ingroup maps
    72 \brief Tools to create new maps from existing ones
    73 
    74 This group describes map adaptors that are used to create "implicit"
    75 maps from other maps.
    76 
    77 Most of them are \ref lemon::concepts::ReadMap "read-only maps".
    78 They can make arithmetic and logical operations between one or two maps
    79 (negation, shifting, addition, multiplication, logical 'and', 'or',
    80 'not' etc.) or e.g. convert a map to another one of different Value type.
    81 
    82 The typical usage of this classes is passing implicit maps to
    83 algorithms.  If a function type algorithm is called then the function
    84 type map adaptors can be used comfortable. For example let's see the
    85 usage of map adaptors with the \c digraphToEps() function.
    86 \code
    87   Color nodeColor(int deg) {
    88     if (deg >= 2) {
    89       return Color(0.5, 0.0, 0.5);
    90     } else if (deg == 1) {
    91       return Color(1.0, 0.5, 1.0);
    92     } else {
    93       return Color(0.0, 0.0, 0.0);
    94     }
    95   }
    96 
    97   Digraph::NodeMap<int> degree_map(graph);
    98 
    99   digraphToEps(graph, "graph.eps")
   100     .coords(coords).scaleToA4().undirected()
   101     .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
   102     .run();
   103 \endcode
   104 The \c functorToMap() function makes an \c int to \c Color map from the
   105 \e nodeColor() function. The \c composeMap() compose the \e degree_map
   106 and the previously created map. The composed map is a proper function to
   107 get the color of each node.
   108 
   109 The usage with class type algorithms is little bit harder. In this
   110 case the function type map adaptors can not be used, because the
   111 function map adaptors give back temporary objects.
   112 \code
   113   Digraph graph;
   114 
   115   typedef Digraph::ArcMap<double> DoubleArcMap;
   116   DoubleArcMap length(graph);
   117   DoubleArcMap speed(graph);
   118 
   119   typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
   120   TimeMap time(length, speed);
   121 
   122   Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
   123   dijkstra.run(source, target);
   124 \endcode
   125 We have a length map and a maximum speed map on the arcs of a digraph.
   126 The minimum time to pass the arc can be calculated as the division of
   127 the two maps which can be done implicitly with the \c DivMap template
   128 class. We use the implicit minimum time map as the length map of the
   129 \c Dijkstra algorithm.
   130 */
   131 
   132 /**
   133 @defgroup paths Path Structures
   134 @ingroup datas
   135 \brief Path structures implemented in LEMON.
   136 
   137 This group describes the path structures implemented in LEMON.
   138 
   139 LEMON provides flexible data structures to work with paths.
   140 All of them have similar interfaces and they can be copied easily with
   141 assignment operators and copy constructors. This makes it easy and
   142 efficient to have e.g. the Dijkstra algorithm to store its result in
   143 any kind of path structure.
   144 
   145 \sa lemon::concepts::Path
   146 
   147 */
   148 
   149 /**
   150 @defgroup auxdat Auxiliary Data Structures
   151 @ingroup datas
   152 \brief Auxiliary data structures implemented in LEMON.
   153 
   154 This group describes some data structures implemented in LEMON in
   155 order to make it easier to implement combinatorial algorithms.
   156 */
   157 
   158 
   159 /**
   160 @defgroup algs Algorithms
   161 \brief This group describes the several algorithms
   162 implemented in LEMON.
   163 
   164 This group describes the several algorithms
   165 implemented in LEMON.
   166 */
   167 
   168 /**
   169 @defgroup search Graph Search
   170 @ingroup algs
   171 \brief Common graph search algorithms.
   172 
   173 This group describes the common graph search algorithms like
   174 Breadth-first search (Bfs) and Depth-first search (Dfs).
   175 */
   176 
   177 /**
   178 @defgroup shortest_path Shortest Path algorithms
   179 @ingroup algs
   180 \brief Algorithms for finding shortest paths.
   181 
   182 This group describes the algorithms for finding shortest paths in graphs.
   183 */
   184 
   185 /**
   186 @defgroup spantree Minimum Spanning Tree algorithms
   187 @ingroup algs
   188 \brief Algorithms for finding a minimum cost spanning tree in a graph.
   189 
   190 This group describes the algorithms for finding a minimum cost spanning
   191 tree in a graph
   192 */
   193 
   194 /**
   195 @defgroup utils Tools and Utilities
   196 \brief Tools and utilities for programming in LEMON
   197 
   198 Tools and utilities for programming in LEMON.
   199 */
   200 
   201 /**
   202 @defgroup gutils Basic Graph Utilities
   203 @ingroup utils
   204 \brief Simple basic graph utilities.
   205 
   206 This group describes some simple basic graph utilities.
   207 */
   208 
   209 /**
   210 @defgroup misc Miscellaneous Tools
   211 @ingroup utils
   212 \brief Tools for development, debugging and testing.
   213 
   214 This group describes several useful tools for development,
   215 debugging and testing.
   216 */
   217 
   218 /**
   219 @defgroup timecount Time measuring and Counting
   220 @ingroup misc
   221 \brief Simple tools for measuring the performance of algorithms.
   222 
   223 This group describes simple tools for measuring the performance
   224 of algorithms.
   225 */
   226 
   227 /**
   228 @defgroup exceptions Exceptions
   229 @ingroup utils
   230 \brief Exceptions defined in LEMON.
   231 
   232 This group describes the exceptions defined in LEMON.
   233 */
   234 
   235 /**
   236 @defgroup io_group Input-Output
   237 \brief Graph Input-Output methods
   238 
   239 This group describes the tools for importing and exporting graphs
   240 and graph related data. Now it supports the LEMON format
   241 and the encapsulated postscript (EPS) format.
   242 */
   243 
   244 /**
   245 @defgroup lemon_io LEMON Input-Output
   246 @ingroup io_group
   247 \brief Reading and writing \ref lgf-format "LEMON Graph Format".
   248 
   249 This group describes methods for reading and writing
   250 \ref lgf-format "LEMON Graph Format".
   251 */
   252 
   253 /**
   254 @defgroup eps_io Postscript exporting
   255 @ingroup io_group
   256 \brief General \c EPS drawer and graph exporter
   257 
   258 This group describes general \c EPS drawing methods and special
   259 graph exporting tools.
   260 */
   261 
   262 
   263 /**
   264 @defgroup concept Concepts
   265 \brief Skeleton classes and concept checking classes
   266 
   267 This group describes the data/algorithm skeletons and concept checking
   268 classes implemented in LEMON.
   269 
   270 The purpose of the classes in this group is fourfold.
   271 
   272 - These classes contain the documentations of the concepts. In order
   273   to avoid document multiplications, an implementation of a concept
   274   simply refers to the corresponding concept class.
   275 
   276 - These classes declare every functions, <tt>typedef</tt>s etc. an
   277   implementation of the concepts should provide, however completely
   278   without implementations and real data structures behind the
   279   interface. On the other hand they should provide nothing else. All
   280   the algorithms working on a data structure meeting a certain concept
   281   should compile with these classes. (Though it will not run properly,
   282   of course.) In this way it is easily to check if an algorithm
   283   doesn't use any extra feature of a certain implementation.
   284 
   285 - The concept descriptor classes also provide a <em>checker class</em>
   286   that makes it possible to check whether a certain implementation of a
   287   concept indeed provides all the required features.
   288 
   289 - Finally, They can serve as a skeleton of a new implementation of a concept.
   290 
   291 */
   292 
   293 
   294 /**
   295 @defgroup graph_concepts Graph Structure Concepts
   296 @ingroup concept
   297 \brief Skeleton and concept checking classes for graph structures
   298 
   299 This group describes the skeletons and concept checking classes of LEMON's
   300 graph structures and helper classes used to implement these.
   301 */
   302 
   303 /**
   304 \anchor demoprograms
   305 
   306 @defgroup demos Demo programs
   307 
   308 Some demo programs are listed here. Their full source codes can be found in
   309 the \c demo subdirectory of the source tree.
   310 
   311 It order to compile them, use <tt>--enable-demo</tt> configure option when
   312 build the library.
   313 */