summary |
shortlog |
changelog |
graph |
tags |
bookmarks |
branches |
files |
changeset |
file |
latest |
revisions |
annotate |
diff |
comparison |
raw |
help

doc/groups.dox

author | Alpar Juttner <alpar@cs.elte.hu> |

Thu, 04 Dec 2008 10:49:54 +0000 | |

branch | 1.0 |

changeset 344 | e562b69acbc6 |

parent 323 | 2592532ee838 |

parent 325 | 1e2d6ca80793 |

child 427 | c59bdcc8e33e |

permissions | -rw-r--r-- |

Bugfix in DfsVisit (the same fix as in [9afe81e4c543] for the main br.) #61

- The stop() must be called in DfsVisit if there are no outgoing

arcs from the newly added node

- The stop() must be called in DfsVisit if there are no outgoing

arcs from the newly added node

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 */

19 /**

20 @defgroup datas Data Structures

21 This group describes the several data structures implemented in LEMON.

22 */

24 /**

25 @defgroup graphs Graph Structures

26 @ingroup datas

27 \brief Graph structures implemented in LEMON.

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.

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.

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.

47 <b>See also:</b> \ref graph_concepts "Graph Structure Concepts".

48 */

50 /**

51 @defgroup maps Maps

52 @ingroup datas

53 \brief Map structures implemented in LEMON.

55 This group describes the map structures implemented in LEMON.

57 LEMON provides several special purpose maps and map adaptors that e.g. combine

58 new maps from existing ones.

60 <b>See also:</b> \ref map_concepts "Map Concepts".

61 */

63 /**

64 @defgroup graph_maps Graph Maps

65 @ingroup maps

66 \brief Special graph-related maps.

68 This group describes maps that are specifically designed to assign

69 values to the nodes and arcs of graphs.

70 */

72 /**

73 \defgroup map_adaptors Map Adaptors

74 \ingroup maps

75 \brief Tools to create new maps from existing ones

77 This group describes map adaptors that are used to create "implicit"

78 maps from other maps.

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.

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 }

100 Digraph::NodeMap<int> degree_map(graph);

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.

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;

118 typedef Digraph::ArcMap<double> DoubleArcMap;

119 DoubleArcMap length(graph);

120 DoubleArcMap speed(graph);

122 typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;

123 TimeMap time(length, speed);

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 */

135 /**

136 @defgroup paths Path Structures

137 @ingroup datas

138 \brief %Path structures implemented in LEMON.

140 This group describes the path structures implemented in LEMON.

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.

148 \sa lemon::concepts::Path

149 */

151 /**

152 @defgroup auxdat Auxiliary Data Structures

153 @ingroup datas

154 \brief Auxiliary data structures implemented in LEMON.

156 This group describes some data structures implemented in LEMON in

157 order to make it easier to implement combinatorial algorithms.

158 */

160 /**

161 @defgroup algs Algorithms

162 \brief This group describes the several algorithms

163 implemented in LEMON.

165 This group describes the several algorithms

166 implemented in LEMON.

167 */

169 /**

170 @defgroup search Graph Search

171 @ingroup algs

172 \brief Common graph search algorithms.

174 This group describes the common graph search algorithms like

175 Breadth-First Search (BFS) and Depth-First Search (DFS).

176 */

178 /**

179 @defgroup shortest_path Shortest Path Algorithms

180 @ingroup algs

181 \brief Algorithms for finding shortest paths.

183 This group describes the algorithms for finding shortest paths in graphs.

184 */

186 /**

187 @defgroup spantree Minimum Spanning Tree Algorithms

188 @ingroup algs

189 \brief Algorithms for finding a minimum cost spanning tree in a graph.

191 This group describes the algorithms for finding a minimum cost spanning

192 tree in a graph

193 */

195 /**

196 @defgroup utils Tools and Utilities

197 \brief Tools and utilities for programming in LEMON

199 Tools and utilities for programming in LEMON.

200 */

202 /**

203 @defgroup gutils Basic Graph Utilities

204 @ingroup utils

205 \brief Simple basic graph utilities.

207 This group describes some simple basic graph utilities.

208 */

210 /**

211 @defgroup misc Miscellaneous Tools

212 @ingroup utils

213 \brief Tools for development, debugging and testing.

215 This group describes several useful tools for development,

216 debugging and testing.

217 */

219 /**

220 @defgroup timecount Time Measuring and Counting

221 @ingroup misc

222 \brief Simple tools for measuring the performance of algorithms.

224 This group describes simple tools for measuring the performance

225 of algorithms.

226 */

228 /**

229 @defgroup exceptions Exceptions

230 @ingroup utils

231 \brief Exceptions defined in LEMON.

233 This group describes the exceptions defined in LEMON.

234 */

236 /**

237 @defgroup io_group Input-Output

238 \brief Graph Input-Output methods

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 */

246 /**

247 @defgroup lemon_io LEMON Input-Output

248 @ingroup io_group

249 \brief Reading and writing LEMON Graph Format.

251 This group describes methods for reading and writing

252 \ref lgf-format "LEMON Graph Format".

253 */

255 /**

256 @defgroup eps_io Postscript Exporting

257 @ingroup io_group

258 \brief General \c EPS drawer and graph exporter

260 This group describes general \c EPS drawing methods and special

261 graph exporting tools.

262 */

264 /**

265 @defgroup concept Concepts

266 \brief Skeleton classes and concept checking classes

268 This group describes the data/algorithm skeletons and concept checking

269 classes implemented in LEMON.

271 The purpose of the classes in this group is fourfold.

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.

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.

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.

290 - Finally, They can serve as a skeleton of a new implementation of a concept.

291 */

293 /**

294 @defgroup graph_concepts Graph Structure Concepts

295 @ingroup concept

296 \brief Skeleton and concept checking classes for graph structures

298 This group describes the skeletons and concept checking classes of LEMON's

299 graph structures and helper classes used to implement these.

300 */

302 /**

303 @defgroup map_concepts Map Concepts

304 @ingroup concept

305 \brief Skeleton and concept checking classes for maps

307 This group describes the skeletons and concept checking classes of maps.

308 */

310 /**

311 \anchor demoprograms

313 @defgroup demos Demo programs

315 Some demo programs are listed here. Their full source codes can be found in

316 the \c demo subdirectory of the source tree.

318 It order to compile them, use <tt>--enable-demo</tt> configure option when

319 build the library.

320 */