Utilities/extra.h

Go to the documentation of this file.

/************************************************************************************
    Copyright (C) 2005-2008 Assefaw H. Gebremedhin, Arijit Tarafdar, Duc Nguyen,
    Alex Pothen

    This file is part of ColPack.

    ColPack is free software: you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as published
    by the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    ColPack is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public License
    along with ColPack.  If not, see <http://www.gnu.org/licenses/>.
************************************************************************************/

#ifndef EXTRA_H
#define EXTRA_H

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <iomanip>
#include <ctime>
#include <cstdlib>
#include <stdarg.h> //  support for variadic functions
//#include <cctype> //for toupper()

#include <list>
#include <set>
#include <map>
#include <string>
#include <vector>

#include "ColPackHeaders.h"

using namespace std;

/*
#include "Definitions.h"
#include "Pause.h"
*/


//Definition for dot
#define DOT 1
#define NEATO 2
#define TWOPI 3
#define CIRCO 4
#define FDP 5


int WriteMatrixMarket_ADOLCInput(string s_postfix, int i_mode, ...);


int ConvertHarwellBoeingDouble(string & num_string);

string itoa(int i);

vector<string> getListOfColors(string s_InputFile);

int buildDotWithoutColor(ColPack::GraphColoringInterface &g, vector<string> &ListOfColors, string fileName);


int buildDotWithColor(ColPack::GraphColoringInterface &g, vector<string> &ListOfColors, string fileName);

int buildDotWithoutColor(ColPack::BipartiteGraphPartialColoringInterface &g, vector<string> &ListOfColors, string fileName);
// !!! TODO: enable conflict detection
int buildDotWithColor(ColPack::BipartiteGraphPartialColoringInterface &g, vector<string> &ListOfColors, string fileName);

// !!! TO BE BUILT
int buildDotWithoutColor(ColPack::BipartiteGraphBicoloringInterface &g, vector<string> &ListOfColors, string fileName);
// !!! TO BE BUILT
int buildDotWithColor(ColPack::BipartiteGraphBicoloringInterface &g, vector<string> &ListOfColors, string fileName);



int ReadRowCompressedFormat(string s_InputFile, unsigned int *** uip3_SparsityPattern, int& rowCount, int& columnCount);


bool isValidOrdering(vector<int> & ordering, int offset = 0);

//Re-order the values randomly
void randomOrdering(vector<int>& ordering);

string toUpper(string input);


int ConvertRowCompressedFormat2SparseSolversFormat_StructureOnly(unsigned int ** uip2_HessianSparsityPattern, unsigned int ui_rowCount, unsigned int** ip2_RowIndex, unsigned int** ip2_ColumnIndex);


int ConvertCoordinateFormat2RowCompressedFormat(unsigned int* uip1_RowIndex, unsigned int* uip1_ColumnIndex, double* dp1_HessianValue, int i_RowCount, int i_NonZeroCount, unsigned int *** dp3_Pattern, double*** dp3_Values );



void ConvertFileDIMACSFormat2MatrixMarketFormat(string fileNameNoExt);


int ConvertMatrixMarketFormat2RowCompressedFormat(string s_InputFile, unsigned int *** uip3_SparsityPattern, double*** dp3_Value, int &rowCount, int &columnCount);

/* !!! the documentation here may not be accurate 
"zero-based indexing, 3-array variation CSR format (used by ADIC)"
Does ADIC use zero-based indexing, 3-array variation CSR format any more?
//*/

// !!! need to be fixed to accomodate dp2_Value parameter
int ConvertRowCompressedFormat2CSR(unsigned int ** uip2_SparsityPattern_RowCompressedFormat, int i_rowCount, int** ip_RowIndex, int** ip_ColumnIndex);

int ConvertRowCompressedFormat2ADIC(unsigned int ** uip2_SparsityPattern_RowCompressedFormat, int i_rowCount , double** dp2_Value, std::list<std::set<int> > &lsi_SparsityPattern, std::list<std::vector<double> > &lvd_Value);


int MatrixMultiplication_VxS(unsigned int ** uip3_SparsityPattern, double** dp3_Value, int rowCount, int columnCount, double** dp2_seed, int colorCount, double*** dp3_CompressedMatrix);

