COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/quicktour.dox @ 1181:848b6006941d

Last change on this file since 1181:848b6006941d was 1181:848b6006941d, checked in by athos, 16 years ago

Some work has been done in the quicktour.

File size: 3.8 KB
[1170]3\page quicktour Quick Tour to LEMON
[1175]5Let us first answer the question <b>"What do I want to use LEMON for?"
7LEMON is a C++ library, so you can use it if you want to write C++
8programs. What kind of tasks does the library LEMON help to solve?
9It helps to write programs that solve optimization problems that arise
10frequently when <b>designing and testing certain networks</b>, for example
11in telecommunication, computer networks, and other areas that I cannot
12think of now. A very natural way of modelling these networks is by means
13of a <b> graph</b> (we will always mean a directed graph by that).
14So if you want to write a program that works with
15graphs then you might find it useful to use our library LEMON.
[1181]19Some examples are the following (you will find links next to the code fragments that help to download full demo programs):
21- First we give two examples that show how to instantiate a graph. The
22first one shows the methods that add nodes and edges, but one will
23usually use the second way which reads a graph from a stream (file).
[1181]24-# 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.
[1175]25 \code
26  typedef ListGraph Graph;
27  typedef Graph::Edge Edge;
28  typedef Graph::InEdgeIt InEdgeIt;
29  typedef Graph::OutEdgeIt OutEdgeIt;
30  typedef Graph::EdgeIt EdgeIt;
31  typedef Graph::Node Node;
32  typedef Graph::NodeIt NodeIt;
34  Graph g;
36  for (int i = 0; i < 3; i++)
37    g.addNode();
39  for (NodeIt i(g); i!=INVALID; ++i)
40    for (NodeIt j(g); j!=INVALID; ++j)
41      if (i != j) g.addEdge(i, j);
42 \endcode
[1181]44If you want to read more on the LEMON graph structures and concepts, read the page about \ref graphs "graphs".
46-# 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
47in that format (find the documentation of the format on the web).
49Graph g;
50std::ifstream f("graph.dim");
51readDimacs(f, g);
53One can also store network (graph+capacity on the edges) instances and other things in DIMACS format: to see the details read the documentation of the \ref dimacs.h "Dimacs file format reader".
56- If you want to solve some transportation problems in a network then
57you will want to find shortest paths between nodes of a graph. This is
58usually solved using Dijkstra's algorithm. A utility
59that solves this is  the \ref lemon::Dijkstra "LEMON Dijkstra class".
60A simple program using the \ref lemon::Dijkstra "LEMON Dijkstra class" is
[1181]61as follows (we do not include the part that instantiates the graph and the length function):
[1181]64  typedef Graph::EdgeMap<int> LengthMap;
65  Graph G;
66  Node s, t;
67  LengthMap cap(G);
68        ...
69  Dijkstra<Graph, LengthMap>
70        dijkstra_test(G, cap);
74- If you want to design a network and want to minimize the total length
75of wires then you might be looking for a <b>minimum spanning tree</b> in
76an undirected graph. This can be found using the Kruskal algorithm: the
77class \ref lemon::Kruskal "LEMON Kruskal class" does this job for you.
78The following code fragment shows an example:
86Some more detailed introduction can be obtained by following the links
[1169]89\ref graphs "Graph structures"
[1175]90play a central role in LEMON, so if you are new to the library,
[1169]91you probably should start \ref graphs "here".
[1175]92(You can also find that page along with others under
93<a class="el" href="pages.html"> Related Pages </a>.)
95If you are
96interested in data structures and algorithms in more details, then
97you should browse the reference manual part of the documentation.
98Section <a class="el" href="modules.html"> Modules </a>
99 is a good starting point for this.
Note: See TracBrowser for help on using the repository browser.