tree.c File Reference

#include <space.h>

Go to the source code of this file.

Functions
elimtree_t *	newElimTree (PORD_INT nvtx, PORD_INT nfronts)
void	freeElimTree (elimtree_t *T)
void	printElimTree (elimtree_t *T)
PORD_INT	firstPostorder (elimtree_t *T)
PORD_INT	firstPostorder2 (elimtree_t *T, PORD_INT root)
PORD_INT	nextPostorder (elimtree_t *T, PORD_INT J)
PORD_INT	firstPreorder (elimtree_t *T)
PORD_INT	nextPreorder (elimtree_t *T, PORD_INT J)
elimtree_t *	setupElimTree (graph_t *G, PORD_INT *perm, PORD_INT *invp)
void	initFchSilbRoot (elimtree_t *T)
void	permFromElimTree (elimtree_t *T, PORD_INT *perm)
elimtree_t *	permuteElimTree (elimtree_t *T, PORD_INT *perm)
elimtree_t *	expandElimTree (elimtree_t *T, PORD_INT *vtxmap, PORD_INT nvtxorg)
elimtree_t *	fundamentalFronts (elimtree_t *T)
elimtree_t *	mergeFronts (elimtree_t *T, PORD_INT maxzeros)
elimtree_t *	compressElimTree (elimtree_t *T, PORD_INT *frontmap, PORD_INT cnfronts)
PORD_INT	justifyFronts (elimtree_t *T)
PORD_INT	nWorkspace (elimtree_t *T)
PORD_INT	nFactorIndices (elimtree_t *T)
PORD_INT	nFactorEntries (elimtree_t *T)
FLOAT	nFactorOps (elimtree_t *T)
void	subtreeFactorOps (elimtree_t *T, FLOAT *ops)
FLOAT	nTriangularOps (elimtree_t *T)

Function Documentation

compressElimTree()

elimtree_t * compressElimTree	(	elimtree_t *	T,
		PORD_INT *	frontmap,
		PORD_INT	cnfronts )

Definition at line 689 of file tree.c.

{ elimtree_t *T2;
  PORD_INT        *ncolfactor, *ncolupdate, *parent, *vtx2front;
  PORD_INT        nvtx, nfronts, u, K, pK, newfront, pnewfront;
 
  nvtx = T->nvtx;
  nfronts = T->nfronts;
  ncolfactor = T->ncolfactor;
  ncolupdate = T->ncolupdate;
  parent = T->parent;
  vtx2front = T->vtx2front;
 
  /* --------------------------------------------
     allocate memory for the new elimtree T2
     and init. ncolfactor, ncolupdate, and parent
     -------------------------------------------- */
  T2 = newElimTree(nvtx, cnfronts);
  for (K = 0; K < cnfronts; K++)
   { T2->ncolfactor[K] = T2->ncolupdate[K] = 0;
     T2->parent[K] = -1;
   }
 
  /* --------------------------------------------------------------
     set the new vectors T2->ncolfactor, T2->ncolupdate, T2->parent
     -------------------------------------------------------------- */
  for (K = 0; K < nfronts; K++)
   { newfront = frontmap[K];
     T2->ncolfactor[newfront] += ncolfactor[K];
     if (((pK = parent[K]) != -1)
        && ((pnewfront = frontmap[pK]) != newfront))
      { T2->parent[newfront] = pnewfront;
        T2->ncolupdate[newfront] = ncolupdate[K];
      }
   }
 
  /* ---------------------------------------------------
     set the new vectors T2->firstchild and T2->silbings
     --------------------------------------------------- */
  initFchSilbRoot(T2);
 
  /* ------------------------------------
     set the the new vector T2->vtx2front
     ------------------------------------ */
  for (u = 0; u < nvtx; u++)
    T2->vtx2front[u] = frontmap[vtx2front[u]];
  return(T2);
}

expandElimTree()

elimtree_t * expandElimTree	(	elimtree_t *	T,
		PORD_INT *	vtxmap,
		PORD_INT	nvtxorg )

Definition at line 517 of file tree.c.

