| 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 |
} |