1 | /** |
---|
2 | |
---|
3 | \page quicktour Quick Tour to LEMON |
---|
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 (you will find links next to the code fragments that help to download full demo programs): |
---|
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 | -# 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. |
---|
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; |
---|
33 | |
---|
34 | Graph g; |
---|
35 | |
---|
36 | for (int i = 0; i < 3; i++) |
---|
37 | g.addNode(); |
---|
38 | |
---|
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 |
---|
43 | |
---|
44 | If you want to read more on the LEMON graph structures and concepts, read the page about \ref graphs "graphs". |
---|
45 | |
---|
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 |
---|
47 | in that format (find the documentation of the format on the web). |
---|
48 | \code |
---|
49 | Graph g; |
---|
50 | std::ifstream f("graph.dim"); |
---|
51 | readDimacs(f, g); |
---|
52 | \endcode |
---|
53 | One 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". |
---|
54 | |
---|
55 | |
---|
56 | - If you want to solve some transportation problems in a network then |
---|
57 | you will want to find shortest paths between nodes of a graph. This is |
---|
58 | usually solved using Dijkstra's algorithm. A utility |
---|
59 | that solves this is the \ref lemon::Dijkstra "LEMON Dijkstra class". |
---|
60 | A simple program using the \ref lemon::Dijkstra "LEMON Dijkstra class" is |
---|
61 | as follows (we do not include the part that instantiates the graph and the length function): |
---|
62 | |
---|
63 | \code |
---|
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); |
---|
71 | dijkstra_test.run(s); |
---|
72 | \endcode |
---|
73 | |
---|
74 | - If you want to design a network and want to minimize the total length |
---|
75 | of wires then you might be looking for a <b>minimum spanning tree</b> in |
---|
76 | an undirected graph. This can be found using the Kruskal algorithm: the |
---|
77 | class \ref lemon::Kruskal "LEMON Kruskal class" does this job for you. |
---|
78 | The following code fragment shows an example: |
---|
79 | |
---|
80 | \code |
---|
81 | |
---|
82 | \endcode |
---|
83 | |
---|
84 | |
---|
85 | |
---|
86 | Some more detailed introduction can be obtained by following the links |
---|
87 | below: |
---|
88 | |
---|
89 | \ref graphs "Graph structures" |
---|
90 | play a central role in LEMON, so if you are new to the library, |
---|
91 | you probably should start \ref graphs "here". |
---|
92 | (You can also find that page along with others under |
---|
93 | <a class="el" href="pages.html"> Related Pages </a>.) |
---|
94 | |
---|
95 | If you are |
---|
96 | interested in data structures and algorithms in more details, then |
---|
97 | you should browse the reference manual part of the documentation. |
---|
98 | Section <a class="el" href="modules.html"> Modules </a> |
---|
99 | is a good starting point for this. |
---|
100 | */ |
---|