{ elimtree_t *T2;
  PORD_INT        *vtx2front, *vtx2front2;
  PORD_INT        nfronts, J, u;
 
  nfronts = T->nfronts;
 
  /* --------------------------------------------------------------
     allocate space for the new elimtree object and copy front data
     the expanded tree has the same number of fronts/tree structure
     -------------------------------------------------------------- */
  T2 = newElimTree(nvtxorg, nfronts);
  T2->root = T->root;
  for (J = 0; J < nfronts; J++)
   { T2->ncolfactor[J] = T->ncolfactor[J];
     T2->ncolupdate[J] = T->ncolupdate[J];
     T2->parent[J] = T->parent[J];
     T2->firstchild[J] = T->firstchild[J];
     T2->silbings[J] = T->silbings[J];
   }
 
  /* ---------------------------------------------------------------------
     set up the new vtx2front vector; the trees only differ in this vector
     --------------------------------------------------------------------- */
  vtx2front = T->vtx2front;
  vtx2front2 = T2->vtx2front;
  for (u = 0; u < nvtxorg; u++)
    vtx2front2[u] = vtx2front[vtxmap[u]];
 
  return(T2);
}

firstPostorder()

PORD_INT firstPostorder

(

elimtree_t *

T

)

Definition at line 213 of file tree.c.

{ PORD_INT *firstchild, J;
 
  firstchild = T->firstchild;
 
  if ((J = T->root) != -1)
    while (firstchild[J] != -1)
      J = firstchild[J];
  return(J);
}

firstPostorder2()

PORD_INT firstPostorder2	(	elimtree_t *	T,
		PORD_INT	root )

Definition at line 228 of file tree.c.

{ PORD_INT *firstchild, J;
 
  firstchild = T->firstchild;
 
  if ((J = root) != -1)
    while (firstchild[J] != -1)
      J = firstchild[J];
  return(J);
}

firstPreorder()

PORD_INT firstPreorder

(

elimtree_t *

T

)

Definition at line 263 of file tree.c.

{
  return(T->root);
}

freeElimTree()

void freeElimTree

(

elimtree_t *

T

)

Definition at line 132 of file tree.c.

{
  free(T->ncolfactor);
  free(T->ncolupdate);
  free(T->parent);
  free(T->firstchild);
  free(T->silbings);
  free(T->vtx2front);
  free(T);
}

fundamentalFronts()

elimtree_t * fundamentalFronts

(

elimtree_t *

T

)

Definition at line 553 of file tree.c.

{ elimtree_t *T2;
  PORD_INT        *ncolfactor, *ncolupdate, *parent, *firstchild, *silbings;
  PORD_INT        *frontmap, nfronts, cnfronts, J, child;
 
  nfronts = T->nfronts;
  ncolfactor = T->ncolfactor;
  ncolupdate = T->ncolupdate;
  parent = T->parent;
  firstchild = T->firstchild;
  silbings = T->silbings;
 
  /* -------------------------
     set up the working arrays
     ------------------------- */
  mymalloc(frontmap, nfronts, PORD_INT);
 
  /* -----------------------------
     search the fundamental fronts
     ----------------------------- */
  cnfronts = 0;
  J = T->root;
  while (J != -1)
   { while (firstchild[J] != -1)
       J = firstchild[J];
     frontmap[J] = cnfronts++;
     while ((silbings[J] == -1) && (parent[J] != -1))
      { J = parent[J];
        child = firstchild[J];
        if ((silbings[child] != -1)
            || (ncolupdate[child] != ncolfactor[J] + ncolupdate[J]))
          frontmap[J] = cnfronts++;
        else
          frontmap[J] = frontmap[child];
      }
     J = silbings[J];
   }
 
  /* ------------------------------
     construct new elimination tree
     ------------------------------ */
  T2 = compressElimTree(T, frontmap, cnfronts);
 
  /* ----------------------
     free memory and return
     ---------------------- */
  free(frontmap);
  return(T2);
}

initFchSilbRoot()

void initFchSilbRoot

(

elimtree_t *

T

)

Definition at line 414 of file tree.c.

{ PORD_INT *parent, *firstchild, *silbings, nfronts, J, pJ;
 
  nfronts = T->nfronts;
  parent = T->parent;
  firstchild = T->firstchild;
  silbings = T->silbings;
 
  for (J = 0; J < nfronts; J++)
    silbings[J] = firstchild[J] = -1;
 
  for (J = nfronts-1; J >= 0; J--)
    if ((pJ = parent[J]) != -1)
     { silbings[J] = firstchild[pJ];
       firstchild[pJ] = J;
     }
    else
     { silbings[J] = T->root;
       T->root = J;
     }
}

