[1169] | 1 | /** |
---|
| 2 | |
---|
[1170] | 3 | \page quicktour Quick Tour to LEMON |
---|
| 4 | |
---|
[1175] | 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 | |
---|
[1181] | 19 | Some examples are the following (you will find links next to the code fragments that help to download full demo programs): |
---|
[1175] | 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). |
---|
[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; |
---|
| 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 | |
---|
[1181] | 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 | |
---|
[1175] | 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 |
---|
[1181] | 61 | as follows (we do not include the part that instantiates the graph and the length function): |
---|
[1175] | 62 | |
---|
| 63 | \code |
---|
[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); |
---|
| 71 | dijkstra_test.run(s); |
---|
[1175] | 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 | |
---|
[1169] | 89 | \ref graphs "Graph structures" |
---|
[1175] | 90 | play a central role in LEMON, so if you are new to the library, |
---|
[1169] | 91 | you 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>.) |
---|
[1169] | 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. |
---|
[1175] | 100 | */ |
---|