ddcreate.c File Reference

#include <space.h>

Go to the source code of this file.

Functions
domdec_t *	newDomainDecomposition (PORD_INT nvtx, PORD_INT nedges)
void	freeDomainDecomposition (domdec_t *dd)
void	printDomainDecomposition (domdec_t *dd)
void	checkDomainDecomposition (domdec_t *dd)
void	buildInitialDomains (graph_t *G, PORD_INT *vtxlist, PORD_INT *vtype, PORD_INT *rep)
void	mergeMultisecs (graph_t *G, PORD_INT *vtype, PORD_INT *rep)
domdec_t *	initialDomainDecomposition (graph_t *G, PORD_INT *map, PORD_INT *vtype, PORD_INT *rep)
domdec_t *	constructDomainDecomposition (graph_t *G, PORD_INT *map)
void	computePriorities (domdec_t *dd, PORD_INT *msvtxlist, PORD_INT *key, PORD_INT scoretype)
void	eliminateMultisecs (domdec_t *dd, PORD_INT *msvtxlist, PORD_INT *rep)
void	findIndMultisecs (domdec_t *dd, PORD_INT *msvtxlist, PORD_INT *rep)
domdec_t *	coarserDomainDecomposition (domdec_t *dd1, PORD_INT *rep)
void	shrinkDomainDecomposition (domdec_t *dd1, PORD_INT scoretype)

Function Documentation

buildInitialDomains()

void buildInitialDomains	(	graph_t *	G,
		PORD_INT *	vtxlist,
		PORD_INT *	vtype,
		PORD_INT *	rep )

Definition at line 224 of file ddcreate.c.

{ PORD_INT *xadj, *adjncy;
  PORD_INT nvtx, u, v, w, i, j, jstart, jstop;
 
  xadj = G->xadj;
  adjncy = G->adjncy;
  nvtx = G->nvtx;
 
  /* --------------------------------------------------------------------
     determine initial domains according to the order of nodes in vtxlist
     -------------------------------------------------------------------- */
  for (i = 0; i < nvtx; i++)
   { u = vtxlist[i];
     if (vtype[u] == 0)
      { vtype[u] = 1;
        jstart = xadj[u];
        jstop = xadj[u+1];
        for (j = jstart; j < jstop; j++)
         { v = adjncy[j];
           vtype[v] = 2;
         }
      }
   }
 
  /* ------------------------------------------------------------
     eliminate all multisecs that are adjacent to only one domain
     ------------------------------------------------------------ */
  for (i = 0; i < nvtx; i++)
   { u = vtxlist[i];
     if (vtype[u] == 2)
      { v = -1;
        jstart = xadj[u];
        jstop = xadj[u+1];
        for (j = jstart; j < jstop; j++)
         { w = adjncy[j];
           if (vtype[w] == 1)
            { if (v == -1)
                v = rep[w];          /* u adjacent to domain v = rep[w] */
              else if (v != rep[w])
               { v = -1;             /* u adjacent to another domain */
                 break;
               }
            }
         }
        if (v != -1)                 /* u absorbed by domain v */
         { vtype[u] = 1;
           rep[u] = v;
         }
      }
   }
}

checkDomainDecomposition()

void checkDomainDecomposition

(

domdec_t *

dd

)

Definition at line 163 of file ddcreate.c.

