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?" |
|
6 </b>. |
|
7 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? |
|
9 It helps to write programs that solve optimization problems that arise |
|
10 frequently when <b>designing and testing certain networks</b>, for example |
|
11 in telecommunication, computer networks, and other areas that I cannot |
|
12 think of now. A very natural way of modelling these networks is by means |
|
13 of a <b> graph</b> (we will always mean a directed graph by that). |
|
14 So if you want to write a program that works with |
|
15 graphs then you might find it useful to use our library LEMON. |
|
16 |
|
17 |
|
18 |
|
19 Some examples are the following: |
|
20 |
|
21 - First we give two examples that show how to instantiate a graph. The |
|
22 first one shows the methods that add nodes and edges, but one will |
|
23 usually use the second way which reads a graph from a stream (file). |
|
24 |
|
25 |
|
26 -# The following code fragment shows how to fill a graph with data. |
|
27 |
|
28 \code |
|
29 |
|
30 typedef ListGraph Graph; |
|
31 typedef Graph::Edge Edge; |
|
32 typedef Graph::InEdgeIt InEdgeIt; |
|
33 typedef Graph::OutEdgeIt OutEdgeIt; |
|
34 typedef Graph::EdgeIt EdgeIt; |
|
35 typedef Graph::Node Node; |
|
36 typedef Graph::NodeIt NodeIt; |
|
37 |
|
38 Graph g; |
|
39 |
|
40 for (int i = 0; i < 3; i++) |
|
41 g.addNode(); |
|
42 |
|
43 for (NodeIt i(g); i!=INVALID; ++i) |
|
44 for (NodeIt j(g); j!=INVALID; ++j) |
|
45 if (i != j) g.addEdge(i, j); |
|
46 |
|
47 \endcode |
|
48 |
|
49 -# |
|
50 |
|
51 - If you want to solve some transportation problems in a network then |
|
52 you will want to find shortest paths between nodes of a graph. This is |
|
53 usually solved using Dijkstra's algorithm. A utility |
|
54 that solves this is the \ref lemon::Dijkstra "LEMON Dijkstra class". |
|
55 A simple program using the \ref lemon::Dijkstra "LEMON Dijkstra class" is |
|
56 as follows (we assume that the graph is already given in the memory): |
|
57 |
|
58 \code |
|
59 |
|
60 \endcode |
|
61 |
|
62 - If you want to design a network and want to minimize the total length |
|
63 of wires then you might be looking for a <b>minimum spanning tree</b> in |
|
64 an undirected graph. This can be found using the Kruskal algorithm: the |
|
65 class \ref lemon::Kruskal "LEMON Kruskal class" does this job for you. |
|
66 The following code fragment shows an example: |
|
67 |
|
68 \code |
|
69 |
|
70 \endcode |
|
71 |
|
72 |
|
73 |
|
74 Some more detailed introduction can be obtained by following the links |
|
75 below: |
|
76 |
5 \ref graphs "Graph structures" |
77 \ref graphs "Graph structures" |
6 play a central role in LEMON, so if you are new to it, |
78 play a central role in LEMON, so if you are new to the library, |
7 you probably should start \ref graphs "here". |
79 you probably should start \ref graphs "here". |
8 You can also find that page along with others under |
80 (You can also find that page along with others under |
9 <a class="el" href="pages.html"> Related Pages </a>. |
81 <a class="el" href="pages.html"> Related Pages </a>.) |
10 |
82 |
11 If you are |
83 If you are |
12 interested in data structures and algorithms in more details, then |
84 interested in data structures and algorithms in more details, then |
13 you should browse the reference manual part of the documentation. |
85 you should browse the reference manual part of the documentation. |
14 Section <a class="el" href="modules.html"> Modules </a> |
86 Section <a class="el" href="modules.html"> Modules </a> |