int MatrixMultiplication_VxS__usingVertexPartialColors(std::list<std::set<int> > &lsi_SparsityPattern, std::list<std::vector<double> > &lvd_Value, int columnCount, vector<int> &vi_VertexPartialColors, int colorCount, double*** dp3_CompressedMatrix);


int MatrixMultiplication_SxV(unsigned int ** uip3_SparsityPattern, double** dp3_Value, int rowCount, int columnCount, double** dp2_seed, int colorCount, double*** dp3_CompressedMatrix);


bool CompressedRowMatricesAreEqual(double** dp3_Value, double** dp3_NewValue, int rowCount, bool compare_exact = 1, bool print_all = 0);

bool ADICMatricesAreEqual(std::list<std::vector<double> >& lvd_Value, std::list<std::vector<double> >& lvd_NewValue, bool compare_exact = 1, bool print_all = 0);

int Times2Plus1point5(double** dp2_Values, int i_RowCount, int i_ColumnCount);

int Times2(double** dp2_Values, int i_RowCount, int i_ColumnCount);

int GenerateValues(unsigned int ** uip2_SparsityPattern, int rowCount, double*** dp3_Value);

int GenerateValuesForSymmetricMatrix(unsigned int ** uip2_SparsityPattern, int rowCount, double*** dp3_Value);

int DisplayADICFormat_Sparsity(std::list<std::set<int> > &lsi_SparsityPattern);
int DisplayADICFormat_Value(std::list<std::vector<double> > &lvd_Value);

int displayGraph(map< int, map<int,bool> > *graph, vector<int>* vi_VertexColors=NULL,int i_RunInBackground = false, int filter = DOT);
int buildDotWithoutColor(map< int, map<int,bool> > *graph, vector<string> &ListOfColors, string fileName);
int buildDotWithColor(map< int, map<int,bool> > *graph, vector<int>* vi_VertexColors, vector<string> &ListOfColors, string fileName);

#ifndef EXTRA_H_TEMPLATE_FUNCTIONS
#define EXTRA_H_TEMPLATE_FUNCTIONS

template<class T>
int displayGraph(T &g,int i_RunInBackground = false, int filter = DOT) {
  static int ranNum = rand();
  static int seq = 0;
  seq++;
  vector<string> ListOfColors = getListOfColors("");
  string fileName = "/tmp/.";
  fileName = fileName + "ColPack_"+ itoa(ranNum)+"_"+itoa(seq)+".dot";
  
  //build the dot file of the graph
  string m_s_VertexColoringVariant = g.GetVertexColoringVariant();
  if(m_s_VertexColoringVariant.empty() || m_s_VertexColoringVariant=="Unknown") {
    //build dot file represents graph without color info
    buildDotWithoutColor(g, ListOfColors, fileName);
  } else {
    //build dot file represents graph with color
    buildDotWithColor(g, ListOfColors, fileName);
  }
  
  //display the graph using xdot
  string command;
  switch (filter) {
    case NEATO: command="xdot -f neato "; break;
    case TWOPI: command="xdot -f twopi "; break;
    case CIRCO: command="xdot -f circo "; break;
    case FDP: command="xdot -f fdp "; break;
    default: command="xdot -f dot "; // case DOT
  }
  
  command = command + fileName;
  if(i_RunInBackground) command = command + " &";
  int i_ReturnValue = system(command.c_str());
  return i_ReturnValue;
}


template<class T>
int diffArrays(T* array1, T* array2, int rowCount, bool compare_exact = 1, bool print_all = 0) {
        double ratio = 0.;
        int none_equal_count = 0;
        for(int i = 0; i < rowCount; i++) {
          if (compare_exact) {
            if(array1[i]!=array2[i]) { // found a difference
              cout<<"At index i="<<i<<"\t array1[] = "<<array1[i]<";\t array2[] = "<<array2[i]<<endl;
              none_equal_count++;
              if(!print_all) return 1;
            }
          }
          else {
            ratio = array1[i] / array2[i];
            if(ratio < .99 || ratio > 1.02) { // found a difference
              cout<<"At index i="<<i<<"\t array1[] = "<<array1[i]<";\t array2[] = "<<array2[i]<<endl;
              none_equal_count++;
              if(!print_all) return 1;
            }
          }
        }
        
        return none_equal_count;
}

