glpqmd.c

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

*
*  adjncy - becomes the adjncy of the quotient graph.
***********************************************************************/

void qmdqt(int *_root, int xadj[], int adjncy[], int marker[],
      int *_rchsze, int rchset[], int nbrhd[])
{     int inhd, irch, j, jstop, jstrt, link, nabor, node;
#     define root   (*_root)
#     define rchsze (*_rchsze)
      irch = 0;
      inhd = 0;
      node = root;
s100: jstrt = xadj[node];
      jstop = xadj[node+1] - 2;
      if (jstop >= jstrt)
      {  /* Place reach nodes into the adjacent list of node. */
         for (j = jstrt; j <= jstop; j++)
         {  irch++;
            adjncy[j] = rchset[irch];
            if (irch >= rchsze) goto s400;
         }
      }
      /* Link to other space provided by the nbrhd set. */
      link = adjncy[jstop+1];
      node = - link;
      if (link >= 0)
      {  inhd++;
         node = nbrhd[inhd];
         adjncy[jstop+1] = - node;
      }
      goto s100;
      /* All reachable nodes have been saved. End the adjacent list.
         Add root to the neighborhood list of each node in the reach
         set. */
s400: adjncy[j+1] = 0;
      for (irch = 1; irch <= rchsze; irch++)
      {  node = rchset[irch];
         if (marker[node] >= 0)
         {  jstrt = xadj[node];
            jstop = xadj[node+1] - 1;
            for (j = jstrt; j <= jstop; j++)
            {  nabor = adjncy[j];
               if (marker[nabor] < 0)
               {  adjncy[j] = root;
                  goto s600;
               }
            }
         }
s600:    ;
      }
      return;
#     undef root
#     undef rchsze
}

/***********************************************************************
*  NAME
*
*  qmdupd - Quotient MD UPDate
*
*  SYNOPSIS
*
*  #include "glpqmd.h"
*  void qmdupd(int xadj[], int adjncy[], int *nlist, int list[],
*     int deg[], int qsize[], int qlink[], int marker[], int rchset[],
*     int nbrhd[]);
*
*  PURPOSE
*
*  This routine performs degree update for a set of nodes in the minimum
*  degree algorithm.
*
*  INPUT PARAMETERS
*
*  (xadj, adjncy) -
*           the adjancy structure;
*  (nlist, list) -
*           the list of nodes whose degree has to be updated.
*
*  UPDATED PARAMETERS
*
*  deg    - the degree vector;
*  qsize  - size of indistinguishable supernodes;
*  qlink  - linked list for indistinguishable nodes;
*  marker - used to mark those nodes in reach/nbrhd sets.
*
*  WORKING PARAMETERS
*
*  rchset - the reachable set;
*  nbrhd  - the neighborhood set.
*
*  PROGRAM SUBROUTINES
*
*  qmdmrg.
***********************************************************************/

void qmdupd(int xadj[], int adjncy[], int *_nlist, int list[],
      int deg[], int qsize[], int qlink[], int marker[], int rchset[],
      int nbrhd[])
{     int deg0, deg1, il, inhd, inode, irch, j, jstop, jstrt, mark,
         nabor, nhdsze, node, rchsze;
#     define nlist  (*_nlist)
      /* Find all eliminated supernodes that are adjacent to some nodes
         in the given list. Put them into (nhdsze, nbrhd). deg0 contains
         the number of nodes in the list. */
      if (nlist <= 0) return;
      deg0 = 0;
      nhdsze = 0;
      for (il = 1; il <= nlist; il++)
      {  node = list[il];
         deg0 += qsize[node];
         jstrt = xadj[node];
         jstop = xadj[node+1] - 1;
         for (j = jstrt; j <= jstop; j++)
         {  nabor = adjncy[j];
            if (marker[nabor] == 0 && deg[nabor] < 0)
            {  marker[nabor] = -1;
               nhdsze++;
               nbrhd[nhdsze] = nabor;
            }
         }
      }
      /* Merge indistinguishable nodes in the list by calling the
         subroutine qmdmrg. */
      if (nhdsze > 0)
         qmdmrg(xadj, adjncy, deg, qsize, qlink, marker, &deg0, &nhdsze,
            nbrhd, rchset, &nbrhd[nhdsze+1]);
      /* Find the new degrees of the nodes that have not been merged. */
      for (il = 1; il <= nlist; il++)
      {  node = list[il];
         mark = marker[node];
         if (mark == 0 || mark == 1)
         {  marker[node] = 2;
            qmdrch(&node, xadj, adjncy, deg, marker, &rchsze, rchset,
               &nhdsze, nbrhd);
            deg1 = deg0;
            if (rchsze > 0)
            {  for (irch = 1; irch <= rchsze; irch++)
               {  inode = rchset[irch];
                  deg1 += qsize[inode];
                  marker[inode] = 0;
               }
            }
            deg[node] = deg1 - 1;
            if (nhdsze > 0)
            {  for (inhd = 1; inhd <= nhdsze; inhd++)
               {  inode = nbrhd[inhd];
                  marker[inode] = 0;
               }
            }
         }
      }
      return;
#     undef nlist
}