{ PORD_INT *xadj, *adjncy, *vwght, *vtype;
  PORD_INT err, nvtx, ndom, domwght, dom, multi, u, v, i, istart, istop;
 
  nvtx = dd->G->nvtx;
  xadj = dd->G->xadj;
  adjncy = dd->G->adjncy;
  vwght = dd->G->vwght;
  vtype = dd->vtype;
 
  err = FALSE;
  printf("checking domain decomposition (#nodes %d, #edges %d)\n",
         dd->G->nvtx, dd->G->nedges >> 1);
 
  ndom = domwght = 0;
  for (u = 0; u < nvtx; u++)
   { /* check node type */
     if ((vtype[u] != 1) && (vtype[u] != 2))
      { printf("ERROR: node %d is neither DOMAIN nor MULTISEC\n", u);
        err = TRUE;
      }
     /* count domains and sum up their weight */
     if (vtype[u] == 1)
      { ndom++;
        domwght += vwght[u];
      } 
     /* check number of neighboring domains and multisecs */
     dom = multi = 0;
     istart = xadj[u];
     istop = xadj[u+1];
     for (i = istart; i < istop; i++)
      { v = adjncy[i];
        if (vtype[v] == 1) dom++;
        if (vtype[v] == 2) multi++;
      }
     if ((vtype[u] == 1) && (dom > 0))
      { printf("ERROR: domain %d is adjacent to other domain\n", u);
        err = TRUE;
      }
     if ((vtype[u] == 2) && (dom < 2))
      { printf("ERROR: less than 2 domains adjacent to multisec node %d\n", u);
        err = TRUE;
      }
     if ((vtype[u] == 2) && (multi > 0))
      { printf("ERROR: multisec %d is adjacent to other multisec nodes\n", u);
        err = TRUE;
      }
   }
  /* check number and weight of domains */
  if ((ndom != dd->ndom) || (domwght != dd->domwght))
   { printf("ERROR: number/size (%d/%d) of domains does not match with those in"
            " domain decomp. (%d/%d)\n", ndom, domwght, dd->ndom, dd->domwght);
     err = TRUE;
   }
  if (err) quit();
}

coarserDomainDecomposition()

domdec_t * coarserDomainDecomposition	(	domdec_t *	dd1,
		PORD_INT *	rep )

Definition at line 778 of file ddcreate.c.

{ domdec_t *dd2;
  PORD_INT      *xadjdd1, *adjncydd1, *vwghtdd1, *vtypedd1, *mapdd1;
  PORD_INT      *xadjdd2, *adjncydd2, *vwghtdd2, *vtypedd2;
  PORD_INT      *tmp, *bin, nvtxdd1, nedgesdd1, nvtxdd2, nedgesdd2;
  PORD_INT      ndom, domwght, flag, u, v, w, i, istart, istop;
 
  nvtxdd1 = dd1->G->nvtx;
  nedgesdd1 = dd1->G->nedges;
  xadjdd1 = dd1->G->xadj;
  adjncydd1 = dd1->G->adjncy;
  vwghtdd1 = dd1->G->vwght;
  vtypedd1 = dd1->vtype;
  mapdd1 = dd1->map;
 
  /* ------------------------
     allocate working storage
     ------------------------ */
  mymalloc(tmp, nvtxdd1, PORD_INT);
  mymalloc(bin, nvtxdd1, PORD_INT);
  for (u = 0; u < nvtxdd1; u++)
   { tmp[u] = -1;
     bin[u] = -1;
   }
 
  /* ------------------------------------------------------------
     allocate memory using the upper bounds nvtxdd1 and nedgesdd1
     ------------------------------------------------------------ */
  dd2 = newDomainDecomposition(nvtxdd1, nedgesdd1);
  xadjdd2 = dd2->G->xadj;
  adjncydd2 = dd2->G->adjncy;
  vwghtdd2 = dd2->G->vwght;
  vtypedd2 = dd2->vtype;
 
  /* -------------------------------------------------------
     put all nodes u belonging to representative v in bin[v]
     ------------------------------------------------------- */
  for (u = 0; u < nvtxdd1; u++)
   { v = rep[u];
     if (u != v)
      { bin[u] = bin[v];
        bin[v] = u;
      }
   }
 
  /* ----------------------------------------------
     and now build the coarser domain decomposition
     ---------------------------------------------- */
  flag = 1;
  nvtxdd2 = nedgesdd2 = 0;
  ndom = domwght = 0;
  for (u = 0; u < nvtxdd1; u++)
    if (rep[u] == u)
     { xadjdd2[nvtxdd2] = nedgesdd2;
       vwghtdd2[nvtxdd2] = 0;
       vtypedd2[nvtxdd2] = vtypedd1[u];
       if (vtypedd2[nvtxdd2] == 3)
         vtypedd2[nvtxdd2] = 1;
       tmp[u] = flag;
 
       /* find all cluster that are adjacent to u in dom. dec. */
       v = u;
       do
        { mapdd1[v] = nvtxdd2;
          vwghtdd2[nvtxdd2] += vwghtdd1[v];
          if ((vtypedd1[v] == 1) || (vtypedd1[v] == 2))
           { istart = xadjdd1[v];
             istop = xadjdd1[v+1];
             for (i = istart; i < istop; i++)
              { w = adjncydd1[i];
                if (tmp[rep[w]] != flag)
                 { tmp[rep[w]] = flag;
                   adjncydd2[nedgesdd2++] = rep[w];
                 }
              }
           }
          v = bin[v];
        } while (v != -1);
 
       if (vtypedd2[nvtxdd2] == 1)
        { ndom++;
          domwght += vwghtdd2[nvtxdd2];
        }
       nvtxdd2++;
       flag++;
     }
 
  /* --------------------------------------------
     finalize the new domain decomposition object
     -------------------------------------------- */
  xadjdd2[nvtxdd2] = nedgesdd2;
  dd2->G->nvtx = nvtxdd2;
  dd2->G->nedges = nedgesdd2;
  dd2->G->type = WEIGHTED;
  dd2->G->totvwght = dd1->G->totvwght;
  for (i = 0; i < nedgesdd2; i++)
    adjncydd2[i] = mapdd1[adjncydd2[i]];
  for (u = 0; u < nvtxdd2; u++)
    dd2->color[u] = dd2->map[u] = -1;
  dd2->ndom = ndom;
  dd2->domwght = domwght;
 
  /* --------------------------
     set back node types in dd1
     -------------------------- */
  for (u = 0; u < nvtxdd1; u++)
    if ((vtypedd1[u] == 3) || (vtypedd1[u] == 4))
      vtypedd1[u] = 2;
 
  /* -------------------------------
     free working storage and return
     ------------------------------- */
  free(tmp); free(bin);
  return(dd2);
}