justifyFronts()

PORD_INT justifyFronts

(

elimtree_t *

T

)

Definition at line 741 of file tree.c.

{ PORD_INT *ncolfactor, *ncolupdate, *firstchild, *silbings, *minWspace, *list;
  PORD_INT nfronts, K, ncolfrontK, frontsizeK, wspace, child, nxtchild;
  PORD_INT count, m, s, i;
 
  nfronts = T->nfronts;
  ncolfactor = T->ncolfactor;
  ncolupdate = T->ncolupdate;
  firstchild = T->firstchild;
  silbings = T->silbings;
 
  /* -------------------------
     set up the working arrays
     ------------------------- */
  mymalloc(minWspace, nfronts, PORD_INT);
  mymalloc(list, nfronts, PORD_INT);
 
  /* ---------------------------------------------------------
     postorder traversal of the elimination tree to obtain the
     optimal justification of the children of each front
     ---------------------------------------------------------- */
  wspace = 0;
  for (K = firstPostorder(T); K != -1; K = nextPostorder(T, K))
   { ncolfrontK = ncolfactor[K] + ncolupdate[K];
     frontsizeK = (ncolfrontK * (ncolfrontK + 1)) >> 1;
 
     if ((child = firstchild[K]) == -1)
       minWspace[K] = frontsizeK;
     else
      { count = 0;
 
        /* sort children according to their minWspace value */
        while (child != -1)
         { list[count++] = child;
           child = silbings[child];
         }
        insertUpIntsWithStaticIntKeys(count, list, minWspace);
        firstchild[K] = -1;
        for (i = 0; i < count; i++)
         { child = list[i];
           silbings[child] = firstchild[K];
           firstchild[K] = child;
         }
 
        /* compute minWspace[K] */
        child = firstchild[K];
        nxtchild = silbings[child];
        m = s = minWspace[child];
        while (nxtchild != -1)
         { s = s - minWspace[child]
               + ((ncolupdate[child] * (ncolupdate[child] + 1)) >> 1)
               + minWspace[nxtchild];
           m = max(m, s);
           child = nxtchild;
           nxtchild = silbings[nxtchild];
         }
        s = s - minWspace[child]
            + ((ncolupdate[child] * (ncolupdate[child] + 1)) >> 1)
            + frontsizeK;
        minWspace[K] = max(m, s);
      }
 
     wspace = max(wspace, minWspace[K]);
   }
 
  /* ----------------------
     free memory and return
     ---------------------- */
  free(minWspace); free(list);
  return(wspace);
}

mergeFronts()

elimtree_t * mergeFronts	(	elimtree_t *	T,
		PORD_INT	maxzeros )

Definition at line 607 of file tree.c.

{ elimtree_t *T2;
  PORD_INT        *ncolfactor, *ncolupdate, *firstchild, *silbings;
  PORD_INT        *frontmap, *newncolfactor, *nzeros, *rep;
  PORD_INT        nfronts, cnfronts, K, ncolfrontK, J, Jall, cost;
 
  nfronts = T->nfronts;
  ncolfactor = T->ncolfactor;
  ncolupdate = T->ncolupdate;
  firstchild = T->firstchild;
  silbings = T->silbings;
 
  /* -------------------------
     set up the working arrays
     ------------------------- */
  mymalloc(frontmap, nfronts, PORD_INT);
  mymalloc(newncolfactor, nfronts, PORD_INT);
  mymalloc(nzeros, nfronts, PORD_INT);
  mymalloc(rep, nfronts, PORD_INT);
  for (K = 0; K < nfronts; K++)
   { newncolfactor[K] = ncolfactor[K];
     nzeros[K] = 0;
     rep[K] = K;
   }
 
  /* -----------------------------------------------------
     perform a postorder traversal of the elimination tree
     ----------------------------------------------------- */
  for (K = firstPostorder(T); K != -1; K = nextPostorder(T, K))
    if (firstchild[K] != -1)
     { ncolfrontK = newncolfactor[K] + ncolupdate[K];
       Jall = 0;
       cost = 0;
       for (J = firstchild[K]; J != -1; J = silbings[J])
        { Jall += newncolfactor[J];
          cost -= newncolfactor[J] * newncolfactor[J];
          cost += 2*newncolfactor[J] * (ncolfrontK - ncolupdate[J]);
          cost += 2*nzeros[J];
        }
       cost += Jall * Jall;
       cost = cost / 2;
       if (cost < maxzeros)
        { for (J = firstchild[K]; J != -1; J = silbings[J])
           { rep[J] = K;
             newncolfactor[K] += newncolfactor[J];
           }
          nzeros[K] = cost;
        }
     }
 
  /* ----------------------------------
     construct frontmap from vector rep
     ---------------------------------- */
  cnfronts = 0;
  for (K = 0; K < nfronts; K++)
    if (rep[K] == K)
      frontmap[K] = cnfronts++;
    else
     { for (J = K; rep[J] != J; J = rep[J]);
       rep[K] = J;
     }
  for (K = 0; K < nfronts; K++)
    if ((J = rep[K]) != K)
      frontmap[K] = frontmap[J];
 
  /* ------------------------------
     construct new elimination tree
     ------------------------------ */
  T2 = compressElimTree(T, frontmap, cnfronts);
 
  /* ----------------------
     free memory and return
     ---------------------- */
  free(frontmap); free(newncolfactor);
  free(nzeros); free(rep);
  return(T2);
}