/***********************************************************************
*  NAME
*
*  qmdmrg - Quotient MD MeRGe
*
*  SYNOPSIS
*
*  #include "qmdmrg.h"
*  void qmdmrg(int xadj[], int adjncy[], int deg[], int qsize[],
*     int qlink[], int marker[], int *deg0, int *nhdsze, int nbrhd[],
*     int rchset[], int ovrlp[]);
*
*  PURPOSE
*
*  This routine merges indistinguishable nodes in the minimum degree
*  ordering algorithm. It also computes the new degrees of these new
*  supernodes.
*
*  INPUT PARAMETERS
*
*  (xadj, adjncy) -
*           the adjancy structure;
*  deg0   - the number of nodes in the given set;
*  (nhdsze, nbrhd) -
*           the set of eliminated supernodes adjacent to some nodes in
*           the set.
*
*  UPDATED PARAMETERS
*
*  deg    - the degree vector;
*  qsize  - size of indistinguishable nodes;
*  qlink  - linked list for indistinguishable nodes;
*  marker - the given set is given by those nodes with marker value set
*           to 1. Those nodes with degree updated will have marker value
*           set to 2.
*
*  WORKING PARAMETERS
*
*  rchset - the reachable set;
*  ovrlp  - temp vector to store the intersection of two reachable sets.
***********************************************************************/

void qmdmrg(int xadj[], int adjncy[], int deg[], int qsize[],
      int qlink[], int marker[], int *_deg0, int *_nhdsze, int nbrhd[],
      int rchset[], int ovrlp[])
{     int deg1, head, inhd, iov, irch, j, jstop, jstrt, link, lnode,
         mark, mrgsze, nabor, node, novrlp, rchsze, root;
#     define deg0   (*_deg0)
#     define nhdsze (*_nhdsze)
      /* Initialization. */
      if (nhdsze <= 0) return;
      for (inhd = 1; inhd <= nhdsze; inhd++)
      {  root = nbrhd[inhd];
         marker[root] = 0;
      }
      /* Loop through each eliminated supernode in the set
         (nhdsze, nbrhd). */
      for (inhd = 1; inhd <= nhdsze; inhd++)
      {  root = nbrhd[inhd];
         marker[root] = -1;
         rchsze = 0;
         novrlp = 0;
         deg1 = 0;
s200:    jstrt = xadj[root];
         jstop = xadj[root+1] - 1;
         /* Determine the reachable set and its intersection with the
            input reachable set. */
         for (j = jstrt; j <= jstop; j++)
         {  nabor = adjncy[j];
            root = - nabor;
            if (nabor < 0) goto s200;
            if (nabor == 0) break;
            mark = marker[nabor];
            if (mark == 0)
            {  rchsze++;
               rchset[rchsze] = nabor;
               deg1 += qsize[nabor];
               marker[nabor] = 1;
            }
            else if (mark == 1)
            {  novrlp++;
               ovrlp[novrlp] = nabor;
               marker[nabor] = 2;
            }
         }
         /* From the overlapped set, determine the nodes that can be
            merged together. */
         head = 0;
         mrgsze = 0;
         for (iov = 1; iov <= novrlp; iov++)
         {  node = ovrlp[iov];
            jstrt = xadj[node];
            jstop = xadj[node+1] - 1;
            for (j = jstrt; j <= jstop; j++)
            {  nabor = adjncy[j];
               if (marker[nabor] == 0)
               {  marker[node] = 1;
                  goto s1100;
               }
            }
            /* Node belongs to the new merged supernode. Update the
               vectors qlink and qsize. */
            mrgsze += qsize[node];
            marker[node] = -1;
            lnode = node;
s900:       link = qlink[lnode];
            if (link > 0)
            {  lnode = link;
               goto s900;
            }
            qlink[lnode] = head;
            head = node;
s1100:      ;
         }
         if (head > 0)
         {  qsize[head] = mrgsze;
            deg[head] = deg0 + deg1 - 1;
            marker[head] = 2;
         }
         /* Reset marker values. */
         root = nbrhd[inhd];
         marker[root] = 0;
         if (rchsze > 0)
         {  for (irch = 1; irch <= rchsze; irch++)
            {  node = rchset[irch];
               marker[node] = 0;
            }
         }
      }
      return;
#     undef deg0
#     undef nhdsze
}

/* eof */