Turn off 32 bit only tests, cont'd.
5 \file graph_orientation.cc
6 \brief Graph orientation with lower bound requirement on the
7 in-degree of the nodes.
9 This demo shows an adaptation of the well-known "preflow push" algorithm to
10 a simple graph orientation problem.
12 The 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
14 of the edges for which the number of edge arriving at each node \e n is at
15 least least <i>f(n)</i>.
17 In fact, the algorithm reads a directed graph and computes a set of edges to
18 be reversed in order to achieve the in-degree requirement.
19 This input is given using
20 \ref graph-io-page ".lgf (Lemon Graph Format)" file. It should contain
21 three 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
23 latter ones are used to generate the output, which is a <tt>.eps</tt> file.
26 \section go-alg-dec The C++ source file
28 Here you find how to solve the problem above using lemon.
30 \subsection go-alg-head Headers and convenience typedefs
32 First we include some important headers.
34 The first one defines \ref lemon::ListGraph "ListGraph",
35 the "Swiss army knife" graph implementation.
36 \dontinclude graph_orientation.cc
39 The next is to read a \ref graph-io-page ".lgf" (Lemon Graph Format) file.
42 This provides us with some special purpose graph \ref maps "maps".
45 The following header defines a simple data structure to store and manipulate
46 planar coordinates. It will be used to draw the result.
49 And finally, this header contains a simple graph drawing utility.
52 As we don't want to type in \ref lemon "lemon::" million times, the
53 following line seems to be useful.
56 The following macro will also save a lot of typing by defining some
57 convenience <tt>typedef</tt>s.
61 Actually, the macro above would be equivalent with the following
65 typedef ListGraph::Node Node;
66 typedef ListGraph::NodeIt NodeIt;
67 typedef ListGraph::Edge Edge;
68 typedef ListGraph::EdgeIt EdgeIt;
69 typedef ListGraph::OutEdgeIt OutEdgeIt;
70 typedef ListGraph::InEdgeIt InEdgeIt;
73 \subsection go-alg-main The main() function
75 Well, we are ready to start <tt>main()</tt>.
79 First we check whether the program is called with exactly one parameter.
80 If it isn't, we print a short help message end exit.
81 The vast majority of people would probably skip this block.
85 Now, we read a graph \c g, and a map \c f containing
86 the in-deg requirements from a \ref graph-io-page ".lgf (Lemon Graph Format)"
87 file. To generate the output picture, we also read the node titles (\c label)
89 coordinates (\c coords).
90 So, first we create the graph
92 and the corresponding NodeMaps.
95 \note The graph must be given to the maps' constructor.
97 Then, the following block will read these data from the file, or exit if
98 the file is missing or corrupt.
103 The algorithm needs an integer value assigned to each node. We call this "level" and the nodes are on level 0 at the
104 beginning of the execution.
108 The deficiency (\c def) of a node is the in-degree requirement minus the
114 A node is \e active if its deficiency is positive (i.e. if it doesn't meet
115 the degree requirement).
119 We also store in a bool map indicating which edges are reverted.
120 Actually this map called \c rev is only
121 used to draw these edges with different color in the output picture. The
122 algorithm updates this map, but will not use it otherwise.
126 The variable \c nodeNum will refer to the number of nodes.
129 Here comes the algorithm itself.
130 In each iteration we choose an active node (\c act will do it for us).
132 no such a node, then the orientation is feasible so we are done.
136 Then we check if there exists an edge leaving this node and
137 stepping down exactly
142 If there exists, we decrease the "activity" of the node \c act by reverting
144 Fortunately, \ref lemon::ListGraph "ListGraph"
145 has a special function \ref lemon::ListGraph::reverseEdge() "reverseEdge()"
146 that makes this easy.
147 We also have to update the maps \c def and
152 Otherwise (i.e. if there is no edge stepping down one level). We lift up the
153 current active node \c act. If it reaches level \c nodeNum, then there
154 exists no appropriate orientation so we stop.
162 Believe it or not, this algorithm works and runs fast.
164 Finally, we print the obtained orientation. Note, how the different
166 \c rev are transformed into different \ref lemon::Color "RGB color"s
168 \ref lemon::Palette "Palette"
169 and the \ref map_adaptors "map adaptor" called
170 \ref lemon::ComposeMap "composeMap".
178 Finally here are again the list of the used include files (because I can't turn