Open64 (mfef90, whirl2f, and IR tools)
TAG: version-openad; SVN changeset: 916
|
00001 /* 00002 00003 Copyright (C) 2000, 2001 Silicon Graphics, Inc. All Rights Reserved. 00004 00005 This program is free software; you can redistribute it and/or modify it 00006 under the terms of version 2 of the GNU General Public License as 00007 published by the Free Software Foundation. 00008 00009 This program is distributed in the hope that it would be useful, but 00010 WITHOUT ANY WARRANTY; without even the implied warranty of 00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00012 00013 Further, this software is distributed without any warranty that it is 00014 free of the rightful claim of any third person regarding infringement 00015 or the like. Any license provided herein, whether implied or 00016 otherwise, applies only to this software file. Patent licenses, if 00017 any, provided herein do not apply to combinations of this program with 00018 other software, or any other product whatsoever. 00019 00020 You should have received a copy of the GNU General Public License along 00021 with this program; if not, write the Free Software Foundation, Inc., 59 00022 Temple Place - Suite 330, Boston MA 02111-1307, USA. 00023 00024 Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pky, 00025 Mountain View, CA 94043, or: 00026 00027 http://www.sgi.com 00028 00029 For further information regarding this notice, see: 00030 00031 http://oss.sgi.com/projects/GenInfo/NoticeExplan 00032 00033 */ 00034 00035 00036 /* ---------------------------------------------------------------------- 00037 * This code adapted by Robert Kennedy from a Push-Relabel 00038 * implementation developed in 1994 at the Stanford University 00039 * department of Computer Science by Boris Cherkassky and Andrew 00040 * Goldberg ([email protected]). 00041 * 00042 * The program implements the "highest level" node selection strategy 00043 * with the global relabeling and gap relabeling heuristics. 00044 * ---------------------------------------------------------------------- 00045 */ 00046 #if 0 00047 00048 #include <sys/types.h> 00049 #include <sys/times.h> 00050 00051 #include "mfmc_defs.h" 00052 00053 #define GLOB_UPDT_FREQ 1.0 00054 00055 /* global variables */ 00056 00057 static INT32 n; /* number of nodes */ 00058 static MFMC_NODE *nodes; /* array of nodes */ 00059 static MFMC_ARC *arcs; /* array of arcs */ 00060 static MFMC_LAYER *layers; /* array of layers */ 00061 static INT64 *cap; /* array of capacities */ 00062 static MFMC_NODE *source; /* origin */ 00063 static MFMC_NODE *sink; /* destination */ 00064 static MFMC_STATS *stats; /* statistics */ 00065 static MFMC_NODE **queue; /* queue for storing nodes */ 00066 static MFMC_NODE **q_read, **q_write; /* queue pointers */ 00067 00068 static INT32 lmax; /* maximal layer */ 00069 static INT32 lmax_push; /* maximal layer with excess node */ 00070 static INT32 lmin_push; /* minimal layer with excess node */ 00071 00072 static INT64 biggest_flow; /* upper bound on the flow value */ 00073 /*--- initialization */ 00074 00075 /*********************************************************************/ 00076 /* */ 00077 /* current processor time in seconds */ 00078 /* difference between two calls is processor time spent by your code */ 00079 /* needs: <sys/types.h>, <sys/times.h> */ 00080 /* depends on compiler and OS */ 00081 /* */ 00082 /*********************************************************************/ 00083 00084 float timer(void) 00085 { 00086 struct tms hold; 00087 00088 times(&hold); 00089 return (float) hold.tms_utime / 60.0; 00090 } 00091 00092 static BOOL 00093 pr_init(INT32 n_p, /* number of nodes */ 00094 MFMC_NODE *nodes_p, /* array of nodes */ 00095 MFMC_ARC *arcs_p, /* array of arcs */ 00096 INT64 *cap_p, /* array of given capacities */ 00097 MFMC_NODE *source_p, /* the source node */ 00098 MFMC_NODE *sink_p, /* the sink node */ 00099 MFMC_NODE **queue_p, /* the BFS node queue */ 00100 MFMC_LAYER *layers_p, /* distance level structure */ 00101 MFMC_STATS *stats_p, /* statistics block */ 00102 INT64 flow_upper_bound) /* flow value upper bound */ 00103 00104 { 00105 MFMC_NODE *i; /* current node */ 00106 00107 n = n_p; 00108 nodes = nodes_p; 00109 arcs = arcs_p; 00110 cap = cap_p; 00111 source = source_p; 00112 sink = sink_p; 00113 stats = stats_p; 00114 queue = queue_p; 00115 layers = layers_p; 00116 00117 for (i = nodes; i < nodes + n; i++) { 00118 i->excess = 0; 00119 } 00120 00121 source->excess = biggest_flow = flow_upper_bound; 00122 00123 lmax = n - 1; 00124 00125 return MFMC_NO_ERROR; 00126 } /* end of initialization */ 00127 00128 00129 /*--- global rank update - breadth first search */ 00130 00131 static void 00132 def_ranks (void) 00133 00134 { 00135 MFMC_NODE *i, *j, *jn; /* current nodes */ 00136 MFMC_ARC *a; /* current arc */ 00137 MFMC_LAYER *l; /* current layer */ 00138 INT32 j_rank; /* rank of node j */ 00139 00140 stats->n_up++; /* statistics */ 00141 00142 /* initialization */ 00143 for (i = nodes; i < nodes + n; i++) { 00144 i->rank = n; 00145 } 00146 00147 sink->rank = 0; 00148 00149 *queue = sink; 00150 00151 for (l = layers; l <= layers + lmax; l++) { 00152 l->push_first = NULL; 00153 l->trans_first = NULL; 00154 } 00155 00156 lmax = lmax_push = 0; 00157 lmin_push = n; 00158 00159 /* breadth first search */ 00160 for (q_read = queue, q_write = queue + 1; 00161 q_read != q_write; 00162 q_read++) { 00163 /* scanning arcs incident to node i */ 00164 i = *q_read; 00165 j_rank = i->rank + 1; 00166 00167 for (a = i->first; a != NULL; a = a->next) { 00168 j = a->head; 00169 00170 if (j->rank == n) { 00171 /* j is not labelled */ 00172 if (a->reverse->r_cap > 0 ) { 00173 /* arc (j, i) is not saturated */ 00174 j->rank = j_rank; 00175 j->current = j->first; 00176 00177 l = layers + j_rank; 00178 if (j_rank > lmax) lmax = j_rank; 00179 00180 if (j->excess > 0) { 00181 j->nl_next = l->push_first; 00182 l->push_first = j; 00183 if (j_rank > lmax_push) lmax_push = j_rank; 00184 if (j_rank < lmin_push) lmin_push = j_rank; 00185 } 00186 else { 00187 /* j->excess == 0 */ 00188 jn = l->trans_first; 00189 j->nl_next = jn; 00190 if (jn != NULL) jn->nl_prev = j; 00191 l->trans_first = j; 00192 } 00193 00194 /* put j to scanning queue */ 00195 *q_write = j; 00196 q_write++; 00197 } 00198 } 00199 } /* node "i" is scanned */ 00200 } /* end of scanning queue */ 00201 } /* end of global update */ 00202 00203 /*--- removing excessive flow - second phase of PR-algorithm */ 00204 00205 static void 00206 prefl_to_flow (void) 00207 00208 { 00209 MFMC_NODE *i,*j, *ir, *is, *it, *front; /* current nodes */ 00210 MFMC_ARC *a; /* current arc */ 00211 INT64 path_cap; /* path capacity */ 00212 BOOL path, out_of_path; /* flags */ 00213 00214 /* initialization */ 00215 for (i = nodes + n; i >= nodes; i--) { 00216 i->current = i->first; 00217 i->nl_next = NULL; 00218 } 00219 00220 /* removing flow from excessive nodes */ 00221 for (i = nodes; i < nodes + n; i ++) { 00222 if (i->excess <= 0 || i == source || i == sink) continue; 00223 00224 /* i - has positive excess */ 00225 for (front = i; i->excess > 0;) { 00226 /* looking for path from i to the source 00227 (cycle may occur) */ 00228 00229 while (front != source) { 00230 for (a = front->current; ; a = a->next) { 00231 if (cap[a - arcs] == 0 && 00232 a->r_cap > 0) 00233 break; 00234 } 00235 front->current = a; 00236 00237 j = a->head; 00238 00239 front->nl_next = j; 00240 front = j; 00241 00242 if (j->nl_next != NULL) 00243 /* cycle is found */ 00244 break; 00245 } /* while (front != source) */ 00246 00247 /* either path from i to the source or cycle is found */ 00248 00249 if (front == source) { 00250 path = TRUE; 00251 is = i; 00252 path_cap = i->excess; 00253 } 00254 else { 00255 path = FALSE; 00256 is = j; 00257 path_cap = biggest_flow; 00258 } 00259 00260 /* finding capacity of the path (cycle) */ 00261 00262 front = ir = is; 00263 00264 do { 00265 a = ir->current; 00266 00267 if (a->r_cap < path_cap) { 00268 front = ir; 00269 path_cap = a ->r_cap; 00270 } 00271 ir = ir->nl_next; 00272 00273 } while (ir != j); 00274 00275 if (path) i->excess -= path_cap; 00276 00277 /* reducing flows along the path */ 00278 00279 ir = is; 00280 out_of_path = 0; 00281 00282 do { 00283 a = ir->current; 00284 a->r_cap -= path_cap; 00285 a->reverse->r_cap += path_cap; 00286 00287 it = ir->nl_next; 00288 00289 if (ir == front) out_of_path = 1; 00290 if (out_of_path) ir->nl_next = NULL; 00291 00292 ir = it; 00293 00294 } while (ir != j); 00295 00296 } /* now excess of i is 0 */ 00297 } 00298 } /* end of prefl_to_flow */ 00299 00300 /*--- cleaning beyond the gap */ 00301 00302 static BOOL 00303 gap (MFMC_LAYER *le) /* pointer to the empty layer */ 00304 00305 { 00306 MFMC_LAYER *l; /* current layer */ 00307 MFMC_NODE *i; /* current nodes */ 00308 INT32 r; /* rank of the layer before l */ 00309 BOOL cc; /* cc = TRUE - no nodes with positive excess before 00310 the gap */ 00311 00312 stats->n_gap++; /* statistics */ 00313 00314 r = (le - layers) - 1; 00315 00316 /* putting ranks beyond the gap to "infinity" */ 00317 00318 for (l = le + 1; l <= layers + lmax; l++) { 00319 for (i = l->push_first; i != NULL; i = i->nl_next) { 00320 i->rank = n; 00321 stats->n_gnode ++; /* statistics */ 00322 } 00323 00324 for (i = l->trans_first; i != NULL; i = i->nl_next) { 00325 i->rank = n; 00326 stats->n_gnode ++; /* statistics */ 00327 } 00328 00329 l->push_first = l->trans_first = NULL; 00330 } 00331 00332 cc = (lmin_push > r) ? TRUE : FALSE; 00333 00334 lmax = r; 00335 lmax_push = r; 00336 00337 return cc; 00338 } /* end of gap */ 00339 00340 00341 /*--- pushing flow from node i */ 00342 00343 static BOOL 00344 push (MFMC_NODE *i) 00345 00346 { 00347 MFMC_NODE *j; /* sucsessor of i */ 00348 MFMC_NODE *j_next, *j_prev; /* j's sucsessor and predecessor in layer list */ 00349 INT32 j_rank; /* rank of the next layer */ 00350 MFMC_LAYER *lj; /* j's layer */ 00351 MFMC_ARC *a; /* current arc (i,j) */ 00352 INT64 fl; /* flow to push through the arc */ 00353 00354 j_rank = i->rank - 1; 00355 00356 /* scanning arcs outgoing from i */ 00357 00358 for (a = i->current; a != NULL; a = a->next) { 00359 if (a->r_cap > 0) { 00360 /* "a" is not saturated */ 00361 00362 j = a->head; 00363 if (j->rank == j_rank) { 00364 /* j belongs to the next layer */ 00365 00366 fl = MIN(i->excess, a->r_cap); 00367 00368 a->r_cap -= fl; 00369 a->reverse->r_cap += fl; 00370 stats->n_push ++; /* statistics */ 00371 00372 if (j_rank > 0) { 00373 lj = layers + j_rank; 00374 00375 if (j->excess == 0) { 00376 /* before current push j had zero excess */ 00377 00378 /* remove j from the list of transit nodes */ 00379 j_next = j->nl_next; 00380 00381 if (lj->trans_first == j) 00382 /* j starts the list */ 00383 lj->trans_first = j_next; 00384 else { 00385 /* j is not the first */ 00386 j_prev = j->nl_prev; 00387 j_prev->nl_next = j_next; 00388 if (j_next != NULL) 00389 j_next->nl_prev = j_prev; 00390 } 00391 00392 /* put j to the push-list */ 00393 j->nl_next = lj->push_first; 00394 lj->push_first = j; 00395 00396 if (j_rank < lmin_push) 00397 lmin_push = j_rank; 00398 } /* j->excess == 0 */ 00399 } /* j->rank > 0 */ 00400 00401 j->excess += fl; 00402 i->excess -= fl; 00403 00404 if (i->excess == 0) break; 00405 00406 } /* j belongs to the next layer */ 00407 } /* a is not saturated */ 00408 } /* end of scanning arcs from i */ 00409 00410 i->current = a; 00411 00412 return a == NULL; 00413 } /* end of push */ 00414 00415 /*--- relabeling node i */ 00416 00417 static INT32 00418 relabel (MFMC_NODE *i) 00419 00420 { 00421 MFMC_NODE *j; /* sucsessor of i */ 00422 INT32 j_rank; /* minimal rank of a node available from j */ 00423 MFMC_ARC *a; /* current arc */ 00424 MFMC_ARC *a_j; /* an arc which leads to the node with minimal rank */ 00425 MFMC_LAYER *l; /* layer for node i */ 00426 00427 stats->n_rel++; /* statistics */ 00428 00429 i->rank = j_rank = n; 00430 00431 /* looking for a node with minimal rank available from i */ 00432 00433 for (a = i->first; a != NULL; a = a->next) { 00434 if (a->r_cap > 0) { 00435 j = a->head; 00436 00437 if (j->rank < j_rank) 00438 { 00439 j_rank = j->rank; 00440 a_j = a; 00441 } 00442 } 00443 } 00444 00445 if (j_rank < n) { 00446 i->rank = ++j_rank; 00447 i->current = a_j; 00448 00449 l = layers + j_rank; 00450 00451 if (i->excess > 0) { 00452 i->nl_next = l->push_first; 00453 l->push_first = i; 00454 if (j_rank > lmax_push) lmax_push = j_rank; 00455 if (j_rank < lmin_push) lmin_push = j_rank; 00456 } 00457 else { 00458 j = l->trans_first; 00459 i->nl_next = j; 00460 if (j != 0) j->nl_prev = i; 00461 l->trans_first = i; 00462 } 00463 00464 if (j_rank > lmax) lmax = j_rank; 00465 } /* end of j_rank < n */ 00466 00467 return j_rank; 00468 } /* end of relabel */ 00469 00470 00471 /* entry point */ 00472 00473 BOOL 00474 MFMC_Find_max_flow_min_cut(INT32 n_p, 00475 MFMC_NODE *nodes_p, 00476 MFMC_ARC *arcs_p, 00477 INT64 *cap_p, 00478 MFMC_NODE *source_p, 00479 MFMC_NODE *sink_p, 00480 MFMC_NODE **queue_p, 00481 MFMC_LAYER *layers_p, 00482 INT64 flow_upper_bound, 00483 MFMC_STATS *stats_p, 00484 INT64 *fl) 00485 00486 { 00487 MFMC_NODE *i; /* current node */ 00488 MFMC_NODE *j; /* i-sucsessor in layer list */ 00489 INT32 i_rank; /* rank of i */ 00490 MFMC_LAYER *l; /* current layer */ 00491 INT32 n_r; /* the number of recent relabels */ 00492 BOOL cc; /* condition code */ 00493 MFMC_STATS stat_buf; /* local buffer in case user doesn't care */ 00494 00495 if (stats_p != NULL) { 00496 stats_p->time = timer(); 00497 } 00498 cc = pr_init(n_p, nodes_p, arcs_p, cap_p, source_p, sink_p, 00499 queue_p, layers_p, 00500 (stats_p != NULL ? stats_p : &stat_buf), 00501 flow_upper_bound); 00502 00503 if (cc != MFMC_NO_ERROR) return cc; 00504 00505 def_ranks(); 00506 00507 n_r = 0; 00508 00509 /* highest level method */ 00510 00511 while (lmax_push >= lmin_push) { 00512 /* main loop */ 00513 l = layers + lmax_push; 00514 00515 i = l->push_first; 00516 00517 if (i == NULL) { 00518 /* nothing to push from this level */ 00519 lmax_push --; 00520 } 00521 else { 00522 l->push_first = i->nl_next; 00523 00524 cc = push(i); 00525 00526 if (cc) { /* i must be relabeled */ 00527 00528 relabel(i); 00529 n_r ++; 00530 00531 if (l->push_first == NULL && 00532 l->trans_first == NULL) { 00533 /* gap is found */ 00534 gap ( l ); 00535 } 00536 00537 /* checking the necessity of global update */ 00538 if (n_r > GLOB_UPDT_FREQ * (float) n) { 00539 /* it is time for global update */ 00540 def_ranks (); 00541 n_r = 0; 00542 } 00543 } 00544 else { /* excess is pushed out of i */ 00545 j = l->trans_first; 00546 i->nl_next = j; 00547 l->trans_first = i; 00548 if (j != NULL) j->nl_prev = i; 00549 } 00550 } 00551 } /* end of the main loop */ 00552 00553 #if 1 00554 *fl = sink->excess; 00555 #else 00556 *fl += sink->excess; 00557 #endif 00558 00559 prefl_to_flow(); 00560 00561 if (stats_p != NULL) { 00562 stats_p->time = timer() - stats_p->time; 00563 } 00564 00565 return MFMC_NO_ERROR; 00566 } /* end of constructing flow */ 00567 00568 #endif