doc/graph_orientation.dox
author alpar
Wed, 09 Aug 2006 12:47:31 +0000
changeset 2169 9f71586a3f74
parent 1953 d4f411003580
child 2172 4b25e7003868
permissions -rw-r--r--
This script lists all the header files included directly or indirectly by a certain header file.
     1 namespace lemon {
     2 /**
     3 
     4 \ingroup demos
     5 \file graph_orientation.cc
     6 \brief Graph orientation with lower bound requirement on the
     7 in-degree of the nodes.
     8 
     9 This demo shows an adaptation of the well-known "preflow push" algorithm to
    10 a simple graph orientation problem.
    11 
    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>.
    16 
    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.
    24 
    25 
    26 \section go-alg-dec The C++ source file
    27 
    28 Here you find how to solve the problem above using lemon.
    29 
    30 \subsection go-alg-head Headers and convenience typedefs
    31 
    32 First we include some important headers.
    33 
    34 The first one defines \ref lemon::ListGraph "ListGraph",
    35 the "Swiss army knife" graph implementation.
    36 \dontinclude graph_orientation.cc
    37 \skipline list_graph
    38 
    39 The next is  to read a \ref graph-io-page ".lgf" (Lemon Graph Format) file.
    40 \skipline reader
    41 
    42 This provides us with some special purpose graph \ref maps "maps".
    43 \skipline iterable
    44 
    45 The following header defines a simple data structure to store and manipulate
    46 planar coordinates. It will be used to draw the result.
    47 \skipline xy
    48 
    49 And finally, this header contains a simple graph drawing utility.
    50 \skipline eps
    51 
    52 As we don't want to type in \ref lemon "lemon::" million times, the
    53 following line seems to be useful.
    54 \skipline namespace
    55 
    56 The 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 
    62 Well, we are ready to start <tt>main()</tt>.
    63 \skip main
    64 \until {
    65 
    66 First we check whether the program is called with exactly one parameter.
    67 If it isn't, we print a short help message end exit.
    68 The vast majority of people would probably skip this block.
    69 \skip if
    70 \until }
    71 
    72 Now, we read a graph \c g, and a map \c f containing
    73 the in-deg requirements from a \ref graph-io-page ".lgf (Lemon Graph Format)"
    74 file. To generate the output picture, we also read the node titles (\c label)
    75 and
    76 coordinates (\c coords).
    77 So, first we create the graph
    78 \skipline ListGraph
    79 and the corresponding NodeMaps.
    80 \skipline NodeMap
    81 \until coords
    82 \note The graph must be given to the maps' constructor.
    83 
    84 Then, the following block will read these data from the file, or exit if
    85 the file is missing or corrupt.
    86 \skip try
    87 \until }
    88 \until }
    89 
    90 The algorithm needs an integer value assigned to each node. We call this "level" and the nodes are on level 0 at the
    91 beginning of the execution.
    92 
    93 \skipline level
    94 
    95 The deficiency (\c def) of a node is the in-degree requirement minus the 
    96 actual in-degree.
    97 
    98 \skip def
    99 \until subMap
   100 
   101 A node is \e active if its deficiency is positive (i.e. if it doesn't meet
   102 the degree requirement).
   103 \skip active
   104 \until def
   105 
   106 We also store in a bool map indicating which edges are reverted.
   107 Actually this map called \c rev is only
   108 used to draw these edges with different color in the output picture. The
   109 algorithm updates this map, but will not use it otherwise.
   110 \skip rev
   111 \until reversed
   112 
   113 The variable \c nodeNum will refer to the number of nodes.
   114 \skipline nodeNum
   115 
   116 Here comes the algorithm itself. 
   117 In each iteration we choose an active node (\c act will do it for us).
   118 If there is
   119 no such a node, then the orientation is feasible so we are done.
   120 \skip act
   121 \until while
   122 
   123 Then we check if there exists an edge leaving this node and
   124 stepping down exactly
   125 one level.
   126 \skip OutEdge
   127 \until while
   128 
   129 If there exists, we decrease the "activity" of the node \c act by reverting
   130 this egde.
   131 Fortunately, \ref lemon::ListGraph "ListGraph"
   132 has a special function \ref lemon::ListGraph::reverseEdge() "reverseEdge()"
   133 that makes this easy.
   134 We also have to update the maps \c def and
   135 \c rev.
   136 \skipline if
   137 \skip if
   138 \until }
   139 Otherwise (i.e. if there is no edge stepping down one level). We lift up the
   140 current active node \c act. If it reaches level \c nodeNum, then there
   141 exists no appropriate orientation so we stop.
   142 \skipline else
   143 \skipline if
   144 \skipline return
   145 \until }
   146 \until }
   147 \until }
   148 
   149 Believe it or not, this algorithm works and runs fast.
   150 
   151 Finally, 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
   154 using the class
   155 \ref lemon::ColorSet "ColorSet"
   156 and 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 
   165 Finally here are again the list of the used include files (because I can't turn
   166 this section off.)
   167 
   168 */
   169 
   170 }