template<class T>
int diffVectors(vector<T> array1, vector<T> array2, bool compare_exact = 1, bool print_all = 0) {
        double ratio = 0.;
        int none_equal_count = 0;
        
        if(array1.size() != array2.size()) {
          cout<<"array1.size() "<<array1.size()<<" != array2.size()"<<array2.size()<<endl;
          none_equal_count++;
        }
        
        int min_array_size = (array1.size() < array2.size())?array1.size():array2.size();
        
        for(int i = 0; i < min_array_size; i++) {
          if (compare_exact) {
            if(array1[i]!=array2[i]) { // found a difference
              cout<<"At index i="<<i<<"\t array1[] = "<<array1[i]<<";\t array2[] = "<<array2[i]<<endl;
              none_equal_count++;
              if(!print_all) return none_equal_count;
            }
          }
          else {
            ratio = array1[i] / array2[i];
            if(ratio < .99 || ratio > 1.02) { // found a difference
              cout<<"At index i="<<i<<"\t array1[] = "<<array1[i]<<";\t array2[] = "<<array2[i]<<endl;
              none_equal_count++;
              if(!print_all) return none_equal_count;
            }
          }
        }
        
        return none_equal_count;
}

template<class T>
int freeMatrix(T** xp2_matrix, int rowCount) {
//cout<<"IN deleteM 2"<<endl<<flush;
//printf("* deleteMatrix rowCount=%d \n",rowCount);
//Pause();
        for(int i = 0; i < rowCount; i++) {
//printf("delete xp2_matrix[%d][0] = %7.2f \n", i, (float) xp2_matrix[i][0]);
                free( xp2_matrix[i]);
        }
//cout<<"MID deleteM 2"<<endl<<flush;
        free( xp2_matrix);
//cout<<"OUT deleteM 2"<<endl<<flush;
        return 0;
}

template<class T>
int freeMatrix(T*** xp3_matrix, int rowCount) {
//cout<<"IN deleteM 3"<<endl<<flush;
        freeMatrix(*xp3_matrix,rowCount);
//cout<<"MID deleteM 3"<<endl<<flush;
        free( xp3_matrix);
//cout<<"OUT deleteM 3"<<endl<<flush;
        return 0;
}

template<class T>
int deleteMatrix(T** xp2_matrix, int rowCount) {
//cout<<"IN deleteM 2"<<endl<<flush;
//printf("* deleteMatrix rowCount=%d \n",rowCount);
//Pause();
        for(int i = 0; i < rowCount; i++) {
//printf("delete xp2_matrix[%d][0] = %7.2f \n", i, (float) xp2_matrix[i][0]);
                delete xp2_matrix[i];
        }
//cout<<"MID deleteM 2"<<endl<<flush;
        delete xp2_matrix;
//cout<<"OUT deleteM 2"<<endl<<flush;
        return 0;
}

template<class T>
int deleteMatrix(T*** xp3_matrix, int rowCount) {
//cout<<"IN deleteM 3"<<endl<<flush;
        deleteMatrix(*xp3_matrix,rowCount);
//cout<<"MID deleteM 3"<<endl<<flush;
        delete xp3_matrix;
//cout<<"OUT deleteM 3"<<endl<<flush;
        return 0;
}

template<class T>
void displayCompressedRowMatrix(T** xp2_Value, int rowCount, bool structureOnly = false) {
        unsigned int estimateColumnCount = 20;
        cout<<setw(4)<<"["<<setw(3)<<"\\"<<"]       ";
        if(structureOnly) {
                for(unsigned int j=0; j < estimateColumnCount; j++) cout<<setw(4)<<j;
        }
        else {
                for(unsigned int j=0; j < estimateColumnCount; j++) cout<<setw(9)<<j;
        }
        cout<<endl;

        for(unsigned int i=0; i < (unsigned int)rowCount; i++) {
                cout<<setw(4)<<"["<<setw(3)<<i<<"]";
                unsigned int numOfNonZeros = (unsigned int)xp2_Value[i][0];
                cout<<"  ("<<setw(3)<<numOfNonZeros<<")";
                if(structureOnly) {
                        for(unsigned int j=1; j <= numOfNonZeros; j++) cout<<setw(4)<<(int)xp2_Value[i][j];
                        //for(unsigned int j=1; j <= numOfNonZeros; j++) {
                        //  printf("  %d",(int)xp2_Value[i][j]);
                        //}
                }
                else {
                        for(unsigned int j=1; j <= numOfNonZeros; j++) cout<<setw(9)<<(float)xp2_Value[i][j];
                        //for(unsigned int j=1; j <= numOfNonZeros; j++) {
                        //  printf("  %7.2f",(float)xp2_Value[i][j]);
                        //}
                }
                cout<<endl<<flush;
        }
        cout<<endl<<endl;
}

