33 \e map \e adaptor \e classes, which perform various operations on the |
33 \e map \e adaptor \e classes, which perform various operations on the |
34 data of the adapted maps when their access operations are called, |
34 data of the adapted maps when their access operations are called, |
35 but without actually copying or modifying the original storage. |
35 but without actually copying or modifying the original storage. |
36 These classes also conform to the map %concepts, thus they can be used |
36 These classes also conform to the map %concepts, thus they can be used |
37 like standard LEMON maps. |
37 like standard LEMON maps. |
38 |
|
39 Let us suppose that we have a traffic network stored in a LEMON digraph |
|
40 structure with two arc maps \c length and \c speed, which |
|
41 denote the physical length of each arc and the maximum (or average) |
|
42 speed that can be achieved on the corresponding road-section, |
|
43 respectively. If we are interested in the best traveling times, |
|
44 the following code can be used. |
|
45 |
|
46 \code |
|
47 dijkstra(g, divMap(length, speed)).distMap(dist).run(s); |
|
48 \endcode |
|
49 |
|
50 |
38 |
51 Maps play a central role in LEMON. As their name suggests, they map a |
39 Maps play a central role in LEMON. As their name suggests, they map a |
52 certain range of \e keys to certain \e values. Each map has two |
40 certain range of \e keys to certain \e values. Each map has two |
53 <tt>typedef</tt>'s to determine the types of keys and values, like this: |
41 <tt>typedef</tt>'s to determine the types of keys and values, like this: |
54 |
42 |
333 See \ref map_adaptors in the reference manual. |
321 See \ref map_adaptors in the reference manual. |
334 |
322 |
335 |
323 |
336 [SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps |
324 [SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps |
337 |
325 |
|
326 |
338 The basic functionality of the algorithms can be highly extended using |
327 The basic functionality of the algorithms can be highly extended using |
339 special purpose map types for their internal data structures. |
328 special purpose map types for their internal data structures. |
340 For example, the \ref Dijkstra class stores a |
329 For example, the \ref Dijkstra class stores a |
341 ef ProcessedMap, |
330 ef ProcessedMap, |
342 which has to be a writable node map of \ref bool value type. |
331 which has to be a writable node map of \ref bool value type. |
347 |
336 |
348 Such specific map types can be passed to the algorithms using the technique of |
337 Such specific map types can be passed to the algorithms using the technique of |
349 named template parameters. Similarly to the named function parameters, |
338 named template parameters. Similarly to the named function parameters, |
350 they allow specifying any subset of the parameters and in arbitrary order. |
339 they allow specifying any subset of the parameters and in arbitrary order. |
351 |
340 |
|
341 Let us suppose that we have a traffic network stored in a LEMON digraph |
|
342 structure with two arc maps \c length and \c speed, which |
|
343 denote the physical length of each arc and the maximum (or average) |
|
344 speed that can be achieved on the corresponding road-section, |
|
345 respectively. If we are interested in the best traveling times, |
|
346 the following code can be used. |
|
347 |
|
348 \code |
|
349 dijkstra(g, divMap(length, speed)).distMap(dist).run(s); |
|
350 \endcode |
|
351 |
352 \code |
352 \code |
353 typedef vector<ListDigraph::Node> Container; |
353 typedef vector<ListDigraph::Node> Container; |
354 typedef back_insert_iterator<Container> InsertIterator; |
354 typedef back_insert_iterator<Container> InsertIterator; |
355 typedef LoggerBoolMap<InsertIterator> ProcessedMap; |
355 typedef LoggerBoolMap<InsertIterator> ProcessedMap; |
356 Dijkstra<ListDigraph> |
356 Dijkstra<ListDigraph> |
375 vector<ListDigraph::Node> process_order; |
375 vector<ListDigraph::Node> process_order; |
376 dijkstra(g, length) |
376 dijkstra(g, length) |
377 .processedMap(loggerBoolMap(back_inserter(process_order))) |
377 .processedMap(loggerBoolMap(back_inserter(process_order))) |
378 .run(s); |
378 .run(s); |
379 \endcode |
379 \endcode |
|
380 |
|
381 Let us see a bit more complex example to demonstrate Dfs's capabilities. |
|
382 |
|
383 We will see a program, which solves the problem of <b>topological ordering</b>. |
|
384 We need to know in which order we should put on our clothes. The program will do the following: |
|
385 <ol> |
|
386 <li>We run the dfs algorithm to all nodes. |
|
387 <li>Put every node into a list when processed completely. |
|
388 <li>Write out the list in reverse order. |
|
389 </ol> |
|
390 |
|
391 \dontinclude topological_ordering.cc |
|
392 First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering |
|
393 will be done through it. |
|
394 \skip MyOrdererMap |
|
395 \until }; |
|
396 The class meets the \ref concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing |
|
397 we need to do is insert the key - that is the node whose processing just finished - into the beginning |
|
398 of the list.<br> |
|
399 Although we implemented this needed helper class ourselves it was not necessary. |
|
400 The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly |
|
401 what we needed. To be correct it's more general - and it's all in \c LEMON. But |
|
402 we wanted to show you, how easy is to add additional functionality. |
|
403 |
|
404 First we declare the needed data structures: the digraph and a map to store the nodes' label. |
|
405 \skip ListDigraph |
|
406 \until label |
|
407 |
|
408 Now we build a digraph. But keep in mind that it must be DAG because cyclic digraphs has no topological |
|
409 ordering. |
|
410 \skip belt |
|
411 \until trousers |
|
412 We label them... |
|
413 \skip label |
|
414 \until trousers |
|
415 Then add arcs which represent the precedences between those items. |
|
416 \skip trousers, belt |
|
417 \until ); |
|
418 |
|
419 See how easy is to access the internal information of this algorithm trough maps. |
|
420 We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap". |
|
421 \skip Dfs |
|
422 \until run |
|
423 |
|
424 And now comes the third part. Write out the list in reverse order. But the list was |
|
425 composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it. |
|
426 \skip std |
|
427 \until endl |
|
428 |
|
429 The program is to be found in the \ref demo directory: \ref topological_ordering.cc |
380 |
430 |
381 LEMON also contains visitor based algorithm classes for |
431 LEMON also contains visitor based algorithm classes for |
382 BFS and DFS. |
432 BFS and DFS. |
383 |
433 |
384 Skeleton visitor classes are defined for both BFS and DFS, the concrete |
434 Skeleton visitor classes are defined for both BFS and DFS, the concrete |