1.1 --- a/doc/graph_orientation.dox	Tue Sep 13 12:41:02 2005 +0000
     1.2 +++ b/doc/graph_orientation.dox	Wed Sep 14 10:00:43 2005 +0000
     1.3 @@ -6,7 +6,28 @@
     1.4  \brief Graph orientation with lower bound requirement on the
     1.5  in-degree of the nodes.
     1.6  
     1.7 +This demo shows an adaptation of the well-known "preflow push" algorithm to
     1.8 +a simple graph orientation problem.
     1.9  
    1.10 +The input of the problem is a(n undirected) graph and an integer value
    1.11 +<i>f(n)</i> assigned to each node \e n. The task is to find an orientation
    1.12 +of the edges for which the number of edge arriving to each node \e n is at
    1.13 +least least <i>f(n)</i>.
    1.14 +
    1.15 +In fact, the algorithm reads a directed graph and computes a set of edges to
    1.16 +be reversed in order to achieve the in-degree requirement.
    1.17 +This input is given using 
    1.18 +\ref graph-io-page ".lgf (Lemon Graph Format)" file. It should contain
    1.19 +three node maps. The one called "f" contains the in-degree requirements, while
    1.20 +"coordinate_x" and "coordinate_y" indicate the position of the nodes. These
    1.21 +latter ones are used to generate the output, which is a <tt>.eps</tt> file.
    1.22 +
    1.23 +
    1.24 +\section go-alg-dec The C++ source file
    1.25 +
    1.26 +Here you find how to solve the problem above using lemon.
    1.27 +
    1.28 +\subsection go-alg-head Headers and convenience typedefs
    1.29  
    1.30  First we include some important headers.
    1.31  
    1.32 @@ -36,6 +57,8 @@
    1.33  \skip typedef
    1.34  \until InEdgeIt
    1.35  
    1.36 +\subsection go-alg-main The main() function
    1.37 +
    1.38  Well, we are ready to start <tt>main()</tt>.
    1.39  \skip main
    1.40  \until {
    1.41 @@ -47,7 +70,7 @@
    1.42  \until }
    1.43  
    1.44  Now, we read a graph \c g, and a map \c f containing
    1.45 -the in-deg requirements from a \ref graph-io-page ".lgf" (Lemon Graph Format)
    1.46 +the in-deg requirements from a \ref graph-io-page ".lgf (Lemon Graph Format)"
    1.47  file. To generate the output picture, we also read the node titles (\c id) and
    1.48  coordinates (\c coords).
    1.49  So, first we create the graph