template<class T>
void displayMatrix(T** xp2_Value, int rowCount, int columnCount, bool structureOnly = false) {
        cout<<setw(4)<<"["<<setw(3)<<"\\"<<"]";
        if(structureOnly) {
                for(unsigned int j=0; j < (unsigned int)columnCount; j++) cout<<setw(3)<<j;
        }
        else {
                for(unsigned int j=0; j < (unsigned int)columnCount; j++) cout<<setw(9)<<j;
        }
        cout<<endl;

        for(unsigned int i=0; i < (unsigned int)rowCount; i++) {
                cout<<setw(4)<<"["<<setw(3)<<i<<"]";
                if(structureOnly) {
                        for(unsigned int j=0; j < (unsigned int)columnCount; j++) cout<<setw(3)<<(bool)xp2_Value[i][j];
                }
                else {
                        for(unsigned int j=0; j < (unsigned int)columnCount; j++) printf("  %7.2f",(float)xp2_Value[i][j]);
                        //for(unsigned int j=0; j < (unsigned int)columnCount; j++) cout<<setw(8)<<xp2_Value[i][j];
                }
                cout<<endl<<flush;
        }
        cout<<endl<<endl;
}

template<class T>
void displayVector(T* xp2_Value, int size, bool structureOnly = false) {
        if(structureOnly) {
                for(unsigned int i=0; i < (unsigned int)size; i++) {
                        cout<<setw(4)<<"["<<setw(3)<<i<<"]";
                        cout<<setw(3)<<(bool)xp2_Value[i];
                        cout<<endl<<flush;
                }
        }
        else {
                for(unsigned int i=0; i < (unsigned int)size; i++) {
                        cout<<setw(4)<<"["<<setw(3)<<i<<"]";
                        printf("  %7.2f",(float)xp2_Value[i]);
                        //cout<<setw(8)<<xp2_Value[i];
                        cout<<endl<<flush;
                }
        }
        cout<<endl<<endl;
}

template<class T>
int displayVector(vector<T> v) {
  for (unsigned int i=0; i < v.size(); i++) {
    cout<<setw(4)<<"["<<setw(3)<<i<<"]";
    printf("  %7.2f",(float)v[i]);
    cout<<endl<<flush;
  }
  return 0;
}


template<class T>
void displayAdjacencyMatrix(vector< vector<T> > &xp2_Value, bool structureOnly = false) {
        unsigned int estimateColumnCount = 20;
        cout<<setw(4)<<"["<<setw(3)<<"\\"<<"]";
        if(structureOnly) {
                for(unsigned int j=0; j < estimateColumnCount; j++) cout<<setw(3)<<j;
        }
        else {
                for(unsigned int j=0; j < estimateColumnCount; j++) cout<<setw(9)<<j;
        }
        cout<<endl;

        unsigned int rowCount = xp2_Value.size();
        for(unsigned int i=0; i < rowCount; i++) {
                cout<<setw(4)<<"["<<setw(3)<<i<<"]";
                unsigned int numOfNonZeros = (int)xp2_Value[i].size();
                cout<<"("<<setw(5)<<numOfNonZeros<<")";
                if(structureOnly) {
                        for(unsigned int j=0; j < numOfNonZeros; j++) cout<<setw(3)<<(bool)xp2_Value[i][j];
                }
                else {
                        for(unsigned int j=0; j < numOfNonZeros; j++) cout<<setw(9)<<xp2_Value[i][j];
                }
                cout<<endl<<flush;
        }
        cout<<endl<<endl;
}


#endif //EXTRA_H_TEMPLATE_FUNCTIONS

#endif //EXTRA_H