minpriority.c File Reference

#include <space.h>

Go to the source code of this file.

Functions
minprior_t *	newMinPriority (PORD_INT nvtx, PORD_INT nstages)
void	freeMinPriority (minprior_t *minprior)
minprior_t *	setupMinPriority (multisector_t *ms)
elimtree_t *	orderMinPriority (minprior_t *minprior, options_t *options, timings_t *cpus)
void	eliminateStage (minprior_t *minprior, PORD_INT istage, PORD_INT scoretype, timings_t *cpus)
PORD_INT	eliminateStep (minprior_t *minprior, PORD_INT istage, PORD_INT scoretype)

Function Documentation

eliminateStage()

void eliminateStage	(	minprior_t *	minprior,
		PORD_INT	istage,
		PORD_INT	scoretype,
		timings_t *	cpus )

Definition at line 232 of file minpriority.c.

{ gelim_t     *Gelim;
  bucket_t    *bucket;
  stageinfo_t *stageinfo;
  PORD_INT         *stage, *reachset, *auxbin, *auxtmp, *auxaux;
  PORD_INT         *degree, *score;
  PORD_INT         *pflag, nreach, nvtx, r, u, i;
 
  Gelim = minprior->Gelim;
  bucket = minprior->bucket;
  stage = minprior->ms->stage;
  stageinfo = minprior->stageinfo + istage;
  reachset = minprior->reachset;
  auxaux = minprior->auxaux;
  auxbin = minprior->auxbin;
  auxtmp = minprior->auxtmp;
  pflag = &(minprior->flag);
  
  nvtx = Gelim->G->nvtx;
  degree = Gelim->degree;
  score = Gelim->score;
 
#ifdef DEBUG
  printf("\nSTARTING NEW ELIMINATION STAGE (nedges %d, maxedges %d)\n\n",
         Gelim->G->nedges, Gelim->maxedges);
  if (istage> 0) printElimGraph(Gelim);
  /* waitkey(); */
#endif
 
  /* -------------------------------------------------------------
     load reachset with all principal variables in stage <= istage
     ------------------------------------------------------------- */
  nreach = 0;
  for (u = 0; u < nvtx; u++)
    if ((score[u] == -1) && (stage[u] <= istage))
     { reachset[nreach++] = u;
       score[u] = degree[u];
       /* score[u] = degree[u]*(degree[u]-1)/2; */
     }
 
  /* ----------------------------------------------------------------
     do an initial update of the vertices in reachset and fill bucket
     ---------------------------------------------------------------- */
  pord_starttimer(cpus[TIME_UPDSCORE]);
  updateDegree(Gelim, reachset, nreach, auxbin);
  updateScore(Gelim, reachset, nreach, scoretype, auxbin);
  pord_stoptimer(cpus[TIME_UPDSCORE]);
  for (i = 0; i < nreach; i++)
   { u = reachset[i];
     insertBucket(bucket, score[u], u);
   }
 
  /* -------------------------------------
     and now start the elimination process
     ------------------------------------- */
  while (TRUE)
   { if (eliminateStep(minprior, istage, scoretype) == 0)
       break;
     nreach = minprior->nreach;
 
#ifdef BE_CAUTIOUS
     printf("checking arrays auxtmp and auxbin\n");
     for (u = 0; u < nvtx; u++)
       if ((auxtmp[u] >= *pflag) || (auxbin[u] != -1))
        { printf("ERROR: flag = %d, auxtmp[%d] = %d, auxbin[%d] = %d\n",
                 *pflag, u, auxtmp[u], u, auxbin[u]);
          quit();
        }
#endif
 
     /* ----------------------------------------------------------
        update the adjacency structure of all vertices in reachset
        ---------------------------------------------------------- */
     pord_starttimer(cpus[TIME_UPDADJNCY]);
     updateAdjncy(Gelim, reachset, nreach, auxtmp, pflag);
     pord_stoptimer(cpus[TIME_UPDADJNCY]);
 
     /* ----------------------------------------
        find indistinguishable nodes in reachset
        ---------------------------------------- */
     pord_starttimer(cpus[TIME_FINDINODES]);
     findIndNodes(Gelim, reachset, nreach, auxbin, auxaux, auxtmp, pflag);
     pord_stoptimer(cpus[TIME_FINDINODES]);
 
#ifdef BE_CAUTIOUS
     printf("checking arrays auxtmp and auxbin\n");
     for (u = 0; u < nvtx; u++)
       if ((auxtmp[u] >= *pflag) || (auxbin[u] != -1))
        { printf("ERROR: flag = %d, auxtmp[%d] = %d, auxbin[%d] = %d\n",
                 *pflag, u, auxtmp[u], u, auxbin[u]);
          quit();
        }
#endif
 
     /* ----------------------------------------------------------------
        clean reachset of nonprincipal nodes and nodes not in this stage
        ---------------------------------------------------------------- */
     r = 0;
     for (i = 0; i < nreach; i++)
      { u = reachset[i];
        if (score[u] >= 0)
          reachset[r++] = u;
      }
     nreach = r;
 
     /* ---------------------------------------------------
        update the degree/score of all vertices in reachset
        --------------------------------------------------- */
     pord_starttimer(cpus[TIME_UPDSCORE]);
     updateDegree(Gelim, reachset, nreach, auxbin);
     updateScore(Gelim, reachset, nreach, scoretype, auxbin);
     pord_stoptimer(cpus[TIME_UPDSCORE]);
 
     /* ----------------------------
        re-insert vertices in bucket
        ---------------------------- */
     for (i = 0; i < nreach; i++)
      { u = reachset[i];
        insertBucket(bucket, score[u], u);
      }
 
     stageinfo->nstep++;
   }
}

