COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/graph_orientation.dox @ 1678:b7b7125a5fe8

Last change on this file since 1678:b7b7125a5fe8 was 1678:b7b7125a5fe8, checked in by Alpar Juttner, 14 years ago

graph_orientation.cc: A thoroughly documented demo application.

File size: 3.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
9
10
11First we include some important headers.
12
13The first one defines \ref lemon::ListGraph "ListGraph",
14the "Swiss army knife" graph implementation.
15\dontinclude graph_orientation.cc
16\skipline list_graph
17
18The next is  to read a \ref graph-io-page ".lgf" (Lemon Graph Format) file.
19\skipline reader
20
21This provides us with some special purpose graph \ref maps "maps".
22\skipline iterable
23
24The following header defines a simple data structure to store and manipulate
25planar coordinates. It will be used to draw the result.
26\skipline xy
27
28And finally, this header contains a simple graph drawing utility.
29\skipline eps
30
31As we don't want to type in \ref lemon "lemon::" million times, the
32following line seems to be useful.
33\skipline namespace
34
35The following <tt>typedef</tt>s will also save a lot of typing.
36\skip typedef
37\until InEdgeIt
38
39Well, we are ready to start <tt>main()</tt>.
40\skip main
41\until {
42
43First we check whether the program is called with exactly 1 parameter.
44If it isn't, we print a short help message end exit.
45The vast majority of people would probably skip this block.
46\skip if
47\until }
48
49Now, we read a graph \c g, and a map \c f containing
50the in-deg requirements from a \ref graph-io-page ".lgf" (Lemon Graph Format)
51file. To generate the output picture, we also read the node titles (\c id) and
52coordinates (\c coords).
53So, first we create the graph
54\skipline ListGraph
55and the corresponding NodeMaps.
56\skipline NodeMap
57\until coords
58\note The graph must be given to the maps' constructor.
59
60Then, the following block will read these data from the file, or exit if
61the file is missing or corrupt.
62\skip try
63\until }
64\until }
65
66The algorithm needs a "level" integer value assigned to each node. In the
67beginning, the nodes are on level 0.
68\skipline level
69
70The deficiency (\c def) of a node is the in-degree requirement minus the
71actual in-degree.
72
73\skip def
74\until subMap
75
76A node is \e active if its deficiency is positive (i.e. if it doesn't meet
77the degree requirement).
78\skip active
79\until def
80
81We also store in a bool map which edges are reverted. Actually this is only
82used to draw these edges with different color in the output picture. The
83algorithm will update this map called \c rev, but will not use it otherwise.
84\skip rev
85\until reversed
86
87The variable \c nodeNum will refer to the number of nodes.
88\skipline nodeNum
89
90Here comes the algorithms itself.
91In each iteration we choose an active node (\c act will store it). If there is
92no such a node, then the orientation is feasible so we are done.
93\skip act
94\until while
95
96Then we check if there exists an edge leaving this node that steps down exactly
97one level.
98\skip OutEdge
99\until while
100
101If there exists, we decrease the "activity" of the node \c act by reverting
102this egde.
103Fortunately, \ref lemon::ListGraph "ListGraph"
104has a special function \ref lemon::ListGraph::reverseEdge() "reverseEdge()"
105that makes this easy.
106We also have to update the maps \c def and
107\c rev.
108\skipline if
109\skip if
110\until }
111Otherwise (i.e. if there is no edge stepping down one level). We lift up the
112current active node \c act. If it reaches level \c nodeNum, then there
113exists no appropriate orientation so we stop.
114\skipline else
115\skipline if
116\skipline return
117\until }
118\until }
119\until }
120
121Believe it or not, this algorithm works and runs fast.
122
123Finally, we print the obtained orientation. Note, how the different
124\c bool values of
125\c rev are transformed into different \ref lemon::Color "RGB color"s
126using the class
127\ref lemon::ColorSet "ColorSet"
128and the \ref map_adaptors "map adaptor" called
129\ref lemon::ComposeMap "composeMap".
130
131\skip graphToEps
132\until run
133
134
135\until end of main
136
137Finally here are again the list of the used include files (because I can't turn
138this section off.)
139
140*/
141
142}
Note: See TracBrowser for help on using the repository browser.