Debian Codegraph @

SYMPHONY/Applications/VRP/src/Heuristics/binomial.c

raw
1 /*===========================================================================*/
2 /* */
3 /* This file is part of a demonstration application for use with the */
4 /* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */
5 /* the Vehicle Routing Problem and the Traveling Salesman Problem. */
6 /* */
7 /* This application was developed by Ted Ralphs ([email protected]) */
8 /* This file was modified by Ali Pilatin January, 2005 ([email protected]) */
9 /* */
10 /* (c) Copyright 2000-2005 Ted Ralphs. All Rights Reserved. */
11 /* */
12 /* This software is licensed under the Eclipse Public License. Please see */
13 /* accompanying file for terms. */
14 /* */
15 /*===========================================================================*/
16
17 #include <stdio.h>
18
19 #include "sym_constants.h"
20 #include "sym_macros.h"
21 #include "binomial.h"
22 #include "vrp_const.h"
23 #include <stdlib.h>
24
25
26 /*-----------------------------------------------------------------------*\
27 | The functions in this file are the standard operations on binomial heaps|
28 | I will not bother to comment each one of them. See a standard data |
29 | structures text for an explanation of these algorithms |
30 \*-----------------------------------------------------------------------*/
31
32 tree_node *make_heap(int cust_num, int savings, int node1,
33 int node2)
34 {
35 tree_node *head;
36
37 head = (tree_node *) calloc (1, sizeof(tree_node));
38
39 head->cust_num = cust_num;
40 head->savings = savings;
41 head->node1 = node1;
42 head->node2 = node2;
43
44 return(head);
45 }
46
47 /*===========================================================================*/
48
49 tree_node *find_max(tree_node *head)
50 {
51 tree_node *max_ptr = NULL, *temp;
52 register int max_val = (-1)*MAXINT;
53
54 temp = head;
55 while (temp != NULL){
56 if (temp->savings > max_val){
57 max_val = temp->savings;
58 max_ptr = temp;
59 }
60 temp = temp->sibling;
61 }
62 return(max_ptr);
63 }
64
65 /*===========================================================================*/
66
67 void link_trees(tree_node *tree1, tree_node *tree2)
68 {
69 tree1->parent = tree2;
70 tree1->sibling = tree2->child;
71 tree2->child = tree1;
72 (tree2->degree)++;
73 }
74
75 /*===========================================================================*/
76
77 tree_node *merge_roots(tree_node *head1, tree_node *head2)
78 {
79 tree_node *head, *temp, *temp1, *temp2;
80 int cur_deg;
81
82 if (!head1) return(head2);
83 if (!head2) return(head1);
84
85 cur_deg = MIN(head1->degree, head2->degree);
86
87 if (head1->degree == cur_deg){
88 head = head1;
89 temp = head;
90 temp1 = head1->sibling;
91 temp2 = head2;
92 }
93 else{
94 head = head2;
95 temp = head;
96 temp2 = head2->sibling;
97 temp1 = head1;
98 }
99
100 while ((temp1 != NULL) && (temp2 != NULL)){
101
102 cur_deg = MIN(temp1->degree, temp2->degree);
103
104 if (temp1->degree == cur_deg){
105 temp->sibling = temp1;
106 temp = temp->sibling;
107 temp1 = temp1->sibling;
108 }
109 if (temp2->degree == cur_deg){
110 temp->sibling = temp2;
111 temp = temp->sibling;
112 temp2 = temp2->sibling;
113 }
114 }
115 if (temp1)
116 temp->sibling = temp1;
117 if (temp2)
118 temp->sibling = temp2;
119
120 return(head);
121 }
122
123 /*===========================================================================*/
124
125 tree_node *merge_heaps(tree_node *head1, tree_node *head2)
126 {
127 tree_node *head, *cur, *next, *prev=NULL;
128
129 head = merge_roots(head1, head2);
130 if (head == NULL) return(head);
131 cur = head;
132 next = cur->sibling;
133
134 if(!head1) return(head2);
135
136 while (next != NULL){
137 if ((cur->degree != next->degree) ||
138 ((next->sibling != NULL) && (cur->degree == next->sibling->degree))){
139 prev = cur;
140 cur = next;
141 }
142 else if (cur->savings >= next->savings){
143 cur->sibling = next->sibling;
144 link_trees(next, cur);
145 }
146 else if (prev == NULL){
147 head = next;
148 link_trees(cur, next);
149 cur = next;
150 }
151 else{
152 prev->sibling = next;
153 link_trees(cur, next);
154 cur = next;
155 }
156 next = cur->sibling;
157 }
158
159 return(head);
160 }
161
162 /*===========================================================================*/
163
164 tree_node *heap_insert(tree_node *head, int cust_num, int savings,
165 int node1, int node2)
166 {
167 tree_node *temp;
168
169 temp = make_heap(cust_num, savings, node1, node2);
170 if (head == NULL)
171 return(temp);
172
173 head = merge_heaps(head, temp);
174
175 return(head);
176 }
177
178 /*===========================================================================*/
179
180 tree_node *reverse_list(tree_node *head)
181 {
182 tree_node *temp1, *temp2, *temp3;
183
184 temp1 = head;
185
186 if (!temp1) return(NULL);
187
188 if (!temp1->sibling){
189 temp1->parent = NULL;
190 return(temp1);
191 }
192
193 if (!temp1->sibling->sibling){
194 temp2 = temp1->sibling;
195 temp2->parent = NULL;
196 temp2->sibling = temp1;
197 temp1->sibling = NULL;
198 temp1->parent = NULL;
199 return(temp2);
200 }
201
202
203 temp1 = head;
204 temp1->parent = NULL;
205 temp2 = temp1->sibling;
206 temp2->parent = NULL;
207 temp3 = temp2->sibling;
208 head ->sibling = NULL;
209
210 while (temp3 != NULL){
211 temp3->parent = NULL;
212 temp2->sibling = temp1;
213 temp1 = temp2;
214 temp2 = temp3;
215 temp3 = temp3->sibling;
216 }
217
218 temp2->sibling = temp1;
219
220 return(temp2);
221 }
222
223 /*===========================================================================*/
224
225 tree_node *extract_max(tree_node *head, tree_node *max_ptr)
226 {
227 tree_node *temp;
228
229 temp = head;
230
231 if (max_ptr == head)
232 head = head->sibling;
233 else{
234 while(temp != NULL){
235 if (temp->sibling == max_ptr){
236 temp->sibling = temp->sibling->sibling;
237 break;
238 }
239 temp=temp->sibling;
240 }
241 }
242 if (max_ptr->child){
243 temp = reverse_list(max_ptr->child);
244 head = merge_heaps(temp, head);
245 }
246 return(head);
247 }
248
249 /*===========================================================================*/
250
251 void exchange_data(tree_node *tree_node1, tree_node *tree_node2)
252 {
253 int temp_savings;
254 int temp_cust_num, temp_node1, temp_node2;
255
256 temp_cust_num = tree_node1->cust_num;
257 temp_savings = tree_node1->savings;
258 temp_node1 = tree_node1->node1;
259 temp_node2 = tree_node1->node2;
260 tree_node1->cust_num = tree_node2->cust_num;
261 tree_node1->savings = tree_node2->savings;
262 tree_node1->node1 = tree_node2->node1;
263 tree_node1->node2 = tree_node2->node2;
264 tree_node2->cust_num = temp_cust_num;
265 tree_node2->savings = temp_savings;
266 tree_node2->node1 = temp_node1;
267 tree_node2->node2 = temp_node2;
268 }
269
270 /*===========================================================================*/
271
272 void update(tree_node *cur_node, int savings, int node1,
273 int node2)
274 {
275 tree_node *temp1, *temp2;
276
277 if (savings < cur_node->savings){
278 printf("\nError: illegal update call\n");
279 exit(1);
280 }
281
282 cur_node->savings = savings;
283 cur_node->node1 = node1;
284 cur_node->node2 = node2;
285 temp1 = cur_node;
286 temp2 = temp1->parent;
287
288 while ((temp2 != NULL) && (temp1->savings > temp2->savings)){
289 exchange_data(temp1, temp2);
290 temp1 = temp2;
291 temp2 = temp1->parent;
292 }
293 }
294
295 /*===========================================================================*/
296
297 /*-------------------------------------------------------------------------*\
298 | This function prints out the current heap and is for debugging purposes |
299 \*-------------------------------------------------------------------------*/
300
301 int print_tree(tree_node *head)
302 {
303 tree_node *temp;
304 int count = 0;
305
306 temp = head;
307
308 while (temp != NULL){
309 printf(" custnum = %i degree = %i savings = %i node1 = %i node2 = %i",
310 temp->cust_num, temp->degree, temp->savings, temp->node1,
311 temp->node2);
312 if (temp->parent)
313 printf(" parent = %i", temp->parent->cust_num);
314 printf("\n");
315 count++;
316 if (temp->child)
317 count += print_tree(temp->child);
318 temp = temp->sibling;
319 }
320 return(count);
321 }
322