nestdiss.c File Reference

#include <space.h>

Go to the source code of this file.

Functions
nestdiss_t *	newNDnode (graph_t *G, PORD_INT *map, PORD_INT nvint)
void	freeNDnode (nestdiss_t *nd)
nestdiss_t *	setupNDroot (graph_t *G, PORD_INT *map)
void	splitNDnode (nestdiss_t *nd, options_t *options, timings_t *cpus)
void	buildNDtree (nestdiss_t *ndroot, options_t *options, timings_t *cpus)
void	freeNDtree (nestdiss_t *ndroot)

Function Documentation

buildNDtree()

void buildNDtree	(	nestdiss_t *	ndroot,
		options_t *	options,
		timings_t *	cpus )

Definition at line 213 of file nestdiss.c.

{ nestdiss_t *nd;
  nestdiss_t *queue[2*MAX_SEPS+1];
  PORD_INT        maxseps, seps, domainsize, qhead, qtail;
 
  maxseps = MAX_SEPS;
  domainsize = options[OPTION_DOMAIN_SIZE];
  if (domainsize == 1) maxseps = DEFAULT_SEPS;   /* secret switch */
 
  /* --------------------------------------------------
     build the nested dissection tree under root ndroot
     -------------------------------------------------- */
  queue[0] = ndroot;
  qhead = 0; qtail = 1; seps = 0;
  while ((qhead != qtail) && (seps < maxseps))
   { seps++;
     nd = queue[qhead++];
 
     splitNDnode(nd, options, cpus);
     if ((nd->childB == NULL) || (nd->childW == NULL))
      { fprintf(stderr, "\nError in function buildNDtree\n"
             "  recursive nested dissection process failed\n");
        quit();
      }
 
     if (options[OPTION_MSGLVL] > 1)
       printf("%4d. S %6d, B %6d, W %6d [bal %4.2f, rel %6.4f, cost %7.2f]\n",
             seps, nd->cwght[GRAY], nd->cwght[BLACK], nd->cwght[WHITE],
             (FLOAT)min(nd->cwght[BLACK], nd->cwght[WHITE])
                     / max(nd->cwght[BLACK], nd->cwght[WHITE]),
             (FLOAT)nd->cwght[GRAY]
                     / (nd->cwght[GRAY] + nd->cwght[BLACK] + nd->cwght[WHITE]),
             F(nd->cwght[GRAY], nd->cwght[BLACK], nd->cwght[WHITE]));
 
     if ((nd->childB->nvint > MIN_NODES)
        && ((nd->cwght[BLACK] > domainsize) || (qtail < DEFAULT_SEPS)))
       queue[qtail++] = nd->childB;
     if ((nd->childW->nvint > MIN_NODES)
        && ((nd->cwght[WHITE] > domainsize) || (qtail < DEFAULT_SEPS)))
       queue[qtail++] = nd->childW;
   }
}

freeNDnode()

void freeNDnode

(

nestdiss_t *

nd

)

Definition at line 96 of file nestdiss.c.

{
  free(nd->intvertex);
  free(nd->intcolor);
  free(nd);
}

freeNDtree()

void freeNDtree

(

nestdiss_t *

ndroot

)

Definition at line 260 of file nestdiss.c.

{ nestdiss_t *nd, *parent;
 
  /* ------------------------------------------------------
     to remove the nested dissection tree under root ndroot
     visit the nodes in post-order
     ------------------------------------------------------ */
  for (nd = ndroot; nd->childB != NULL; nd = nd->childB);
  while (nd != ndroot)
   { parent = nd->parent;
     if ((parent == NULL) || (parent->childB == NULL)
        || (parent->childW == NULL))
       { fprintf(stderr, "\nError in function removeNDtree\n"
              "  nested dissection tree corrupted\n");
         quit();
       }
     if (parent->childB == nd)  /* left subtree of parent visited */
      { freeNDnode(nd);         /* free root of left subtree and goto right */
        for (nd = parent->childW; nd->childB != NULL; nd = nd->childB);
      }
     else                       /* right subtree of parent visited */
      { freeNDnode(nd);         /* free root of right subtree and goto parent */
        nd = parent;
      }
   }
}

newNDnode()

nestdiss_t * newNDnode	(	graph_t *	G,
		PORD_INT *	map,
		PORD_INT	nvint )

Definition at line 75 of file nestdiss.c.

