4 \ingroup demos |
4 \ingroup demos |
5 \file graph_orientation.cc |
5 \file graph_orientation.cc |
6 \brief Graph orientation with lower bound requirement on the |
6 \brief Graph orientation with lower bound requirement on the |
7 in-degree of the nodes. |
7 in-degree of the nodes. |
8 |
8 |
|
9 This demo shows an adaptation of the well-known "preflow push" algorithm to |
|
10 a simple graph orientation problem. |
9 |
11 |
|
12 The input of the problem is a(n undirected) graph and an integer value |
|
13 <i>f(n)</i> assigned to each node \e n. The task is to find an orientation |
|
14 of the edges for which the number of edge arriving to each node \e n is at |
|
15 least least <i>f(n)</i>. |
|
16 |
|
17 In fact, the algorithm reads a directed graph and computes a set of edges to |
|
18 be reversed in order to achieve the in-degree requirement. |
|
19 This input is given using |
|
20 \ref graph-io-page ".lgf (Lemon Graph Format)" file. It should contain |
|
21 three node maps. The one called "f" contains the in-degree requirements, while |
|
22 "coordinate_x" and "coordinate_y" indicate the position of the nodes. These |
|
23 latter ones are used to generate the output, which is a <tt>.eps</tt> file. |
|
24 |
|
25 |
|
26 \section go-alg-dec The C++ source file |
|
27 |
|
28 Here you find how to solve the problem above using lemon. |
|
29 |
|
30 \subsection go-alg-head Headers and convenience typedefs |
10 |
31 |
11 First we include some important headers. |
32 First we include some important headers. |
12 |
33 |
13 The first one defines \ref lemon::ListGraph "ListGraph", |
34 The first one defines \ref lemon::ListGraph "ListGraph", |
14 the "Swiss army knife" graph implementation. |
35 the "Swiss army knife" graph implementation. |
45 The vast majority of people would probably skip this block. |
68 The vast majority of people would probably skip this block. |
46 \skip if |
69 \skip if |
47 \until } |
70 \until } |
48 |
71 |
49 Now, we read a graph \c g, and a map \c f containing |
72 Now, we read a graph \c g, and a map \c f containing |
50 the in-deg requirements from a \ref graph-io-page ".lgf" (Lemon Graph Format) |
73 the in-deg requirements from a \ref graph-io-page ".lgf (Lemon Graph Format)" |
51 file. To generate the output picture, we also read the node titles (\c id) and |
74 file. To generate the output picture, we also read the node titles (\c id) and |
52 coordinates (\c coords). |
75 coordinates (\c coords). |
53 So, first we create the graph |
76 So, first we create the graph |
54 \skipline ListGraph |
77 \skipline ListGraph |
55 and the corresponding NodeMaps. |
78 and the corresponding NodeMaps. |