22 example a length or capacity function defined on the edges. You can do this in |
22 example a length or capacity function defined on the edges. You can do this in |
23 LEMON using so called \b 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 of any type. Read more about maps \ref maps-page "here". |
23 LEMON using so called \b 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 of any type. Read more about maps \ref maps-page "here". |
24 |
24 |
25 Some examples are the following (you will find links next to the code fragments that help to download full demo programs: save them on your computer and compile them according to the description in the page about \ref getsart How to start using LEMON): |
25 Some examples are the following (you will find links next to the code fragments that help to download full demo programs: save them on your computer and compile them according to the description in the page about \ref getsart How to start using LEMON): |
26 |
26 |
27 <ul> |
27 <ul> <li> The first thing to discuss is the way one can create data structures |
28 <li> First we give two examples that show how to instantiate a graph. The |
28 like graphs and maps in a program using LEMON. |
29 first one shows the methods that add nodes and edges, but one will |
29 //There are more graph types |
30 usually use the second way which reads a graph from a stream (file). |
30 //implemented in LEMON and you can implement your own graph type just as well: |
31 <ol> |
31 //read more about this in the already mentioned page on \ref graphs "graphs". |
32 <li>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 suppose them later as well. |
32 |
33 \code |
33 First we show how to add nodes and edges to a graph manually. We will also |
34 typedef ListGraph Graph; |
34 define a map on the edges of the graph. After this we show the way one can |
|
35 read a graph (and perhaps maps on it) from a stream (e.g. a file). Of course |
|
36 we also have routines that write a graph (and perhaps maps) to a stream |
|
37 (file): this will also be shown. LEMON supports the DIMACS file formats to |
|
38 store network optimization problems, but more importantly we also have our own |
|
39 file format that gives a more flexible way to store data related to network |
|
40 optimization. |
|
41 |
|
42 <ol> <li>The following code fragment shows how to fill a graph with |
|
43 data. It creates a complete graph on 4 nodes. The type Listgraph is one of the |
|
44 LEMON graph types: the typedefs in the beginning are for convenience and we |
|
45 will suppose them later as well. |
|
46 |
|
47 \code |
|
48 |
|
49 typedef ListGraph Graph; |
35 typedef Graph::NodeIt NodeIt; |
50 typedef Graph::NodeIt NodeIt; |
36 |
51 |
37 Graph g; |
52 Graph g; |
38 |
53 |
39 for (int i = 0; i < 3; i++) |
54 for (int i = 0; i < 3; i++) |
40 g.addNode(); |
55 g.addNode(); |
41 |
56 |
42 for (NodeIt i(g); i!=INVALID; ++i) |
57 for (NodeIt i(g); i!=INVALID; ++i) |
43 for (NodeIt j(g); j!=INVALID; ++j) |
58 for (NodeIt j(g); j!=INVALID; ++j) |
44 if (i != j) g.addEdge(i, j); |
59 if (i != j) g.addEdge(i, j); |
45 \endcode |
60 |
|
61 \endcode |
46 |
62 |
47 See the whole program in file \ref helloworld.cc. |
63 See the whole program in file \ref helloworld.cc. |
48 |
64 |
49 If you want to read more on the LEMON graph structures and concepts, read the page about \ref graphs "graphs". |
65 If you want to read more on the LEMON graph structures and concepts, read the page about \ref graphs "graphs". |
50 |
66 |
51 <li> 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 |
67 <li> The following code shows how to read a graph from a stream (e.g. a file) |
52 in that format (find the documentation of the DIMACS file format on the web). |
68 in the DIMACS file format (find the documentation of the DIMACS file formats on the web). |
|
69 |
53 \code |
70 \code |
54 Graph g; |
71 Graph g; |
55 std::ifstream f("graph.dim"); |
72 std::ifstream f("graph.dim"); |
56 readDimacs(f, g); |
73 readDimacs(f, g); |
57 \endcode |
74 \endcode |
58 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". |
75 |
|
76 One can also store network (graph+capacity on the edges) instances and other |
|
77 things (minimum cost flow instances etc.) in DIMACS format and use these in LEMON: to see the details read the |
|
78 documentation of the \ref dimacs.h "Dimacs file format reader". There you will |
|
79 also find the details about the output routines into files of the DIMACS |
|
80 format. |
|
81 |
|
82 <li>We needed much greater flexibility than the DIMACS formats could give us, |
|
83 so we worked out our own file format. Instead of any explanation let us give a |
|
84 short example file in this format: read the detailed description of the LEMON |
|
85 graph file format and input-output routines \ref graph-io-page here. |
|
86 |
|
87 So here is a file describing a graph of 10 nodes (0 to 9), two nodemaps |
|
88 (called \c coordinates_x and \c coordinates_y), several edges, an edge map |
|
89 called \c length and two designated nodes (called \c source and \c target). |
|
90 |
|
91 \todo Maybe another example would be better here. |
|
92 |
|
93 \code |
|
94 @nodeset |
|
95 id coordinates_x coordinates_y |
|
96 9 447.907 578.328 |
|
97 8 79.2573 909.464 |
|
98 7 878.677 960.04 |
|
99 6 11.5504 938.413 |
|
100 5 327.398 815.035 |
|
101 4 427.002 954.002 |
|
102 3 148.549 753.748 |
|
103 2 903.889 326.476 |
|
104 1 408.248 577.327 |
|
105 0 189.239 92.5316 |
|
106 @edgeset |
|
107 length |
|
108 2 3 901.074 |
|
109 8 5 270.85 |
|
110 6 9 601.553 |
|
111 5 9 285.022 |
|
112 9 4 408.091 |
|
113 3 0 719.712 |
|
114 7 5 612.836 |
|
115 0 4 933.353 |
|
116 5 0 778.871 |
|
117 5 5 0 |
|
118 7 1 664.049 |
|
119 5 5 0 |
|
120 0 9 560.464 |
|
121 4 8 352.36 |
|
122 4 9 399.625 |
|
123 4 1 402.171 |
|
124 1 2 591.688 |
|
125 3 8 182.376 |
|
126 4 5 180.254 |
|
127 3 1 345.283 |
|
128 5 4 184.511 |
|
129 6 2 1112.45 |
|
130 0 1 556.624 |
|
131 @nodes |
|
132 source 1 |
|
133 target 8 |
|
134 @end |
|
135 \endcode |
|
136 |
|
137 Finally let us give a simple example that reads a graph from a file and writes |
|
138 it to another. |
|
139 |
|
140 \todo This is to be done! |
59 |
141 |
60 </ol> |
142 </ol> |
61 <li> If you want to solve some transportation problems in a network then |
143 <li> If you want to solve some transportation problems in a network then |
62 you will want to find shortest paths between nodes of a graph. This is |
144 you will want to find shortest paths between nodes of a graph. This is |
63 usually solved using Dijkstra's algorithm. A utility |
145 usually solved using Dijkstra's algorithm. A utility |
64 that solves this is the \ref lemon::Dijkstra "LEMON Dijkstra class". |
146 that solves this is the \ref lemon::Dijkstra "LEMON Dijkstra class". |
65 The following code is a simple program using the \ref lemon::Dijkstra "LEMON |
147 The following code is a simple program using the |
66 Dijkstra class" and it also shows how to define a map on the edges (the length |
148 \ref lemon::Dijkstra "LEMON Dijkstra class" and it also shows how to define a map on the edges (the length |
67 function): |
149 function): |
68 |
150 |
69 \code |
151 \code |
70 |
152 |
71 typedef ListGraph Graph; |
153 typedef ListGraph Graph; |