doc/graph_orientation.dox
changeset 2167 7e109b222053
parent 1953 d4f411003580
child 2172 4b25e7003868
equal deleted inserted replaced
3:14376c5a0d48 4:e1873d126fbe
     9 This demo shows an adaptation of the well-known "preflow push" algorithm to
     9 This demo shows an adaptation of the well-known "preflow push" algorithm to
    10 a simple graph orientation problem.
    10 a simple graph orientation problem.
    11 
    11 
    12 The input of the problem is a(n undirected) graph and an integer value
    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
    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
    14 of the edges for which the number of edge arriving at each node \e n is at
    15 least least <i>f(n)</i>.
    15 least least <i>f(n)</i>.
    16 
    16 
    17 In fact, the algorithm reads a directed graph and computes a set of edges to
    17 In fact, the algorithm reads a directed graph and computes a set of edges to
    18 be reversed in order to achieve the in-degree requirement.
    18 be reversed in order to achieve the in-degree requirement.
    19 This input is given using 
    19 This input is given using 
   111 \until reversed
   111 \until reversed
   112 
   112 
   113 The variable \c nodeNum will refer to the number of nodes.
   113 The variable \c nodeNum will refer to the number of nodes.
   114 \skipline nodeNum
   114 \skipline nodeNum
   115 
   115 
   116 Here comes the algorithms itself. 
   116 Here comes the algorithm itself. 
   117 In each iteration we choose an active node (\c act will do it for us).
   117 In each iteration we choose an active node (\c act will do it for us).
   118 If there is
   118 If there is
   119 no such a node, then the orientation is feasible so we are done.
   119 no such a node, then the orientation is feasible so we are done.
   120 \skip act
   120 \skip act
   121 \until while
   121 \until while
   122 
   122 
   123 Then we check if there exists an edge leaving this node that steps down exactly
   123 Then we check if there exists an edge leaving this node and
       
   124 stepping down exactly
   124 one level.
   125 one level.
   125 \skip OutEdge
   126 \skip OutEdge
   126 \until while
   127 \until while
   127 
   128 
   128 If there exists, we decrease the "activity" of the node \c act by reverting
   129 If there exists, we decrease the "activity" of the node \c act by reverting