1 /****************************************************************/ 2 /* Parallel Combinatorial BLAS Library (for Graph Computations) */ 3 /* version 1.6 -------------------------------------------------*/ 4 /* date: 6/15/2017 ---------------------------------------------*/ 5 /* authors: Ariful Azad, Aydin Buluc --------------------------*/ 6 /****************************************************************/ 7 /* 8 Copyright (c) 2010-2017, The Regents of the University of California 9 10 Permission is hereby granted, free of charge, to any person obtaining a copy 11 of this software and associated documentation files (the "Software"), to deal 12 in the Software without restriction, including without limitation the rights 13 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 14 copies of the Software, and to permit persons to whom the Software is 15 furnished to do so, subject to the following conditions: 16 17 The above copyright notice and this permission notice shall be included in 18 all copies or substantial portions of the Software. 19 20 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 21 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 22 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 23 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 24 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 25 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 26 THE SOFTWARE. 27 */ 28 29 30 #ifndef _SP_TUPLES_H 31 #define _SP_TUPLES_H 32 33 #include <iostream> 34 #include <fstream> 35 #include <cmath> 36 #include <cassert> 37 #include "CombBLAS.h" 38 #include "SpMat.h" 39 #include "SpDefs.h" 40 #include "StackEntry.h" 41 #include "Compare.h" 42 43 namespace combblas { 44 45 template <class IU, class NU> 46 class SpDCCols; 47 48 template <class IU, class NU> 49 class Dcsc; 50 51 52 /** 53 * Triplets are represented using the boost::tuple class of the Boost library 54 * Number of entries are 64-bit addressible, but each entry is only <class IT> addressible 55 * Therefore, size is int64_t but nrows/ncols (representing range of first two entries in tuple) is of type IT 56 * \remarks Indices start from 0 in this class 57 * \remarks Sorted with respect to columns (Column-sorted triples) 58 */ 59 template <class IT, class NT> 60 class SpTuples: public SpMat<IT, NT, SpTuples<IT,NT> > 61 { 62 public: 63 // Constructors 64 SpTuples (int64_t size, IT nRow, IT nCol); 65 SpTuples (int64_t size, IT nRow, IT nCol, std::tuple<IT, IT, NT> * mytuples, bool sorted = false, bool isOpNew = false); 66 SpTuples (int64_t maxnnz, IT nRow, IT nCol, std::vector<IT> & edges, bool removeloops = true); // Graph500 contructor 67 SpTuples (int64_t size, IT nRow, IT nCol, StackEntry<NT, std::pair<IT,IT> > * & multstack); 68 SpTuples (const SpTuples<IT,NT> & rhs); // Actual Copy constructor 69 SpTuples (const SpDCCols<IT,NT> & rhs); // Copy constructor for conversion from SpDCCols 70 ~SpTuples(); 71 72 SpTuples<IT,NT> & operator=(const SpTuples<IT,NT> & rhs); 73 rowindex(IT i)74 IT & rowindex (IT i) { return joker::get<0>(tuples[i]); } colindex(IT i)75 IT & colindex (IT i) { return joker::get<1>(tuples[i]); } numvalue(IT i)76 NT & numvalue (IT i) { return joker::get<2>(tuples[i]); } 77 rowindex(IT i)78 IT rowindex (IT i) const { return joker::get<0>(tuples[i]); } colindex(IT i)79 IT colindex (IT i) const { return joker::get<1>(tuples[i]); } numvalue(IT i)80 NT numvalue (IT i) const { return joker::get<2>(tuples[i]); } 81 82 83 template <typename BINFUNC> 84 void RemoveDuplicates(BINFUNC BinOp); 85 SortRowBased()86 void SortRowBased() 87 { 88 RowLexiCompare<IT,NT> rowlexicogcmp; 89 if(!SpHelper::is_sorted(tuples, tuples+nnz, rowlexicogcmp)) 90 sort(tuples , tuples+nnz, rowlexicogcmp); 91 92 // Default "operator<" for tuples uses lexicographical ordering 93 // However, cray compiler complains about it, so we use rowlexicogcmp 94 } 95 SortColBased()96 void SortColBased() 97 { 98 ColLexiCompare<IT,NT> collexicogcmp; 99 if(!SpHelper::is_sorted(tuples, tuples+nnz, collexicogcmp)) 100 sort(tuples , tuples+nnz, collexicogcmp ); 101 } 102 103 /** 104 * @pre {should only be called on diagonal processors (others will add non-loop nonzeros)} 105 * @pre {both the implementation and its semantics is meaningless for non-square matrices} 106 **/ 107 IT AddLoops(NT loopval, bool replaceExisting=false) 108 { 109 std::vector<bool> existing(n,false); // none of the diagonals exist 110 IT loop = 0; 111 for(IT i=0; i< nnz; ++i) 112 { 113 if(joker::get<0>(tuples[i]) == joker::get<1>(tuples[i])) 114 { 115 ++loop; 116 existing[joker::get<0>(tuples[i])] = true; 117 if(replaceExisting) 118 joker::get<2>(tuples[i]) = loopval; 119 } 120 } 121 std::vector<IT> missingindices; 122 for(IT i = 0; i < n; ++i) 123 { 124 if(!existing[i]) missingindices.push_back(i); 125 } 126 IT toadd = n - loop; // number of new entries needed (equals missingindices.size()) 127 std::tuple<IT, IT, NT> * ntuples = new std::tuple<IT,IT,NT>[nnz+toadd]; 128 129 std::copy(tuples,tuples+nnz, ntuples); 130 131 // MCL: As for the loop weights that are chosen, experience shows that a neutral value works well. It is possible to choose larger weights, 132 // and this will increase cluster granularity. The effect is secondary however to that of varying the inflation parameter, 133 // and the algorithm is not very sensitive to changes in the loop weights. 134 for(IT i=0; i< toadd; ++i) 135 { 136 ntuples[nnz+i] = std::make_tuple(missingindices[i], missingindices[i], loopval); 137 } 138 if(isOperatorNew) 139 ::operator delete(tuples); 140 else 141 delete [] tuples; 142 tuples = ntuples; 143 isOperatorNew = false; 144 nnz = nnz+toadd; 145 146 return loop; 147 } 148 149 150 /** 151 * @pre {should only be called on diagonal processors (others will add non-loop nonzeros)} 152 * @pre {both the implementation and its semantics is meaningless for non-square matrices} 153 **/ 154 IT AddLoops(std::vector<NT> loopvals, bool replaceExisting=false) 155 { 156 // expectation n == loopvals.size()) 157 158 std::vector<bool> existing(n,false); // none of the diagonals exist 159 IT loop = 0; 160 for(IT i=0; i< nnz; ++i) 161 { 162 if(joker::get<0>(tuples[i]) == joker::get<1>(tuples[i])) 163 { 164 ++loop; 165 existing[joker::get<0>(tuples[i])] = true; 166 if(replaceExisting) 167 joker::get<2>(tuples[i]) = loopvals[joker::get<0>(tuples[i])]; 168 } 169 } 170 std::vector<IT> missingindices; 171 for(IT i = 0; i < n; ++i) 172 { 173 if(!existing[i]) missingindices.push_back(i); 174 } 175 IT toadd = n - loop; // number of new entries needed (equals missingindices.size()) 176 std::tuple<IT, IT, NT> * ntuples = new std::tuple<IT,IT,NT>[nnz+toadd]; 177 178 std::copy(tuples,tuples+nnz, ntuples); 179 180 for(IT i=0; i< toadd; ++i) 181 { 182 ntuples[nnz+i] = std::make_tuple(missingindices[i], missingindices[i], loopvals[missingindices[i]]); 183 } 184 if(isOperatorNew) 185 ::operator delete(tuples); 186 else 187 delete [] tuples; 188 tuples = ntuples; 189 isOperatorNew = false; 190 nnz = nnz+toadd; 191 return loop; 192 } 193 194 /** 195 * @pre {should only be called on diagonal processors (others will remove non-loop nonzeros)} 196 **/ RemoveLoops()197 IT RemoveLoops() 198 { 199 IT loop = 0; 200 for(IT i=0; i< nnz; ++i) 201 { 202 if(joker::get<0>(tuples[i]) == joker::get<1>(tuples[i])) ++loop; 203 } 204 std::tuple<IT, IT, NT> * ntuples = new std::tuple<IT,IT,NT>[nnz-loop]; 205 206 IT ni = 0; 207 for(IT i=0; i< nnz; ++i) 208 { 209 if(joker::get<0>(tuples[i]) != joker::get<1>(tuples[i])) 210 { 211 ntuples[ni++] = tuples[i]; 212 } 213 } 214 if(isOperatorNew) 215 ::operator delete(tuples); 216 else 217 delete [] tuples; 218 tuples = ntuples; 219 isOperatorNew = false; 220 nnz = nnz-loop; 221 return loop; 222 } 223 RowLimits()224 std::pair<IT,IT> RowLimits() 225 { 226 if(nnz > 0) 227 { 228 RowCompare<IT,NT> rowcmp; 229 std::tuple<IT,IT,NT> * maxit = std::max_element(tuples, tuples+nnz, rowcmp); 230 std::tuple<IT,IT,NT> * minit = std::min_element(tuples, tuples+nnz, rowcmp); 231 return std::make_pair(joker::get<0>(*minit), joker::get<0>(*maxit)); 232 } 233 else 234 return std::make_pair(0,0); 235 } ColLimits()236 std::pair<IT,IT> ColLimits() 237 { 238 if(nnz > 0) 239 { 240 ColCompare<IT,NT> colcmp; 241 std::tuple<IT,IT,NT> * maxit = std::max_element(tuples, tuples+nnz, colcmp); 242 std::tuple<IT,IT,NT> * minit = std::min_element(tuples, tuples+nnz, colcmp); 243 return std::make_pair(joker::get<1>(*minit), joker::get<1>(*maxit)); 244 } 245 else 246 return std::make_pair(0,0); 247 } front()248 std::tuple<IT, IT, NT> front() { return tuples[0]; }; back()249 std::tuple<IT, IT, NT> back() { return tuples[nnz-1]; }; 250 251 // Performs a balanced merge of the array of SpTuples 252 template<typename SR, typename IU, typename NU> 253 friend SpTuples<IU,NU> MergeAll(const std::vector<SpTuples<IU,NU> *> & ArrSpTups, IU mstar, IU nstar, bool delarrs); 254 255 template<typename SR, typename IU, typename NU> 256 friend SpTuples<IU,NU> * MergeAllRec(const std::vector<SpTuples<IU,NU> *> & ArrSpTups, IU mstar, IU nstar); 257 258 std::ofstream& putstream (std::ofstream& outfile) const; put(std::ofstream & outfile)259 std::ofstream& put (std::ofstream& outfile) const 260 { return putstream(outfile); } 261 262 std::ifstream& getstream (std::ifstream& infile); get(std::ifstream & infile)263 std::ifstream& get (std::ifstream& infile) { return getstream(infile); } 264 265 isZero()266 bool isZero() const { return (nnz == 0); } getnrow()267 IT getnrow() const { return m; } getncol()268 IT getncol() const { return n; } getnnz()269 int64_t getnnz() const { return nnz; } 270 271 void PrintInfo(); 272 std::tuple<IT, IT, NT> * tuples; 273 274 private: 275 276 IT m; 277 IT n; 278 int64_t nnz; 279 bool isOperatorNew; // if Operator New was used to allocate memory 280 SpTuples()281 SpTuples (){}; // Default constructor does nothing, hide it 282 283 void FillTuples (Dcsc<IT,NT> * mydcsc); 284 285 template <class IU, class NU> 286 friend class SpDCCols; 287 288 template <class IU, class NU> 289 friend class SpCCols; 290 }; 291 292 293 // At this point, complete type of of SpTuples is known, safe to declare these specialization (but macros won't work as they are preprocessed) 294 template <> struct promote_trait< SpTuples<int,int> , SpTuples<int,int> > 295 { 296 typedef SpTuples<int,int> T_promote; 297 }; 298 template <> struct promote_trait< SpTuples<int,float> , SpTuples<int,float> > 299 { 300 typedef SpTuples<int,float> T_promote; 301 }; 302 template <> struct promote_trait< SpTuples<int,double> , SpTuples<int,double> > 303 { 304 typedef SpTuples<int,double> T_promote; 305 }; 306 template <> struct promote_trait< SpTuples<int,bool> , SpTuples<int,int> > 307 { 308 typedef SpTuples<int,int> T_promote; 309 }; 310 template <> struct promote_trait< SpTuples<int,int> , SpTuples<int,bool> > 311 { 312 typedef SpTuples<int,int> T_promote; 313 }; 314 template <> struct promote_trait< SpTuples<int,int> , SpTuples<int,float> > 315 { 316 typedef SpTuples<int,float> T_promote; 317 }; 318 template <> struct promote_trait< SpTuples<int,float> , SpTuples<int,int> > 319 { 320 typedef SpTuples<int,float> T_promote; 321 }; 322 template <> struct promote_trait< SpTuples<int,int> , SpTuples<int,double> > 323 { 324 typedef SpTuples<int,double> T_promote; 325 }; 326 template <> struct promote_trait< SpTuples<int,double> , SpTuples<int,int> > 327 { 328 typedef SpTuples<int,double> T_promote; 329 }; 330 template <> struct promote_trait< SpTuples<int,unsigned> , SpTuples<int,bool> > 331 { 332 typedef SpTuples<int,unsigned> T_promote; 333 }; 334 template <> struct promote_trait< SpTuples<int,bool> , SpTuples<int,unsigned> > 335 { 336 typedef SpTuples<int,unsigned> T_promote; 337 }; 338 template <> struct promote_trait< SpTuples<int,bool> , SpTuples<int,double> > 339 { 340 typedef SpTuples<int,double> T_promote; 341 }; 342 template <> struct promote_trait< SpTuples<int,bool> , SpTuples<int,float> > 343 { 344 typedef SpTuples<int,float> T_promote; 345 }; 346 template <> struct promote_trait< SpTuples<int,double> , SpTuples<int,bool> > 347 { 348 typedef SpTuples<int,double> T_promote; 349 }; 350 template <> struct promote_trait< SpTuples<int,float> , SpTuples<int,bool> > 351 { 352 typedef SpTuples<int,float> T_promote; 353 }; 354 template <> struct promote_trait< SpTuples<int64_t,int> , SpTuples<int64_t,int> > 355 { 356 typedef SpTuples<int64_t,int> T_promote; 357 }; 358 template <> struct promote_trait< SpTuples<int64_t,float> , SpTuples<int64_t,float> > 359 { 360 typedef SpTuples<int64_t,float> T_promote; 361 }; 362 template <> struct promote_trait< SpTuples<int64_t,double> , SpTuples<int64_t,double> > 363 { 364 typedef SpTuples<int64_t,double> T_promote; 365 }; 366 template <> struct promote_trait< SpTuples<int64_t,int64_t> , SpTuples<int64_t,int64_t> > 367 { 368 typedef SpTuples<int64_t,int64_t> T_promote; 369 }; 370 template <> struct promote_trait< SpTuples<int64_t,bool> , SpTuples<int64_t,int> > 371 { 372 typedef SpTuples<int64_t,int> T_promote; 373 }; 374 template <> struct promote_trait< SpTuples<int64_t,int> , SpTuples<int64_t,bool> > 375 { 376 typedef SpTuples<int64_t,int> T_promote; 377 }; 378 template <> struct promote_trait< SpTuples<int64_t,int> , SpTuples<int64_t,float> > 379 { 380 typedef SpTuples<int64_t,float> T_promote; 381 }; 382 template <> struct promote_trait< SpTuples<int64_t,float> , SpTuples<int64_t,int> > 383 { 384 typedef SpTuples<int64_t,float> T_promote; 385 }; 386 template <> struct promote_trait< SpTuples<int64_t,int> , SpTuples<int64_t,double> > 387 { 388 typedef SpTuples<int64_t,double> T_promote; 389 }; 390 template <> struct promote_trait< SpTuples<int64_t,double> , SpTuples<int64_t,int> > 391 { 392 typedef SpTuples<int64_t,double> T_promote; 393 }; 394 template <> struct promote_trait< SpTuples<int64_t,unsigned> , SpTuples<int64_t,bool> > 395 { 396 typedef SpTuples<int64_t,unsigned> T_promote; 397 }; 398 template <> struct promote_trait< SpTuples<int64_t,bool> , SpTuples<int64_t,unsigned> > 399 { 400 typedef SpTuples<int64_t,unsigned> T_promote; 401 }; 402 template <> struct promote_trait< SpTuples<int64_t,bool> , SpTuples<int64_t,double> > 403 { 404 typedef SpTuples<int64_t,double> T_promote; 405 }; 406 template <> struct promote_trait< SpTuples<int64_t,bool> , SpTuples<int64_t,float> > 407 { 408 typedef SpTuples<int64_t,float> T_promote; 409 }; 410 template <> struct promote_trait< SpTuples<int64_t,double> , SpTuples<int64_t,bool> > 411 { 412 typedef SpTuples<int64_t,double> T_promote; 413 }; 414 template <> struct promote_trait< SpTuples<int64_t,float> , SpTuples<int64_t,bool> > 415 { 416 typedef SpTuples<int64_t,float> T_promote; 417 }; 418 } 419 420 #include "SpTuples.cpp" 421 422 #endif 423