eliminateStep()

PORD_INT eliminateStep	(	minprior_t *	minprior,
		PORD_INT	istage,
		PORD_INT	scoretype )

Definition at line 361 of file minpriority.c.

{ gelim_t     *Gelim;
  bucket_t    *bucket;
  stageinfo_t *stageinfo;
  PORD_INT         *stage, *reachset, *auxtmp;
  PORD_INT         *xadj, *adjncy, *vwght, *len, *degree, *score;
  PORD_INT         *pflag, *pnreach, nelim, minscr, vwghtu, u, v, i, istart, istop;
  FLOAT       tri, rec;
 
  Gelim = minprior->Gelim;
  bucket = minprior->bucket;
  stage = minprior->ms->stage;
  stageinfo = minprior->stageinfo + istage;
  reachset = minprior->reachset;
  pnreach = &(minprior->nreach);
  auxtmp = minprior->auxtmp;
  pflag = &(minprior->flag);
 
  xadj = Gelim->G->xadj;
  adjncy = Gelim->G->adjncy;
  vwght = Gelim->G->vwght;
  len = Gelim->len;
  degree = Gelim->degree;
  score = Gelim->score;
 
#ifdef DEBUG
  printf("\nStarting new elimination step (nedges %d, maxedges %d)\n",
         Gelim->G->nedges, Gelim->maxedges);
  /* waitkey(); */
#endif
 
  /* ----------------------
     check for empty bucket
     ---------------------- */
  if ((u = minBucket(bucket)) == -1)
    return(0);
  minscr = score[u];
 
  /* ----------------------------------------
     loop while nodes of minimum score remain
     ---------------------------------------- */
  nelim = 0;
  *pnreach = 0;
  while (TRUE)
   { vwghtu = vwght[u];
 
     /* --------------------------------------------------
        increment welim and nelim and remove u from bucket
        -------------------------------------------------- */
     removeBucket(bucket, u);
     stageinfo->welim += vwghtu;
     nelim++;
 
     /* -----------------------------------------------------------------
        call buildElement to create element u and merge u's boundary with 
        the nodes in reachset; remove any vertex from bucket that belongs
        to u's boundary and to the actual stage
        ----------------------------------------------------------------- */
     buildElement(Gelim, u);
     istart = xadj[u];
     istop = istart + len[u];
     for (i = istart; i < istop; i++)
      { v = adjncy[i];                 /* v belongs to u's boundary */
        if (auxtmp[v] < *pflag)        /* v not yet in reachset */
         { auxtmp[v] = *pflag;
           if (stage[v] <= istage)     /* v belongs to actual stage */
             removeBucket(bucket, v);
           reachset[(*pnreach)++] = v;
         }
      }
 
#ifdef DEBUG
     printf("Node %d (weight %d, score %d) eliminated: (boundary weight %d)\n",
            u, vwghtu, minscr, degree[u]);
     for (i = istart; i < istop; i++)
       printf("%4d (degree %2d)", adjncy[i], degree[adjncy[i]]);
     printf("\n");
#endif
 
      /* ---------------------------------------------------------------
         increment the storage and operation counts for this elim. stage
         --------------------------------------------------------------- */
     tri = vwghtu;
     rec = degree[u];
     stageinfo->nzf += (PORD_INT)((tri * (tri+1)) / 2);
     stageinfo->nzf += (PORD_INT)(tri * rec);
     stageinfo->ops += (tri*tri*tri) / 3.0 + (tri*tri) / 2.0 - (5*tri) / 6.0;
     stageinfo->ops += (tri*tri*rec) + (rec*(rec+1)*tri);
 
     /* ---------------------------------------------------------------
        end this elim. step, if one of the following conditions is true
         (1) no multiple elimination
         (2) bucket empty
         (3) no further variable with minimum score
        ---------------------------------------------------------------- */
     if (scoretype / 10 == 0)
       break;
     if ((u = minBucket(bucket)) == -1)
       break;
     if (score[u] > minscr)
       break;
   }
 
  /* -----------------------
     clear auxtmp and return
     ----------------------- */
  (*pflag)++;
  return(nelim);
}

freeMinPriority()

void freeMinPriority

(

minprior_t *

minprior

)

Definition at line 107 of file minpriority.c.

