40 running time or on memory usage, some structures may fail to provide |
40 running time or on memory usage, some structures may fail to provide |
41 some graph features like arc/edge or node deletion. |
41 some graph features like arc/edge or node deletion. |
42 |
42 |
43 You are free to use the graph structure that fit your requirements |
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 |
44 the best, most graph algorithms and auxiliary data structures can be used |
45 with any graph structures. |
45 with any graph structure. |
|
46 |
|
47 <b>See also:</b> \ref graph_concepts "Graph Structure Concepts". |
46 */ |
48 */ |
47 |
49 |
48 /** |
50 /** |
49 @defgroup maps Maps |
51 @defgroup maps Maps |
50 @ingroup datas |
52 @ingroup datas |
51 \brief Map structures implemented in LEMON. |
53 \brief Map structures implemented in LEMON. |
52 |
54 |
53 This group describes the map structures implemented in LEMON. |
55 This group describes the map structures implemented in LEMON. |
54 |
56 |
55 LEMON provides several special purpose maps that e.g. combine |
57 LEMON provides several special purpose maps and map adaptors that e.g. combine |
56 new maps from existing ones. |
58 new maps from existing ones. |
|
59 |
|
60 <b>See also:</b> \ref map_concepts "Map Concepts". |
57 */ |
61 */ |
58 |
62 |
59 /** |
63 /** |
60 @defgroup graph_maps Graph Maps |
64 @defgroup graph_maps Graph Maps |
61 @ingroup maps |
65 @ingroup maps |
62 \brief Special graph-related maps. |
66 \brief Special graph-related maps. |
63 |
67 |
64 This group describes maps that are specifically designed to assign |
68 This group describes maps that are specifically designed to assign |
65 values to the nodes and arcs of graphs. |
69 values to the nodes and arcs of graphs. |
66 */ |
70 */ |
67 |
|
68 |
71 |
69 /** |
72 /** |
70 \defgroup map_adaptors Map Adaptors |
73 \defgroup map_adaptors Map Adaptors |
71 \ingroup maps |
74 \ingroup maps |
72 \brief Tools to create new maps from existing ones |
75 \brief Tools to create new maps from existing ones |
80 'not' etc.) or e.g. convert a map to another one of different Value type. |
83 'not' etc.) or e.g. convert a map to another one of different Value type. |
81 |
84 |
82 The typical usage of this classes is passing implicit maps to |
85 The typical usage of this classes is passing implicit maps to |
83 algorithms. If a function type algorithm is called then the function |
86 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 |
87 type map adaptors can be used comfortable. For example let's see the |
85 usage of map adaptors with the \c digraphToEps() function. |
88 usage of map adaptors with the \c graphToEps() function. |
86 \code |
89 \code |
87 Color nodeColor(int deg) { |
90 Color nodeColor(int deg) { |
88 if (deg >= 2) { |
91 if (deg >= 2) { |
89 return Color(0.5, 0.0, 0.5); |
92 return Color(0.5, 0.0, 0.5); |
90 } else if (deg == 1) { |
93 } else if (deg == 1) { |
94 } |
97 } |
95 } |
98 } |
96 |
99 |
97 Digraph::NodeMap<int> degree_map(graph); |
100 Digraph::NodeMap<int> degree_map(graph); |
98 |
101 |
99 digraphToEps(graph, "graph.eps") |
102 graphToEps(graph, "graph.eps") |
100 .coords(coords).scaleToA4().undirected() |
103 .coords(coords).scaleToA4().undirected() |
101 .nodeColors(composeMap(functorToMap(nodeColor), degree_map)) |
104 .nodeColors(composeMap(functorToMap(nodeColor), degree_map)) |
102 .run(); |
105 .run(); |
103 \endcode |
106 \endcode |
104 The \c functorToMap() function makes an \c int to \c Color map from the |
107 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 |
108 \c nodeColor() function. The \c composeMap() compose the \c degree_map |
106 and the previously created map. The composed map is a proper function to |
109 and the previously created map. The composed map is a proper function to |
107 get the color of each node. |
110 get the color of each node. |
108 |
111 |
109 The usage with class type algorithms is little bit harder. In this |
112 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 |
113 case the function type map adaptors can not be used, because the |
141 assignment operators and copy constructors. This makes it easy and |
144 assignment operators and copy constructors. This makes it easy and |
142 efficient to have e.g. the Dijkstra algorithm to store its result in |
145 efficient to have e.g. the Dijkstra algorithm to store its result in |
143 any kind of path structure. |
146 any kind of path structure. |
144 |
147 |
145 \sa lemon::concepts::Path |
148 \sa lemon::concepts::Path |
146 |
|
147 */ |
149 */ |
148 |
150 |
149 /** |
151 /** |
150 @defgroup auxdat Auxiliary Data Structures |
152 @defgroup auxdat Auxiliary Data Structures |
151 @ingroup datas |
153 @ingroup datas |
153 |
155 |
154 This group describes some data structures implemented in LEMON in |
156 This group describes some data structures implemented in LEMON in |
155 order to make it easier to implement combinatorial algorithms. |
157 order to make it easier to implement combinatorial algorithms. |
156 */ |
158 */ |
157 |
159 |
158 |
|
159 /** |
160 /** |
160 @defgroup algs Algorithms |
161 @defgroup algs Algorithms |
161 \brief This group describes the several algorithms |
162 \brief This group describes the several algorithms |
162 implemented in LEMON. |
163 implemented in LEMON. |
163 |
164 |
169 @defgroup search Graph Search |
170 @defgroup search Graph Search |
170 @ingroup algs |
171 @ingroup algs |
171 \brief Common graph search algorithms. |
172 \brief Common graph search algorithms. |
172 |
173 |
173 This group describes the common graph search algorithms like |
174 This group describes the common graph search algorithms like |
174 Breadth-first search (Bfs) and Depth-first search (Dfs). |
175 Breadth-First Search (BFS) and Depth-First Search (DFS). |
175 */ |
176 */ |
176 |
177 |
177 /** |
178 /** |
178 @defgroup shortest_path Shortest Path algorithms |
179 @defgroup shortest_path Shortest Path Algorithms |
179 @ingroup algs |
180 @ingroup algs |
180 \brief Algorithms for finding shortest paths. |
181 \brief Algorithms for finding shortest paths. |
181 |
182 |
182 This group describes the algorithms for finding shortest paths in graphs. |
183 This group describes the algorithms for finding shortest paths in graphs. |
183 */ |
184 */ |
184 |
185 |
185 /** |
186 /** |
186 @defgroup spantree Minimum Spanning Tree algorithms |
187 @defgroup spantree Minimum Spanning Tree Algorithms |
187 @ingroup algs |
188 @ingroup algs |
188 \brief Algorithms for finding a minimum cost spanning tree in a graph. |
189 \brief Algorithms for finding a minimum cost spanning tree in a graph. |
189 |
190 |
190 This group describes the algorithms for finding a minimum cost spanning |
191 This group describes the algorithms for finding a minimum cost spanning |
191 tree in a graph |
192 tree in a graph |
192 */ |
193 */ |
193 |
194 |
|
195 @ingroup algs |
194 /** |
196 /** |
195 @defgroup utils Tools and Utilities |
197 @defgroup utils Tools and Utilities |
196 \brief Tools and utilities for programming in LEMON |
198 \brief Tools and utilities for programming in LEMON |
197 |
199 |
198 Tools and utilities for programming in LEMON. |
200 Tools and utilities for programming in LEMON. |
214 This group describes several useful tools for development, |
216 This group describes several useful tools for development, |
215 debugging and testing. |
217 debugging and testing. |
216 */ |
218 */ |
217 |
219 |
218 /** |
220 /** |
219 @defgroup timecount Time measuring and Counting |
221 @defgroup timecount Time Measuring and Counting |
220 @ingroup misc |
222 @ingroup misc |
221 \brief Simple tools for measuring the performance of algorithms. |
223 \brief Simple tools for measuring the performance of algorithms. |
222 |
224 |
223 This group describes simple tools for measuring the performance |
225 This group describes simple tools for measuring the performance |
224 of algorithms. |
226 of algorithms. |
237 \brief Graph Input-Output methods |
239 \brief Graph Input-Output methods |
238 |
240 |
239 This group describes the tools for importing and exporting graphs |
241 This group describes the tools for importing and exporting graphs |
240 and graph related data. Now it supports the LEMON format |
242 and graph related data. Now it supports the LEMON format |
241 and the encapsulated postscript (EPS) format. |
243 and the encapsulated postscript (EPS) format. |
|
244 postscript (EPS) format. |
242 */ |
245 */ |
243 |
246 |
244 /** |
247 /** |
245 @defgroup lemon_io LEMON Input-Output |
248 @defgroup lemon_io LEMON Input-Output |
246 @ingroup io_group |
249 @ingroup io_group |
247 \brief Reading and writing \ref lgf-format "LEMON Graph Format". |
250 \brief Reading and writing LEMON Graph Format. |
248 |
251 |
249 This group describes methods for reading and writing |
252 This group describes methods for reading and writing |
250 \ref lgf-format "LEMON Graph Format". |
253 \ref lgf-format "LEMON Graph Format". |
251 */ |
254 */ |
252 |
255 |
253 /** |
256 /** |
254 @defgroup eps_io Postscript exporting |
257 @defgroup eps_io Postscript Exporting |
255 @ingroup io_group |
258 @ingroup io_group |
256 \brief General \c EPS drawer and graph exporter |
259 \brief General \c EPS drawer and graph exporter |
257 |
260 |
258 This group describes general \c EPS drawing methods and special |
261 This group describes general \c EPS drawing methods and special |
259 graph exporting tools. |
262 graph exporting tools. |
260 */ |
263 */ |
261 |
|
262 |
264 |
263 /** |
265 /** |
264 @defgroup concept Concepts |
266 @defgroup concept Concepts |
265 \brief Skeleton classes and concept checking classes |
267 \brief Skeleton classes and concept checking classes |
266 |
268 |
285 - The concept descriptor classes also provide a <em>checker class</em> |
287 - The concept descriptor classes also provide a <em>checker class</em> |
286 that makes it possible to check whether a certain implementation of a |
288 that makes it possible to check whether a certain implementation of a |
287 concept indeed provides all the required features. |
289 concept indeed provides all the required features. |
288 |
290 |
289 - Finally, They can serve as a skeleton of a new implementation of a concept. |
291 - Finally, They can serve as a skeleton of a new implementation of a concept. |
290 |
292 */ |
291 */ |
|
292 |
|
293 |
293 |
294 /** |
294 /** |
295 @defgroup graph_concepts Graph Structure Concepts |
295 @defgroup graph_concepts Graph Structure Concepts |
296 @ingroup concept |
296 @ingroup concept |
297 \brief Skeleton and concept checking classes for graph structures |
297 \brief Skeleton and concept checking classes for graph structures |
298 |
298 |
299 This group describes the skeletons and concept checking classes of LEMON's |
299 This group describes the skeletons and concept checking classes of LEMON's |
300 graph structures and helper classes used to implement these. |
300 graph structures and helper classes used to implement these. |
301 */ |
301 */ |
302 |
302 |
|
303 |
|
304 This group describes the skeletons and concept checking classes of maps. |
303 /** |
305 /** |
304 \anchor demoprograms |
306 \anchor demoprograms |
305 |
307 |
306 @defgroup demos Demo programs |
308 @defgroup demos Demo programs |
307 |
309 |