computePriorities()

void computePriorities	(	domdec_t *	dd,
		PORD_INT *	msvtxlist,
		PORD_INT *	key,
		PORD_INT	scoretype )

Definition at line 536 of file ddcreate.c.

{ PORD_INT *xadj, *adjncy, *vwght, *marker;
  PORD_INT nvtx, nlist, k, weight, deg, u, v, w;
  PORD_INT i, istart, istop, j, jstart, jstop;
 
  nvtx = dd->G->nvtx;
  xadj = dd->G->xadj;
  adjncy = dd->G->adjncy;
  vwght = dd->G->vwght;
  marker = dd->map;
  nlist = nvtx - dd->ndom;
 
  switch(scoretype)
   { case QMRDV:  /* maximal relative decrease of variables in quotient graph */
       for (k = 0; k < nlist; k++)
        { u = msvtxlist[k];
          weight = vwght[u];
          istart = xadj[u];
          istop = xadj[u+1];
          for (i = istart; i < istop; i++)
            weight += vwght[adjncy[i]];
          key[u] = weight / vwght[u];
        }
       break;
 
     case QMD:    /* ----------------------- minimum degree in quotient graph */
       for (k = 0; k < nlist; k++)
        { u = msvtxlist[k];
          marker[u] = -1;
        }
       for (k = 0; k < nlist; k++)
        { u = msvtxlist[k];
          marker[u] = u;
          deg = 0;
          istart = xadj[u];
          istop = xadj[u+1];
          for (i = istart; i < istop; i++)
           { v = adjncy[i];
             jstart = xadj[v];
             jstop = xadj[v+1];
             for (j = jstart; j < jstop; j++)
              { w = adjncy[j];
                if (marker[w] != u)
                 { marker[w] = u;
                   deg += vwght[w];
                 }
              }
           }
          key[u] = deg;
        }
       break;
 
     case QRAND:  /* ------------------------------------------------- random */
       for (k = 0; k < nlist; k++)
        { u = msvtxlist[k];
          key[u] = myrandom(nvtx);
        }
       break;
 
     default:
       fprintf(stderr, "\nError in internal function computePriorities\n"
            "  unrecognized node selection strategy %d\n", scoretype);
       quit();
   }
}

constructDomainDecomposition()

domdec_t * constructDomainDecomposition	(	graph_t *	G,
		PORD_INT *	map )

Definition at line 472 of file ddcreate.c.

