source:lemon-0.x/doc/graph_orientation.dox@2166:c67e8b928a95

Last change on this file since 2166:c67e8b928a95 was 2158:0b620ff10e7c, checked in by Alpar Juttner, 15 years ago

Minor doc improvement

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 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
30\subsection go-alg-head Headers and convenience typedefs
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.
40\skipline reader
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 algorithm 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 and
124stepping down exactly
125one level.
126\skip OutEdge
127\until while
128
129If there exists, we decrease the "activity" of the node \c act by reverting
130this egde.
131Fortunately, \ref lemon::ListGraph "ListGraph"
132has a special function \ref lemon::ListGraph::reverseEdge() "reverseEdge()"
133that makes this easy.
134We also have to update the maps \c def and
135\c rev.
136\skipline if
137\skip if
138\until }
139Otherwise (i.e. if there is no edge stepping down one level). We lift up the
140current active node \c act. If it reaches level \c nodeNum, then there
141exists no appropriate orientation so we stop.
142\skipline else
143\skipline if
144\skipline return
145\until }
146\until }
147\until }
148
149Believe it or not, this algorithm works and runs fast.
150
151Finally, we print the obtained orientation. Note, how the different
152\c bool values of
153\c rev are transformed into different \ref lemon::Color "RGB color"s
154using the class
155\ref lemon::ColorSet "ColorSet"
156and the \ref map_adaptors "map adaptor" called
157\ref lemon::ComposeMap "composeMap".
158
159\skip graphToEps
160\until run
161
162
163\until end of main
164
165Finally here are again the list of the used include files (because I can't turn
166this section off.)
167
168*/
169
170}
Note: See TracBrowser for help on using the repository browser.