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