COIN-OR::LEMON - Graph Library

Changeset 1684:df3820d7989d in lemon-0.x


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

Better doc.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/graph_orientation.dox

    r1678 r1684  
    77in-degree of the nodes.
    88
     9This demo shows an adaptation of the well-known "preflow push" algorithm to
     10a simple graph orientation problem.
    911
     12The 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
     14of the edges for which the number of edge arriving to each node \e n is at
     15least least <i>f(n)</i>.
     16
     17In fact, the algorithm reads a directed graph and computes a set of edges to
     18be reversed in order to achieve the in-degree requirement.
     19This input is given using
     20\ref graph-io-page ".lgf (Lemon Graph Format)" file. It should contain
     21three 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
     23latter 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
     28Here you find how to solve the problem above using lemon.
     29
     30\subsection go-alg-head Headers and convenience typedefs
    1031
    1132First we include some important headers.
     
    3758\until InEdgeIt
    3859
     60\subsection go-alg-main The main() function
     61
    3962Well, we are ready to start <tt>main()</tt>.
    4063\skip main
     
    4871
    4972Now, 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)
     73the in-deg requirements from a \ref graph-io-page ".lgf (Lemon Graph Format)"
    5174file. To generate the output picture, we also read the node titles (\c id) and
    5275coordinates (\c coords).
Note: See TracChangeset for help on using the changeset viewer.