# source:lemon-0.x/doc/graph_orientation.dox@2015:5e51c9eb5e83

Last change on this file since 2015:5e51c9eb5e83 was 1953:d4f411003580, checked in by Alpar Juttner, 14 years ago

Polish the doc.

File size: 4.9 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 to 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 <tt>typedef</tt>s will also save a lot of typing.
57\skip typedef
58\until InEdgeIt
59
60\subsection go-alg-main The main() function
61
62Well, we are ready to start <tt>main()</tt>.
63\skip main
64\until {
65
66First we check whether the program is called with exactly one parameter.
67If it isn't, we print a short help message end exit.
68The vast majority of people would probably skip this block.
69\skip if
70\until }
71
72Now, we read a graph \c g, and a map \c f containing
73the in-deg requirements from a \ref graph-io-page ".lgf (Lemon Graph Format)"
74file. To generate the output picture, we also read the node titles (\c label)
75and
76coordinates (\c coords).
77So, first we create the graph
78\skipline ListGraph
79and the corresponding NodeMaps.
80\skipline NodeMap
81\until coords
82\note The graph must be given to the maps' constructor.
83
84Then, the following block will read these data from the file, or exit if
85the file is missing or corrupt.
86\skip try
87\until }
88\until }
89
90The algorithm needs an integer value assigned to each node. We call this "level" and the nodes are on level 0 at the
91beginning of the execution.
92
93\skipline level
94
95The deficiency (\c def) of a node is the in-degree requirement minus the
96actual in-degree.
97
98\skip def
99\until subMap
100
101A node is \e active if its deficiency is positive (i.e. if it doesn't meet
102the degree requirement).
103\skip active
104\until def
105
106We also store in a bool map indicating which edges are reverted.
107Actually this map called \c rev is only
108used to draw these edges with different color in the output picture. The
109algorithm updates this map, but will not use it otherwise.
110\skip rev
111\until reversed
112
113The variable \c nodeNum will refer to the number of nodes.
114\skipline nodeNum
115
116Here comes the algorithms itself.
117In each iteration we choose an active node (\c act will do it for us).
118If there is
119no such a node, then the orientation is feasible so we are done.
120\skip act
121\until while
122
123Then we check if there exists an edge leaving this node that steps down exactly
124one level.
125\skip OutEdge
126\until while
127
128If there exists, we decrease the "activity" of the node \c act by reverting
129this egde.
130Fortunately, \ref lemon::ListGraph "ListGraph"
131has a special function \ref lemon::ListGraph::reverseEdge() "reverseEdge()"
132that makes this easy.
133We also have to update the maps \c def and
134\c rev.
135\skipline if
136\skip if
137\until }
138Otherwise (i.e. if there is no edge stepping down one level). We lift up the
139current active node \c act. If it reaches level \c nodeNum, then there
140exists no appropriate orientation so we stop.
141\skipline else
142\skipline if
143\skipline return
144\until }
145\until }
146\until }
147
148Believe it or not, this algorithm works and runs fast.
149
150Finally, we print the obtained orientation. Note, how the different
151\c bool values of
152\c rev are transformed into different \ref lemon::Color "RGB color"s
153using the class
154\ref lemon::ColorSet "ColorSet"
156\ref lemon::ComposeMap "composeMap".
157
158\skip graphToEps
159\until run
160
161
162\until end of main
163
164Finally here are again the list of the used include files (because I can't turn
165this section off.)
166
167*/
168
169}
Note: See TracBrowser for help on using the repository browser.