doc/graph_orientation.dox
changeset 1697 4c593a4096da
parent 1678 b7b7125a5fe8
child 1715 e71778873dd0
equal deleted inserted replaced
0:c2c78dc83fb3 1:96f1df77173d
     4 \ingroup demos
     4 \ingroup demos
     5 \file graph_orientation.cc
     5 \file graph_orientation.cc
     6 \brief Graph orientation with lower bound requirement on the
     6 \brief Graph orientation with lower bound requirement on the
     7 in-degree of the nodes.
     7 in-degree of the nodes.
     8 
     8 
       
     9 This demo shows an adaptation of the well-known "preflow push" algorithm to
       
    10 a simple graph orientation problem.
     9 
    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 to 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
    10 
    31 
    11 First we include some important headers.
    32 First we include some important headers.
    12 
    33 
    13 The first one defines \ref lemon::ListGraph "ListGraph",
    34 The first one defines \ref lemon::ListGraph "ListGraph",
    14 the "Swiss army knife" graph implementation.
    35 the "Swiss army knife" graph implementation.
    34 
    55 
    35 The following <tt>typedef</tt>s will also save a lot of typing.
    56 The following <tt>typedef</tt>s will also save a lot of typing.
    36 \skip typedef
    57 \skip typedef
    37 \until InEdgeIt
    58 \until InEdgeIt
    38 
    59 
       
    60 \subsection go-alg-main The main() function
       
    61 
    39 Well, we are ready to start <tt>main()</tt>.
    62 Well, we are ready to start <tt>main()</tt>.
    40 \skip main
    63 \skip main
    41 \until {
    64 \until {
    42 
    65 
    43 First we check whether the program is called with exactly 1 parameter.
    66 First we check whether the program is called with exactly 1 parameter.
    45 The vast majority of people would probably skip this block.
    68 The vast majority of people would probably skip this block.
    46 \skip if
    69 \skip if
    47 \until }
    70 \until }
    48 
    71 
    49 Now, we read a graph \c g, and a map \c f containing
    72 Now, we read a graph \c g, and a map \c f containing
    50 the in-deg requirements from a \ref graph-io-page ".lgf" (Lemon Graph Format)
    73 the in-deg requirements from a \ref graph-io-page ".lgf (Lemon Graph Format)"
    51 file. To generate the output picture, we also read the node titles (\c id) and
    74 file. To generate the output picture, we also read the node titles (\c id) and
    52 coordinates (\c coords).
    75 coordinates (\c coords).
    53 So, first we create the graph
    76 So, first we create the graph
    54 \skipline ListGraph
    77 \skipline ListGraph
    55 and the corresponding NodeMaps.
    78 and the corresponding NodeMaps.