{ domdec_t *dd;
  PORD_INT      *xadj, *adjncy, *vwght, *vtxlist, *vtype, *key, *rep;
  PORD_INT      nvtx, deg, u, i, istart, istop;
 
  nvtx = G->nvtx;
  xadj = G->xadj;
  adjncy = G->adjncy;
  vwght = G->vwght;
 
  /* ---------------------------------------------------------
     sort the vertices in G in ascending order of their degree
     --------------------------------------------------------- */
  mymalloc(vtxlist, nvtx, PORD_INT);
  mymalloc(key, nvtx, PORD_INT);
  for (u = 0; u < nvtx; u++)
   { vtxlist[u] = u;
     istart = xadj[u];
     istop = xadj[u+1];
     switch(G->type)
      { case UNWEIGHTED:
          deg = istop - istart;
          break;
        case WEIGHTED:
          deg = 0;
          for (i = istart; i < istop; i++)
            deg += vwght[adjncy[i]];
          break;
        default:
          fprintf(stderr, "\nError in function constructDomainDecomposition\n"
               "  unrecognized graph type %d\n", G->type);
          quit();
      }
     key[u] = deg;
   }
  distributionCounting(nvtx, vtxlist, key);
  free(key);
 
   /* -------------------------------------------------------------
      build initial domains and cluster multisecs that do not share
      a common domain
      ------------------------------------------------------------- */
   mymalloc(vtype, nvtx, PORD_INT);
   mymalloc(rep, nvtx, PORD_INT);
   for (u = 0; u < nvtx; u++)
    { vtype[u] = 0;
      rep[u] = u;
    }
   buildInitialDomains(G, vtxlist, vtype, rep);
   mergeMultisecs(G, vtype, rep);
   free(vtxlist);
 
   /* --------------------------------------------------
      finally, build the domain decomposition and return
      -------------------------------------------------- */
   dd = initialDomainDecomposition(G, map, vtype, rep);
   free(vtype); free(rep);
   return(dd);
}

eliminateMultisecs()

void eliminateMultisecs	(	domdec_t *	dd,
		PORD_INT *	msvtxlist,
		PORD_INT *	rep )

Definition at line 606 of file ddcreate.c.

{ PORD_INT *xadj, *adjncy, *vtype;
  PORD_INT nvtx, nlist, keepon, u, v, w, k, i, istart, istop;
 
  nvtx = dd->G->nvtx;
  xadj = dd->G->xadj;
  adjncy = dd->G->adjncy;
  vtype = dd->vtype;
  nlist = nvtx - dd->ndom;
 
  /* -------------------------------------------------------
     eliminate multisecs according to the order in msvtxlist
     ------------------------------------------------------- */
  for (k = 0; k < nlist; k++)
   { u = msvtxlist[k];
     istart = xadj[u];
     istop = xadj[u+1];
     keepon = TRUE;
     for (i = istart; i < istop; i++)
      { v = adjncy[i];
        if (rep[v] != v)        /* domain already absorbed by an eliminated */
         { keepon = FALSE;      /* multisec => multisec u cannot be deleted */
           break;
         }
      }
     if (keepon)
      { vtype[u] = 3;
        for (i = istart; i < istop; i++)
         { v = adjncy[i];
           rep[v] = u;
         }
      }
   }
 
  /* ------------------------------------------------------------
     eliminate all multisecs that are adjacent to only one domain
     ------------------------------------------------------------ */
  for (k = 0; k < nlist; k++)
   { u = msvtxlist[k];
     if (vtype[u] == 2)
      { v = -1;
        istart = xadj[u];
        istop = xadj[u+1];
        for (i = istart; i < istop; i++)
         { w = adjncy[i];
           if (v == -1)
             v = rep[w];          /* u adjacent to domain v = rep[w] */
           else if (v != rep[w])
            { v = -1;             /* u adjacent to another domain */
              break;
            }
         }
        if (v != -1)              /* u absorbed by domain v */
         { vtype[u] = 4;
           rep[u] = v;
         }
      }
   }
}

findIndMultisecs()

void findIndMultisecs	(	domdec_t *	dd,
		PORD_INT *	msvtxlist,
		PORD_INT *	rep )

Definition at line 670 of file ddcreate.c.

