equal
deleted
inserted
replaced
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 |