Debian Codegraph @

SYMPHONY/Applications/CNRP/src/DrawGraph/cnrp_dg_functions.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 /* Capacitated Network Routing Problems. */
6 /* */
7 /* (c) Copyright 2000-2007 Ted Ralphs. All Rights Reserved. */
8 /* */
9 /* This application was developed by Ted Ralphs ([email protected]) */
10 /* */
11 /* This software is licensed under the Eclipse Public License. Please see */
12 /* accompanying file for terms. */
13 /* */
14 /*===========================================================================*/
15
16 /* system include files */
17 #include <stdio.h>
18 #include <string.h>
19 #include <math.h>
20 #include <stdlib.h>
21
22 /* SYMPHONY include files */
23 #include "sym_constants.h"
24 #include "sym_proccomm.h"
25 #include "sym_dg_params.h"
26 #include "sym_qsort.h"
27
28 /* CNRP include files */
29 #include "cnrp_messages.h"
30 #include "cnrp_common_types.h"
31 #include "cnrp_dg_functions.h"
32 #include "cnrp_macros.h"
33
34 /*===========================================================================*/
35
36 /*===========================================================================*\
37 * This file contains additional user functions for the draw graph process.
38 \*===========================================================================*/
39
40 void init_window(int dg_id, char *name, int width, int height)
41 {
42 if (dg_id){
43 int s_bufid, code;
44 s_bufid = init_send(DataInPlace);
45 send_str(name);
46 send_str(name);
47 /* no change in the default window_desc data structure */
48 code = 4;
49 send_int_array(&code, 1);
50 code = CANVAS_WIDTH;
51 send_int_array(&code, 1);
52 send_int_array(&width, 1);
53 code = CANVAS_HEIGHT;
54 send_int_array(&code, 1);
55 send_int_array(&height, 1);
56 code = VIEWABLE_WIDTH;
57 send_int_array(&code, 1);
58 send_int_array(&width, 1);
59 code = VIEWABLE_HEIGHT;
60 send_int_array(&code, 1);
61 send_int_array(&height, 1);
62 send_msg(dg_id, CTOI_INITIALIZE_WINDOW);
63 freebuf(s_bufid);
64 }
65 }
66
67 /*===========================================================================*/
68
69 void wait_for_click(int dg_id, char *name, int report)
70 {
71 if (dg_id){
72 int s_bufid, r_bufid;
73 s_bufid = init_send(DataInPlace);
74 send_str(name);
75 send_msg(dg_id, report);
76 freebuf(s_bufid);
77 if (report == CTOI_WAIT_FOR_CLICK_AND_REPORT){
78 r_bufid = receive_msg(dg_id, ITOC_CLICK_HAPPENED);
79 freebuf(r_bufid);
80 }
81 }
82 }
83
84 /*===========================================================================*/
85
86 void delete_graph(int dg_id, char *name)
87 {
88 if (dg_id){
89 int s_bufid;
90 s_bufid = init_send(DataInPlace);
91 send_str(name);
92 send_msg(dg_id, CTOI_DELETE_GRAPH);
93 freebuf(s_bufid);
94 }
95 }
96
97 /*===========================================================================*/
98
99 void display_graph(int dg_id, char *name)
100 {
101 if (dg_id){
102 int s_bufid;
103 s_bufid = init_send(DataInPlace);
104 send_str(name);
105 send_msg(dg_id, CTOI_DRAW_GRAPH);
106 freebuf(s_bufid);
107 }
108 }
109
110 /*===========================================================================*/
111
112 void copy_node_set(int dg_id, int clone, char *name)
113 {
114 if (dg_id){
115 int s_bufid;
116 char node_place[MAX_NAME_LENGTH +1] = {"node_placement"};
117 s_bufid = init_send(DataInPlace);
118 if (clone){
119 send_str(node_place);
120 send_str(name);
121 send_str(name);
122 send_msg(dg_id, CTOI_CLONE_WINDOW);
123 }else{
124 send_str(name);
125 send_str(node_place);
126 send_msg(dg_id, CTOI_COPY_GRAPH);
127 }
128 freebuf(s_bufid);
129 }
130 }
131
132 /*===========================================================================*/
133
134 void disp_vrp_tour(int dg_id, int clone, char *name,
135 _node *tour, int vertnum, int numroutes, int report)
136 {
137 if (dg_id){
138 int i, j, prev_j, key = 0, s_bufid, zero = 0;
139 int v0 = 0, v1 = tour[0].next;
140 int edgenum = vertnum+numroutes-1;
141
142 copy_node_set(dg_id, clone, name);
143 s_bufid = init_send(DataInPlace);
144 send_str(name);
145 i = MODIFY_ADD_EDGES;
146 send_int_array(&i, 1);
147 send_int_array(&edgenum, 1);
148 j = INDEX(v0, v1);
149 send_int_array(&j, 1);
150 send_int_array(&v0, 1);
151 send_int_array(&v1, 1);
152 send_int_array(&key, 1);
153 for (i = 1; i < vertnum; i++){
154 v1=tour[v0=v1].next;
155 if (tour[v0].route == tour[v1].route){
156 j = INDEX(v0, v1);
157 send_int_array(&j, 1);
158 send_int_array(&v0, 1);
159 send_int_array(&v1, 1);
160 send_int_array(&key, 1);
161 }else if (v1 == 0){
162 j = INDEX(v0, 0);
163 send_int_array(&j, 1);
164 send_int_array(&v0, 1);
165 send_int_array(&zero, 1);
166 send_int_array(&key, 1);
167 }else{
168 prev_j = j;
169 if ((j = INDEX(v0, 0)) != prev_j){
170 send_int_array(&j, 1);
171 send_int_array(&v0, 1);
172 send_int_array(&zero, 1);
173 send_int_array(&key, 1);
174 }
175 j = INDEX(0, v1);
176 send_int_array(&j, 1);
177 send_int_array(&zero, 1);
178 send_int_array(&v1, 1);
179 send_int_array(&key, 1);
180 }
181 }
182 i = MODIFY_END_OF_MESSAGE;
183 send_int_array(&i, 1);
184 send_msg(dg_id, CTOI_MODIFY_GRAPH);
185 display_graph(dg_id, name);
186 if (report == CTOI_WAIT_FOR_CLICK_NO_REPORT ||
187 report == CTOI_WAIT_FOR_CLICK_AND_REPORT)
188 wait_for_click(dg_id, name, report);
189 }
190 }
191
192 /*===========================================================================*/
193
194 void draw_edge_set_from_edge_data(int dg_id, char *name,
195 int edgenum, edge_data *edges)
196 {
197 if (dg_id){
198 int i, j, key, s_bufid;
199
200 key = 0;
201 s_bufid = init_send(DataInPlace);
202 send_str(name);
203 i = MODIFY_ADD_EDGES;
204 send_int_array(&i, 1);
205 send_int_array(&edgenum, 1);
206 for (i = 0; i < edgenum; i++){
207 j = INDEX(edges[i].v0, edges[i].v1);
208 send_int_array(&j, 1);
209 send_int_array(&edges[i].v0, 1);
210 send_int_array(&edges[i].v1, 1);
211 send_int_array(&key, 1);
212 }
213 i = MODIFY_END_OF_MESSAGE;
214 send_int_array(&i, 1);
215 send_msg(dg_id, CTOI_MODIFY_GRAPH);
216 }
217 }
218
219 /*===========================================================================*/
220
221 void draw_edge_set_from_userind(int dg_id, char *name,
222 int edgenum, int *userind)
223 {
224 if (dg_id){
225 int i, v0, v1, key, s_bufid;
226
227 key = 0;
228 s_bufid = init_send(DataInPlace);
229 send_str(name);
230 i = MODIFY_ADD_EDGES;
231 send_int_array(&i, 1);
232 send_int_array(&edgenum, 1);
233 for (i = 0; i < edgenum; i++){
234 BOTH_ENDS(userind[i], &v0, &v1);
235 send_int_array(userind + i, 1);
236 send_int_array(&v0, 1);
237 send_int_array(&v1, 1);
238 send_int_array(&key, 1);
239 }
240 i = MODIFY_END_OF_MESSAGE;
241 send_int_array(&i, 1);
242 send_msg(dg_id, CTOI_MODIFY_GRAPH);
243 }
244 }
245
246 /*===========================================================================*/
247
248 void draw_weighted_edge_set(int dg_id, char *name,
249 int edgenum, int *userind,
250 double *value, double etol)
251 {
252 if (dg_id){
253 int i, v0, v1, key, s_bufid;
254 char dashpattern[MAX_DASH_PATTERN_LENGTH +1];
255 char weight[MAX_WEIGHT_LENGTH +1];
256
257 strcpy(dashpattern, "4 3");
258 s_bufid = init_send(DataInPlace);
259 send_str(name);
260 i = MODIFY_ADD_EDGES;
261 send_int_array(&i, 1);
262 send_int_array(&edgenum, 1);
263 for (i = 0; i < edgenum; i++){
264 if (!value[i]) continue;
265 BOTH_ENDS(userind[i], &v0, &v1);
266 send_int_array(userind + i, 1);
267 send_int_array(&v0, 1);
268 send_int_array(&v1, 1);
269 if (value[i] > 1-etol && value[i] < 1 + etol){
270 strcpy(weight, "1");
271 key = 8;
272 }else{
273 sprintf(weight, "%.3f", value[i]);
274 key = 10;
275 }
276 send_int_array(&key, 1);
277 send_str(weight);
278 if (key & 2)
279 send_str(dashpattern);
280 }
281 i = MODIFY_END_OF_MESSAGE;
282 send_int_array(&i, 1);
283 send_msg(dg_id, CTOI_MODIFY_GRAPH);
284 }
285 }
286
287 /*===========================================================================*/
288
289 void display_support_graph(int dg_id, int clone, char *name,
290 int edgenum, int *userind,
291 double *value, double etol, int total_edgenum,
292 int report)
293 {
294 double *weights = (double *) calloc(edgenum, DSIZE);
295 int *inds = (int *) calloc(edgenum, ISIZE);
296 int i, j, tmp = 0;
297
298 for (i = 0; i < edgenum; i++){
299 if (userind[i] < total_edgenum){
300 weights[i] += value[i];
301 inds[i] = userind[i];
302 }else{
303 for (j = 0; j < edgenum; j++){
304 if (userind[i] == userind[j] + total_edgenum){
305 weights[j] += value[i];
306 weights[i] = 0;
307 tmp++;
308 break;
309 }
310 }
311 if (j == edgenum){
312 weights[i] += value[i];
313 inds[i] = userind[i] - total_edgenum;
314 }
315 }
316 }
317
318 qsort_di(weights, inds, edgenum);
319
320 if (dg_id){
321 copy_node_set(dg_id, clone, name);
322 draw_weighted_edge_set(dg_id, name, edgenum-tmp, inds+tmp, weights+tmp,
323 etol);
324 display_graph(dg_id, name);
325 if (report == CTOI_WAIT_FOR_CLICK_NO_REPORT ||
326 report == CTOI_WAIT_FOR_CLICK_AND_REPORT)
327 wait_for_click(dg_id, name, report);
328 }
329 free(weights);
330 free(inds);
331 }
332
333 /*===========================================================================*/
334
335 void display_support_graph_flow(int dg_id, int clone, char *name,
336 int edgenum, int flow_start, int *userind,
337 double *value, double etol, int total_edgenum,
338 int report)
339 {
340 int i, j, tmp = 0;
341 double *flow_vals = (double *) calloc(flow_start, DSIZE);
342 int *inds = (int *) calloc(flow_start, ISIZE);
343
344 for (i = 0; i < flow_start; i++){
345 if (userind[i] < total_edgenum){
346 for (j = flow_start; j < edgenum; j++){
347 if (userind[j] == userind[i] + 2*total_edgenum){
348 flow_vals[i] += value[j];
349 break;
350 }
351 }
352 }else if (userind[i] < 2*total_edgenum){
353 for (j = flow_start; j < edgenum; j++){
354 if (userind[j] == userind[i] + 2*total_edgenum){
355 flow_vals[i] += value[j];
356 }
357 }
358 }
359 }
360
361 for (i = 0; i < flow_start; i++){
362 if (userind[i] < total_edgenum){
363 inds[i] = userind[i];
364 }else{
365 for (j = 0; j < edgenum; j++){
366 if (userind[i] == userind[j] + total_edgenum){
367 flow_vals[j] -= flow_vals[i];
368 flow_vals[j] = fabs(flow_vals[j]);
369 flow_vals[i] = 0;
370 break;
371 }
372 }
373 if (j == edgenum){
374 inds[i] = userind[i] - total_edgenum;
375 }
376 }
377 }
378
379 qsort_di(flow_vals, inds, flow_start);
380
381 for (tmp = 0; flow_vals[tmp] < etol; tmp++);
382
383 if (dg_id){
384 copy_node_set(dg_id, clone, name);
385 draw_weighted_edge_set(dg_id, name, flow_start-tmp, inds+tmp,
386 flow_vals+tmp, etol);
387 display_graph(dg_id, name);
388 if (report == CTOI_WAIT_FOR_CLICK_NO_REPORT ||
389 report == CTOI_WAIT_FOR_CLICK_AND_REPORT)
390 wait_for_click(dg_id, name, report);
391 }
392
393 free(flow_vals);
394 }
395
396 /*===========================================================================*/
397
398 void display_compressed_support_graph(int dg_id, int clone, char *name,
399 int edgenum, int *userind,
400 double *value, int report)
401 {
402 if (dg_id){
403 int s_bufid, i;
404
405 copy_node_set(dg_id, clone, name);
406 s_bufid = init_send(DataInPlace);
407 send_str(name);
408 i = CNRP_CTOI_DRAW_FRAC_GRAPH;
409 send_int_array(&i, 1);
410 send_int_array(&edgenum, 1);
411 send_int_array(userind, edgenum);
412 send_dbl_array(value, edgenum);
413 send_msg(dg_id, CTOI_USER_MESSAGE);
414 if (report == CTOI_WAIT_FOR_CLICK_NO_REPORT ||
415 report == CTOI_WAIT_FOR_CLICK_AND_REPORT)
416 wait_for_click(dg_id, name, report);
417 }
418 }
419
420 /*===========================================================================*/
421
422 void display_part_tour(int dg_id, int clone, char *name, int *tour,
423 int numroutes, int report)
424 {
425 if (dg_id){
426 int v0 = 0, v1 = tour[0], nv1, nv0;
427 int s_bufid, i, j;
428 int edgenum = 0, key = 0;
429
430 copy_node_set(dg_id, TRUE, name);
431
432 s_bufid = init_send(DataInPlace);
433 send_str(name);
434 i = MODIFY_ADD_EDGES;
435 send_int_array(&i, 1);
436 /*first count the number of edges*/
437 edgenum++;
438 while (v1 != numroutes){
439 v1 = tour[v0=v1];
440 edgenum++;
441 }
442 send_int_array(&edgenum, 1);
443 /*Now reset and pack the edges themselves*/
444 v0 = 0;
445 v1 = tour[0];
446 nv1 = v1>numroutes?v1-numroutes:0;
447 nv0 = v0>numroutes?v0-numroutes:0;
448 j = INDEX(nv0,nv1);
449 send_int_array(&j, 1);
450 send_int_array(&nv0, 1);
451 send_int_array(&nv1, 1);
452 send_int_array(&key, 1);
453 while (v1 != numroutes){
454 v1 = tour[v0=v1];
455 nv1 = v1>numroutes?v1-numroutes:0;
456 nv0 = v0>numroutes?v0-numroutes:0;
457 j = INDEX(nv0,nv1);
458 send_int_array(&j, 1);
459 send_int_array(&nv0, 1);
460 send_int_array(&nv1, 1);
461 send_int_array(&key, 1);
462 }
463 i = MODIFY_END_OF_MESSAGE;
464 send_int_array(&i, 1);
465 send_msg(dg_id, CTOI_MODIFY_GRAPH);
466 display_graph(dg_id, name);
467 if (report == CTOI_WAIT_FOR_CLICK_NO_REPORT ||
468 report == CTOI_WAIT_FOR_CLICK_AND_REPORT)
469 wait_for_click(dg_id, name, report);
470 }
471 }
472
473 /*===========================================================================*/
474
475 void disp_lb(int dg_id, int clone, char *name, int *tree,
476 dbl_edge_data *best_edges, int vertnum,
477 int numroutes, int report)
478 {
479 if (dg_id){
480 int i, j, s_bufid, zero = 0;
481 int edgenum = vertnum + numroutes - 1;
482
483 copy_node_set(dg_id, clone, name);
484
485 s_bufid = init_send(DataInPlace);
486 send_str(name);
487 i = MODIFY_ADD_EDGES;
488 send_int_array(&i, 1);
489 send_int_array(&edgenum, 1);
490 for (i=1; i < vertnum; i++){
491 j = INDEX(i, tree[i]);
492 send_int_array(&j, 1);
493 send_int_array(&i, 1);
494 send_int_array(tree+i, 1);
495 send_int_array(&zero, 1);
496 }
497
498 for (i=0; i < numroutes; i++){
499 j = INDEX(best_edges[i].v0, best_edges[i].v1);
500 send_int_array(&j, 1);
501 send_int_array(&best_edges[i].v0, 1);
502 send_int_array(&best_edges[i].v1, 1);
503 send_int_array(&zero, 1);
504 }
505 i = MODIFY_END_OF_MESSAGE;
506 send_int_array(&i, 1);
507 send_msg(dg_id, CTOI_MODIFY_GRAPH);
508 display_graph(dg_id, name);
509 if (report == CTOI_WAIT_FOR_CLICK_NO_REPORT ||
510 report == CTOI_WAIT_FOR_CLICK_AND_REPORT)
511 wait_for_click(dg_id, name, report);
512 }
513 }
514
515