# source:lemon-0.x/doc/graph_orientation.dox@1847:7cbc12e42482

Last change on this file since 1847:7cbc12e42482 was 1715:e71778873dd0, checked in by Alpar Juttner, 15 years ago

Doc improvments

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