newElimTree()

elimtree_t * newElimTree	(	PORD_INT	nvtx,
		PORD_INT	nfronts )

Definition at line 110 of file tree.c.

{ elimtree_t *T;
 
  mymalloc(T, 1, elimtree_t);
  mymalloc(T->ncolfactor, nfronts, PORD_INT);
  mymalloc(T->ncolupdate, nfronts, PORD_INT);
  mymalloc(T->parent, nfronts, PORD_INT);
  mymalloc(T->firstchild, nfronts, PORD_INT);
  mymalloc(T->silbings, nfronts, PORD_INT);
  mymalloc(T->vtx2front, nvtx, PORD_INT);
 
  T->nvtx = nvtx;
  T->nfronts = nfronts;
  T->root = -1;
 
  return(T);
}

nextPostorder()

PORD_INT nextPostorder	(	elimtree_t *	T,
		PORD_INT	J )

Definition at line 243 of file tree.c.

{ PORD_INT *parent, *firstchild, *silbings;
 
  parent = T->parent;
  firstchild = T->firstchild;
  silbings = T->silbings;
 
  if (silbings[J] != -1)
   { J = silbings[J];
     while (firstchild[J] != -1)
       J = firstchild[J];
   }
  else J = parent[J];
  return(J);
}

nextPreorder()

PORD_INT nextPreorder	(	elimtree_t *	T,
		PORD_INT	J )

Definition at line 272 of file tree.c.

{ PORD_INT *parent, *firstchild, *silbings;
 
  parent = T->parent;
  firstchild = T->firstchild;
  silbings = T->silbings;
 
  if (firstchild[J] != -1)
    J = firstchild[J];
  else
   { while ((silbings[J] == -1) && (parent[J] != -1))
       J = parent[J];
     J = silbings[J];
   }
  return(J);
}

nFactorEntries()

PORD_INT nFactorEntries

(

elimtree_t *

T

)

Definition at line 892 of file tree.c.

{ PORD_INT *ncolfactor, *ncolupdate;
  PORD_INT ent, tri, rec, K;
 
  ncolfactor = T->ncolfactor;
  ncolupdate = T->ncolupdate;
 
  ent = 0;
  for (K = firstPostorder(T); K != -1; K = nextPostorder(T, K))
   { tri = ncolfactor[K];
     rec = ncolupdate[K];
     ent += (tri * (tri+1)) / 2;
     ent += (tri * rec);
   }
  return(ent);
}

nFactorIndices()

PORD_INT nFactorIndices

(

elimtree_t *

T

)

Definition at line 874 of file tree.c.

{ PORD_INT *ncolfactor, *ncolupdate;
  PORD_INT nfronts, ind, K;
 
  nfronts = T->nfronts;
  ncolfactor = T->ncolfactor;
  ncolupdate = T->ncolupdate;
 
  ind = 0;
  for (K = 0; K < nfronts; K++)
    ind += (ncolfactor[K] + ncolupdate[K]);
  return(ind);
}

nFactorOps()

FLOAT nFactorOps

(

elimtree_t *

T

)

Definition at line 913 of file tree.c.

