1 /** |
1 /** |
2 |
2 |
3 \page quicktour Quick Tour to LEMON |
3 \page quicktour Quick Tour to LEMON |
4 |
4 |
5 Let us first answer the question <b>"What do I want to use LEMON for?" |
5 Let us first answer the question <b>"What do I want to use LEMON for?"</b>. |
6 </b>. |
|
7 LEMON is a C++ library, so you can use it if you want to write C++ |
6 LEMON is a C++ library, so you can use it if you want to write C++ |
8 programs. What kind of tasks does the library LEMON help to solve? |
7 programs. What kind of tasks does the library LEMON help to solve? |
9 It helps to write programs that solve optimization problems that arise |
8 It helps to write programs that solve optimization problems that arise |
10 frequently when <b>designing and testing certain networks</b>, for example |
9 frequently when <b>designing and testing certain networks</b>, for example |
11 in telecommunication, computer networks, and other areas that I cannot |
10 in telecommunication, computer networks, and other areas that I cannot |
144 <li> If you want to design a network and want to minimize the total |
143 <li> If you want to design a network and want to minimize the total |
145 length of wires then you might be looking for a <b>minimum spanning |
144 length of wires then you might be looking for a <b>minimum spanning |
146 tree</b> in an undirected graph. This can be found using the Kruskal |
145 tree</b> in an undirected graph. This can be found using the Kruskal |
147 algorithm: the function \ref lemon::kruskal "LEMON Kruskal " does |
146 algorithm: the function \ref lemon::kruskal "LEMON Kruskal " does |
148 this job for you. After we had a graph \c g and a cost map \c |
147 this job for you. After we had a graph \c g and a cost map \c |
149 edge_cost_map , the following code fragment shows an example how to get weight of the minmum spanning tree, if the costs are uniform: |
148 edge_cost_map , the following code fragment shows an example how to get weight of the minmum spanning tree (in this first example the costs are uniform; this is of course not the case in real life applications): |
150 |
149 |
151 \dontinclude kruskal_demo.cc |
150 \dontinclude kruskal_demo.cc |
152 \skip std::cout |
151 \skip std::cout |
153 \until kruskal |
152 \until kruskal |
154 |
153 |
155 It gives back a edge bool map, which contains the edges of the tree. |
154 In the variable \c tree_map the function gives back an edge bool map, which contains the edges of the found tree. |
|
155 |
156 If the costs are non-uniform, for example the cost is given by \c |
156 If the costs are non-uniform, for example the cost is given by \c |
157 edge_cost_map_2 , or the edges of the tree are have to be given in a |
157 edge_cost_map_2 , or the edges of the tree have to be given in a |
158 vector, then we can give to the kruskal a vector \c tree_edge_vec , instead of |
158 vector, then we can give to the kruskal a vector \c tree_edge_vec , instead of |
159 an edge bool map: |
159 an edge bool map: |
160 |
160 |
161 \skip edge_cost_map_2 |
161 \skip edge_cost_map_2 |
162 \until edge_cost_map_2, std::back_inserter |
162 \until edge_cost_map_2, std::back_inserter |