Changeset 1684:df3820d7989d in lemon0.x for doc/graph_orientation.dox
 Timestamp:
 09/14/05 12:00:43 (16 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2206
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

doc/graph_orientation.dox
r1678 r1684 7 7 indegree of the nodes. 8 8 9 This demo shows an adaptation of the wellknown "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 indegree requirement. 19 This input is given using 20 \ref graphiopage ".lgf (Lemon Graph Format)" file. It should contain 21 three node maps. The one called "f" contains the indegree 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 goalgdec The C++ source file 27 28 Here you find how to solve the problem above using lemon. 29 30 \subsection goalghead Headers and convenience typedefs 10 31 11 32 First we include some important headers. … … 37 58 \until InEdgeIt 38 59 60 \subsection goalgmain The main() function 61 39 62 Well, we are ready to start <tt>main()</tt>. 40 63 \skip main … … 48 71 49 72 Now, we read a graph \c g, and a map \c f containing 50 the indeg requirements from a \ref graphiopage ".lgf " (Lemon Graph Format)73 the indeg requirements from a \ref graphiopage ".lgf (Lemon Graph Format)" 51 74 file. To generate the output picture, we also read the node titles (\c id) and 52 75 coordinates (\c coords).
Note: See TracChangeset
for help on using the changeset viewer.