{ PORD_INT   *ncolfactor, *ncolupdate;
  FLOAT ops, tri, rec;
  PORD_INT   K;
 
  ncolfactor = T->ncolfactor;
  ncolupdate = T->ncolupdate;
 
  ops = 0.0;
  for (K = firstPostorder(T); K != -1; K = nextPostorder(T, K))
   { tri = ncolfactor[K];
     rec = ncolupdate[K];
     ops += (tri*tri*tri) / 3.0 + (tri*tri) / 2.0 - (5*tri) / 6.0;
     ops += (tri*tri*rec) + (rec*(rec+1)*tri);
   }
  return(ops);
}

nTriangularOps()

FLOAT nTriangularOps

(

elimtree_t *

T

)

Definition at line 957 of file tree.c.

{ PORD_INT   *ncolfactor, *ncolupdate;
  FLOAT ops, tri, rec;
  PORD_INT   K;
 
  ncolfactor = T->ncolfactor;
  ncolupdate = T->ncolupdate;
 
  ops = 0.0;
  for (K = firstPostorder(T); K != -1; K = nextPostorder(T, K))
   { tri = ncolfactor[K];
     rec = ncolupdate[K];
     ops += (tri*tri) + 2.0*tri*rec;  /* forward ops */
     ops += (tri*tri) + 2.0*tri*rec;  /* backward ops */
   }
  return(ops);
}

nWorkspace()

PORD_INT nWorkspace

(

elimtree_t *

T

)

Definition at line 817 of file tree.c.

{ PORD_INT *ncolfactor, *ncolupdate, *firstchild, *silbings, *minWspace;
  PORD_INT nfronts, K, ncolfrontK, frontsizeK, wspace, child, nxtchild, m, s;
 
  nfronts = T->nfronts;
  ncolfactor = T->ncolfactor;
  ncolupdate = T->ncolupdate;
  firstchild = T->firstchild;
  silbings = T->silbings;
 
  /* -------------------------
     set up the working arrays
     ------------------------- */
  mymalloc(minWspace, nfronts, PORD_INT);
 
  /* -------------------------------------------
     postorder traversal of the elimination tree
     ------------------------------------------- */
  wspace = 0;
  for (K = firstPostorder(T); K != -1; K = nextPostorder(T, K))
   { ncolfrontK = ncolfactor[K] + ncolupdate[K];
     frontsizeK = (ncolfrontK * (ncolfrontK + 1)) >> 1;
 
     if ((child = firstchild[K]) == -1)
       minWspace[K] = frontsizeK;
     else
      { child = firstchild[K];
        nxtchild = silbings[child];
        m = s = minWspace[child];
        while (nxtchild != -1)
         { s = s - minWspace[child]
               + ((ncolupdate[child] * (ncolupdate[child] + 1)) >> 1)
               + minWspace[nxtchild];
           m = max(m, s);
           child = nxtchild;
           nxtchild = silbings[nxtchild];
         }
        s = s - minWspace[child]
            + ((ncolupdate[child] * (ncolupdate[child] + 1)) >> 1)
            + frontsizeK;
        minWspace[K] = max(m, s);
      }
 
     wspace = max(wspace, minWspace[K]);
   }
 
  /* ----------------------
     free memory and return
     ---------------------- */
  free(minWspace);
  return(wspace);
}

permFromElimTree()

void permFromElimTree	(	elimtree_t *	T,
		PORD_INT *	perm )

Definition at line 440 of file tree.c.

{ PORD_INT *vtx2front, *first, *link;
  PORD_INT nvtx, nfronts, K, u, count;
 
  nvtx = T->nvtx;
  nfronts = T->nfronts;
  vtx2front = T->vtx2front;
 
  /* -----------------------------------------------------------
     store the vertices/columns of a front in a bucket structure
     ----------------------------------------------------------- */
  mymalloc(first, nfronts, PORD_INT);
  mymalloc(link, nvtx, PORD_INT);
 
  for (K = 0; K < nfronts; K++)
    first[K] = -1;
  for (u = nvtx-1; u >= 0; u--)
   { K = vtx2front[u];
     link[u] = first[K];
     first[K] = u;
   }
 
  /* -----------------------------------------------------
     postorder traversal of the elimination tree to obtain
     the permutation vectors perm, invp
     ----------------------------------------------------- */
  count = 0;
  for (K = firstPostorder(T); K != -1; K = nextPostorder(T, K))
    for (u = first[K]; u != -1; u = link[u])
     { perm[u] = count;
       count++;
     }
 
  /* ----------------------
     free memory and return
     ---------------------- */
  free(first); free(link);
}