{ nestdiss_t *nd;
 
  mymalloc(nd, 1, nestdiss_t);
  mymalloc(nd->intvertex, nvint, PORD_INT);
  mymalloc(nd->intcolor, nvint, PORD_INT);
 
  nd->G = G;
  nd->map = map;
  nd->depth = 0;
  nd->nvint = nvint;
  nd->cwght[GRAY] = nd->cwght[BLACK] = nd->cwght[WHITE] = 0;
  nd->parent = nd->childB = nd->childW = NULL;
 
  return(nd);
}

setupNDroot()

nestdiss_t * setupNDroot	(	graph_t *	G,
		PORD_INT *	map )

Definition at line 107 of file nestdiss.c.

{ nestdiss_t *ndroot;
  PORD_INT        *intvertex, nvtx, i;
 
  nvtx = G->nvtx;
  ndroot = newNDnode(G, map, nvtx);
  intvertex = ndroot->intvertex;
 
  for (i = 0; i < nvtx; i++)
    intvertex[i] = i;
 
  return(ndroot);
}

splitNDnode()

void splitNDnode	(	nestdiss_t *	nd,
		options_t *	options,
		timings_t *	cpus )

Definition at line 125 of file nestdiss.c.

{ nestdiss_t *b_nd, *w_nd;
  graph_t    *Gsub;
  gbisect_t  *Gbisect;
  PORD_INT        *map, *intvertex, *intcolor, *b_intvertex, *w_intvertex;
  PORD_INT        nvint, b_nvint, w_nvint, u, i;
 
  map = nd->map;
  nvint = nd->nvint;
  intvertex = nd->intvertex;
  intcolor = nd->intcolor;
 
  /* -------------------------------------------------------------
     extract the subgraph for which a bisection has to be computed
     ------------------------------------------------------------- */
  if (nd->G->nvtx == nd->nvint)
   { Gsub = nd->G;                    /* a hack to save time and space */
     for (u = 0; u < nd->nvint; u++)  /* but do not forget the map vector */
       map[u] = u;
   }
  else
    Gsub = setupSubgraph(nd->G, intvertex, nvint, map);
  Gbisect = newGbisect(Gsub);
 
  /* ---------------------------------
     compute the bisection for Gbisect
     --------------------------------- */
  pord_starttimer(cpus[TIME_MULTILEVEL]);
  constructSeparator(Gbisect, options, cpus);
  pord_stoptimer(cpus[TIME_MULTILEVEL]);
 
  pord_starttimer(cpus[TIME_SMOOTH]);
  if (Gbisect->cwght[GRAY] > 0)
    smoothSeparator(Gbisect, options);
  pord_stoptimer(cpus[TIME_SMOOTH]);
 
  /* ----------------------------------------
     copy the bisection back to the nd object
     ---------------------------------------- */
  b_nvint = w_nvint = 0;
  nd->cwght[GRAY] = Gbisect->cwght[GRAY];
  nd->cwght[BLACK] = Gbisect->cwght[BLACK];
  nd->cwght[WHITE] = Gbisect->cwght[WHITE];
  for (i = 0; i < nvint; i++)
   { u = intvertex[i];
     intcolor[i] = Gbisect->color[map[u]];
     switch(intcolor[i])
      { case GRAY: break;
        case BLACK: b_nvint++; break;
        case WHITE: w_nvint++; break;
        default:
          fprintf(stderr, "\nError in function splitNDnode\n"
               "  node %d has unrecognized color %d\n", u, intcolor[i]);
          quit();
      }
   }
 
  /* ------------------------------------------------------
     and now split the nd object according to the bisection
     ------------------------------------------------------ */
  b_nd = newNDnode(nd->G, map, b_nvint);
  b_intvertex = b_nd->intvertex;
  w_nd = newNDnode(nd->G, map, w_nvint);
  w_intvertex = w_nd->intvertex;
 
  b_nvint = w_nvint = 0;
  for (i = 0; i < nvint; i++)
   { u = intvertex[i];
     if (intcolor[i] == BLACK) b_intvertex[b_nvint++] = u;
     if (intcolor[i] == WHITE) w_intvertex[w_nvint++] = u;
   }
  nd->childB = b_nd; b_nd->parent = nd;
  nd->childW = w_nd; w_nd->parent = nd;
  b_nd->depth = nd->depth + 1;
  w_nd->depth = nd->depth + 1;
 
  /* -----------------
     free the subgraph
     ----------------- */
  if (Gsub != nd->G)
    freeGraph(Gsub);
  freeGbisect(Gbisect);
}