Isorropia: Partitioning, Load Balancing and more
Isorropia_EpetraMatcher.hpp
Go to the documentation of this file.
00001 //@HEADER
00002 /*
00003 ************************************************************************
00004 
00005               Isorropia: Partitioning and Load Balancing Package
00006                 Copyright (2006,2011) Sandia Corporation
00007 
00008 Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
00009 license for use of this work by or on behalf of the U.S. Government.
00010 
00011 This library is free software; you can redistribute it and/or modify
00012 it under the terms of the GNU Lesser General Public License as
00013 published by the Free Software Foundation; either version 2.1 of the
00014 License, or (at your option) any later version.
00015 
00016 This library is distributed in the hope that it will be useful, but
00017 WITHOUT ANY WARRANTY; without even the implied warranty of
00018 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00019 Lesser General Public License for more details.
00020 
00021 You should have received a copy of the GNU Lesser General Public
00022 License along with this library; if not, write to the Free Software
00023 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
00024 USA
00025 
00026 ************************************************************************
00027 */
00028 //@HEADER
00029 
00030 #ifndef _Isorropia_EpetraMatcher_hpp_
00031 #define _Isorropia_EpetraMatcher_hpp_
00032 
00033 #include <Isorropia_Epetra.hpp>
00034 
00035 #include <Epetra_SerialComm.h>
00036 #include <Epetra_Map.h>
00037 #include <Epetra_CrsMatrix.h>
00038 #include <Epetra_Import.h>
00039 
00040 #ifdef ISORROPIA_HAVE_OMP
00041 #include <omp.h>
00042 #endif
00043 
00044 #include <Isorropia_ConfigDefs.hpp>
00045 #include <iostream>
00046 #include <fstream>
00047 #include <string>
00048 #include <vector>
00049 #include <algorithm>
00050 
00051 #ifdef MIN
00052 #undef MIN
00053 #endif
00054 
00055 #define MIN(a,b) ((a)<(b)?(a):(b))
00056 
00057 namespace Isorropia {
00058 namespace Epetra {
00059 
00070 class Matcher {
00071 private:
00072     int* mateU_;
00073     int* mateV_;
00074     int* Queue_;
00075     int* LV_;
00076     int* LU_;
00077     int* unmatchedU_;
00078     int *parent_;
00079     int *lookahead_;
00080     int *CRS_pointers_;
00081     int *CRS_indices_;
00082     double *CRS_vals_;
00083     bool finish_;
00084     int U_,V_,E_,avgDegU_,k_star_,icm_,BFSInd_,numThread_,Qst_,Qend_,matched_,choice_;
00085    const Epetra_CrsMatrix *A_;
00086 
00087 #ifdef ISORROPIA_HAVE_OMP
00088     omp_lock_t *scannedV_;
00089 #endif
00090 
00091     void delete_matched_v();
00092     void complete_nonperfect_permutation();
00093     int SGM();  
00094     int match_dfs();
00095     int match_hk();
00096     int construct_layered_graph();
00097     int find_set_del_M();
00098     int recursive_path_finder(int, int);
00099     int dfs_path_finder(int);
00100     int dfs_augment();
00101     int augment_matching(int);
00102     int DW_phase();
00103 
00104 public:
00113     Matcher(const Epetra_CrsMatrix*, const Teuchos::ParameterList&
00114     paramlist=Teuchos::ParameterList("EmptyParameterList"));
00115     
00124     Matcher(Teuchos::RCP<const Epetra_CrsMatrix>,const Teuchos::ParameterList&
00125     paramlist=Teuchos::ParameterList("EmptyParameterList"));
00126 
00135     Matcher(const Epetra_CrsGraph *,const Teuchos::ParameterList& paramlist=Teuchos::ParameterList("EmptyParameterList"));
00136     
00145     Matcher(Teuchos::RCP<const Epetra_CrsGraph>,const Teuchos::ParameterList& paramlist=Teuchos::ParameterList("EmptyParameterList"));
00146     
00150      virtual ~Matcher();
00151 
00160     void getMatchedColumnsForRowsCopy(int, int&, int* ) const;
00161 
00170     void getMatchedRowsForColumnsCopy(int, int&, int*) const;
00171 
00172     /* @ingroup matching_grp
00173     Returns the number of matched vertices from Maximum Cardinality
00174      Matching set
00175     */
00176     int getNumberOfMatchedVertices();
00177 
00182     Teuchos::RCP<Epetra_CrsMatrix> applyRowPermutation();
00183 
00188     Teuchos::RCP<Epetra_CrsMatrix> applyColumnPermutation();
00189 
00190     //Epetra_Map* getPermutedRowMap();
00191 
00192     /* @ingroup matching_grp
00193     Provides the row map which is actually the complete row permutation
00194     */
00195     //Epetra_Map* getPermutedColumnMap();
00196 
00205     int match();
00206 };
00207 }
00208 }
00209 #endif