permuteElimTree()

elimtree_t * permuteElimTree	(	elimtree_t *	T,
		PORD_INT *	perm )

Definition at line 483 of file tree.c.

{ elimtree_t *PTP;
  PORD_INT        nvtx, nfronts, J, u;
 
  nvtx = T->nvtx;
  nfronts = T->nfronts;
 
  /* --------------------------------------------------------------
     allocate space for the new elimtree object and copy front data
     the permuted tree has the same number of fronts/tree structure
     -------------------------------------------------------------- */
  PTP = newElimTree(nvtx, nfronts);
  PTP->root = T->root;
  for (J = 0; J < nfronts; J++)
   { PTP->ncolfactor[J] = T->ncolfactor[J];
     PTP->ncolupdate[J] = T->ncolupdate[J];
     PTP->parent[J] = T->parent[J];
     PTP->firstchild[J] = T->firstchild[J];
     PTP->silbings[J] = T->silbings[J];
   }
 
  /* ---------------------------------------------------------------------
     set up the new vtx2front vector; the trees only differ in this vector
     --------------------------------------------------------------------- */
  for (u = 0; u < nvtx; u++)
    PTP->vtx2front[perm[u]] = T->vtx2front[u];
 
  return(PTP);
}

printElimTree()

void printElimTree

(

elimtree_t *

T

)

Definition at line 147 of file tree.c.

{ PORD_INT *ncolfactor, *ncolupdate, *parent, *firstchild, *silbings, *vtx2front;
  PORD_INT *first, *link, nvtx, nfronts, root, J, K, u, count, child;
 
  nvtx = T->nvtx;
  nfronts = T->nfronts;
  root = T->root;
  ncolfactor = T->ncolfactor;
  ncolupdate = T->ncolupdate;
  parent = T->parent;
  firstchild = T->firstchild;
  silbings = T->silbings;
  vtx2front = T->vtx2front;
 
  printf("#fronts %d, root %d\n", nfronts, root);
 
  /* -----------------------------------------------------------
     store the vertices/columns of a front in a bucket structure
     ----------------------------------------------------------- */
  mymalloc(first, nfronts, PORD_INT);
  mymalloc(link, nvtx, PORD_INT);
 
  for (J = 0; J < nfronts; J++)
    first[J] = -1;
  for (u = nvtx-1; u >= 0; u--)
   { J = vtx2front[u];
     link[u] = first[J];
     first[J] = u;
   }
 
  /* -----------------------------------------------------------
     print fronts according to a postorder traversal of the tree
     ----------------------------------------------------------- */
  for (K = firstPostorder(T); K != -1; K = nextPostorder(T, K))
   { printf("--- front %d, ncolfactor %d, ncolupdate %d, parent %d\n",
            K, ncolfactor[K], ncolupdate[K], parent[K]);
     count = 0;
     printf("children:\n");
     for (child = firstchild[K]; child != -1; child = silbings[child])
      { printf("%5d", child);
        if ((++count % 16) == 0)
          printf("\n");
      }
     if ((count % 16) != 0)
       printf("\n");
     count = 0;
     printf("vertices mapped to front:\n");
     for (u = first[K]; u != -1; u = link[u])
      { printf("%5d", u);
        if ((++count % 16) == 0)
          printf("\n");
      }
     if ((count % 16) != 0)
       printf("\n");
   }
 
  /* ----------------------
     free memory and return
     ---------------------- */
  free(first); free(link);
}

setupElimTree()

elimtree_t * setupElimTree	(	graph_t *	G,
		PORD_INT *	perm,
		PORD_INT *	invp )

Definition at line 293 of file tree.c.

