1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/doc/graph_orientation.dox Mon Sep 12 05:35:36 2005 +0000
1.3 @@ -0,0 +1,142 @@
1.4 +namespace lemon {
1.5 +/**
1.6 +
1.7 +\ingroup demos
1.8 +\file graph_orientation.cc
1.9 +\brief Graph orientation with lower bound requirement on the
1.10 +in-degree of the nodes.
1.11 +
1.12 +
1.13 +
1.14 +First we include some important headers.
1.15 +
1.16 +The first one defines \ref lemon::ListGraph "ListGraph",
1.17 +the "Swiss army knife" graph implementation.
1.18 +\dontinclude graph_orientation.cc
1.19 +\skipline list_graph
1.20 +
1.21 +The next is to read a \ref graph-io-page ".lgf" (Lemon Graph Format) file.
1.22 +\skipline reader
1.23 +
1.24 +This provides us with some special purpose graph \ref maps "maps".
1.25 +\skipline iterable
1.26 +
1.27 +The following header defines a simple data structure to store and manipulate
1.28 +planar coordinates. It will be used to draw the result.
1.29 +\skipline xy
1.30 +
1.31 +And finally, this header contains a simple graph drawing utility.
1.32 +\skipline eps
1.33 +
1.34 +As we don't want to type in \ref lemon "lemon::" million times, the
1.35 +following line seems to be useful.
1.36 +\skipline namespace
1.37 +
1.38 +The following <tt>typedef</tt>s will also save a lot of typing.
1.39 +\skip typedef
1.40 +\until InEdgeIt
1.41 +
1.42 +Well, we are ready to start <tt>main()</tt>.
1.43 +\skip main
1.44 +\until {
1.45 +
1.46 +First we check whether the program is called with exactly 1 parameter.
1.47 +If it isn't, we print a short help message end exit.
1.48 +The vast majority of people would probably skip this block.
1.49 +\skip if
1.50 +\until }
1.51 +
1.52 +Now, we read a graph \c g, and a map \c f containing
1.53 +the in-deg requirements from a \ref graph-io-page ".lgf" (Lemon Graph Format)
1.54 +file. To generate the output picture, we also read the node titles (\c id) and
1.55 +coordinates (\c coords).
1.56 +So, first we create the graph
1.57 +\skipline ListGraph
1.58 +and the corresponding NodeMaps.
1.59 +\skipline NodeMap
1.60 +\until coords
1.61 +\note The graph must be given to the maps' constructor.
1.62 +
1.63 +Then, the following block will read these data from the file, or exit if
1.64 +the file is missing or corrupt.
1.65 +\skip try
1.66 +\until }
1.67 +\until }
1.68 +
1.69 +The algorithm needs a "level" integer value assigned to each node. In the
1.70 +beginning, the nodes are on level 0.
1.71 +\skipline level
1.72 +
1.73 +The deficiency (\c def) of a node is the in-degree requirement minus the
1.74 +actual in-degree.
1.75 +
1.76 +\skip def
1.77 +\until subMap
1.78 +
1.79 +A node is \e active if its deficiency is positive (i.e. if it doesn't meet
1.80 +the degree requirement).
1.81 +\skip active
1.82 +\until def
1.83 +
1.84 +We also store in a bool map which edges are reverted. Actually this is only
1.85 +used to draw these edges with different color in the output picture. The
1.86 +algorithm will update this map called \c rev, but will not use it otherwise.
1.87 +\skip rev
1.88 +\until reversed
1.89 +
1.90 +The variable \c nodeNum will refer to the number of nodes.
1.91 +\skipline nodeNum
1.92 +
1.93 +Here comes the algorithms itself.
1.94 +In each iteration we choose an active node (\c act will store it). If there is
1.95 +no such a node, then the orientation is feasible so we are done.
1.96 +\skip act
1.97 +\until while
1.98 +
1.99 +Then we check if there exists an edge leaving this node that steps down exactly
1.100 +one level.
1.101 +\skip OutEdge
1.102 +\until while
1.103 +
1.104 +If there exists, we decrease the "activity" of the node \c act by reverting
1.105 +this egde.
1.106 +Fortunately, \ref lemon::ListGraph "ListGraph"
1.107 +has a special function \ref lemon::ListGraph::reverseEdge() "reverseEdge()"
1.108 +that makes this easy.
1.109 +We also have to update the maps \c def and
1.110 +\c rev.
1.111 +\skipline if
1.112 +\skip if
1.113 +\until }
1.114 +Otherwise (i.e. if there is no edge stepping down one level). We lift up the
1.115 +current active node \c act. If it reaches level \c nodeNum, then there
1.116 +exists no appropriate orientation so we stop.
1.117 +\skipline else
1.118 +\skipline if
1.119 +\skipline return
1.120 +\until }
1.121 +\until }
1.122 +\until }
1.123 +
1.124 +Believe it or not, this algorithm works and runs fast.
1.125 +
1.126 +Finally, we print the obtained orientation. Note, how the different
1.127 +\c bool values of
1.128 +\c rev are transformed into different \ref lemon::Color "RGB color"s
1.129 +using the class
1.130 +\ref lemon::ColorSet "ColorSet"
1.131 +and the \ref map_adaptors "map adaptor" called
1.132 +\ref lemon::ComposeMap "composeMap".
1.133 +
1.134 +\skip graphToEps
1.135 +\until run
1.136 +
1.137 +
1.138 +\until end of main
1.139 +
1.140 +Finally here are again the list of the used include files (because I can't turn
1.141 +this section off.)
1.142 +
1.143 +*/
1.144 +
1.145 +}
1.146 \ No newline at end of file