Changeset 1684:df3820d7989d in lemon-0.x

Timestamp:

09/14/05 12:00:43 (19 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2206

Message:

Better doc.

File:

• doc/graph_orientation.dox (modified) (3 diffs)

doc/graph_orientation.dox

@@ -7 +7 @@
 in-degree of the nodes.
 
+This demo shows an adaptation of the well-known "preflow push" algorithm to
+a simple graph orientation problem.
 
+The input of the problem is a(n undirected) graph and an integer value
+<i>f(n)</i> assigned to each node \e n. The task is to find an orientation
+of the edges for which the number of edge arriving to each node \e n is at
+least least <i>f(n)</i>.
+
+In fact, the algorithm reads a directed graph and computes a set of edges to
+be reversed in order to achieve the in-degree requirement.
+This input is given using 
+\ref graph-io-page ".lgf (Lemon Graph Format)" file. It should contain
+three node maps. The one called "f" contains the in-degree requirements, while
+"coordinate_x" and "coordinate_y" indicate the position of the nodes. These
+latter ones are used to generate the output, which is a <tt>.eps</tt> file.
+
+
+\section go-alg-dec The C++ source file
+
+Here you find how to solve the problem above using lemon.
+
+\subsection go-alg-head Headers and convenience typedefs
 
 First we include some important headers.
@@ -37 +58 @@
 \until InEdgeIt
 
+\subsection go-alg-main The main() function
+
 Well, we are ready to start <tt>main()</tt>.
 \skip main
@@ -48 +71 @@
 
 Now, we read a graph \c g, and a map \c f containing
-the in-deg requirements from a \ref graph-io-page ".lgf" (Lemon Graph Format)
+the in-deg requirements from a \ref graph-io-page ".lgf (Lemon Graph Format)"
 file. To generate the output picture, we also read the node titles (\c id) and
 coordinates (\c coords).