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

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