lemon-project-template-glpk

annotate deps/glpk/src/glpqmd.c @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
rev   line source
alpar@9 1 /* glpqmd.c (quotient minimum degree algorithm) */
alpar@9 2
alpar@9 3 /***********************************************************************
alpar@9 4 * This code is part of GLPK (GNU Linear Programming Kit).
alpar@9 5 *
alpar@9 6 * THIS CODE IS THE RESULT OF TRANSLATION OF THE FORTRAN SUBROUTINES
alpar@9 7 * GENQMD, QMDRCH, QMDQT, QMDUPD, AND QMDMRG FROM THE BOOK:
alpar@9 8 *
alpar@9 9 * ALAN GEORGE, JOSEPH W-H LIU. COMPUTER SOLUTION OF LARGE SPARSE
alpar@9 10 * POSITIVE DEFINITE SYSTEMS. PRENTICE-HALL, 1981.
alpar@9 11 *
alpar@9 12 * THE TRANSLATION HAS BEEN DONE WITH THE PERMISSION OF THE AUTHORS
alpar@9 13 * OF THE ORIGINAL FORTRAN SUBROUTINES: ALAN GEORGE AND JOSEPH LIU,
alpar@9 14 * UNIVERSITY OF WATERLOO, WATERLOO, ONTARIO, CANADA.
alpar@9 15 *
alpar@9 16 * The translation was made by Andrew Makhorin <mao@gnu.org>.
alpar@9 17 *
alpar@9 18 * GLPK is free software: you can redistribute it and/or modify it
alpar@9 19 * under the terms of the GNU General Public License as published by
alpar@9 20 * the Free Software Foundation, either version 3 of the License, or
alpar@9 21 * (at your option) any later version.
alpar@9 22 *
alpar@9 23 * GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@9 24 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@9 25 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@9 26 * License for more details.
alpar@9 27 *
alpar@9 28 * You should have received a copy of the GNU General Public License
alpar@9 29 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@9 30 ***********************************************************************/
alpar@9 31
alpar@9 32 #include "glpqmd.h"
alpar@9 33
alpar@9 34 /***********************************************************************
alpar@9 35 * NAME
alpar@9 36 *
alpar@9 37 * genqmd - GENeral Quotient Minimum Degree algorithm
alpar@9 38 *
alpar@9 39 * SYNOPSIS
alpar@9 40 *
alpar@9 41 * #include "glpqmd.h"
alpar@9 42 * void genqmd(int *neqns, int xadj[], int adjncy[], int perm[],
alpar@9 43 * int invp[], int deg[], int marker[], int rchset[], int nbrhd[],
alpar@9 44 * int qsize[], int qlink[], int *nofsub);
alpar@9 45 *
alpar@9 46 * PURPOSE
alpar@9 47 *
alpar@9 48 * This routine implements the minimum degree algorithm. It makes use
alpar@9 49 * of the implicit representation of the elimination graph by quotient
alpar@9 50 * graphs, and the notion of indistinguishable nodes.
alpar@9 51 *
alpar@9 52 * CAUTION
alpar@9 53 *
alpar@9 54 * The adjancy vector adjncy will be destroyed.
alpar@9 55 *
alpar@9 56 * INPUT PARAMETERS
alpar@9 57 *
alpar@9 58 * neqns - number of equations;
alpar@9 59 * (xadj, adjncy) -
alpar@9 60 * the adjancy structure.
alpar@9 61 *
alpar@9 62 * OUTPUT PARAMETERS
alpar@9 63 *
alpar@9 64 * perm - the minimum degree ordering;
alpar@9 65 * invp - the inverse of perm.
alpar@9 66 *
alpar@9 67 * WORKING PARAMETERS
alpar@9 68 *
alpar@9 69 * deg - the degree vector. deg[i] is negative means node i has been
alpar@9 70 * numbered;
alpar@9 71 * marker - a marker vector, where marker[i] is negative means node i
alpar@9 72 * has been merged with another nodeand thus can be ignored;
alpar@9 73 * rchset - vector used for the reachable set;
alpar@9 74 * nbrhd - vector used for neighborhood set;
alpar@9 75 * qsize - vector used to store the size of indistinguishable
alpar@9 76 * supernodes;
alpar@9 77 * qlink - vector used to store indistinguishable nodes, i, qlink[i],
alpar@9 78 * qlink[qlink[i]], ... are the members of the supernode
alpar@9 79 * represented by i.
alpar@9 80 *
alpar@9 81 * PROGRAM SUBROUTINES
alpar@9 82 *
alpar@9 83 * qmdrch, qmdqt, qmdupd.
alpar@9 84 ***********************************************************************/
alpar@9 85
alpar@9 86 void genqmd(int *_neqns, int xadj[], int adjncy[], int perm[],
alpar@9 87 int invp[], int deg[], int marker[], int rchset[], int nbrhd[],
alpar@9 88 int qsize[], int qlink[], int *_nofsub)
alpar@9 89 { int inode, ip, irch, j, mindeg, ndeg, nhdsze, node, np, num,
alpar@9 90 nump1, nxnode, rchsze, search, thresh;
alpar@9 91 # define neqns (*_neqns)
alpar@9 92 # define nofsub (*_nofsub)
alpar@9 93 /* Initialize degree vector and other working variables. */
alpar@9 94 mindeg = neqns;
alpar@9 95 nofsub = 0;
alpar@9 96 for (node = 1; node <= neqns; node++)
alpar@9 97 { perm[node] = node;
alpar@9 98 invp[node] = node;
alpar@9 99 marker[node] = 0;
alpar@9 100 qsize[node] = 1;
alpar@9 101 qlink[node] = 0;
alpar@9 102 ndeg = xadj[node+1] - xadj[node];
alpar@9 103 deg[node] = ndeg;
alpar@9 104 if (ndeg < mindeg) mindeg = ndeg;
alpar@9 105 }
alpar@9 106 num = 0;
alpar@9 107 /* Perform threshold search to get a node of min degree.
alpar@9 108 Variable search point to where search should start. */
alpar@9 109 s200: search = 1;
alpar@9 110 thresh = mindeg;
alpar@9 111 mindeg = neqns;
alpar@9 112 s300: nump1 = num + 1;
alpar@9 113 if (nump1 > search) search = nump1;
alpar@9 114 for (j = search; j <= neqns; j++)
alpar@9 115 { node = perm[j];
alpar@9 116 if (marker[node] >= 0)
alpar@9 117 { ndeg = deg[node];
alpar@9 118 if (ndeg <= thresh) goto s500;
alpar@9 119 if (ndeg < mindeg) mindeg = ndeg;
alpar@9 120 }
alpar@9 121 }
alpar@9 122 goto s200;
alpar@9 123 /* Node has minimum degree. Find its reachable sets by calling
alpar@9 124 qmdrch. */
alpar@9 125 s500: search = j;
alpar@9 126 nofsub += deg[node];
alpar@9 127 marker[node] = 1;
alpar@9 128 qmdrch(&node, xadj, adjncy, deg, marker, &rchsze, rchset, &nhdsze,
alpar@9 129 nbrhd);
alpar@9 130 /* Eliminate all nodes indistinguishable from node. They are given
alpar@9 131 by node, qlink[node], ... . */
alpar@9 132 nxnode = node;
alpar@9 133 s600: num++;
alpar@9 134 np = invp[nxnode];
alpar@9 135 ip = perm[num];
alpar@9 136 perm[np] = ip;
alpar@9 137 invp[ip] = np;
alpar@9 138 perm[num] = nxnode;
alpar@9 139 invp[nxnode] = num;
alpar@9 140 deg[nxnode] = -1;
alpar@9 141 nxnode = qlink[nxnode];
alpar@9 142 if (nxnode > 0) goto s600;
alpar@9 143 if (rchsze > 0)
alpar@9 144 { /* Update the degrees of the nodes in the reachable set and
alpar@9 145 identify indistinguishable nodes. */
alpar@9 146 qmdupd(xadj, adjncy, &rchsze, rchset, deg, qsize, qlink,
alpar@9 147 marker, &rchset[rchsze+1], &nbrhd[nhdsze+1]);
alpar@9 148 /* Reset marker value of nodes in reach set. Update threshold
alpar@9 149 value for cyclic search. Also call qmdqt to form new
alpar@9 150 quotient graph. */
alpar@9 151 marker[node] = 0;
alpar@9 152 for (irch = 1; irch <= rchsze; irch++)
alpar@9 153 { inode = rchset[irch];
alpar@9 154 if (marker[inode] >= 0)
alpar@9 155 { marker[inode] = 0;
alpar@9 156 ndeg = deg[inode];
alpar@9 157 if (ndeg < mindeg) mindeg = ndeg;
alpar@9 158 if (ndeg <= thresh)
alpar@9 159 { mindeg = thresh;
alpar@9 160 thresh = ndeg;
alpar@9 161 search = invp[inode];
alpar@9 162 }
alpar@9 163 }
alpar@9 164 }
alpar@9 165 if (nhdsze > 0)
alpar@9 166 qmdqt(&node, xadj, adjncy, marker, &rchsze, rchset, nbrhd);
alpar@9 167 }
alpar@9 168 if (num < neqns) goto s300;
alpar@9 169 return;
alpar@9 170 # undef neqns
alpar@9 171 # undef nofsub
alpar@9 172 }
alpar@9 173
alpar@9 174 /***********************************************************************
alpar@9 175 * NAME
alpar@9 176 *
alpar@9 177 * qmdrch - Quotient MD ReaCHable set
alpar@9 178 *
alpar@9 179 * SYNOPSIS
alpar@9 180 *
alpar@9 181 * #include "glpqmd.h"
alpar@9 182 * void qmdrch(int *root, int xadj[], int adjncy[], int deg[],
alpar@9 183 * int marker[], int *rchsze, int rchset[], int *nhdsze,
alpar@9 184 * int nbrhd[]);
alpar@9 185 *
alpar@9 186 * PURPOSE
alpar@9 187 *
alpar@9 188 * This subroutine determines the reachable set of a node through a
alpar@9 189 * given subset. The adjancy structure is assumed to be stored in a
alpar@9 190 * quotient graph format.
alpar@9 191 *
alpar@9 192 * INPUT PARAMETERS
alpar@9 193 *
alpar@9 194 * root - the given node not in the subset;
alpar@9 195 * (xadj, adjncy) -
alpar@9 196 * the adjancy structure pair;
alpar@9 197 * deg - the degree vector. deg[i] < 0 means the node belongs to the
alpar@9 198 * given subset.
alpar@9 199 *
alpar@9 200 * OUTPUT PARAMETERS
alpar@9 201 *
alpar@9 202 * (rchsze, rchset) -
alpar@9 203 * the reachable set;
alpar@9 204 * (nhdsze, nbrhd) -
alpar@9 205 * the neighborhood set.
alpar@9 206 *
alpar@9 207 * UPDATED PARAMETERS
alpar@9 208 *
alpar@9 209 * marker - the marker vector for reach and nbrhd sets. > 0 means the
alpar@9 210 * node is in reach set. < 0 means the node has been merged
alpar@9 211 * with others in the quotient or it is in nbrhd set.
alpar@9 212 ***********************************************************************/
alpar@9 213
alpar@9 214 void qmdrch(int *_root, int xadj[], int adjncy[], int deg[],
alpar@9 215 int marker[], int *_rchsze, int rchset[], int *_nhdsze,
alpar@9 216 int nbrhd[])
alpar@9 217 { int i, istop, istrt, j, jstop, jstrt, nabor, node;
alpar@9 218 # define root (*_root)
alpar@9 219 # define rchsze (*_rchsze)
alpar@9 220 # define nhdsze (*_nhdsze)
alpar@9 221 /* Loop through the neighbors of root in the quotient graph. */
alpar@9 222 nhdsze = 0;
alpar@9 223 rchsze = 0;
alpar@9 224 istrt = xadj[root];
alpar@9 225 istop = xadj[root+1] - 1;
alpar@9 226 if (istop < istrt) return;
alpar@9 227 for (i = istrt; i <= istop; i++)
alpar@9 228 { nabor = adjncy[i];
alpar@9 229 if (nabor == 0) return;
alpar@9 230 if (marker[nabor] == 0)
alpar@9 231 { if (deg[nabor] >= 0)
alpar@9 232 { /* Include nabor into the reachable set. */
alpar@9 233 rchsze++;
alpar@9 234 rchset[rchsze] = nabor;
alpar@9 235 marker[nabor] = 1;
alpar@9 236 goto s600;
alpar@9 237 }
alpar@9 238 /* nabor has been eliminated. Find nodes reachable from
alpar@9 239 it. */
alpar@9 240 marker[nabor] = -1;
alpar@9 241 nhdsze++;
alpar@9 242 nbrhd[nhdsze] = nabor;
alpar@9 243 s300: jstrt = xadj[nabor];
alpar@9 244 jstop = xadj[nabor+1] - 1;
alpar@9 245 for (j = jstrt; j <= jstop; j++)
alpar@9 246 { node = adjncy[j];
alpar@9 247 nabor = - node;
alpar@9 248 if (node < 0) goto s300;
alpar@9 249 if (node == 0) goto s600;
alpar@9 250 if (marker[node] == 0)
alpar@9 251 { rchsze++;
alpar@9 252 rchset[rchsze] = node;
alpar@9 253 marker[node] = 1;
alpar@9 254 }
alpar@9 255 }
alpar@9 256 }
alpar@9 257 s600: ;
alpar@9 258 }
alpar@9 259 return;
alpar@9 260 # undef root
alpar@9 261 # undef rchsze
alpar@9 262 # undef nhdsze
alpar@9 263 }
alpar@9 264
alpar@9 265 /***********************************************************************
alpar@9 266 * NAME
alpar@9 267 *
alpar@9 268 * qmdqt - Quotient MD Quotient graph Transformation
alpar@9 269 *
alpar@9 270 * SYNOPSIS
alpar@9 271 *
alpar@9 272 * #include "glpqmd.h"
alpar@9 273 * void qmdqt(int *root, int xadj[], int adjncy[], int marker[],
alpar@9 274 * int *rchsze, int rchset[], int nbrhd[]);
alpar@9 275 *
alpar@9 276 * PURPOSE
alpar@9 277 *
alpar@9 278 * This subroutine performs the quotient graph transformation after a
alpar@9 279 * node has been eliminated.
alpar@9 280 *
alpar@9 281 * INPUT PARAMETERS
alpar@9 282 *
alpar@9 283 * root - the node just eliminated. It becomes the representative of
alpar@9 284 * the new supernode;
alpar@9 285 * (xadj, adjncy) -
alpar@9 286 * the adjancy structure;
alpar@9 287 * (rchsze, rchset) -
alpar@9 288 * the reachable set of root in the old quotient graph;
alpar@9 289 * nbrhd - the neighborhood set which will be merged with root to form
alpar@9 290 * the new supernode;
alpar@9 291 * marker - the marker vector.
alpar@9 292 *
alpar@9 293 * UPDATED PARAMETERS
alpar@9 294 *
alpar@9 295 * adjncy - becomes the adjncy of the quotient graph.
alpar@9 296 ***********************************************************************/
alpar@9 297
alpar@9 298 void qmdqt(int *_root, int xadj[], int adjncy[], int marker[],
alpar@9 299 int *_rchsze, int rchset[], int nbrhd[])
alpar@9 300 { int inhd, irch, j, jstop, jstrt, link, nabor, node;
alpar@9 301 # define root (*_root)
alpar@9 302 # define rchsze (*_rchsze)
alpar@9 303 irch = 0;
alpar@9 304 inhd = 0;
alpar@9 305 node = root;
alpar@9 306 s100: jstrt = xadj[node];
alpar@9 307 jstop = xadj[node+1] - 2;
alpar@9 308 if (jstop >= jstrt)
alpar@9 309 { /* Place reach nodes into the adjacent list of node. */
alpar@9 310 for (j = jstrt; j <= jstop; j++)
alpar@9 311 { irch++;
alpar@9 312 adjncy[j] = rchset[irch];
alpar@9 313 if (irch >= rchsze) goto s400;
alpar@9 314 }
alpar@9 315 }
alpar@9 316 /* Link to other space provided by the nbrhd set. */
alpar@9 317 link = adjncy[jstop+1];
alpar@9 318 node = - link;
alpar@9 319 if (link >= 0)
alpar@9 320 { inhd++;
alpar@9 321 node = nbrhd[inhd];
alpar@9 322 adjncy[jstop+1] = - node;
alpar@9 323 }
alpar@9 324 goto s100;
alpar@9 325 /* All reachable nodes have been saved. End the adjacent list.
alpar@9 326 Add root to the neighborhood list of each node in the reach
alpar@9 327 set. */
alpar@9 328 s400: adjncy[j+1] = 0;
alpar@9 329 for (irch = 1; irch <= rchsze; irch++)
alpar@9 330 { node = rchset[irch];
alpar@9 331 if (marker[node] >= 0)
alpar@9 332 { jstrt = xadj[node];
alpar@9 333 jstop = xadj[node+1] - 1;
alpar@9 334 for (j = jstrt; j <= jstop; j++)
alpar@9 335 { nabor = adjncy[j];
alpar@9 336 if (marker[nabor] < 0)
alpar@9 337 { adjncy[j] = root;
alpar@9 338 goto s600;
alpar@9 339 }
alpar@9 340 }
alpar@9 341 }
alpar@9 342 s600: ;
alpar@9 343 }
alpar@9 344 return;
alpar@9 345 # undef root
alpar@9 346 # undef rchsze
alpar@9 347 }
alpar@9 348
alpar@9 349 /***********************************************************************
alpar@9 350 * NAME
alpar@9 351 *
alpar@9 352 * qmdupd - Quotient MD UPDate
alpar@9 353 *
alpar@9 354 * SYNOPSIS
alpar@9 355 *
alpar@9 356 * #include "glpqmd.h"
alpar@9 357 * void qmdupd(int xadj[], int adjncy[], int *nlist, int list[],
alpar@9 358 * int deg[], int qsize[], int qlink[], int marker[], int rchset[],
alpar@9 359 * int nbrhd[]);
alpar@9 360 *
alpar@9 361 * PURPOSE
alpar@9 362 *
alpar@9 363 * This routine performs degree update for a set of nodes in the minimum
alpar@9 364 * degree algorithm.
alpar@9 365 *
alpar@9 366 * INPUT PARAMETERS
alpar@9 367 *
alpar@9 368 * (xadj, adjncy) -
alpar@9 369 * the adjancy structure;
alpar@9 370 * (nlist, list) -
alpar@9 371 * the list of nodes whose degree has to be updated.
alpar@9 372 *
alpar@9 373 * UPDATED PARAMETERS
alpar@9 374 *
alpar@9 375 * deg - the degree vector;
alpar@9 376 * qsize - size of indistinguishable supernodes;
alpar@9 377 * qlink - linked list for indistinguishable nodes;
alpar@9 378 * marker - used to mark those nodes in reach/nbrhd sets.
alpar@9 379 *
alpar@9 380 * WORKING PARAMETERS
alpar@9 381 *
alpar@9 382 * rchset - the reachable set;
alpar@9 383 * nbrhd - the neighborhood set.
alpar@9 384 *
alpar@9 385 * PROGRAM SUBROUTINES
alpar@9 386 *
alpar@9 387 * qmdmrg.
alpar@9 388 ***********************************************************************/
alpar@9 389
alpar@9 390 void qmdupd(int xadj[], int adjncy[], int *_nlist, int list[],
alpar@9 391 int deg[], int qsize[], int qlink[], int marker[], int rchset[],
alpar@9 392 int nbrhd[])
alpar@9 393 { int deg0, deg1, il, inhd, inode, irch, j, jstop, jstrt, mark,
alpar@9 394 nabor, nhdsze, node, rchsze;
alpar@9 395 # define nlist (*_nlist)
alpar@9 396 /* Find all eliminated supernodes that are adjacent to some nodes
alpar@9 397 in the given list. Put them into (nhdsze, nbrhd). deg0 contains
alpar@9 398 the number of nodes in the list. */
alpar@9 399 if (nlist <= 0) return;
alpar@9 400 deg0 = 0;
alpar@9 401 nhdsze = 0;
alpar@9 402 for (il = 1; il <= nlist; il++)
alpar@9 403 { node = list[il];
alpar@9 404 deg0 += qsize[node];
alpar@9 405 jstrt = xadj[node];
alpar@9 406 jstop = xadj[node+1] - 1;
alpar@9 407 for (j = jstrt; j <= jstop; j++)
alpar@9 408 { nabor = adjncy[j];
alpar@9 409 if (marker[nabor] == 0 && deg[nabor] < 0)
alpar@9 410 { marker[nabor] = -1;
alpar@9 411 nhdsze++;
alpar@9 412 nbrhd[nhdsze] = nabor;
alpar@9 413 }
alpar@9 414 }
alpar@9 415 }
alpar@9 416 /* Merge indistinguishable nodes in the list by calling the
alpar@9 417 subroutine qmdmrg. */
alpar@9 418 if (nhdsze > 0)
alpar@9 419 qmdmrg(xadj, adjncy, deg, qsize, qlink, marker, &deg0, &nhdsze,
alpar@9 420 nbrhd, rchset, &nbrhd[nhdsze+1]);
alpar@9 421 /* Find the new degrees of the nodes that have not been merged. */
alpar@9 422 for (il = 1; il <= nlist; il++)
alpar@9 423 { node = list[il];
alpar@9 424 mark = marker[node];
alpar@9 425 if (mark == 0 || mark == 1)
alpar@9 426 { marker[node] = 2;
alpar@9 427 qmdrch(&node, xadj, adjncy, deg, marker, &rchsze, rchset,
alpar@9 428 &nhdsze, nbrhd);
alpar@9 429 deg1 = deg0;
alpar@9 430 if (rchsze > 0)
alpar@9 431 { for (irch = 1; irch <= rchsze; irch++)
alpar@9 432 { inode = rchset[irch];
alpar@9 433 deg1 += qsize[inode];
alpar@9 434 marker[inode] = 0;
alpar@9 435 }
alpar@9 436 }
alpar@9 437 deg[node] = deg1 - 1;
alpar@9 438 if (nhdsze > 0)
alpar@9 439 { for (inhd = 1; inhd <= nhdsze; inhd++)
alpar@9 440 { inode = nbrhd[inhd];
alpar@9 441 marker[inode] = 0;
alpar@9 442 }
alpar@9 443 }
alpar@9 444 }
alpar@9 445 }
alpar@9 446 return;
alpar@9 447 # undef nlist
alpar@9 448 }
alpar@9 449
alpar@9 450 /***********************************************************************
alpar@9 451 * NAME
alpar@9 452 *
alpar@9 453 * qmdmrg - Quotient MD MeRGe
alpar@9 454 *
alpar@9 455 * SYNOPSIS
alpar@9 456 *
alpar@9 457 * #include "qmdmrg.h"
alpar@9 458 * void qmdmrg(int xadj[], int adjncy[], int deg[], int qsize[],
alpar@9 459 * int qlink[], int marker[], int *deg0, int *nhdsze, int nbrhd[],
alpar@9 460 * int rchset[], int ovrlp[]);
alpar@9 461 *
alpar@9 462 * PURPOSE
alpar@9 463 *
alpar@9 464 * This routine merges indistinguishable nodes in the minimum degree
alpar@9 465 * ordering algorithm. It also computes the new degrees of these new
alpar@9 466 * supernodes.
alpar@9 467 *
alpar@9 468 * INPUT PARAMETERS
alpar@9 469 *
alpar@9 470 * (xadj, adjncy) -
alpar@9 471 * the adjancy structure;
alpar@9 472 * deg0 - the number of nodes in the given set;
alpar@9 473 * (nhdsze, nbrhd) -
alpar@9 474 * the set of eliminated supernodes adjacent to some nodes in
alpar@9 475 * the set.
alpar@9 476 *
alpar@9 477 * UPDATED PARAMETERS
alpar@9 478 *
alpar@9 479 * deg - the degree vector;
alpar@9 480 * qsize - size of indistinguishable nodes;
alpar@9 481 * qlink - linked list for indistinguishable nodes;
alpar@9 482 * marker - the given set is given by those nodes with marker value set
alpar@9 483 * to 1. Those nodes with degree updated will have marker value
alpar@9 484 * set to 2.
alpar@9 485 *
alpar@9 486 * WORKING PARAMETERS
alpar@9 487 *
alpar@9 488 * rchset - the reachable set;
alpar@9 489 * ovrlp - temp vector to store the intersection of two reachable sets.
alpar@9 490 ***********************************************************************/
alpar@9 491
alpar@9 492 void qmdmrg(int xadj[], int adjncy[], int deg[], int qsize[],
alpar@9 493 int qlink[], int marker[], int *_deg0, int *_nhdsze, int nbrhd[],
alpar@9 494 int rchset[], int ovrlp[])
alpar@9 495 { int deg1, head, inhd, iov, irch, j, jstop, jstrt, link, lnode,
alpar@9 496 mark, mrgsze, nabor, node, novrlp, rchsze, root;
alpar@9 497 # define deg0 (*_deg0)
alpar@9 498 # define nhdsze (*_nhdsze)
alpar@9 499 /* Initialization. */
alpar@9 500 if (nhdsze <= 0) return;
alpar@9 501 for (inhd = 1; inhd <= nhdsze; inhd++)
alpar@9 502 { root = nbrhd[inhd];
alpar@9 503 marker[root] = 0;
alpar@9 504 }
alpar@9 505 /* Loop through each eliminated supernode in the set
alpar@9 506 (nhdsze, nbrhd). */
alpar@9 507 for (inhd = 1; inhd <= nhdsze; inhd++)
alpar@9 508 { root = nbrhd[inhd];
alpar@9 509 marker[root] = -1;
alpar@9 510 rchsze = 0;
alpar@9 511 novrlp = 0;
alpar@9 512 deg1 = 0;
alpar@9 513 s200: jstrt = xadj[root];
alpar@9 514 jstop = xadj[root+1] - 1;
alpar@9 515 /* Determine the reachable set and its intersection with the
alpar@9 516 input reachable set. */
alpar@9 517 for (j = jstrt; j <= jstop; j++)
alpar@9 518 { nabor = adjncy[j];
alpar@9 519 root = - nabor;
alpar@9 520 if (nabor < 0) goto s200;
alpar@9 521 if (nabor == 0) break;
alpar@9 522 mark = marker[nabor];
alpar@9 523 if (mark == 0)
alpar@9 524 { rchsze++;
alpar@9 525 rchset[rchsze] = nabor;
alpar@9 526 deg1 += qsize[nabor];
alpar@9 527 marker[nabor] = 1;
alpar@9 528 }
alpar@9 529 else if (mark == 1)
alpar@9 530 { novrlp++;
alpar@9 531 ovrlp[novrlp] = nabor;
alpar@9 532 marker[nabor] = 2;
alpar@9 533 }
alpar@9 534 }
alpar@9 535 /* From the overlapped set, determine the nodes that can be
alpar@9 536 merged together. */
alpar@9 537 head = 0;
alpar@9 538 mrgsze = 0;
alpar@9 539 for (iov = 1; iov <= novrlp; iov++)
alpar@9 540 { node = ovrlp[iov];
alpar@9 541 jstrt = xadj[node];
alpar@9 542 jstop = xadj[node+1] - 1;
alpar@9 543 for (j = jstrt; j <= jstop; j++)
alpar@9 544 { nabor = adjncy[j];
alpar@9 545 if (marker[nabor] == 0)
alpar@9 546 { marker[node] = 1;
alpar@9 547 goto s1100;
alpar@9 548 }
alpar@9 549 }
alpar@9 550 /* Node belongs to the new merged supernode. Update the
alpar@9 551 vectors qlink and qsize. */
alpar@9 552 mrgsze += qsize[node];
alpar@9 553 marker[node] = -1;
alpar@9 554 lnode = node;
alpar@9 555 s900: link = qlink[lnode];
alpar@9 556 if (link > 0)
alpar@9 557 { lnode = link;
alpar@9 558 goto s900;
alpar@9 559 }
alpar@9 560 qlink[lnode] = head;
alpar@9 561 head = node;
alpar@9 562 s1100: ;
alpar@9 563 }
alpar@9 564 if (head > 0)
alpar@9 565 { qsize[head] = mrgsze;
alpar@9 566 deg[head] = deg0 + deg1 - 1;
alpar@9 567 marker[head] = 2;
alpar@9 568 }
alpar@9 569 /* Reset marker values. */
alpar@9 570 root = nbrhd[inhd];
alpar@9 571 marker[root] = 0;
alpar@9 572 if (rchsze > 0)
alpar@9 573 { for (irch = 1; irch <= rchsze; irch++)
alpar@9 574 { node = rchset[irch];
alpar@9 575 marker[node] = 0;
alpar@9 576 }
alpar@9 577 }
alpar@9 578 }
alpar@9 579 return;
alpar@9 580 # undef deg0
alpar@9 581 # undef nhdsze
alpar@9 582 }
alpar@9 583
alpar@9 584 /* eof */