{ PORD_INT *xadj, *adjncy, *vtype, *tmp, *bin, *checksum, *next, *key;
  PORD_INT nvtx, nlist, flag, keepon, deg, chk, ulast, u, v, k, i, istart, istop;
 
  nvtx = dd->G->nvtx;
  xadj = dd->G->xadj;
  adjncy = dd->G->adjncy;
  vtype = dd->vtype;
  nlist = nvtx - dd->ndom;
  checksum = dd->map;
 
  /* ------------------------
     allocate working storage
     ------------------------ */
  mymalloc(tmp, nvtx, PORD_INT);
  mymalloc(bin, nvtx, PORD_INT);
  mymalloc(next, nvtx, PORD_INT);
  mymalloc(key, nvtx, PORD_INT);
  for (u = 0; u < nvtx; u++)
   { tmp[u] = -1;
     bin[u] = -1;
   }
 
  /* -------------------------------------------------------------------
     compute checksums for all unelim./unabsorbed multisecs in msvtxlist
     ------------------------------------------------------------------- */
  flag = 1;
  for (k = 0; k < nlist; k++)
   { u = msvtxlist[k];
     if (vtype[u] == 2)
      { deg = chk = 0;
        istart = xadj[u];
        istop = xadj[u+1];
        for (i = istart; i < istop; i++)
         { v = adjncy[i];
           if (tmp[rep[v]] != flag)
            { tmp[rep[v]] = flag;
              chk += rep[v];
              deg++;
            }
         }
        chk = chk % nvtx;
        checksum[u] = chk;
        key[u] = deg;
        next[u] = bin[chk];
        bin[chk] = u;
        flag++;
      }
   }
 
  /* ---------------------------------
     merge indistinguishable multisecs
     --------------------------------- */
  for (k = 0; k < nlist; k++)
   { u = msvtxlist[k];
     if (vtype[u] == 2)
      { chk = checksum[u];
        v = bin[chk];          /* examine all multisecs in bin[hash] */
        bin[chk] = -1;         /* do this only once */
        while (v != -1)
         { istart = xadj[v];
           istop = xadj[v+1];
           for (i = istart; i < istop; i++)
             tmp[rep[adjncy[i]]] = flag;
           ulast = v;          /* v is principal and u is a potiential */
           u = next[v];        /* nonprincipal variable */
           while (u != -1)
            { keepon = TRUE;
              if (key[u] != key[v])
                keepon = FALSE;
              if (keepon)
               { istart = xadj[u];
                 istop = xadj[u+1];
                 for (i = istart; i < istop; i++)
                   if (tmp[rep[adjncy[i]]] != flag)
                    { keepon = FALSE;
                      break;
                    }
               }
              if (keepon)           /* found it! mark u as nonprincipal */
               { rep[u] = v;
                 /* printf(" >> mapping %d onto %d\n", u, v); */
                 vtype[u] = 4;
                 u = next[u];
                 next[ulast] = u;  /* remove u from bin */
               }
              else                 /* failed */
               { ulast = u;
                 u = next[u];
               }
            }
           v = next[v];        /* no more variables can be absorbed by v */
           flag++;             /* clear tmp vector for next round */
         }
      }
   }
 
  /* --------------------
     free working storage
     -------------------- */
  free(tmp); free(bin);
  free(next); free(key);
}

freeDomainDecomposition()

void freeDomainDecomposition

(

domdec_t *

dd

)

Definition at line 120 of file ddcreate.c.

{
  freeGraph(dd->G);
  free(dd->vtype);
  free(dd->color);
  free(dd->map);
  free(dd);
}

initialDomainDecomposition()

domdec_t * initialDomainDecomposition	(	graph_t *	G,
		PORD_INT *	map,
		PORD_INT *	vtype,
		PORD_INT *	rep )

Definition at line 366 of file ddcreate.c.

