/*************************************************************************/
/*                                                                       */
/*  Copyright (c) 1994 Stanford University                               */
/*                                                                       */
/*  All rights reserved.                                                 */
/*                                                                       */
/*  Permission is given to use, copy, and modify this software for any   */
/*  non-commercial purpose as long as this copyright notice is not       */
/*  removed.  All other uses, including redistribution in whole or in    */
/*  part, are forbidden without prior written permission.                */
/*                                                                       */
/*  This software is provided with absolutely no warranty and no         */
/*  support.                                                             */
/*                                                                       */
/*************************************************************************/

EXTERN_ENV

#include "matrix.h"

long *firstchild, *child;
double *work_tree;

void EliminationTreeFromA(SMatrix A, long *T, long *P, long *INVP)
{
  long *subtree;
  long i, nd, nabor, j, r, nextr, root;

  subtree = (long *) malloc((A.n+1)*sizeof(long));

  for (i=0; i<=A.n; i++)
    T[i] = subtree[i] = A.n;

  for (j=0; j<A.n; j++) {
    nd = P[j];

    for (i=A.col[nd]; i<A.col[nd+1]; i++) {

      nabor = INVP[A.row[i]];

      if (nabor < j) {

	for (r=nabor; subtree[r] != A.n; r = subtree[r])
	  ;
	if (r != j)
	  T[r] = subtree[r] = root = j;
	else root = r;

	r = nabor;
	while (subtree[r] != A.n) {
	  nextr = subtree[r];
	  subtree[r] = root;
	  r = nextr;
	}
      }
    }
  }

  free(subtree);
}


void ParentToChild(long *T, long n, long *firstchild, long *child)
{
  long i, k, parent, count=0;
  long *next;

  next = (long *) malloc((n+1)*sizeof(long));

  for (i=0; i<=n; i++)
    firstchild[i] = next[i] = -1;

  for (i=n; i>=0; i--) {
    parent = T[i];
    if (parent != i) {
	next[i] = firstchild[parent];
	firstchild[parent] = i;
    }
  }

  for (i=0; i<=n; i++) {
    k = firstchild[i];
    firstchild[i] = count;
    while (k != -1) {
      child[count++] = k;
      k = next[k];
    }
  }
  firstchild[n+1] = count;

  free(next);

}


void ComputeNZ(SMatrix A, long *T, long *nz, long *PERM, long *INVP)
{
  long i, j, nd, nabor, k;
  long *marker;

  marker = (long *) malloc(A.n*sizeof(long));
  for (i=0; i<A.n; i++)
    nz[i] = 1;
  nz[A.n] = 0;

  for (i=0; i<A.n; i++) {
    nd = PERM[i];
    marker[i] = -1;
    for (j=A.col[nd]; j<A.col[nd+1]; j++) {
      nabor = INVP[A.row[j]];
      k = nabor;
      while (marker[k] != i && k < i) {
        nz[k]++;
	marker[k] = i;
	k = T[k];
      }
    }
  }

  free(marker);
}


void FindSupernodes(SMatrix A, long *T, long *nz, long *node)
{
  long i;
  long *nchild;
  long supers, current, size, max_super = 0;

  nchild = (long *) malloc((A.n+1)*sizeof(long));
  for (i=0; i<=A.n; i++)
    nchild[i] = 0;

  for (i=0; i<A.n; i++)
    nchild[T[i]]++;

  current = 0;
  supers = 1;
  size = 1;
  for (i=1; i<A.n; i++) {
    if (nz[i] == nz[i-1]-1 && T[i-1] == i && nchild[i] == 1) {
      node[i] = current-i;
      size++;
    }
    else {
      node[current] = size;
      if (size > max_super)
	max_super = size;
      supers++;
      current = i;
      size = 1;
    }
  }

  node[current] = size;
  if (size > max_super)
    max_super = size;
  node[A.n] = 0;

  printf("%ld supers, %4.2f nodes/super, %ld max super\n",
	 supers, A.n/(double) supers, max_super);  

  free(nchild);
}


void ComputeWorkTree(SMatrix A, long *nz, double *work_tree)
{
  long i, j, nzj;

  for (j=0; j<=A.n; j++) {
    if (j != A.n) {
      nzj = nz[j];
      work_tree[j] = nzj+nzj*(nzj-1);
    }
    else
      work_tree[j] = 0;

    for (i=firstchild[j]; i<firstchild[j+1]; i++)
      work_tree[j] += work_tree[child[i]];
  }
}