Changeset 1684:df3820d7989d in lemon-0.x for doc/graph_orientation.dox

Ignore:
Timestamp:
09/14/05 12:00:43 (16 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2206
Message:

Better doc.

File:
1 edited

Unmodified
Added
Removed
• doc/graph_orientation.dox

 r1678 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 f(n) 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 f(n). 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 .eps 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. \until InEdgeIt \subsection go-alg-main The main() function Well, we are ready to start main(). \skip main 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).
Note: See TracChangeset for help on using the changeset viewer.