alpar@1: /* glpqmd.c (quotient minimum degree algorithm) */
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  This code is part of GLPK (GNU Linear Programming Kit).
alpar@1: *
alpar@1: *  THIS CODE IS THE RESULT OF TRANSLATION OF THE FORTRAN SUBROUTINES
alpar@1: *  GENQMD, QMDRCH, QMDQT, QMDUPD, AND QMDMRG FROM THE BOOK:
alpar@1: *
alpar@1: *  ALAN GEORGE, JOSEPH W-H LIU. COMPUTER SOLUTION OF LARGE SPARSE
alpar@1: *  POSITIVE DEFINITE SYSTEMS. PRENTICE-HALL, 1981.
alpar@1: *
alpar@1: *  THE TRANSLATION HAS BEEN DONE WITH THE PERMISSION OF THE AUTHORS
alpar@1: *  OF THE ORIGINAL FORTRAN SUBROUTINES: ALAN GEORGE AND JOSEPH LIU,
alpar@1: *  UNIVERSITY OF WATERLOO, WATERLOO, ONTARIO, CANADA.
alpar@1: *
alpar@1: *  The translation was made by Andrew Makhorin <mao@gnu.org>.
alpar@1: *
alpar@1: *  GLPK is free software: you can redistribute it and/or modify it
alpar@1: *  under the terms of the GNU General Public License as published by
alpar@1: *  the Free Software Foundation, either version 3 of the License, or
alpar@1: *  (at your option) any later version.
alpar@1: *
alpar@1: *  GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@1: *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@1: *  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@1: *  License for more details.
alpar@1: *
alpar@1: *  You should have received a copy of the GNU General Public License
alpar@1: *  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@1: ***********************************************************************/
alpar@1: 
alpar@1: #include "glpqmd.h"
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  genqmd - GENeral Quotient Minimum Degree algorithm
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  #include "glpqmd.h"
alpar@1: *  void genqmd(int *neqns, int xadj[], int adjncy[], int perm[],
alpar@1: *     int invp[], int deg[], int marker[], int rchset[], int nbrhd[],
alpar@1: *     int qsize[], int qlink[], int *nofsub);
alpar@1: *
alpar@1: *  PURPOSE
alpar@1: *
alpar@1: *  This routine implements the minimum degree algorithm. It makes use
alpar@1: *  of the implicit representation of the elimination graph by quotient
alpar@1: *  graphs, and the notion of indistinguishable nodes.
alpar@1: *
alpar@1: *  CAUTION
alpar@1: *
alpar@1: *  The adjancy vector adjncy will be destroyed.
alpar@1: *
alpar@1: *  INPUT PARAMETERS
alpar@1: *
alpar@1: *  neqns  - number of equations;
alpar@1: *  (xadj, adjncy) -
alpar@1: *           the adjancy structure.
alpar@1: *
alpar@1: *  OUTPUT PARAMETERS
alpar@1: *
alpar@1: *  perm   - the minimum degree ordering;
alpar@1: *  invp   - the inverse of perm.
alpar@1: *
alpar@1: *  WORKING PARAMETERS
alpar@1: *
alpar@1: *  deg    - the degree vector. deg[i] is negative means node i has been
alpar@1: *           numbered;
alpar@1: *  marker - a marker vector, where marker[i] is negative means node i
alpar@1: *           has been merged with another nodeand thus can be ignored;
alpar@1: *  rchset - vector used for the reachable set;
alpar@1: *  nbrhd  - vector used for neighborhood set;
alpar@1: *  qsize  - vector used to store the size of indistinguishable
alpar@1: *           supernodes;
alpar@1: *  qlink  - vector used to store indistinguishable nodes, i, qlink[i],
alpar@1: *           qlink[qlink[i]], ... are the members of the supernode
alpar@1: *           represented by i.
alpar@1: *
alpar@1: *  PROGRAM SUBROUTINES
alpar@1: *
alpar@1: *  qmdrch, qmdqt, qmdupd.
alpar@1: ***********************************************************************/
alpar@1: 
alpar@1: void genqmd(int *_neqns, int xadj[], int adjncy[], int perm[],
alpar@1:       int invp[], int deg[], int marker[], int rchset[], int nbrhd[],
alpar@1:       int qsize[], int qlink[], int *_nofsub)
alpar@1: {     int inode, ip, irch, j, mindeg, ndeg, nhdsze, node, np, num,
alpar@1:          nump1, nxnode, rchsze, search, thresh;
alpar@1: #     define neqns  (*_neqns)
alpar@1: #     define nofsub (*_nofsub)
alpar@1:       /* Initialize degree vector and other working variables. */
alpar@1:       mindeg = neqns;
alpar@1:       nofsub = 0;
alpar@1:       for (node = 1; node <= neqns; node++)
alpar@1:       {  perm[node] = node;
alpar@1:          invp[node] = node;
alpar@1:          marker[node] = 0;
alpar@1:          qsize[node] = 1;
alpar@1:          qlink[node] = 0;
alpar@1:          ndeg = xadj[node+1] - xadj[node];
alpar@1:          deg[node] = ndeg;
alpar@1:          if (ndeg < mindeg) mindeg = ndeg;
alpar@1:       }
alpar@1:       num = 0;
alpar@1:       /* Perform threshold search to get a node of min degree.
alpar@1:          Variable search point to where search should start. */
alpar@1: s200: search = 1;
alpar@1:       thresh = mindeg;
alpar@1:       mindeg = neqns;
alpar@1: s300: nump1 = num + 1;
alpar@1:       if (nump1 > search) search = nump1;
alpar@1:       for (j = search; j <= neqns; j++)
alpar@1:       {  node = perm[j];
alpar@1:          if (marker[node] >= 0)
alpar@1:          {  ndeg = deg[node];
alpar@1:             if (ndeg <= thresh) goto s500;
alpar@1:             if (ndeg < mindeg) mindeg = ndeg;
alpar@1:          }
alpar@1:       }
alpar@1:       goto s200;
alpar@1:       /* Node has minimum degree. Find its reachable sets by calling
alpar@1:          qmdrch. */
alpar@1: s500: search = j;
alpar@1:       nofsub += deg[node];
alpar@1:       marker[node] = 1;
alpar@1:       qmdrch(&node, xadj, adjncy, deg, marker, &rchsze, rchset, &nhdsze,
alpar@1:          nbrhd);
alpar@1:       /* Eliminate all nodes indistinguishable from node. They are given
alpar@1:          by node, qlink[node], ... . */
alpar@1:       nxnode = node;
alpar@1: s600: num++;
alpar@1:       np = invp[nxnode];
alpar@1:       ip = perm[num];
alpar@1:       perm[np] = ip;
alpar@1:       invp[ip] = np;
alpar@1:       perm[num] = nxnode;
alpar@1:       invp[nxnode] = num;
alpar@1:       deg[nxnode] = -1;
alpar@1:       nxnode = qlink[nxnode];
alpar@1:       if (nxnode > 0) goto s600;
alpar@1:       if (rchsze > 0)
alpar@1:       {  /* Update the degrees of the nodes in the reachable set and
alpar@1:             identify indistinguishable nodes. */
alpar@1:          qmdupd(xadj, adjncy, &rchsze, rchset, deg, qsize, qlink,
alpar@1:             marker, &rchset[rchsze+1], &nbrhd[nhdsze+1]);
alpar@1:          /* Reset marker value of nodes in reach set. Update threshold
alpar@1:             value for cyclic search. Also call qmdqt to form new
alpar@1:             quotient graph. */
alpar@1:          marker[node] = 0;
alpar@1:          for (irch = 1; irch <= rchsze; irch++)
alpar@1:          {  inode = rchset[irch];
alpar@1:             if (marker[inode] >= 0)
alpar@1:             {  marker[inode] = 0;
alpar@1:                ndeg = deg[inode];
alpar@1:                if (ndeg < mindeg) mindeg = ndeg;
alpar@1:                if (ndeg <= thresh)
alpar@1:                {  mindeg = thresh;
alpar@1:                   thresh = ndeg;
alpar@1:                   search = invp[inode];
alpar@1:                }
alpar@1:             }
alpar@1:          }
alpar@1:          if (nhdsze > 0)
alpar@1:             qmdqt(&node, xadj, adjncy, marker, &rchsze, rchset, nbrhd);
alpar@1:       }
alpar@1:       if (num < neqns) goto s300;
alpar@1:       return;
alpar@1: #     undef neqns
alpar@1: #     undef nofsub
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  qmdrch - Quotient MD ReaCHable set
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  #include "glpqmd.h"
alpar@1: *  void qmdrch(int *root, int xadj[], int adjncy[], int deg[],
alpar@1: *     int marker[], int *rchsze, int rchset[], int *nhdsze,
alpar@1: *     int nbrhd[]);
alpar@1: *
alpar@1: *  PURPOSE
alpar@1: *
alpar@1: *  This subroutine determines the reachable set of a node through a
alpar@1: *  given subset. The adjancy structure is assumed to be stored in a
alpar@1: *  quotient graph format.
alpar@1: * 
alpar@1: *  INPUT PARAMETERS
alpar@1: *
alpar@1: *  root   - the given node not in the subset;
alpar@1: *  (xadj, adjncy) -
alpar@1: *           the adjancy structure pair;
alpar@1: *  deg    - the degree vector. deg[i] < 0 means the node belongs to the
alpar@1: *           given subset.
alpar@1: *
alpar@1: *  OUTPUT PARAMETERS
alpar@1: *
alpar@1: *  (rchsze, rchset) -
alpar@1: *           the reachable set;
alpar@1: *  (nhdsze, nbrhd) -
alpar@1: *           the neighborhood set.
alpar@1: *
alpar@1: *  UPDATED PARAMETERS
alpar@1: *
alpar@1: *  marker - the marker vector for reach and nbrhd sets. > 0 means the
alpar@1: *           node is in reach set. < 0 means the node has been merged
alpar@1: *           with others in the quotient or it is in nbrhd set.
alpar@1: ***********************************************************************/
alpar@1: 
alpar@1: void qmdrch(int *_root, int xadj[], int adjncy[], int deg[],
alpar@1:       int marker[], int *_rchsze, int rchset[], int *_nhdsze,
alpar@1:       int nbrhd[])
alpar@1: {     int i, istop, istrt, j, jstop, jstrt, nabor, node;
alpar@1: #     define root   (*_root)
alpar@1: #     define rchsze (*_rchsze)
alpar@1: #     define nhdsze (*_nhdsze)
alpar@1:       /* Loop through the neighbors of root in the quotient graph. */
alpar@1:       nhdsze = 0;
alpar@1:       rchsze = 0;
alpar@1:       istrt = xadj[root];
alpar@1:       istop = xadj[root+1] - 1;
alpar@1:       if (istop < istrt) return;
alpar@1:       for (i = istrt; i <= istop; i++)
alpar@1:       {  nabor = adjncy[i];
alpar@1:          if (nabor == 0) return;
alpar@1:          if (marker[nabor] == 0)
alpar@1:          {  if (deg[nabor] >= 0)
alpar@1:             {  /* Include nabor into the reachable set. */
alpar@1:                rchsze++;
alpar@1:                rchset[rchsze] = nabor;
alpar@1:                marker[nabor] = 1;
alpar@1:                goto s600;
alpar@1:             }
alpar@1:             /* nabor has been eliminated. Find nodes reachable from
alpar@1:                it. */
alpar@1:             marker[nabor] = -1;
alpar@1:             nhdsze++;
alpar@1:             nbrhd[nhdsze] = nabor;
alpar@1: s300:       jstrt = xadj[nabor];
alpar@1:             jstop = xadj[nabor+1] - 1;
alpar@1:             for (j = jstrt; j <= jstop; j++)
alpar@1:             {  node = adjncy[j];
alpar@1:                nabor = - node;
alpar@1:                if (node < 0) goto s300;
alpar@1:                if (node == 0) goto s600;
alpar@1:                if (marker[node] == 0)
alpar@1:                {  rchsze++;
alpar@1:                   rchset[rchsze] = node;
alpar@1:                   marker[node] = 1;
alpar@1:                }
alpar@1:             }
alpar@1:          }
alpar@1: s600:    ;
alpar@1:       }
alpar@1:       return;
alpar@1: #     undef root
alpar@1: #     undef rchsze
alpar@1: #     undef nhdsze
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  qmdqt - Quotient MD Quotient graph Transformation
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  #include "glpqmd.h"
alpar@1: *  void qmdqt(int *root, int xadj[], int adjncy[], int marker[],
alpar@1: *     int *rchsze, int rchset[], int nbrhd[]);
alpar@1: *
alpar@1: *  PURPOSE
alpar@1: *
alpar@1: *  This subroutine performs the quotient graph transformation after a
alpar@1: *  node has been eliminated.
alpar@1: *
alpar@1: *  INPUT PARAMETERS
alpar@1: *
alpar@1: *  root   - the node just eliminated. It becomes the representative of
alpar@1: *           the new supernode;
alpar@1: *  (xadj, adjncy) -
alpar@1: *           the adjancy structure;
alpar@1: *  (rchsze, rchset) -
alpar@1: *           the reachable set of root in the old quotient graph;
alpar@1: *  nbrhd  - the neighborhood set which will be merged with root to form
alpar@1: *           the new supernode;
alpar@1: *  marker - the marker vector.
alpar@1: *
alpar@1: *  UPDATED PARAMETERS
alpar@1: *
alpar@1: *  adjncy - becomes the adjncy of the quotient graph.
alpar@1: ***********************************************************************/
alpar@1: 
alpar@1: void qmdqt(int *_root, int xadj[], int adjncy[], int marker[],
alpar@1:       int *_rchsze, int rchset[], int nbrhd[])
alpar@1: {     int inhd, irch, j, jstop, jstrt, link, nabor, node;
alpar@1: #     define root   (*_root)
alpar@1: #     define rchsze (*_rchsze)
alpar@1:       irch = 0;
alpar@1:       inhd = 0;
alpar@1:       node = root;
alpar@1: s100: jstrt = xadj[node];
alpar@1:       jstop = xadj[node+1] - 2;
alpar@1:       if (jstop >= jstrt)
alpar@1:       {  /* Place reach nodes into the adjacent list of node. */
alpar@1:          for (j = jstrt; j <= jstop; j++)
alpar@1:          {  irch++;
alpar@1:             adjncy[j] = rchset[irch];
alpar@1:             if (irch >= rchsze) goto s400;
alpar@1:          }
alpar@1:       }
alpar@1:       /* Link to other space provided by the nbrhd set. */
alpar@1:       link = adjncy[jstop+1];
alpar@1:       node = - link;
alpar@1:       if (link >= 0)
alpar@1:       {  inhd++;
alpar@1:          node = nbrhd[inhd];
alpar@1:          adjncy[jstop+1] = - node;
alpar@1:       }
alpar@1:       goto s100;
alpar@1:       /* All reachable nodes have been saved. End the adjacent list.
alpar@1:          Add root to the neighborhood list of each node in the reach
alpar@1:          set. */
alpar@1: s400: adjncy[j+1] = 0;
alpar@1:       for (irch = 1; irch <= rchsze; irch++)
alpar@1:       {  node = rchset[irch];
alpar@1:          if (marker[node] >= 0)
alpar@1:          {  jstrt = xadj[node];
alpar@1:             jstop = xadj[node+1] - 1;
alpar@1:             for (j = jstrt; j <= jstop; j++)
alpar@1:             {  nabor = adjncy[j];
alpar@1:                if (marker[nabor] < 0)
alpar@1:                {  adjncy[j] = root;
alpar@1:                   goto s600;
alpar@1:                }
alpar@1:             }
alpar@1:          }
alpar@1: s600:    ;
alpar@1:       }
alpar@1:       return;
alpar@1: #     undef root
alpar@1: #     undef rchsze
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  qmdupd - Quotient MD UPDate
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  #include "glpqmd.h"
alpar@1: *  void qmdupd(int xadj[], int adjncy[], int *nlist, int list[],
alpar@1: *     int deg[], int qsize[], int qlink[], int marker[], int rchset[],
alpar@1: *     int nbrhd[]);
alpar@1: *
alpar@1: *  PURPOSE
alpar@1: *
alpar@1: *  This routine performs degree update for a set of nodes in the minimum
alpar@1: *  degree algorithm.
alpar@1: *
alpar@1: *  INPUT PARAMETERS
alpar@1: *
alpar@1: *  (xadj, adjncy) -
alpar@1: *           the adjancy structure;
alpar@1: *  (nlist, list) -
alpar@1: *           the list of nodes whose degree has to be updated.
alpar@1: *
alpar@1: *  UPDATED PARAMETERS
alpar@1: *
alpar@1: *  deg    - the degree vector;
alpar@1: *  qsize  - size of indistinguishable supernodes;
alpar@1: *  qlink  - linked list for indistinguishable nodes;
alpar@1: *  marker - used to mark those nodes in reach/nbrhd sets.
alpar@1: *
alpar@1: *  WORKING PARAMETERS
alpar@1: *
alpar@1: *  rchset - the reachable set;
alpar@1: *  nbrhd  - the neighborhood set.
alpar@1: *
alpar@1: *  PROGRAM SUBROUTINES
alpar@1: *
alpar@1: *  qmdmrg.
alpar@1: ***********************************************************************/
alpar@1: 
alpar@1: void qmdupd(int xadj[], int adjncy[], int *_nlist, int list[],
alpar@1:       int deg[], int qsize[], int qlink[], int marker[], int rchset[],
alpar@1:       int nbrhd[])
alpar@1: {     int deg0, deg1, il, inhd, inode, irch, j, jstop, jstrt, mark,
alpar@1:          nabor, nhdsze, node, rchsze;
alpar@1: #     define nlist  (*_nlist)
alpar@1:       /* Find all eliminated supernodes that are adjacent to some nodes
alpar@1:          in the given list. Put them into (nhdsze, nbrhd). deg0 contains
alpar@1:          the number of nodes in the list. */
alpar@1:       if (nlist <= 0) return;
alpar@1:       deg0 = 0;
alpar@1:       nhdsze = 0;
alpar@1:       for (il = 1; il <= nlist; il++)
alpar@1:       {  node = list[il];
alpar@1:          deg0 += qsize[node];
alpar@1:          jstrt = xadj[node];
alpar@1:          jstop = xadj[node+1] - 1;
alpar@1:          for (j = jstrt; j <= jstop; j++)
alpar@1:          {  nabor = adjncy[j];
alpar@1:             if (marker[nabor] == 0 && deg[nabor] < 0)
alpar@1:             {  marker[nabor] = -1;
alpar@1:                nhdsze++;
alpar@1:                nbrhd[nhdsze] = nabor;
alpar@1:             }
alpar@1:          }
alpar@1:       }
alpar@1:       /* Merge indistinguishable nodes in the list by calling the
alpar@1:          subroutine qmdmrg. */
alpar@1:       if (nhdsze > 0)
alpar@1:          qmdmrg(xadj, adjncy, deg, qsize, qlink, marker, &deg0, &nhdsze,
alpar@1:             nbrhd, rchset, &nbrhd[nhdsze+1]);
alpar@1:       /* Find the new degrees of the nodes that have not been merged. */
alpar@1:       for (il = 1; il <= nlist; il++)
alpar@1:       {  node = list[il];
alpar@1:          mark = marker[node];
alpar@1:          if (mark == 0 || mark == 1)
alpar@1:          {  marker[node] = 2;
alpar@1:             qmdrch(&node, xadj, adjncy, deg, marker, &rchsze, rchset,
alpar@1:                &nhdsze, nbrhd);
alpar@1:             deg1 = deg0;
alpar@1:             if (rchsze > 0)
alpar@1:             {  for (irch = 1; irch <= rchsze; irch++)
alpar@1:                {  inode = rchset[irch];
alpar@1:                   deg1 += qsize[inode];
alpar@1:                   marker[inode] = 0;
alpar@1:                }
alpar@1:             }
alpar@1:             deg[node] = deg1 - 1;
alpar@1:             if (nhdsze > 0)
alpar@1:             {  for (inhd = 1; inhd <= nhdsze; inhd++)
alpar@1:                {  inode = nbrhd[inhd];
alpar@1:                   marker[inode] = 0;
alpar@1:                }
alpar@1:             }
alpar@1:          }
alpar@1:       }
alpar@1:       return;
alpar@1: #     undef nlist
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  qmdmrg - Quotient MD MeRGe
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  #include "qmdmrg.h"
alpar@1: *  void qmdmrg(int xadj[], int adjncy[], int deg[], int qsize[],
alpar@1: *     int qlink[], int marker[], int *deg0, int *nhdsze, int nbrhd[],
alpar@1: *     int rchset[], int ovrlp[]);
alpar@1: *
alpar@1: *  PURPOSE
alpar@1: *
alpar@1: *  This routine merges indistinguishable nodes in the minimum degree
alpar@1: *  ordering algorithm. It also computes the new degrees of these new
alpar@1: *  supernodes.
alpar@1: *
alpar@1: *  INPUT PARAMETERS
alpar@1: *
alpar@1: *  (xadj, adjncy) -
alpar@1: *           the adjancy structure;
alpar@1: *  deg0   - the number of nodes in the given set;
alpar@1: *  (nhdsze, nbrhd) -
alpar@1: *           the set of eliminated supernodes adjacent to some nodes in
alpar@1: *           the set.
alpar@1: *
alpar@1: *  UPDATED PARAMETERS
alpar@1: *
alpar@1: *  deg    - the degree vector;
alpar@1: *  qsize  - size of indistinguishable nodes;
alpar@1: *  qlink  - linked list for indistinguishable nodes;
alpar@1: *  marker - the given set is given by those nodes with marker value set
alpar@1: *           to 1. Those nodes with degree updated will have marker value
alpar@1: *           set to 2.
alpar@1: *
alpar@1: *  WORKING PARAMETERS
alpar@1: *
alpar@1: *  rchset - the reachable set;
alpar@1: *  ovrlp  - temp vector to store the intersection of two reachable sets.
alpar@1: ***********************************************************************/
alpar@1: 
alpar@1: void qmdmrg(int xadj[], int adjncy[], int deg[], int qsize[],
alpar@1:       int qlink[], int marker[], int *_deg0, int *_nhdsze, int nbrhd[],
alpar@1:       int rchset[], int ovrlp[])
alpar@1: {     int deg1, head, inhd, iov, irch, j, jstop, jstrt, link, lnode,
alpar@1:          mark, mrgsze, nabor, node, novrlp, rchsze, root;
alpar@1: #     define deg0   (*_deg0)
alpar@1: #     define nhdsze (*_nhdsze)
alpar@1:       /* Initialization. */
alpar@1:       if (nhdsze <= 0) return;
alpar@1:       for (inhd = 1; inhd <= nhdsze; inhd++)
alpar@1:       {  root = nbrhd[inhd];
alpar@1:          marker[root] = 0;
alpar@1:       }
alpar@1:       /* Loop through each eliminated supernode in the set
alpar@1:          (nhdsze, nbrhd). */
alpar@1:       for (inhd = 1; inhd <= nhdsze; inhd++)
alpar@1:       {  root = nbrhd[inhd];
alpar@1:          marker[root] = -1;
alpar@1:          rchsze = 0;
alpar@1:          novrlp = 0;
alpar@1:          deg1 = 0;
alpar@1: s200:    jstrt = xadj[root];
alpar@1:          jstop = xadj[root+1] - 1;
alpar@1:          /* Determine the reachable set and its intersection with the
alpar@1:             input reachable set. */
alpar@1:          for (j = jstrt; j <= jstop; j++)
alpar@1:          {  nabor = adjncy[j];
alpar@1:             root = - nabor;
alpar@1:             if (nabor < 0) goto s200;
alpar@1:             if (nabor == 0) break;
alpar@1:             mark = marker[nabor];
alpar@1:             if (mark == 0)
alpar@1:             {  rchsze++;
alpar@1:                rchset[rchsze] = nabor;
alpar@1:                deg1 += qsize[nabor];
alpar@1:                marker[nabor] = 1;
alpar@1:             }
alpar@1:             else if (mark == 1)
alpar@1:             {  novrlp++;
alpar@1:                ovrlp[novrlp] = nabor;
alpar@1:                marker[nabor] = 2;
alpar@1:             }
alpar@1:          }
alpar@1:          /* From the overlapped set, determine the nodes that can be
alpar@1:             merged together. */
alpar@1:          head = 0;
alpar@1:          mrgsze = 0;
alpar@1:          for (iov = 1; iov <= novrlp; iov++)
alpar@1:          {  node = ovrlp[iov];
alpar@1:             jstrt = xadj[node];
alpar@1:             jstop = xadj[node+1] - 1;
alpar@1:             for (j = jstrt; j <= jstop; j++)
alpar@1:             {  nabor = adjncy[j];
alpar@1:                if (marker[nabor] == 0)
alpar@1:                {  marker[node] = 1;
alpar@1:                   goto s1100;
alpar@1:                }
alpar@1:             }
alpar@1:             /* Node belongs to the new merged supernode. Update the
alpar@1:                vectors qlink and qsize. */
alpar@1:             mrgsze += qsize[node];
alpar@1:             marker[node] = -1;
alpar@1:             lnode = node;
alpar@1: s900:       link = qlink[lnode];
alpar@1:             if (link > 0)
alpar@1:             {  lnode = link;
alpar@1:                goto s900;
alpar@1:             }
alpar@1:             qlink[lnode] = head;
alpar@1:             head = node;
alpar@1: s1100:      ;
alpar@1:          }
alpar@1:          if (head > 0)
alpar@1:          {  qsize[head] = mrgsze;
alpar@1:             deg[head] = deg0 + deg1 - 1;
alpar@1:             marker[head] = 2;
alpar@1:          }
alpar@1:          /* Reset marker values. */
alpar@1:          root = nbrhd[inhd];
alpar@1:          marker[root] = 0;
alpar@1:          if (rchsze > 0)
alpar@1:          {  for (irch = 1; irch <= rchsze; irch++)
alpar@1:             {  node = rchset[irch];
alpar@1:                marker[node] = 0;
alpar@1:             }
alpar@1:          }
alpar@1:       }
alpar@1:       return;
alpar@1: #     undef deg0
alpar@1: #     undef nhdsze
alpar@1: }
alpar@1: 
alpar@1: /* eof */