{ domdec_t *dd;
  PORD_INT      *xadj, *adjncy, *vwght, *xadjdd, *adjncydd, *vwghtdd, *vtypedd;
  PORD_INT      *tmp, *bin, nvtx, nedges, nvtxdd, nedgesdd, ndom, domwght, flag;
  PORD_INT      i, j, jstart, jstop, u, v, w;
 
  nvtx = G->nvtx;
  nedges = G->nedges;
  xadj = G->xadj;
  adjncy = G->adjncy;
  vwght = G->vwght;
 
  /* ------------------------
     allocate working storage
     ------------------------ */
  mymalloc(tmp, nvtx, PORD_INT);
  mymalloc(bin, nvtx, PORD_INT);
  for (u = 0; u < nvtx; u++)
   { tmp[u] = -1;
     bin[u] = -1;
   }
 
  /* -------------------------------------------------------------
     allocate memory for the dd using upper bounds nvtx and nedges
     ------------------------------------------------------------- */
  dd = newDomainDecomposition(nvtx, nedges);
  xadjdd = dd->G->xadj;
  adjncydd = dd->G->adjncy;
  vwghtdd = dd->G->vwght;
  vtypedd = dd->vtype;
 
  /* -------------------------------------------------------
     put all nodes u belonging to representative v in bin[v]
     ------------------------------------------------------- */
  for (u = 0; u < nvtx; u++)
   { v = rep[u];
     if (u != v)
      { bin[u] = bin[v];
        bin[v] = u;
      }
   }
 
  /* ----------------------------------------------
     and now build the initial domain decomposition
     ---------------------------------------------- */
  flag = 1;
  nedgesdd = nvtxdd = 0;
  ndom = domwght = 0;
  for (u = 0; u < nvtx; u++)
    if (rep[u] == u)
     { xadjdd[nvtxdd] = nedgesdd;
       vtypedd[nvtxdd] = vtype[u];
       vwghtdd[nvtxdd] = 0;
       tmp[u] = flag;
 
       /* find all cluster that are adjacent to u in dom. dec. */
       v = u;
       do
        { map[v] = nvtxdd;
          vwghtdd[nvtxdd] += vwght[v];
          jstart = xadj[v];
          jstop = xadj[v+1];
          for (j = jstart; j < jstop; j++)
           { w = adjncy[j];
             if ((vtype[w] != vtype[u]) && (tmp[rep[w]] != flag))
              { tmp[rep[w]] = flag;
                adjncydd[nedgesdd++] = rep[w];
              }
           }
          v = bin[v];
        } while (v != -1);
 
       if (vtypedd[nvtxdd] == 1)
        { ndom++;
          domwght += vwghtdd[nvtxdd];
        }
       nvtxdd++;
       flag++;
     }
 
  /* --------------------------------------------
     finalize the new domain decomposition object
     -------------------------------------------- */
  xadjdd[nvtxdd] = nedgesdd;
  dd->G->nvtx = nvtxdd;
  dd->G->nedges = nedgesdd;
  dd->G->type = WEIGHTED;
  dd->G->totvwght = G->totvwght;
  for (i = 0; i < nedgesdd; i++)
    adjncydd[i] = map[adjncydd[i]];
  for (u = 0; u < nvtxdd; u++)
    dd->color[u] = dd->map[u] = -1;
  dd->ndom = ndom;
  dd->domwght = domwght;
 
  /* -------------------------------
     free working storage and return
     ------------------------------- */
  free(tmp); free(bin);
  return(dd);
}

mergeMultisecs()

void mergeMultisecs	(	graph_t *	G,
		PORD_INT *	vtype,
		PORD_INT *	rep )

Definition at line 280 of file ddcreate.c.

{ PORD_INT *xadj, *adjncy, *tmp, *queue;
  PORD_INT nvtx, qhead, qtail, flag, keepon, u, v, w, x;
  PORD_INT i, istart, istop, j, jstart, jstop;
 
  nvtx = G->nvtx;
  xadj = G->xadj;
  adjncy = G->adjncy;
 
  /* ------------------------
     allocate working storage
     ------------------------ */
  mymalloc(tmp, nvtx, PORD_INT);
  mymalloc(queue, nvtx, PORD_INT);
  for (u = 0; u < nvtx; u++)
    tmp[u] = -1;
 
  /* -------------------------------------------------------
     merge all adjacent multisecs that do not share a domain
     ------------------------------------------------------- */
  flag = 1;
  for (u = 0; u < nvtx; u++)
    if (vtype[u] == 2)
     { qhead = 0; qtail = 1;
       queue[0] = u;
       vtype[u] = -2;
 
       /* multisec u is the seed of a new cluster, mark all adj. domains */
       istart = xadj[u];
       istop = xadj[u+1];
       for (i = istart; i < istop; i++)
        { v = adjncy[i];
          if (vtype[v] == 1)
            tmp[rep[v]] = flag;
        }
 
       /* and now build the cluster */
       while (qhead != qtail)
        { v = queue[qhead++];
          istart = xadj[v];
          istop = xadj[v+1];
          for (i = istart; i < istop; i++)
           { keepon = TRUE;
             w = adjncy[i];
             if (vtype[w] == 2)
              { jstart = xadj[w];
                jstop = xadj[w+1];
                for (j = jstart; j < jstop; j++)
                 { x = adjncy[j];
                   if ((vtype[x] == 1) && (tmp[rep[x]] == flag))
                    { keepon = FALSE;
                      break;
                    }
                 }
                if (keepon)
                /* multisecs v and w have no domain in common; mark */
                /* all domains adjacent to w and put w in cluster u */
                 { for (j = jstart; j < jstop; j++)
                    { x = adjncy[j];
                      if (vtype[x] == 1) tmp[rep[x]] = flag;
                     }
                    queue[qtail++] = w;
                    rep[w] = u;
                    vtype[w] = -2;
                 }
              }
           }
        }
 
       /* clear tmp vector for next round */
       flag++;
     }
 
  /* ------------------------------------
     reset vtype and free working storage
     ------------------------------------ */
  for (u = 0; u < nvtx; u++)
    if (vtype[u] == -2)
      vtype[u] = 2;
  free(tmp); free(queue);
}

