equal
deleted
inserted
replaced
61 |
61 |
62 Well, we are ready to start <tt>main()</tt>. |
62 Well, we are ready to start <tt>main()</tt>. |
63 \skip main |
63 \skip main |
64 \until { |
64 \until { |
65 |
65 |
66 First we check whether the program is called with exactly 1 parameter. |
66 First we check whether the program is called with exactly one parameter. |
67 If it isn't, we print a short help message end exit. |
67 If it isn't, we print a short help message end exit. |
68 The vast majority of people would probably skip this block. |
68 The vast majority of people would probably skip this block. |
69 \skip if |
69 \skip if |
70 \until } |
70 \until } |
71 |
71 |
72 Now, we read a graph \c g, and a map \c f containing |
72 Now, we read a graph \c g, and a map \c f containing |
73 the in-deg requirements from a \ref graph-io-page ".lgf (Lemon Graph Format)" |
73 the in-deg requirements from a \ref graph-io-page ".lgf (Lemon Graph Format)" |
74 file. To generate the output picture, we also read the node titles (\c id) and |
74 file. To generate the output picture, we also read the node titles (\c label) |
|
75 and |
75 coordinates (\c coords). |
76 coordinates (\c coords). |
76 So, first we create the graph |
77 So, first we create the graph |
77 \skipline ListGraph |
78 \skipline ListGraph |
78 and the corresponding NodeMaps. |
79 and the corresponding NodeMaps. |
79 \skipline NodeMap |
80 \skipline NodeMap |
84 the file is missing or corrupt. |
85 the file is missing or corrupt. |
85 \skip try |
86 \skip try |
86 \until } |
87 \until } |
87 \until } |
88 \until } |
88 |
89 |
89 The algorithm needs a "level" integer value assigned to each node. In the |
90 The algorithm needs an integer value assigned to each node. We call this "level" and the nodes are on level 0 at the |
90 beginning, the nodes are on level 0. |
91 beginning of the execution. |
|
92 |
91 \skipline level |
93 \skipline level |
92 |
94 |
93 The deficiency (\c def) of a node is the in-degree requirement minus the |
95 The deficiency (\c def) of a node is the in-degree requirement minus the |
94 actual in-degree. |
96 actual in-degree. |
95 |
97 |
99 A node is \e active if its deficiency is positive (i.e. if it doesn't meet |
101 A node is \e active if its deficiency is positive (i.e. if it doesn't meet |
100 the degree requirement). |
102 the degree requirement). |
101 \skip active |
103 \skip active |
102 \until def |
104 \until def |
103 |
105 |
104 We also store in a bool map indicating which edges are reverted. Actually this is only |
106 We also store in a bool map indicating which edges are reverted. |
|
107 Actually this map called \c rev is only |
105 used to draw these edges with different color in the output picture. The |
108 used to draw these edges with different color in the output picture. The |
106 algorithm will update this map called \c rev, but will not use it otherwise. |
109 algorithm updates this map, but will not use it otherwise. |
107 \skip rev |
110 \skip rev |
108 \until reversed |
111 \until reversed |
109 |
112 |
110 The variable \c nodeNum will refer to the number of nodes. |
113 The variable \c nodeNum will refer to the number of nodes. |
111 \skipline nodeNum |
114 \skipline nodeNum |
112 |
115 |
113 Here comes the algorithms itself. |
116 Here comes the algorithms itself. |
114 In each iteration we choose an active node (\c act will store it). If there is |
117 In each iteration we choose an active node (\c act will do it for us). |
|
118 If there is |
115 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. |
116 \skip act |
120 \skip act |
117 \until while |
121 \until while |
118 |
122 |
119 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 that steps down exactly |