#include "BSprivate.h"
    
/*@ BSmain_perm - Permute the matrix for efficient parallel execution

    Input Parameters:
.   procinfo - the usual processor context information
.   A - the sparse matrix

    Returns:
    the sparse matrix permuted into an efficient structure

    Notes:
$   (1) The sparse matrix must be symmetric in structure
$   (2) The graph associated with the sparse matrix must be connected
$   (3) max_inode_size and max_clique_size should usually be set to
$       INT_MAX (they are kept in the context)
$   (4) see the manual for more details on what algorithms BSmain_perm uses
$   (5) the context variable "retain" will indicate whether or not 
$       some extra data should be kept around to allow for fast permutation
$       of a matrix with the same structure in the future

 @*/
BSpar_mat *BSmain_perm(BSprocinfo *procinfo, BSspmat *A)
{
	BSpar_mat *pA;
	BSnumbering	*inode_number;
	BSdistribution *inode_distr;
	BSpermutation *inode_perm;
	BSnumbering *inode_row;
	BSnumbering	*clique_number;
	BSdistribution *clique_distr;
	BSpermutation *clique_perm;
	BSnumbering	*color_number;
	BSdistribution *color_distr;
	BSpermutation *color_perm;
	BSspmat	*iA;
	BSspmat	*cA;
	BSnumbering	*color_offset;
	BSnumbering *color_base;
	BSdistribution *new_clique_distr;
	BSdistribution *new_color_distr;
	BSnumbering	*clique_gnum;
	BSnumbering	*inode_gnum;
	BSnumbering	*row_gnum;
	BScl_2_inode	*col_cA;
	BSinode_list	*col_iA;
	BSnumbering	*color_2_cl;
	BSkey_arr	*key_arr;
	BSsprow **perm_rows;
	BSpermutation *g_perm, *g_iperm;
	int	max_gcolors;
	int	max_row_len;
	int	local_num_inodes, global_num_inodes;
	int	local_num_cliques, global_num_cliques;
	int	num_colors;
	int	ierr;
    
	/* *************************************************************** */
	/* BEGIN SECTION:                                                  */
	/* Find the various permutations and contracted graphs             */
	/* *************************************************************** */

	/* first check that matrix symmetry property and storage will work */
	if((!A->symmetric)&&(A->icc_storage)) {
		MY_SETERRCN(SYM_ERROR,"Attempt to store nonsymmetric matrix in ICC structure\n");
	}

	/* check rows for consistency */
	if (procinfo->error_check) {
		BSrow_err_check(A,procinfo); CHKERRN(0);
	}

	/* now get an i-node numbering */
	MLOG_ELM(procinfo->procset);
	inode_number = BSfnd_inode(A,procinfo->max_inode_size,procinfo); CHKERRN(0);

	inode_distr = BSnum2distr(inode_number); CHKERRN(0);

	inode_perm = BSnum2perm(inode_number,inode_distr); CHKERRN(0);

	inode_row = BSlow2high(A,inode_number,inode_distr,procinfo); CHKERRN(0);

	if (procinfo->single) {
		iA = A;
	} else {
		iA = BSdo_contract(A,inode_number,inode_perm,procinfo,TRUE); CHKERRN(0);
	}

	MLOG_IT(INODE);
	local_num_inodes = iA->num_rows;
	global_num_inodes = iA->global_num_rows;
	if ((procinfo->print) && (PSISROOT(procinfo))) {
		printf("************** Blocksolve Reordering Info *****************\n");
		printf("o  Inode graph size is %d\n",iA->global_num_rows);
	}

	/* check rows for consistency */
	if (procinfo->error_check) {
		BSrow_err_check(iA,procinfo); CHKERRN(0);
	}

	/* now get a clique numbering */
	MLOG_ELM(procinfo->procset);
	clique_number = BSfnd_clique(iA,procinfo->max_clique_size,
		inode_distr->distribution,procinfo); CHKERRN(0);
	clique_distr = BSnum2distr(clique_number); CHKERRN(0);
	clique_perm = BSnum2perm(clique_number,clique_distr); CHKERRN(0);
	if (procinfo->single) {
		cA = A;
	} else {
		cA = BSdo_contract(iA,clique_number,clique_perm,procinfo,FALSE); 
		CHKERRN(0);
	}
	MLOG_IT(CLIQUE);
	local_num_cliques = cA->num_rows;
	global_num_cliques = cA->global_num_rows;
	if ((procinfo->print) && (PSISROOT(procinfo))) {
		printf("o  Clique graph size is %d\n",cA->global_num_rows);
	}

	/* find weights */
	new_clique_distr = BSfold_distr(clique_distr,inode_distr,clique_number);
	CHKERRN(0);

	/* now do the coloring */
	BSrem_diag(cA); CHKERRN(0);
	color_number = BSalloc_numbering(cA->num_rows); CHKERRN(0);
	BSx_color(color_number->numbers,cA,procinfo,&max_gcolors,
		procinfo->coloring_type); CHKERRN(0);
	color_distr = BSnum2distr(color_number); CHKERRN(0);
	color_perm = BSnum2perm(color_number,color_distr); CHKERRN(0);
	BSins_diag(cA); CHKERRN(0);
	/* check rows for consistency */
	if (procinfo->error_check) {
		BSrow_err_check(cA,procinfo); CHKERRN(0);
	}

	/* *************************************************************** */
	/* END SECTION:                                                    */
	/* *************************************************************** */

	/* *************************************************************** */
	/* BEGIN SECTION:                                                  */
	/* Find global row numbers                                         */
	/* *************************************************************** */
	MLOG_ELM(procinfo->procset);
	new_color_distr = BSfold_distr(color_distr,new_clique_distr,color_number);
	CHKERRN(0);

	/* find the new global offsets for the colors */
	MY_MALLOCN(color_offset,(BSnumbering *),sizeof(BSnumbering),1);
	color_offset->length = BSoffset(new_color_distr->max+1,
		new_color_distr->distribution,&(color_offset->numbers),procinfo); 
	CHKERRN(0);
	num_colors = color_offset->length;
	if ((procinfo->print) && (PSISROOT(procinfo))) {
		printf("o  Number of colors is %d\n",color_offset->length);
	}

	/* find the new global base addresses for the colors */
	/* this is the same on every processors */
	color_base = BSbase(new_color_distr,procinfo); CHKERRN(0);

	/* find the new global offsets for the cliques */
	clique_gnum = BSoff_gnum(color_offset,color_number,new_clique_distr); 
	CHKERRN(0);

	/* find the new global offsets for the inodes */
	inode_gnum = BSoff_gnum(clique_gnum,clique_number,inode_distr); CHKERRN(0);

	/* find the new global addresses for the rows */
	row_gnum = BSoff_gnum(inode_gnum,inode_number,NULL); CHKERRN(0);

	/* get permutation based on new global addresses */
	/* also get a permuted version of the rows */
	g_perm = BSglobal_perm(row_gnum); CHKERRN(0);
	g_iperm = BSalloc_permutation(g_perm->length); CHKERRN(0);
	BSperm2iperm(g_perm,g_iperm); CHKERRN(0);

	/* *************************************************************** */
	/* END SECTION:                                                    */
	/* *************************************************************** */

	/* *************************************************************** */
	/* BEGIN SECTION:                                                  */
	/* Propagate the permutation until the row level                   */
	/* *************************************************************** */
	/* get the transpose structure of the cliques */
	col_cA = BStrans_perm_cl(cA,clique_gnum,procinfo); CHKERRN(0);
	/* get the tranpose structure of the inodes */
	col_iA = BStrans_perm_in(iA,inode_gnum,inode_row,inode_distr,
			procinfo); CHKERRN(0);
	/* set the pointers of the clique structure into the inode structure */
	BSclique_2_inode(A,col_cA,col_iA,procinfo); CHKERRN(0);
	/* set the pointers of the color structure into the clique structure */
	color_2_cl = BScolor_2_clique(color_base,col_cA); CHKERRN(0);

	/* *************************************************************** */
	/* END SECTION:                                                    */
	/* *************************************************************** */

	/* *************************************************************** */
	/* BEGIN SECTION:                                                  */
	/* Permute the nonzeros at the row level and sort them             */
	/* Remember to unsort them                                         */
	/* *************************************************************** */

	key_arr = BSperm_rows(A,row_gnum,inode_perm,inode_distr,procinfo,TRUE,
		&max_row_len); CHKERRN(0);

	/* *************************************************************** */
	/* END SECTION:                                                    */
	/* *************************************************************** */

	/* *************************************************************** */
	/* BEGIN SECTION:                                                  */
	/* Put the row numbers into the transposed inode structure         */
	/* *************************************************************** */

	perm_rows = BSrow_perm(A,g_iperm); CHKERRN(0);
	ierr = BSrows_2_inode(A,row_gnum,g_perm,g_iperm,perm_rows,col_iA,
		 col_cA,key_arr,inode_number,inode_distr,procinfo); CHKERRN(0);
	BSfree_key_arr(key_arr); CHKERRN(0);

	/* *************************************************************** */
	/* END SECTION:                                                    */
	/* *************************************************************** */

	/* *************************************************************** */
	/* BEGIN SECTION:                                                  */
	/* Put the numeric values into the transposed inode structure      */
	/* *************************************************************** */
	BSnz_2_inode(A,perm_rows,col_iA,col_cA,procinfo); CHKERRN(0);
	MY_FREEN(perm_rows);

	/* *************************************************************** */
	/* END SECTION:                                                    */
	/* *************************************************************** */

	/* *************************************************************** */
	/* BEGIN SECTION:                                                  */
	/* Unsort the rows to original condition                           */
	/* *************************************************************** */

	BSsort_rows(A,inode_perm,inode_distr,max_row_len); CHKERRN(0);

	/* *************************************************************** */
	/* END SECTION:                                                    */
	/* *************************************************************** */

	BSfree_numbering(inode_number); CHKERRN(0);
	BSfree_numbering(inode_row); CHKERRN(0);
	BSfree_numbering(clique_number); CHKERRN(0);
	BSfree_distribution(clique_distr); CHKERRN(0);
	BSfree_permutation(clique_perm); CHKERRN(0);
	BSfree_numbering(color_number); CHKERRN(0);
	BSfree_distribution(color_distr); CHKERRN(0);
	BSfree_permutation(color_perm); CHKERRN(0);
	if (!procinfo->single) {
		BSfree_spmat(iA);
		CHKERRN(0);
	}
	if (!procinfo->single) {
		BSfree_spmat(cA);
		CHKERRN(0);
	}
	BSfree_numbering(color_offset); CHKERRN(0);
	BSfree_numbering(color_base); CHKERRN(0);
	BSfree_distribution(new_clique_distr); CHKERRN(0);
	BSfree_distribution(new_color_distr); CHKERRN(0);
	BSfree_numbering(clique_gnum); CHKERRN(0);
	BSfree_numbering(inode_gnum); CHKERRN(0);

	/* set up return structure */
	MY_MALLOCN(pA,(BSpar_mat *),sizeof(BSpar_mat),2);
	pA->num_rows = A->num_rows;
	pA->global_num_rows = A->global_num_rows;
	pA->local_num_inodes = local_num_inodes;
	pA->global_num_inodes = global_num_inodes;
	pA->local_num_cliques = local_num_cliques;
	pA->global_num_cliques = global_num_cliques;
	pA->num_colors = num_colors;
	pA->symmetric = A->symmetric;
	pA->icc_storage = A->icc_storage;
	pA->perm = g_perm;
	pA->inv_perm = g_iperm;
	pA->color2clique = color_2_cl;
	pA->clique2inode = col_cA;
	pA->inodes = col_iA;
	pA->global_row_num = row_gnum;
	pA->map = A->map;
	/* allocate space for and get the diagonals */
	MY_MALLOCN(pA->diag,(FLOAT *),pA->num_rows*sizeof(FLOAT),3);
	BSget_diag(pA,pA->diag,procinfo); CHKERRN(0);
	pA->save_diag = pA->diag;
	pA->scale_diag = NULL;
	if (procinfo->retain) {
		MY_MALLOCN(pA->reperm,(BSreperm *),sizeof(BSreperm),4);
		pA->reperm->inode_perm = inode_perm;
		pA->reperm->inode_distr = inode_distr;
	} else {
		pA->reperm = NULL;
		BSfree_distribution(inode_distr); CHKERRN(0);
		BSfree_permutation(inode_perm); CHKERRN(0);
	}

	/* go over and patch up inode structure with original inode numbers */
	BSorig_inode(pA,procinfo); CHKERRN(0);
	pA->local_nnz = BScount_nz(pA,procinfo); CHKERRN(0);
	pA->max_local_row_length = max_row_len;
	MLOG_IT(PERMUTE);

	return(pA);
}