{
  freeElimGraph(minprior->Gelim);
  freeBucket(minprior->bucket);
  free(minprior->stageinfo);
  free(minprior->reachset);
  free(minprior->auxaux);
  free(minprior->auxbin);
  free(minprior->auxtmp);
  free(minprior);
}

newMinPriority()

minprior_t * newMinPriority	(	PORD_INT	nvtx,
		PORD_INT	nstages )

Definition at line 81 of file minpriority.c.

{ minprior_t  *minprior;
  stageinfo_t *stageinfo;
 
  mymalloc(stageinfo, nstages, stageinfo_t);
  mymalloc(minprior, 1, minprior_t);
  minprior->Gelim = NULL;
  minprior->ms = NULL;
  minprior->bucket = NULL;
  minprior->stageinfo = stageinfo;
 
  mymalloc(minprior->reachset, nvtx, PORD_INT);
  mymalloc(minprior->auxaux, nvtx, PORD_INT);
  mymalloc(minprior->auxbin, nvtx, PORD_INT);
  mymalloc(minprior->auxtmp, nvtx, PORD_INT);
 
  minprior->nreach = 0;
  minprior->flag = 1;
 
  return(minprior);
}

orderMinPriority()

elimtree_t * orderMinPriority	(	minprior_t *	minprior,
		options_t *	options,
		timings_t *	cpus )

Definition at line 159 of file minpriority.c.

{ elimtree_t *T;
  PORD_INT        nvtx, nstages, istage, scoretype, ordtype;
 
  nvtx = minprior->Gelim->G->nvtx;
  nstages = minprior->ms->nstages;
 
  ordtype = options[OPTION_ORDTYPE];
  scoretype = options[OPTION_NODE_SELECTION2];
 
  /* ------------------------------
     check whether nstages is valid
     ------------------------------ */
  if ((nstages < 1) || (nstages > nvtx))
   { fprintf(stderr, "\nError in function orderMinPriority\n"
          "  no valid number of stages in multisector (#stages = %d)\n",
          nstages);
     quit();
   }
 
  if ((nstages < 2) && (ordtype != MINIMUM_PRIORITY))
   { fprintf(stderr, "\nError in function orderMinPriority\n"
          "  not enough stages in multisector (#stages = %d)\n", nstages);
     quit();
   }
 
  /* --------------------------------------------------------------
     first stage: eliminate all vertices in the remaining subgraphs
     -------------------------------------------------------------- */
  scoretype = options[OPTION_NODE_SELECTION1];
  eliminateStage(minprior, 0, scoretype, cpus);
 
  /* -------------------------------------------------------
     other stages: eliminate all vertices in the multisector
     ------------------------------------------------------- */
  switch(ordtype)
   { case MINIMUM_PRIORITY:
       break;
     case INCOMPLETE_ND:
       for (istage = 1; istage < nstages; istage++)
         eliminateStage(minprior, istage, scoretype, cpus);
       break;
     case MULTISECTION:
       eliminateStage(minprior, nstages-1, scoretype, cpus);
       break;
     default:
       fprintf(stderr, "\nError in function orderMinPriority\n"
            "  unrecognized ordering type %d\n", ordtype);
       quit();
   }
 
  /* -------------------------------------------
     print statistics for the elimination stages
     ------------------------------------------- */
  if ((ordtype != MINIMUM_PRIORITY) && (options[OPTION_MSGLVL] > 1))
    for (istage = 0; istage < nstages; istage++)
      printf("%4d. stage: #steps %6d, weight %6d, nzl %8d, ops %e\n", istage,
             minprior->stageinfo[istage].nstep,
             minprior->stageinfo[istage].welim,
             minprior->stageinfo[istage].nzf,
             minprior->stageinfo[istage].ops);
 
  /* -----------------------------------
     extract elimination tree and return
     ----------------------------------- */
  T = extractElimTree(minprior->Gelim);
  return(T);
}

setupMinPriority()

minprior_t * setupMinPriority

(

multisector_t *

ms

)

Definition at line 123 of file minpriority.c.

{ minprior_t  *minprior;
  stageinfo_t *stageinfo;
  PORD_INT         *auxbin, *auxtmp;
  PORD_INT         nvtx, nstages, istage, u;
 
  nvtx = ms->G->nvtx;
  nstages = ms->nstages;
 
  minprior = newMinPriority(nvtx, nstages);
  minprior->ms = ms;
  minprior->Gelim = setupElimGraph(ms->G);
  minprior->bucket = setupBucket(nvtx, nvtx, 0);
 
  auxbin = minprior->auxbin;
  auxtmp = minprior->auxtmp;
  for (u = 0; u < nvtx; u++)
   { auxbin[u] = -1;
     auxtmp[u] = 0;
   }
 
  for (istage = 0; istage < nstages; istage++)
   { stageinfo = minprior->stageinfo + istage;
     stageinfo->nstep = 0;
     stageinfo->welim = 0;
     stageinfo->nzf = 0;
     stageinfo->ops = 0.0;
   }
 
  return(minprior);
}