newDomainDecomposition()

domdec_t * newDomainDecomposition	(	PORD_INT	nvtx,
		PORD_INT	nedges )

Definition at line 100 of file ddcreate.c.

{ domdec_t *dd;
 
  mymalloc(dd, 1, domdec_t);
  mymalloc(dd->vtype, nvtx, PORD_INT);
  mymalloc(dd->color, nvtx, PORD_INT);
  mymalloc(dd->map, nvtx, PORD_INT);
 
  dd->G = newGraph(nvtx, nedges);
  dd->ndom = dd->domwght = 0;
  dd->cwght[GRAY] = dd->cwght[BLACK] = dd->cwght[WHITE] = 0;
  dd->prev = dd->next = NULL;
 
  return(dd);
}

printDomainDecomposition()

void printDomainDecomposition

(

domdec_t *

dd

)

Definition at line 133 of file ddcreate.c.

{ graph_t *G;
  PORD_INT   count, u, v, i, istart, istop;
 
  G = dd->G;
  printf("\n#nodes %d (#domains %d, weight %d), #edges %d, totvwght %d\n",
         G->nvtx, dd->ndom, dd->domwght, G->nedges >> 1, G->totvwght);
  printf("partition weights: S %d, B %d, W %d\n", dd->cwght[GRAY],
         dd->cwght[BLACK], dd->cwght[WHITE]);
  for (u = 0; u < G->nvtx; u++)
   { count = 0;
     printf("--- adjacency list of node %d (vtype %d, color %d, map %d\n",
            u, dd->vtype[u], dd->color[u], dd->map[u]);
     istart = G->xadj[u];
     istop = G->xadj[u+1];
     for (i = istart; i < istop; i++)
      { v = G->adjncy[i];
        printf("%5d (vtype %2d, color %2d)", v, dd->vtype[v], dd->color[v]);
        if ((++count % 3) == 0)
          printf("\n");
      }
     if ((count % 3) != 0)
       printf("\n");
   }
}

shrinkDomainDecomposition()

void shrinkDomainDecomposition	(	domdec_t *	dd1,
		PORD_INT	scoretype )

Definition at line 898 of file ddcreate.c.

{ domdec_t *dd2;
  PORD_INT      *msvtxlist, *rep, *key;
  PORD_INT      nvtxdd1, nlist, u;
 
  nvtxdd1 = dd1->G->nvtx;
  mymalloc(msvtxlist, nvtxdd1, PORD_INT);
  mymalloc(rep, nvtxdd1, PORD_INT);
  mymalloc(key, nvtxdd1, PORD_INT);
 
  /* ---------------
     initializations
     --------------- */
  nlist = 0;
  for (u = 0; u < nvtxdd1; u++)
   { if (dd1->vtype[u] == 2)
       msvtxlist[nlist++] = u;
     rep[u] = u;
   }
 
  /* -------------------------------------
     compute priorities and sort multisecs
     ------------------------------------- */
  computePriorities(dd1, msvtxlist, key, scoretype);
  distributionCounting(nlist, msvtxlist, key);
 
  /* ----------------------------------------------------------
     eliminate multisecs and build coarser domain decomposition
     ---------------------------------------------------------- */
  eliminateMultisecs(dd1, msvtxlist, rep);
  findIndMultisecs(dd1, msvtxlist, rep);
  dd2 = coarserDomainDecomposition(dd1, rep);
 
  /* -----------------------------------
     append coarser domain decomposition
     ----------------------------------- */
  dd1->next = dd2;
  dd2->prev = dd1;
 
  free(msvtxlist);
  free(rep);
  free(key);
}