Debian Codegraph @

SYMPHONY/Applications/VRP/src/Master/small_graph.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 /* (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 <stdlib.h> /* malloc() is here in AIX ... */
19 #include <string.h>
20
21 /* VRP include files */
22 #include "vrp_types.h"
23 #include "small_graph.h"
24 #include "vrp_master_functions.h"
25 #include "compute_cost.h"
26
27 /*===========================================================================*/
28
29 /*===========================================================================*\
30 * Pick the cheapest edges incident to the nodes, and list them in
31 * g->edges st. the lower numbered nodes are the first in every node pair.
32 \*===========================================================================*/
33
34 void make_small_graph(vrp_problem *p, int plus_edges)
35 {
36 closenode *closenodes;
37 int cost;
38 int ch, pos, last;
39 int v, w;
40 edge_data *nextedge;
41 small_graph *g;
42 distances *dist = &p->dist;
43 int k_closest = p->par.k_closest;
44
45 /*------------------------------------------------------------------------*\
46 * While the others processes are working, pick the cheapest edges incident
47 * to each of the nodes
48 \*------------------------------------------------------------------------*/
49 closenodes = (closenode *)
50 calloc (p->vertnum, sizeof(closenode));
51
52 g = p->g = (small_graph *) calloc (1, sizeof(small_graph));
53 g->vertnum = p->vertnum;
54 g->allocated_edgenum = (k_closest+1) * (p->vertnum-1) + plus_edges;
55 g->edges = (edge_data *) calloc
56 (g->allocated_edgenum, sizeof(edge_data));
57
58 for (v=0, nextedge=g->edges; v < p->vertnum; v++){
59 /*---------------------------------------------------------------------*\
60 | Using binary tree pick the k closest node to v. |
61 \*---------------------------------------------------------------------*/
62 for (last=0, w=0; w < p->vertnum; w++){
63 if (v == w)
64 continue;
65 cost = ICOST(dist, v, w);
66 if ((last < k_closest) || ((last < p->vertnum) && (!v))){
67 pos = ++last;
68 while ((ch=pos/2) != 0){
69 if (closenodes[ch].cost >= cost) break;
70 (void) memcpy ((char *)(closenodes+pos),
71 (char *)(closenodes+ch), sizeof(closenode));
72 pos = ch;
73 }
74 }else{
75 if (closenodes[1].cost <= cost)
76 continue;
77 pos = 1;
78 while ((ch=2*pos) < last){
79 if (closenodes[ch].cost < closenodes[ch+1].cost)
80 ch++;
81 if (cost >= closenodes[ch].cost)
82 break;
83 (void) memcpy ((char *)(closenodes+pos),
84 (char *)(closenodes+ch), sizeof(closenode));
85 pos = ch;
86 }
87 if (ch == last)
88 if (cost < closenodes[ch].cost){
89 (void) memcpy ((char *)(closenodes+pos),
90 (char *)(closenodes+ch), sizeof(closenode));
91 pos = ch;
92 }
93 }
94 closenodes[pos].node = w;
95 closenodes[pos].cost = cost;
96 }
97
98 /*---------------------------------------------------------------------*\
99 | Record those close edges in g->edges. |
100 \*---------------------------------------------------------------------*/
101 for (pos=last; pos>0; pos--){
102 if ((w=closenodes[pos].node) < v){
103 nextedge->v0 = w;
104 nextedge->v1 = v;
105 }else{
106 nextedge->v0 = v;
107 nextedge->v1 = w;
108 }
109 (nextedge++)->cost = closenodes[pos].cost;
110 }
111 }
112
113 g->edgenum = (k_closest+1) * (p->vertnum-1);
114 free ((char *)closenodes);
115 delete_dup_edges(g);
116 }
117
118 /*===========================================================================*/
119
120 void save_small_graph(vrp_problem *vrp)
121 {
122 FILE *sgfile;
123 small_graph *g = vrp->g;
124 edge_data *ed;
125 int i, j;
126 _node *tour;
127
128 if ((sgfile = fopen(vrp->par.small_graph_file, "w")) == NULL){
129 printf(" **************** Couldn't open small_graph_file for save!!\n");
130 return;
131 }
132 fprintf(sgfile, "p %5i %7i\n", g->vertnum, g->edgenum);
133 for (i=g->edgenum, ed=g->edges; i; i--, ed++)
134 fprintf(sgfile, "a %5i %5i %i\n", ed->v0, ed->v1, ed->cost);
135
136 tour = vrp->cur_tour->tour;
137 fprintf(sgfile, "cost %i\n", vrp->cur_tour->cost);
138 fprintf(sgfile, "numroutes %i\n", vrp->cur_tour->numroutes);
139 for (j = 0; j < g->vertnum; j++)
140 fprintf(sgfile, "%i %i\n", tour[j].next, tour[j].route);
141
142 fclose(sgfile);
143 }
144
145 /*===========================================================================*/
146
147 void read_small_graph(vrp_problem *vrp)
148 {
149 FILE *sgfile;
150 small_graph *g;
151 edge_data *ed;
152 int i, j;
153 _node *tour;
154
155 if ((sgfile = fopen(vrp->par.small_graph_file, "r")) == NULL){
156 printf(" **************** Couldn't open small_graph_file for load!!\n");
157 exit(-1);
158 }
159 g = vrp->g = (small_graph *) calloc (1, sizeof(small_graph));
160 fscanf(sgfile, "p %5i %7i\n", &g->vertnum, &g->edgenum);
161 g->allocated_edgenum = g->edgenum;
162 g->del_edgenum = 0;
163 g->edges = (edge_data *) malloc (g->edgenum * sizeof(edge_data));
164
165 for (i=g->edgenum, ed=g->edges; i; i--, ed++)
166 fscanf(sgfile, "a %5i %5i %i\n", &ed->v0, &ed->v1, &ed->cost);
167
168 tour = vrp->cur_tour->tour;
169 fscanf(sgfile, "cost %i\n", &vrp->cur_tour->cost);
170 fscanf(sgfile, "numroutes %i\n", &vrp->cur_tour->numroutes);
171 for (j=0; j<g->vertnum; j++)
172 fscanf(sgfile, "%i %i\n", &tour[j].next, &tour[j].route);
173
174 fclose(sgfile);
175 }