doc/groups.dox
author deba
Mon, 19 Feb 2007 18:21:28 +0000
changeset 2369 6ae1a97055a2
parent 2350 eb371753e814
child 2370 ed6539025f27
permissions -rw-r--r--
Naming convention changes

setObj => obj
is_min => isMin
is_max => isMax
     1 
     2 /**
     3 @defgroup datas Data Structures
     4 This group describes the several graph structures implemented in LEMON.
     5 */
     6 
     7 /**
     8 @defgroup graphs Graph Structures
     9 @ingroup datas
    10 \brief Graph structures implemented in LEMON.
    11 
    12 The implementation of combinatorial algorithms heavily relies on 
    13 efficient graph implementations. LEMON offers data structures which are 
    14 planned to be easily used in an experimental phase of implementation studies, 
    15 and thereafter the program code can be made efficient by small modifications. 
    16 
    17 The most efficient implementation of diverse applications require the
    18 usage of different physical graph implementations. These differences
    19 appear in the size of graph we require to handle, memory or time usage
    20 limitations or in the set of operations through which the graph can be
    21 accessed.  LEMON provides several physical graph structures to meet
    22 the diverging requirements of the possible users.  In order to save on
    23 running time or on memory usage, some structures may fail to provide
    24 some graph features like edge or node deletion.
    25 
    26 Alteration of standard containers need a very limited number of 
    27 operations, these together satisfy the everyday requirements. 
    28 In the case of graph structures, different operations are needed which do 
    29 not alter the physical graph, but gives another view. If some nodes or 
    30 edges have to be hidden or the reverse oriented graph have to be used, then 
    31 this is the case. It also may happen that in a flow implementation 
    32 the residual graph can be accessed by another algorithm, or a node-set 
    33 is to be shrunk for another algorithm. 
    34 LEMON also provides a variety of graphs for these requirements called 
    35 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only 
    36 in conjunction with other graph representation. 
    37 
    38 You are free to use the graph structure that fit your requirements
    39 the best, most graph algorithms and auxiliary data structures can be used
    40 with any graph structures. 
    41 */
    42 
    43 /**
    44 @defgroup semi_adaptors Semi-Adaptors Classes for Graphs
    45 @ingroup graphs
    46 \brief Graph types between real graphs and graph adaptors.
    47 
    48 Graph types between real graphs and graph adaptors. These classes wrap
    49 graphs to give new functionality as the adaptors do it. On the other
    50 hand they are not light-weight structures as the adaptors.
    51 */
    52 
    53 /**
    54 @defgroup maps Maps 
    55 @ingroup datas
    56 \brief Some special purpose map to make life easier.
    57 
    58 LEMON provides several special maps that e.g. combine
    59 new maps from existing ones.
    60 */
    61 
    62 /**
    63 @defgroup graph_maps Graph Maps 
    64 @ingroup maps
    65 \brief Special Graph-Related Maps.
    66 
    67 These maps are specifically designed to assign values to the nodes and edges of
    68 graphs.
    69 */
    70 
    71 
    72 /**
    73 \defgroup map_adaptors Map Adaptors
    74 \ingroup maps
    75 \brief Tools to create new maps from existing ones
    76 
    77 Map adaptors are used to create "implicit" maps from other maps.
    78 
    79 Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can
    80 make arithmetic operations between one or two maps (negation, scaling,
    81 addition, multiplication etc.) or e.g. convert a map to another one
    82 of different Value type.
    83 */
    84 
    85 /**
    86 @defgroup matrices Matrices 
    87 @ingroup datas
    88 \brief Two dimensional data storages.
    89 
    90 Two dimensional data storages.
    91 */
    92 
    93 /**
    94 @defgroup paths Path Structures
    95 @ingroup datas
    96 \brief Path structures implemented in LEMON.
    97 
    98 LEMON provides flexible data structures
    99 to work with paths.
   100 
   101 All of them have the same interface, especially they can be built or extended
   102 using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
   103 algorithm to store its result in any kind of path structure.
   104 
   105 \sa lemon::concepts::Path
   106 
   107 */
   108 
   109 /**
   110 @defgroup auxdat Auxiliary Data Structures
   111 @ingroup datas
   112 \brief Some data structures implemented in LEMON.
   113 
   114 This group describes the data structures implemented in LEMON in
   115 order to make it easier to implement combinatorial algorithms.
   116 */
   117 
   118 /**
   119 @defgroup graphbits Tools to Make It Easier to Make Graphs
   120 @ingroup auxdat
   121 \brief Tools to Make It Easier to Make Graphs.
   122 
   123 This group describes the tools that makes it easier to make graphs and
   124 the maps that dynamically update with the graph changes.
   125 */
   126 
   127 /**
   128 @defgroup algs Algorithms
   129 \brief This group describes the several algorithms
   130 implemented in LEMON.
   131 
   132 This group describes the several algorithms
   133 implemented in LEMON.
   134 */
   135 
   136 /**
   137 @defgroup gutils Basic Graph Utilities
   138 @ingroup algs
   139 \brief This group describes some simple basic graph utilities.
   140 
   141 This group describes some simple basic graph utilities.
   142 */
   143 
   144 /**
   145 @defgroup flowalgs Path and Flow Algorithms
   146 @ingroup algs
   147 \brief This group describes the algorithms
   148 for finding paths and flows in graphs.
   149 
   150 This group describes the algorithms
   151 for finding paths and flows in graphs.
   152 
   153 \image html flow.png
   154 \image latex flow.eps "Graph flow" width=\textwidth
   155 */
   156 
   157 /**
   158 @defgroup topology Topology related algorithms
   159 @ingroup algs
   160 \brief This group describes the algorithms
   161 for discover the topology of the graphs.
   162 
   163 This group describes the algorithms
   164 for discover the topology of the graphs.
   165 
   166 \image html edge_biconnected_components.png
   167 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
   168 
   169 */
   170 
   171 /**
   172 @defgroup matching Matching algorithms in graphs and bipartite graphs
   173 @ingroup algs
   174 \brief This group describes the algorithms
   175 for find matchings in graphs and bipartite graphs.
   176 
   177 This group provides some algorithm objects and function
   178 to calculate matchings in graphs and bipartite graphs.
   179 
   180 \image html bipartite_matching.png
   181 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
   182 
   183 */
   184 
   185 /**
   186 @defgroup spantree Minimum Cost Spanning Tree Algorithms
   187 @ingroup algs
   188 \brief This group contains the algorithms for finding a minimum cost spanning
   189 tree in a graph
   190 
   191 This group contains the algorithms for finding a minimum cost spanning
   192 tree in a graph
   193 */
   194 
   195 
   196 /**
   197 @defgroup auxalg Auxiliary Algorithms
   198 @ingroup algs
   199 \brief Some algorithms implemented in LEMON.
   200 
   201 This group describes the algorithms in LEMON in order to make 
   202 it easier to implement complex algorithms.
   203 
   204 */
   205 
   206 /**
   207 @defgroup gen_opt_group General Optimization Tools
   208 \brief This group describes some general optimization frameworks
   209 implemented in LEMON.
   210 
   211 This group describes some general optimization frameworks
   212 implemented in LEMON.
   213 
   214 */
   215 
   216 /** 
   217 \ingroup gen_opt_group 
   218 @defgroup gen_opt_tools Various Tools for Optimization 
   219 \brief This group adds some helper tools to general optimization
   220 framework implemented in LEMON.
   221 
   222 This group adds some helper tools to general optimization framework
   223 implemented in LEMON.
   224 
   225 */
   226 
   227 /**
   228 @defgroup misc Miscellaneous Tools
   229 Here you can find several useful tools for development,
   230 debugging and testing.
   231 */
   232 
   233 /**
   234 @defgroup timecount Time measuring and Counting
   235 @ingroup misc
   236 Here you can find simple tools for measuring the performance
   237 of algorithms.
   238 */
   239 
   240 /**
   241 @defgroup io_group Input-Output
   242 \brief Several Graph Input-Output methods
   243 
   244 Here you can find tools for importing and exporting graphs 
   245 and graph related data. Now it supports the LEMON format, the
   246 \c DIMACS format and the encapsulated postscript format.
   247 */
   248 
   249 /**
   250 @defgroup lemon_io Lemon Input-Output
   251 @ingroup io_group
   252 \brief Reading and writing LEMON format
   253 
   254 Methods for reading and writing LEMON format. More about this
   255 format you can find on the \ref graph-io-page "Graph Input-Output"
   256 tutorial pages.
   257 
   258 */
   259 
   260 /**
   261 @defgroup section_io Section readers and writers
   262 @ingroup lemon_io
   263 \brief Section readers and writers for lemon Input-Output.
   264 
   265 Here you can find which section readers and writers can attach to
   266 the LemonReader and LemonWriter.
   267 */
   268 
   269 /**
   270 @defgroup item_io Item Readers and Writers
   271 @ingroup lemon_io
   272 \brief Item readers and writers for lemon Input-Output.
   273 
   274 The Input-Output classes can handle more data type by example
   275 as map or attribute value. Each of these should be written and
   276 read some way. The module make possible to do this.  
   277 */
   278 
   279 /**
   280 @defgroup eps_io Postscript exporting
   281 @ingroup io_group
   282 \brief General \c EPS drawer and graph exporter
   283 
   284 This group contains general \c EPS drawing methods and special
   285 graph exporting tools. 
   286 */
   287 
   288 /**
   289 @defgroup exceptions Exceptions
   290 This group contains the exceptions thrown by LEMON library
   291 */
   292 
   293 /**
   294 @defgroup concept Concepts
   295 \brief Skeleton classes and concept checking classes
   296 
   297 This group describes the data/algorithm skeletons and concept checking
   298 classes implemented in LEMON.
   299 
   300 The purpose of the classes in this group is fourfold.
   301  
   302 - These classes contain the documentations of the concepts. In order
   303   to avoid document multiplications, an implementation of a concept
   304   simply refers to the corresponding concept class.
   305 
   306 - These classes declare every functions, <tt>typedef</tt>s etc. an
   307   implementation of the concepts should provide, however completely
   308   without implementations and real data structures behind the
   309   interface. On the other hand they should provide nothing else. All
   310   the algorithms working on a data structure meeting a certain concept
   311   should compile with these classes. (Though it will not run properly,
   312   of course.) In this way it is easily to check if an algorithm
   313   doesn't use any extra feature of a certain implementation.
   314 
   315 - The concept descriptor classes also provide a <em>checker class</em>
   316   that makes it possible check whether a certain implementation of a
   317   concept indeed provides all the required features.
   318 
   319 - Finally, They can serve as a skeleton of a new implementation of a concept.
   320 
   321 */
   322 
   323 
   324 /**
   325 @defgroup graph_concepts Graph Structure Concepts
   326 @ingroup concept
   327 \brief Skeleton and concept checking classes for graph structures
   328 
   329 This group contains the skeletons and concept checking classes of LEMON's
   330 graph structures and helper classes used to implement these.
   331 */
   332 
   333 /* --- Unused group
   334 @defgroup experimental Experimental Structures and Algorithms
   335 This group contains some Experimental structures and algorithms.
   336 The stuff here is subject to change.
   337 */
   338 
   339 /**
   340 \anchor demoprograms
   341 
   342 @defgroup demos Demo programs
   343 
   344 Some demo programs are listed here. Their full source codes can be found in
   345 the \c demo subdirectory of the source tree.
   346 
   347 The standard compilation procedure (<tt>./configure;make</tt>) will compile
   348 them, as well. 
   349 
   350 */
   351