doc/graph_orientation.dox
author deba
Tue, 31 Oct 2006 14:27:58 +0000
changeset 2282 9d7b12f83daa
parent 2158 0b620ff10e7c
child 2310 96cca167430a
permissions -rw-r--r--
Bug fixes
alpar@1678
     1
namespace lemon {
alpar@1678
     2
/**
alpar@1678
     3
alpar@1678
     4
\ingroup demos
alpar@1678
     5
\file graph_orientation.cc
alpar@1678
     6
\brief Graph orientation with lower bound requirement on the
alpar@1678
     7
in-degree of the nodes.
alpar@1678
     8
alpar@1684
     9
This demo shows an adaptation of the well-known "preflow push" algorithm to
alpar@1684
    10
a simple graph orientation problem.
alpar@1678
    11
alpar@1684
    12
The input of the problem is a(n undirected) graph and an integer value
alpar@1684
    13
<i>f(n)</i> assigned to each node \e n. The task is to find an orientation
alpar@2158
    14
of the edges for which the number of edge arriving at each node \e n is at
alpar@1684
    15
least least <i>f(n)</i>.
alpar@1684
    16
alpar@1684
    17
In fact, the algorithm reads a directed graph and computes a set of edges to
alpar@1684
    18
be reversed in order to achieve the in-degree requirement.
alpar@1684
    19
This input is given using 
alpar@1684
    20
\ref graph-io-page ".lgf (Lemon Graph Format)" file. It should contain
alpar@1684
    21
three node maps. The one called "f" contains the in-degree requirements, while
alpar@1684
    22
"coordinate_x" and "coordinate_y" indicate the position of the nodes. These
alpar@1684
    23
latter ones are used to generate the output, which is a <tt>.eps</tt> file.
alpar@1684
    24
alpar@1684
    25
alpar@1684
    26
\section go-alg-dec The C++ source file
alpar@1684
    27
alpar@1684
    28
Here you find how to solve the problem above using lemon.
alpar@1684
    29
alpar@1684
    30
\subsection go-alg-head Headers and convenience typedefs
alpar@1678
    31
alpar@1678
    32
First we include some important headers.
alpar@1678
    33
alpar@1678
    34
The first one defines \ref lemon::ListGraph "ListGraph",
alpar@1678
    35
the "Swiss army knife" graph implementation.
alpar@1678
    36
\dontinclude graph_orientation.cc
alpar@1678
    37
\skipline list_graph
alpar@1678
    38
alpar@1678
    39
The next is  to read a \ref graph-io-page ".lgf" (Lemon Graph Format) file.
alpar@1678
    40
\skipline reader
alpar@1678
    41
alpar@1678
    42
This provides us with some special purpose graph \ref maps "maps".
alpar@1678
    43
\skipline iterable
alpar@1678
    44
alpar@1678
    45
The following header defines a simple data structure to store and manipulate
alpar@1678
    46
planar coordinates. It will be used to draw the result.
alpar@1678
    47
\skipline xy
alpar@1678
    48
alpar@1678
    49
And finally, this header contains a simple graph drawing utility.
alpar@1678
    50
\skipline eps
alpar@1678
    51
alpar@1678
    52
As we don't want to type in \ref lemon "lemon::" million times, the
alpar@1678
    53
following line seems to be useful.
alpar@1678
    54
\skipline namespace
alpar@1678
    55
alpar@2172
    56
The following macro will also save a lot of typing by defining some
alpar@2172
    57
convenience <tt>typedef</tt>s.
alpar@2172
    58
alpar@2172
    59
\skipline TYPEDEF
alpar@2172
    60
alpar@2172
    61
Actually, the macro above would be equivalent with the following
alpar@2172
    62
<tt>typedef</tt>s.
alpar@2172
    63
alpar@2172
    64
\code
alpar@2172
    65
typedef ListGraph::Node Node;
alpar@2172
    66
typedef ListGraph::NodeIt NodeIt;
alpar@2172
    67
typedef ListGraph::Edge Edge;
alpar@2172
    68
typedef ListGraph::EdgeIt EdgeIt;
alpar@2172
    69
typedef ListGraph::OutEdgeIt OutEdgeIt;
alpar@2172
    70
typedef ListGraph::InEdgeIt InEdgeIt;
alpar@2172
    71
\endcode
alpar@1678
    72
alpar@1684
    73
\subsection go-alg-main The main() function
alpar@1684
    74
alpar@1678
    75
Well, we are ready to start <tt>main()</tt>.
alpar@1678
    76
\skip main
alpar@1678
    77
\until {
alpar@1678
    78
alpar@1953
    79
First we check whether the program is called with exactly one parameter.
alpar@1678
    80
If it isn't, we print a short help message end exit.
alpar@1678
    81
The vast majority of people would probably skip this block.
alpar@1678
    82
\skip if
alpar@1678
    83
\until }
alpar@1678
    84
alpar@1678
    85
Now, we read a graph \c g, and a map \c f containing
alpar@1684
    86
the in-deg requirements from a \ref graph-io-page ".lgf (Lemon Graph Format)"
alpar@1953
    87
file. To generate the output picture, we also read the node titles (\c label)
alpar@1953
    88
and
alpar@1678
    89
coordinates (\c coords).
alpar@1678
    90
So, first we create the graph
alpar@1678
    91
\skipline ListGraph
alpar@1678
    92
and the corresponding NodeMaps.
alpar@1678
    93
\skipline NodeMap
alpar@1678
    94
\until coords
alpar@1678
    95
\note The graph must be given to the maps' constructor.
alpar@1678
    96
alpar@1678
    97
Then, the following block will read these data from the file, or exit if
alpar@1678
    98
the file is missing or corrupt.
alpar@1678
    99
\skip try
alpar@1678
   100
\until }
alpar@1678
   101
\until }
alpar@1678
   102
alpar@1953
   103
The algorithm needs an integer value assigned to each node. We call this "level" and the nodes are on level 0 at the
alpar@1953
   104
beginning of the execution.
alpar@1953
   105
alpar@1678
   106
\skipline level
alpar@1678
   107
alpar@1678
   108
The deficiency (\c def) of a node is the in-degree requirement minus the 
alpar@1678
   109
actual in-degree.
alpar@1678
   110
alpar@1678
   111
\skip def
alpar@1678
   112
\until subMap
alpar@1678
   113
alpar@1678
   114
A node is \e active if its deficiency is positive (i.e. if it doesn't meet
alpar@1678
   115
the degree requirement).
alpar@1678
   116
\skip active
alpar@1678
   117
\until def
alpar@1678
   118
alpar@1953
   119
We also store in a bool map indicating which edges are reverted.
alpar@1953
   120
Actually this map called \c rev is only
alpar@1678
   121
used to draw these edges with different color in the output picture. The
alpar@1953
   122
algorithm updates this map, but will not use it otherwise.
alpar@1678
   123
\skip rev
alpar@1678
   124
\until reversed
alpar@1678
   125
alpar@1678
   126
The variable \c nodeNum will refer to the number of nodes.
alpar@1678
   127
\skipline nodeNum
alpar@1678
   128
alpar@2158
   129
Here comes the algorithm itself. 
alpar@1953
   130
In each iteration we choose an active node (\c act will do it for us).
alpar@1953
   131
If there is
alpar@1678
   132
no such a node, then the orientation is feasible so we are done.
alpar@1678
   133
\skip act
alpar@1678
   134
\until while
alpar@1678
   135
alpar@2158
   136
Then we check if there exists an edge leaving this node and
alpar@2158
   137
stepping down exactly
alpar@1678
   138
one level.
alpar@1678
   139
\skip OutEdge
alpar@1678
   140
\until while
alpar@1678
   141
alpar@1678
   142
If there exists, we decrease the "activity" of the node \c act by reverting
alpar@1678
   143
this egde.
alpar@1678
   144
Fortunately, \ref lemon::ListGraph "ListGraph"
alpar@1678
   145
has a special function \ref lemon::ListGraph::reverseEdge() "reverseEdge()"
alpar@1678
   146
that makes this easy.
alpar@1678
   147
We also have to update the maps \c def and
alpar@1678
   148
\c rev.
alpar@1678
   149
\skipline if
alpar@1678
   150
\skip if
alpar@1678
   151
\until }
alpar@1678
   152
Otherwise (i.e. if there is no edge stepping down one level). We lift up the
alpar@1678
   153
current active node \c act. If it reaches level \c nodeNum, then there
alpar@1678
   154
exists no appropriate orientation so we stop.
alpar@1678
   155
\skipline else
alpar@1678
   156
\skipline if
alpar@1678
   157
\skipline return
alpar@1678
   158
\until }
alpar@1678
   159
\until }
alpar@1678
   160
\until }
alpar@1678
   161
alpar@1678
   162
Believe it or not, this algorithm works and runs fast.
alpar@1678
   163
alpar@1678
   164
Finally, we print the obtained orientation. Note, how the different
alpar@1678
   165
\c bool values of
alpar@1678
   166
\c rev are transformed into different \ref lemon::Color "RGB color"s
alpar@1678
   167
using the class
alpar@2172
   168
\ref lemon::Palette "Palette"
alpar@1678
   169
and the \ref map_adaptors "map adaptor" called
alpar@1678
   170
\ref lemon::ComposeMap "composeMap".
alpar@1678
   171
alpar@1678
   172
\skip graphToEps
alpar@1678
   173
\until run
alpar@1678
   174
alpar@1678
   175
alpar@1678
   176
\until end of main
alpar@1678
   177
alpar@1678
   178
Finally here are again the list of the used include files (because I can't turn
alpar@1678
   179
this section off.)
alpar@1678
   180
alpar@1678
   181
*/
alpar@1678
   182
alpar@1678
   183
}