# source:lemon-0.x/doc/graph_orientation.dox

Last change on this file was 2553:bfced05fa852, checked in by Alpar Juttner, 13 years ago

File size: 5.8 KB
Line
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19namespace lemon {
20/**
21
22\ingroup demos
23\file graph_orientation.cc
24\brief Graph orientation with lower bound requirement on the
25in-degree of the nodes.
26
27This demo shows an adaptation of the well-known "preflow push" algorithm to
28a simple graph orientation problem.
29
30The input of the problem is a(n undirected) graph and an integer value
31<i>f(n)</i> assigned to each node \e n. The task is to find an orientation
32of the edges for which the number of edge arriving at each node \e n is at
33least least <i>f(n)</i>.
34
35In fact, the algorithm reads a directed graph and computes a set of edges to
36be reversed in order to achieve the in-degree requirement.
37This input is given using
38\ref graph-io-page ".lgf (Lemon Graph Format)" file. It should contain
39three node maps. The one called "f" contains the in-degree requirements, while
40"coordinate_x" and "coordinate_y" indicate the position of the nodes. These
41latter ones are used to generate the output, which is a <tt>.eps</tt> file.
42
43
44\section go-alg-dec The C++ source file
45
46Here you find how to solve the problem above using lemon.
47
49
50First we include some important headers.
51
52The first one defines \ref lemon::ListGraph "ListGraph",
53the "Swiss army knife" graph implementation.
54\dontinclude graph_orientation.cc
55\skipline list_graph
56
57The next is  to read a \ref graph-io-page ".lgf" (Lemon Graph Format) file.
59
60This provides us with some special purpose graph \ref maps "maps".
61\skipline iterable
62
63The following header defines a simple data structure to store and manipulate
64planar coordinates. It will be used to draw the result.
65\skipline dim2
66
67And finally, this header contains a simple graph drawing utility.
68\skipline eps
69
70As we don't want to type in \ref lemon "lemon::" million times, the
71following line seems to be useful.
72\skipline namespace
73
74The following macro will also save a lot of typing by defining some
75convenience <tt>typedef</tt>s.
76
77\skipline TYPEDEF
78
79Actually, the macro above would be equivalent with the following
80<tt>typedef</tt>s.
81
82\code
83typedef ListGraph::Node Node;
84typedef ListGraph::NodeIt NodeIt;
85typedef ListGraph::Edge Edge;
86typedef ListGraph::EdgeIt EdgeIt;
87typedef ListGraph::OutEdgeIt OutEdgeIt;
88typedef ListGraph::InEdgeIt InEdgeIt;
89\endcode
90
91\subsection go-alg-main The main() function
92
93Well, we are ready to start <tt>main()</tt>.
94\skip main
95\until {
96
97First we check whether the program is called with exactly one parameter.
98If it isn't, we print a short help message end exit.
99The vast majority of people would probably skip this block.
100\skip if
101\until }
102
103Now, we read a graph \c g, and a map \c f containing
104the in-deg requirements from a \ref graph-io-page ".lgf (Lemon Graph Format)"
105file. To generate the output picture, we also read the node titles (\c label)
106and
107coordinates (\c coords).
108So, first we create the graph
109\skipline ListGraph
110and the corresponding NodeMaps.
111\skipline NodeMap
112\until coords
113\note The graph must be given to the maps' constructor.
114
115Then, the following block will read these data from the file, or exit if
116the file is missing or corrupt.
117\skip try
118\until }
119\until }
120
121The algorithm needs an integer value assigned to each node. We call this "level" and the nodes are on level 0 at the
122beginning of the execution.
123
124\skipline level
125
126The deficiency (\c def) of a node is the in-degree requirement minus the
127actual in-degree.
128
129\skip def
130\until subMap
131
132A node is \e active if its deficiency is positive (i.e. if it doesn't meet
133the degree requirement).
134\skip active
135\until def
136
137We also store a bool map indicating which edges are reverted.
138Actually this map called \c rev is only
139used to draw these edges with different color in the output picture. The
140algorithm updates this map, but will not use it otherwise.
141\skip rev
142\until reversed
143
144The variable \c nodeNum will refer to the number of nodes.
145\skipline nodeNum
146
147Here comes the algorithm itself.
148In each iteration we choose an active node (\c act will do it for us).
149If there is
150no such a node, then the orientation is feasible so we are done.
151\skip act
152\until while
153
154Then we check if there exists an edge leaving this node and
155stepping down exactly
156one level.
157\skip OutEdge
158\until while
159
160If there exists, we decrease the "activity" of the node \c act by reverting
161this egde.
162Fortunately, \ref lemon::ListGraph "ListGraph"
163has a special function \ref lemon::ListGraph::reverseEdge() "reverseEdge()"
164that makes this easy.
165We also have to update the maps \c def and
166\c rev.
167\skipline if
168\skip if
169\until }
170Otherwise (i.e. if there is no edge stepping down one level) we lift up the
171current active node \c act. If it reaches level \c nodeNum, then there
172exists no appropriate orientation so we stop.
173\skipline else
174\skipline if
175\skipline return
176\until }
177\until }
178\until }
179
180Believe it or not, this algorithm works and runs fast.
181
182Finally, we print the obtained orientation. Note, how the different
183\c bool values of
184\c rev are transformed into different \ref lemon::Color "RGB color"s
185using the class
186\ref lemon::Palette "Palette"
188\ref lemon::ComposeMap "composeMap".
189
190\skip graphToEps
191\until run
192
193
194\until end of main
195
196Finally here are again the list of the used include files (because I can't turn
197this section off.)
198
199*/
200
201}
Note: See TracBrowser for help on using the repository browser.