doc/groups.dox
author deba
Wed, 06 Sep 2006 11:17:12 +0000
changeset 2205 c20b0eb92a33
parent 2084 59769591eb60
child 2233 b3abb7ed76a8
permissions -rw-r--r--
UnionFind
Changing the representation of the union-find
it has the same running time but it takes just 2/3 space
! does not auto insert items /performance/

UnionFindEnum
Changing the interface - more convenient to UnionFind
Does not based on the stl data structures /it could be disadvantage/
=> does not use singular iterator assignment /not stl conform, but always work/
Just new iterator interface

MaxMatching + UnionFindTest
Using new iterator interface instead of the old
     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::concept::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::concept::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 General Graph Utilities
   138 @ingroup algs
   139 \brief This group describes some simple general graph utilities.
   140 
   141 This group describes some simple general 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 @defgroup misc Miscellaneous Tools
   218 Here you can find several useful tools for development,
   219 debugging and testing.
   220 */
   221 
   222 /**
   223 @defgroup timecount Time measuring and Counting
   224 @ingroup misc
   225 Here you can find simple tools for measuring the performance
   226 of algorithms.
   227 */
   228 
   229 /**
   230 @defgroup io_group Input-Output
   231 \brief Several Graph Input-Output methods
   232 
   233 Here you can find tools for importing and exporting graphs 
   234 and graph related data. Now it supports the LEMON format, the
   235 \c DIMACS format and the encapsulated postscript format.
   236 */
   237 
   238 /**
   239 @defgroup lemon_io Lemon Input-Output
   240 @ingroup io_group
   241 \brief Reading and writing LEMON format
   242 
   243 Methods for reading and writing LEMON format. More about this
   244 format you can find on the \ref graph-io-page "Graph Input-Output"
   245 tutorial pages.
   246 
   247 */
   248 
   249 /**
   250 @defgroup section_io Section readers and writers
   251 @ingroup lemon_io
   252 \brief Section readers and writers for lemon Input-Output.
   253 
   254 Here you can find which section readers and writers can attach to
   255 the LemonReader and LemonWriter.
   256 */
   257 
   258 /**
   259 @defgroup item_io Item Readers and Writers
   260 @ingroup lemon_io
   261 \brief Item readers and writers for lemon Input-Output.
   262 
   263 The Input-Output classes can handle more data type by example
   264 as map or attribute value. Each of these should be written and
   265 read some way. The module make possible to do this.  
   266 */
   267 
   268 /**
   269 @defgroup eps_io Postscript exporting
   270 @ingroup io_group
   271 \brief General \c EPS drawer and graph exporter
   272 
   273 This group contains general \c EPS drawing methods and special
   274 graph exporting tools. 
   275 */
   276 
   277 /**
   278 @defgroup exceptions Exceptions
   279 This group contains the exceptions thrown by LEMON library
   280 */
   281 
   282 /**
   283 @defgroup concept Concepts
   284 \brief Skeleton classes and concept checking classes
   285 
   286 This group describes the data/algorithm skeletons and concept checking
   287 classes implemented in LEMON.
   288 
   289 The purpose of the classes in this group is fourfold.
   290  
   291 - These classes contain the documentations of the concepts. In order
   292   to avoid document multiplications, an implementation of a concept
   293   simply refers to the corresponding concept class.
   294 
   295 - These classes declare every functions, <tt>typedef<tt>s etc. an
   296   implementation of the concepts should provide, however completely
   297   without implementations and real data structures behind the
   298   interface. On the other hand they should provide nothing else. All
   299   the algorithms working on a data structure meeting a certain concept
   300   should compile with these classes. (Though it will not run properly,
   301   of course.) In this way it is easily to check if an algorithm
   302   doesn't use any extra feature of a certain implementation.
   303 
   304 - The concept descriptor classes also provide a <em>checker class<em>
   305   that makes it possible check whether a certain implementation of a
   306   concept indeed provides all the required features.
   307 
   308 - Finally, They can serve as a skeleton of a new implementation of a concept.
   309 
   310 */
   311 
   312 
   313 /**
   314 @defgroup graph_concepts Graph Structure Concepts
   315 @ingroup concept
   316 \brief Skeleton and concept checking classes for graph structures
   317 
   318 This group contains the skeletons and concept checking classes of LEMON's
   319 graph structures and helper classes used to implement these.
   320 */
   321 
   322 /* --- Unused group
   323 @defgroup experimental Experimental Structures and Algorithms
   324 This group contains some Experimental structures and algorithms.
   325 The stuff here is subject to change.
   326 */
   327 
   328 /**
   329 \anchor demoprograms
   330 
   331 @defgroup demos Demo programs
   332 
   333 Some demo programs are listed here. Their full source codes can be found in
   334 the \c demo subdirectory of the source tree.
   335 
   336 The standard compilation procedure (<tt>./configure;make</tt>) will compile
   337 them, as well. 
   338 
   339 */
   340