[2391] | 1 | /* -*- C++ -*- |
---|
| 2 | * |
---|
| 3 | * This file is a part of LEMON, a generic C++ optimization library |
---|
| 4 | * |
---|
| 5 | * Copyright (C) 2003-2007 |
---|
| 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 | */ |
---|
| 18 | |
---|
[2216] | 19 | namespace lemon { |
---|
[2196] | 20 | /** |
---|
| 21 | \page algorithms Algorithms |
---|
| 22 | |
---|
[2216] | 23 | \section algo_bfs_dfs Bfs/Dfs |
---|
| 24 | Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient |
---|
| 25 | implementations of the well known algorithms. The algorithms are placed most cases in |
---|
| 26 | separated files named after the algorithm itself but lower case as all other header file names. |
---|
| 27 | For example the next Bfs class is in the \c lemon/bfs.h. |
---|
| 28 | |
---|
| 29 | \subsection Bfs |
---|
| 30 | The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function. |
---|
[2408] | 31 | The class has two template parameters: \b GR and \b TR.<br> |
---|
[2216] | 32 | GR is the graph the algorithm runs on. It has \ref lemon::ListGraph "ListGraph" as default type. |
---|
| 33 | TR is a Traits class commonly used to easy the parametrization of templates. In most cases you |
---|
| 34 | wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits<GR>". |
---|
| 35 | |
---|
| 36 | To use the class, declare it! |
---|
| 37 | \code |
---|
| 38 | Bfs<ListUGraph> bfs(gr); |
---|
| 39 | \endcode |
---|
| 40 | Note the lack of second template argument because of the default parameter. |
---|
| 41 | |
---|
| 42 | It provides a simple but powerful interface to control the execution. |
---|
| 43 | \code |
---|
| 44 | int dist = bfs.run(s,t); |
---|
| 45 | \endcode |
---|
| 46 | It finds the shortest path from node \c s to node \c t and returns it, or zero |
---|
| 47 | if there is no path from \c s to \c t.<br> |
---|
| 48 | If you want the shortest path from a specified node to all other node, just write: |
---|
| 49 | \code |
---|
| 50 | bfs.run(s); |
---|
| 51 | \endcode |
---|
| 52 | Now the distances and path information are stored in maps which you can access with |
---|
| 53 | member functions like \ref lemon::Bfs::distMap "distMap()" or \ref lemon::Bfs::predMap "predMap()".<br> |
---|
[2408] | 54 | Or more directly with other member functions like \ref lemon::Bfs::predNode "predNode()". Once the algorithm |
---|
[2216] | 55 | is finished (or to be precise reached that node) \ref lemon::Bfs::dist "dist()" or \ref lemon::Bfs::predNode |
---|
| 56 | "predNode()" can be called. |
---|
| 57 | |
---|
| 58 | For an example let's say we want to print the shortest path of those nodes which |
---|
| 59 | are in a certain distance. |
---|
| 60 | \code |
---|
| 61 | bfs.run(s); |
---|
| 62 | |
---|
| 63 | for( ListUGraph::NodeIt n(gr); n != INVALID; ++n ) { |
---|
| 64 | if( bfs.reached(n) && bfs.dist(n) <= max_dist ) { |
---|
| 65 | std::cout << gr.id(n); |
---|
| 66 | |
---|
| 67 | Node prev = bfs.prevNode(n); |
---|
| 68 | while( prev != INVALID ) { |
---|
| 69 | std::cout << "<-" << gr.id(prev); |
---|
| 70 | prev = bfs.prevNode(n); |
---|
| 71 | } |
---|
| 72 | |
---|
| 73 | std::cout << std::endl; |
---|
| 74 | } |
---|
| 75 | } |
---|
| 76 | \endcode |
---|
| 77 | |
---|
| 78 | \subsubsection bfs_adv_control Advanced control |
---|
| 79 | In the previous code we only used \c run(). Now we introduce the way you can directly |
---|
| 80 | control the execution of the algorithm. |
---|
| 81 | |
---|
| 82 | First you have to initialize the variables with \ref lemon::Bfs::init "init()". |
---|
| 83 | \code |
---|
| 84 | bfs.init(); |
---|
| 85 | \endcode |
---|
| 86 | |
---|
| 87 | Then you add one or more source nodes to the queue. They will be processed, as they would |
---|
| 88 | be reached by the algorithm before. And yes - you can add more sources during the execution. |
---|
| 89 | \code |
---|
| 90 | bfs.addSource(node_1); |
---|
| 91 | bfs.addSource(node_2); |
---|
| 92 | ... |
---|
| 93 | \endcode |
---|
| 94 | |
---|
| 95 | And finally you can start the process with \ref lemon::Bfs::start "start()", or |
---|
| 96 | you can write your own loop to process the nodes one-by-one. |
---|
| 97 | |
---|
[2470] | 98 | \todo Demo for Bfs advanced control. |
---|
[2216] | 99 | |
---|
| 100 | \subsection Dfs |
---|
| 101 | Since Dfs is very similar to Bfs with a few tiny differences we only see a bit more complex example |
---|
| 102 | to demonstrate Dfs's capabilities. |
---|
| 103 | |
---|
| 104 | We will see a program, which solves the problem of <b>topological ordering</b>. |
---|
| 105 | We need to know in which order we should put on our clothes. The program will do the following: |
---|
| 106 | <ol> |
---|
| 107 | <li>We run the dfs algorithm to all nodes. |
---|
| 108 | <li>Put every node into a list when processed completely. |
---|
| 109 | <li>Write out the list in reverse order. |
---|
| 110 | </ol> |
---|
| 111 | |
---|
| 112 | \dontinclude topological_ordering.cc |
---|
| 113 | First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering |
---|
| 114 | will be done through it. |
---|
[2281] | 115 | \skip MyOrdererMap |
---|
[2216] | 116 | \until }; |
---|
| 117 | The class meets the \ref lemon::WriteMap "WriteMap" concept. In it's \c set() method the only thing |
---|
[2408] | 118 | we need to do is insert the key - that is the node whose processing just finished - into the beginning |
---|
[2281] | 119 | of the list.<br> |
---|
| 120 | Although we implemented this needed helper class ourselves it was not necessary. |
---|
| 121 | The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly |
---|
| 122 | what we needed. To be correct it's more general - and it's all in \c LEMON. But |
---|
| 123 | we wanted to show you, how easy is to add additional functionality. |
---|
[2216] | 124 | |
---|
| 125 | First we declare the needed data structures: the graph and a map to store the nodes' label. |
---|
| 126 | \skip ListGraph |
---|
| 127 | \until label |
---|
| 128 | |
---|
| 129 | Now we build a graph. But keep in mind that it must be DAG because cyclic graphs has no topological |
---|
| 130 | ordering. |
---|
| 131 | \skip belt |
---|
| 132 | \until trousers |
---|
| 133 | We label them... |
---|
| 134 | \skip label |
---|
| 135 | \until trousers |
---|
| 136 | Then add directed edges which represent the precedences between those items. |
---|
| 137 | \skip trousers, belt |
---|
| 138 | \until ); |
---|
| 139 | |
---|
| 140 | See how easy is to access the internal information of this algorithm trough maps. |
---|
| 141 | We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap". |
---|
| 142 | \skip Dfs |
---|
| 143 | \until run |
---|
| 144 | |
---|
| 145 | And now comes the third part. Write out the list in reverse order. But the list was |
---|
| 146 | composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it. |
---|
| 147 | \skip std |
---|
| 148 | \until endl |
---|
| 149 | |
---|
| 150 | The program is to be found in the \ref demo directory: \ref topological_ordering.cc |
---|
[2281] | 151 | |
---|
[2470] | 152 | \todo Check the linking of the demo file, the code samples are missing. |
---|
| 153 | |
---|
[2281] | 154 | More algorithms are described in the \ref algorithms2 "second part". |
---|
[2196] | 155 | */ |
---|
[2216] | 156 | } |
---|