Debian Codegraph @

SYMPHONY/Applications/SPP/src/Common/spp_common.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 Set Partitioning Problem. */
6 /* */
7 /* (c) Copyright 2005-2007 Marta Eso and Ted Ralphs. All Rights Reserved. */
8 /* */
9 /* This application was originally developed by Marta Eso and was modified */
10 /* Ted Ralphs ([email protected]) */
11 /* */
12 /* This software is licensed under the Eclipse Public License. Please see */
13 /* accompanying file for terms. */
14 /* */
15 /*===========================================================================*/
16
17 /* system include files */
18 #include <stdlib.h>
19 #include <string.h>
20
21 /* SYMPHONY include files */
22 #include "sym_constants.h"
23 #include "sym_macros.h"
24
25 /* SPP include files */
26 #include "spp_constants.h"
27 #include "spp_types.h"
28 #include "spp_common.h"
29 #include "spp_macros.h"
30
31 /*===========================================================================*/
32
33 static col_ordered *lexsort_matrix;
34 static row_ind_type *lexbeg_i, *lexbeg_j;
35 static int lexlength_i, lexlength_j;
36 static double obj_i, obj_j;
37
38 /*===========================================================================*/
39
40 int *spp_lexsort(col_ordered *matrix)
41 {
42 int *order = (int *) malloc( matrix->colnum * ISIZE );
43
44 int i;
45
46 for ( i = matrix->colnum -1; i >= 0; i-- )
47 order[i] = i;
48
49 lexsort_matrix = matrix;
50
51 qsort(order, matrix->colnum, ISIZE, spp_lexcompare);
52
53 return(order);
54
55 }
56
57 /*****************************************************************************
58 * qsort sorts into ascending (<) order.
59 * Return 1 if first elt is greater than second, -1 if less, 0 if equal.
60 *****************************************************************************/
61
62 int spp_lexcompare(const void *i, const void *j)
63 {
64 int k, l; /* run thru the columns indexed by i and j */
65 int *matbeg = lexsort_matrix->matbeg;
66
67 lexbeg_i = lexsort_matrix->matind + matbeg[*(int *)i];
68 lexbeg_j = lexsort_matrix->matind + matbeg[*(int *)j];
69 lexlength_i = matbeg[*(int *)i+1] - matbeg[*(int *)i];
70 lexlength_j = matbeg[*(int *)j+1] - matbeg[*(int *)j];
71 obj_i = lexsort_matrix->obj[*(int *)i];
72 obj_j = lexsort_matrix->obj[*(int *)j];
73
74 for ( k = 0, l = 0; k < lexlength_i && l < lexlength_j; k++, l++) {
75 if (lexbeg_i[k] < lexbeg_j[l]) {
76 return 1;
77 } else if (lexbeg_i[k] > lexbeg_j[l]) {
78 return -1;
79 }
80 }
81
82 if (k < lexlength_i)
83 return 1;
84 if (l < lexlength_j)
85 return -1;
86
87 /* now the two columns are the same. the one with the higher objective
88 coef is the greater */
89 if ( obj_i > obj_j ) {
90 return 1;
91 } else if ( obj_i < obj_j ) {
92 return -1;
93 }
94
95 return 0;
96 }
97
98 /*===========================================================================*/
99
100 void spp_free_cmatrix(col_ordered *m)
101 {
102 if ( m != NULL ) {
103 FREE(m->colnames);
104 FREE(m->col_deleted);
105 FREE(m->obj);
106 FREE(m->matbeg);
107 FREE(m->matind);
108 }
109 }
110
111 /*===========================================================================*/
112
113 void spp_free_rmatrix(row_ordered *m)
114 {
115 if ( m != NULL ) {
116 FREE(m->rownames);
117 FREE(m->row_deleted);
118 FREE(m->rmatbeg);
119 FREE(m->rmatind);
120 }
121 }
122
123 /*===========================================================================*/
124
125 /*****************************************************************************
126 * Transform a column ordered matrix into a row ordered matrix.
127 * Space must be already allocated for rmatbeg and rmatind. Fill out only
128 * rmatbeg and rmatind in rmatrix.
129 * i_tmpm and istar_tmpm temporary arrays of length at least m (allocated
130 * before functio is invoked).
131 *****************************************************************************/
132
133 void spp_column_to_row(col_ordered *cm, row_ordered *rm, int *i_tmpm,
134 int **istar_tmpm)
135 {
136 int rownum = cm->rownum;
137 int colnum = cm->colnum;
138 int *rmatbeg = rm->rmatbeg;
139 int *rmatind = rm->rmatind;
140 int *matbeg = cm->matbeg;
141 row_ind_type *matind = cm->matind;
142 int *row_length = i_tmpm;
143 int **row_pointers = istar_tmpm;
144
145 row_ind_type *col_beg;
146 int col_length;
147 int i, j;
148
149 /* zero out the row_length array */
150 for ( i = rownum-1; i >= 0; i-- )
151 row_length[i] = 0;
152
153 /* for each row count how many columns intersect it */
154 for ( i = cm->nzcnt - 1; i >= 0; i-- )
155 row_length[matind[i]]++;
156
157 /* now set rmatbeg appropriately, and set a pointer to the beginning of
158 each row in rmatind */
159 for ( i = 0, rmatbeg[0] = 0; i < rownum; i++ ) {
160 rmatbeg[i+1] = rmatbeg[i] + row_length[i];
161 row_pointers[i] = rmatind + rmatbeg[i];
162 }
163
164 /* construct rmatind: scan thru each column */
165 for ( i = 0; i < colnum; i++ ) {
166 col_length = matbeg[i+1] - matbeg[i];
167 col_beg = matind + matbeg[i];
168 for ( j = 0; j < col_length; j++ ) {
169 *row_pointers[col_beg[j]] = i;
170 row_pointers[col_beg[j]]++;
171 }
172 }
173 }
174
175 /*===========================================================================*/
176
177 /*****************************************************************************
178 * Transform a row ordered matrix into a column ordered matrix.
179 * Space must be already allocated for matbeg and matind. Fill out only
180 * matbeg and matind in cmatrix.
181 * i_tmpn and rowindstar_tmpn are tmp arrays allocated before this function
182 * is invoked.
183 *****************************************************************************/
184
185 void spp_row_to_column(row_ordered *rm, col_ordered *cm, int *i_tmpn,
186 row_ind_type **rowindstar_tmpn)
187 {
188 int rownum = cm->rownum;
189 int colnum = cm->colnum;
190 int *rmatbeg = rm->rmatbeg;
191 int *rmatind = rm->rmatind;
192 int *matbeg = cm->matbeg;
193 row_ind_type *matind = cm->matind;
194 int *col_length = i_tmpn;
195 row_ind_type **col_pointers = rowindstar_tmpn;
196
197 int *row_beg;
198 int row_length;
199 int i, j;
200
201 /* zero out the col_length array */
202 for ( i = colnum-1; i >= 0; i-- )
203 col_length[i] = 0;
204
205 /* for each column count how many rows intersect it */
206 for ( i = rm->nzcnt - 1; i >= 0; i-- )
207 col_length[rmatind[i]]++;
208
209 /* set matbeg appropriately and set the column-pointers */
210 for ( i = 0, matbeg[0] = 0; i < colnum; i++ ) {
211 matbeg[i+1] = matbeg[i] + col_length[i];
212 col_pointers[i] = matind + matbeg[i];
213 }
214
215 /* construct matind: scan thru each row */
216 for ( i = 0; i < rownum; i++ ) {
217 row_length = rmatbeg[i+1] - rmatbeg[i];
218 row_beg = rmatind + rmatbeg[i];
219 for ( j = 0; j < row_length; j++ ) {
220 *col_pointers[row_beg[j]] = i;
221 col_pointers[row_beg[j]]++;
222 }
223 }
224 }
225
226 /*===========================================================================*/
227
228 /*===========================================================================*
229 * Creates a file name using filename and counter (e.g. if filename is
230 * "aaa.res" and counter is 4, fname will be "aaa_4.res", a handler to
231 * the open file will be returned.
232 *===========================================================================*/
233
234 FILE *get_filehandler(int counter, char *filename, char *fname)
235 {
236 FILE *f;
237 char *dot_pos;
238
239 if ( filename[0] == 0 ) {
240 fprintf(stderr, "ERROR: No filename is given!\n");
241 exit(1);
242 }
243 if ( !strcmp(filename, (char *)"stdout") ) {
244 f = stdout;
245 } else {
246 /* find the last "dot" in filename */
247 if ( (dot_pos = strrchr(filename,'.')) == NULL ) {
248 sprintf(fname, "%s_%i", filename, counter);
249 } else {
250 *dot_pos = 0;
251 sprintf(fname, "%s_%i.%s", filename, counter, dot_pos+1);
252 *dot_pos = '.';
253 }
254 if ((f = fopen(fname, "w")) == NULL) {
255 OPEN_WRITE_ERROR(fname);
256 exit(1);
257 }
258 }
259
260 return(f);
261 }