14 So if you want to write a program that works with |
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. |
15 graphs then you might find it useful to use our library LEMON. |
16 |
16 |
17 |
17 |
18 |
18 |
19 Some examples are the following: |
19 Some examples are the following (you will find links next to the code fragments that help to download full demo programs): |
20 |
20 |
21 - First we give two examples that show how to instantiate a graph. The |
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 |
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). |
23 usually use the second way which reads a graph from a stream (file). |
24 |
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 |
|
26 -# The following code fragment shows how to fill a graph with data. |
|
27 |
|
28 \code |
25 \code |
29 |
|
30 typedef ListGraph Graph; |
26 typedef ListGraph Graph; |
31 typedef Graph::Edge Edge; |
27 typedef Graph::Edge Edge; |
32 typedef Graph::InEdgeIt InEdgeIt; |
28 typedef Graph::InEdgeIt InEdgeIt; |
33 typedef Graph::OutEdgeIt OutEdgeIt; |
29 typedef Graph::OutEdgeIt OutEdgeIt; |
34 typedef Graph::EdgeIt EdgeIt; |
30 typedef Graph::EdgeIt EdgeIt; |
41 g.addNode(); |
37 g.addNode(); |
42 |
38 |
43 for (NodeIt i(g); i!=INVALID; ++i) |
39 for (NodeIt i(g); i!=INVALID; ++i) |
44 for (NodeIt j(g); j!=INVALID; ++j) |
40 for (NodeIt j(g); j!=INVALID; ++j) |
45 if (i != j) g.addEdge(i, j); |
41 if (i != j) g.addEdge(i, j); |
46 |
|
47 \endcode |
42 \endcode |
48 |
43 |
49 -# |
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 |
50 |
55 |
51 - If you want to solve some transportation problems in a network then |
56 - If you want to solve some transportation problems in a network then |
52 you will want to find shortest paths between nodes of a graph. This is |
57 you will want to find shortest paths between nodes of a graph. This is |
53 usually solved using Dijkstra's algorithm. A utility |
58 usually solved using Dijkstra's algorithm. A utility |
54 that solves this is the \ref lemon::Dijkstra "LEMON Dijkstra class". |
59 that solves this is the \ref lemon::Dijkstra "LEMON Dijkstra class". |
55 A simple program using the \ref lemon::Dijkstra "LEMON Dijkstra class" is |
60 A simple program using the \ref lemon::Dijkstra "LEMON Dijkstra class" is |
56 as follows (we assume that the graph is already given in the memory): |
61 as follows (we do not include the part that instantiates the graph and the length function): |
57 |
62 |
58 \code |
63 \code |
59 |
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); |
60 \endcode |
72 \endcode |
61 |
73 |
62 - If you want to design a network and want to minimize the total length |
74 - If you want to design a network and want to minimize the total length |
63 of wires then you might be looking for a <b>minimum spanning tree</b> in |
75 of wires then you might be looking for a <b>minimum spanning tree</b> in |
64 an undirected graph. This can be found using the Kruskal algorithm: the |
76 an undirected graph. This can be found using the Kruskal algorithm: the |