doc/quicktour.dox
author marci
Thu, 24 Feb 2005 17:42:11 +0000
changeset 1176 1ba2b4c0c970
parent 1170 fb0159aa582d
child 1181 848b6006941d
permissions -rw-r--r--
glpk is able to search 5x5 magic square, let's celebrate the free software
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
*/