doc/quicktour.dox
author ladanyi
Wed, 06 Apr 2005 08:14:16 +0000
changeset 1310 1b434e6cc405
parent 1183 8f623d1833a7
child 1511 d6b95a59da26
permissions -rw-r--r--
make distcheck works again
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@1183
    13
of a <b> graph</b> (we will always mean a directed graph by that and say
athos@1183
    14
<b> undirected graph </b> otherwise). 
athos@1175
    15
So if you want to write a program that works with 
athos@1183
    16
graphs then you might find it useful to use our library LEMON. LEMON 
athos@1183
    17
defines various graph concepts depending on what you want to do with the 
athos@1183
    18
graph: a very good description can be found in the page
athos@1183
    19
about \ref graphs "graphs".
athos@1175
    20
athos@1183
    21
You will also want to assign data to the edges or nodes of the graph, for example a length or capacity function defined on the edges. You can do this in LEMON using so called \ref maps "maps". You can define a map on the nodes or on the edges of the graph and the value of the map (the range of the function) can be practically almost any type. Read more about maps \ref maps-page "here".
athos@1175
    22
athos@1181
    23
Some examples are the following (you will find links next to the code fragments that help to download full demo programs):
athos@1175
    24
athos@1175
    25
- First we give two examples that show how to instantiate a graph. The
athos@1175
    26
first one shows the methods that add nodes and edges, but one will
athos@1175
    27
usually use the second way which reads a graph from a stream (file).
athos@1181
    28
-# The following code fragment shows how to fill a graph with data. It creates a complete graph on 4 nodes. The type Listgraph is one of the LEMON graph types: the typedefs in the beginning are for convenience and we will supppose them later as well.
athos@1175
    29
 \code
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
 \endcode 
athos@1175
    47
athos@1181
    48
If you want to read more on the LEMON graph structures and concepts, read the page about \ref graphs "graphs". 
athos@1181
    49
athos@1181
    50
-# The following code shows how to read a graph from a stream (e.g. a file). LEMON supports the DIMACS file format: it can read a graph instance from a file 
athos@1183
    51
in that format (find the documentation of the DIMECS file format on the web). 
athos@1181
    52
\code
athos@1181
    53
Graph g;
athos@1181
    54
std::ifstream f("graph.dim");
athos@1181
    55
readDimacs(f, g);
athos@1181
    56
\endcode
athos@1183
    57
One can also store network (graph+capacity on the edges) instances and other things in DIMACS format and use these in LEMON: to see the details read the documentation of the \ref dimacs.h "Dimacs file format reader".
athos@1181
    58
athos@1175
    59
athos@1175
    60
- If you want to solve some transportation problems in a network then 
athos@1175
    61
you will want to find shortest paths between nodes of a graph. This is 
athos@1175
    62
usually solved using Dijkstra's algorithm. A utility
athos@1175
    63
that solves this is  the \ref lemon::Dijkstra "LEMON Dijkstra class".
athos@1183
    64
The following code is a simple program using the \ref lemon::Dijkstra "LEMON
athos@1183
    65
Dijkstra class" and it also shows how to define a map on the edges (the length
athos@1183
    66
function):
athos@1175
    67
athos@1175
    68
\code
athos@1183
    69
athos@1183
    70
    typedef ListGraph Graph;
athos@1183
    71
    typedef Graph::Node Node;
athos@1183
    72
    typedef Graph::Edge Edge;
athos@1183
    73
    typedef Graph::EdgeMap<int> LengthMap;
athos@1183
    74
athos@1183
    75
    Graph g;
athos@1183
    76
athos@1183
    77
    //An example from Ahuja's book
athos@1183
    78
athos@1183
    79
    Node s=g.addNode();
athos@1183
    80
    Node v2=g.addNode();
athos@1183
    81
    Node v3=g.addNode();
athos@1183
    82
    Node v4=g.addNode();
athos@1183
    83
    Node v5=g.addNode();
athos@1183
    84
    Node t=g.addNode();
athos@1183
    85
athos@1183
    86
    Edge s_v2=g.addEdge(s, v2);
athos@1183
    87
    Edge s_v3=g.addEdge(s, v3);
athos@1183
    88
    Edge v2_v4=g.addEdge(v2, v4);
athos@1183
    89
    Edge v2_v5=g.addEdge(v2, v5);
athos@1183
    90
    Edge v3_v5=g.addEdge(v3, v5);
athos@1183
    91
    Edge v4_t=g.addEdge(v4, t);
athos@1183
    92
    Edge v5_t=g.addEdge(v5, t);
athos@1183
    93
  
athos@1183
    94
    LengthMap len(g);
athos@1183
    95
athos@1183
    96
    len.set(s_v2, 10);
athos@1183
    97
    len.set(s_v3, 10);
athos@1183
    98
    len.set(v2_v4, 5);
athos@1183
    99
    len.set(v2_v5, 8);
athos@1183
   100
    len.set(v3_v5, 5);
athos@1183
   101
    len.set(v4_t, 8);
athos@1183
   102
    len.set(v5_t, 8);
athos@1183
   103
athos@1183
   104
    std::cout << "The id of s is " << g.id(s)<< ", the id of t is " << g.id(t)<<"."<<std::endl;
athos@1183
   105
athos@1183
   106
    std::cout << "Dijkstra algorithm test..." << std::endl;
athos@1183
   107
athos@1183
   108
    Dijkstra<Graph, LengthMap> dijkstra_test(g,len);
athos@1183
   109
    
athos@1183
   110
    dijkstra_test.run(s);
athos@1183
   111
athos@1183
   112
    
athos@1183
   113
    std::cout << "The distance of node t from node s: " << dijkstra_test.dist(t)<<std::endl;
athos@1183
   114
athos@1183
   115
    std::cout << "The shortest path from s to t goes through the following nodes (the first one is t, the last one is s): "<<std::endl;
athos@1183
   116
athos@1183
   117
    for (Node v=t;v != s; v=dijkstra_test.predNode(v)){
athos@1183
   118
	std::cout << g.id(v) << "<-";
athos@1183
   119
    }
athos@1183
   120
    std::cout << g.id(s) << std::endl;	
athos@1175
   121
\endcode
athos@1175
   122
alpar@1287
   123
See the whole program in \ref dijkstra_demo.cc.
athos@1183
   124
athos@1183
   125
The first part of the code is self-explanatory: we build the graph and set the
athos@1183
   126
length values of the edges. Then we instantiate a member of the Dijkstra class
athos@1183
   127
and run the Dijkstra algorithm from node \c s. After this we read some of the
athos@1183
   128
results. 
athos@1183
   129
You can do much more with the Dijkstra class, for example you can run it step
athos@1183
   130
by step and gain full control of the execution. For a detailed description, see the documentation of the \ref lemon::Dijkstra "LEMON Dijkstra class".
athos@1183
   131
athos@1183
   132
athos@1175
   133
- If you want to design a network and want to minimize the total length
athos@1175
   134
of wires then you might be looking for a <b>minimum spanning tree</b> in
athos@1175
   135
an undirected graph. This can be found using the Kruskal algorithm: the 
athos@1175
   136
class \ref lemon::Kruskal "LEMON Kruskal class" does this job for you.
athos@1175
   137
The following code fragment shows an example:
athos@1175
   138
athos@1175
   139
\code
athos@1175
   140
athos@1175
   141
\endcode
athos@1175
   142
athos@1175
   143
athos@1175
   144
*/