{ elimtree_t *T;
  css_t      *css;
  PORD_INT        *xadj, *adjncy, *vwght, *ncolfactor, *ncolupdate, *parent;
  PORD_INT        *vtx2front, *realroot, *uf_father, *uf_size;
  PORD_INT        *xnzl, *nzlsub, *xnzlsub;
  PORD_INT        nvtx, front, front2, froot, f, r, u, v, i, istart, istop;
  PORD_INT        prevlen, len, h, hsub;
 
  nvtx = G->nvtx;
  xadj = G->xadj;
  adjncy = G->adjncy;
  vwght = G->vwght;
 
  /* --------------------------
     set up the working storage
     -------------------------- */
  mymalloc(realroot, nvtx, PORD_INT);
  mymalloc(uf_father, nvtx, PORD_INT);
  mymalloc(uf_size, nvtx, PORD_INT);
 
  /* ------------------------------------------------
     allocate storage for the elimination tree object
     ------------------------------------------------ */
  T = newElimTree(nvtx, nvtx);
  ncolfactor = T->ncolfactor;
  ncolupdate = T->ncolupdate;
  parent = T->parent;
  vtx2front = T->vtx2front;
 
  /* -----------------------------
     set up the parent vector of T
     ----------------------------- */
  for (front = 0; front < nvtx; front++)
   { parent[front] = -1;
     u = invp[front];           /* only vertex u belongs to this front */
     uf_father[front] = front;  /* front forms a set in union-find structure */
     uf_size[front] = 1;        /* the set consists of a single front */
     realroot[front] = front;
     froot = front;
 
     /* run through the adjacency list of u */
     istart = xadj[u];
     istop = xadj[u+1];
     for (i = istart; i < istop; i++)
      { v = adjncy[i];
        front2 = perm[v];
        if (front2 < front)
         { r = front2;
 
           while (uf_father[r] != r)  /* find root of front2 in union-find */
             r = uf_father[r];
           while (front2 != r)        /* path compression */
            { f = front2;
              front2 = uf_father[front2];
              uf_father[f] = r;
            }
 
           f = realroot[r];           /* merge union-find sets */
           if ((parent[f] == -1) && (f != front))
            { parent[f] = front;
              if (uf_size[froot] < uf_size[r])
               { uf_father[froot] = r;
                 uf_size[r] += uf_size[froot];
                 froot = r;
               }
              else
               { uf_father[r] = froot;
                 uf_size[froot] += uf_size[r];
               }
              realroot[froot] = front;
            }
         }
      }
   }
 
  /* ---------------------------------------------
     set the vectors T->firstchild and T->silbings
     --------------------------------------------- */
  initFchSilbRoot(T);
 
  /* ----------------------------------------------------------
     set the vectors T->vtx2front, T->ncolfactor, T->ncolupdate
     ---------------------------------------------------------- */
  css = setupCSSFromGraph(G, perm, invp);
  xnzl = css->xnzl;
  nzlsub = css->nzlsub;
  xnzlsub = css->xnzlsub;
 
  prevlen = 0;
  for (front = 0; front < nvtx; front++)
   { u = invp[front];
     ncolfactor[front] = vwght[u];
     ncolupdate[front] = 0;
     vtx2front[u] = front;
     len = xnzl[front+1] - xnzl[front];
     if (prevlen - 1 == len)
       ncolupdate[front] = ncolupdate[front-1] - vwght[u];
     else
      { h = xnzlsub[front] + 1;
        for (i = 1; i < len; i++)
         { hsub = nzlsub[h++];
           v = invp[hsub];
           ncolupdate[front] += vwght[v];
         }
      }
     prevlen = len;
   }
 
  /* ----------------------
     free memory and return
     ---------------------- */
  free(css);
  free(realroot); free(uf_father); free(uf_size);
  return(T);
}

subtreeFactorOps()

void subtreeFactorOps	(	elimtree_t *	T,
		FLOAT *	ops )

Definition at line 935 of file tree.c.

{ PORD_INT   *ncolfactor, *ncolupdate;
  FLOAT tri, rec;
  PORD_INT   J, K;
 
  ncolfactor = T->ncolfactor;
  ncolupdate = T->ncolupdate;
 
  for (K = firstPostorder(T); K != -1; K = nextPostorder(T, K))
   { tri = ncolfactor[K];
     rec = ncolupdate[K];
     ops[K] = (tri*tri*tri) / 3.0 + (tri*tri) / 2.0 - (5*tri) / 6.0;
     ops[K] += (tri*tri*rec) + (rec*(rec+1)*tri);
     for (J = T->firstchild[K]; J != -1; J = T->silbings[J])
       ops[K] += ops[J];
   }
}