Isorropia: Partitioning, Load Balancing and more
Isorropia_EpetraMatcher.hpp
Go to the documentation of this file.
00001 //@HEADER
00002 //************************************************************************
00003 //
00004 //              Isorropia: Partitioning and Load Balancing Package
00005 //                Copyright (2006) Sandia Corporation
00006 //
00007 //Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
00008 //license for use of this work by or on behalf of the U.S. Government.
00009 //
00010 // Redistribution and use in source and binary forms, with or without
00011 // modification, are permitted provided that the following conditions are
00012 // met:
00013 //
00014 // 1. Redistributions of source code must retain the above copyright
00015 // notice, this list of conditions and the following disclaimer.
00016 //
00017 // 2. Redistributions in binary form must reproduce the above copyright
00018 // notice, this list of conditions and the following disclaimer in the
00019 // documentation and/or other materials provided with the distribution.
00020 //
00021 // 3. Neither the name of the Corporation nor the names of the
00022 // contributors may be used to endorse or promote products derived from
00023 // this software without specific prior written permission.
00024 //
00025 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
00026 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00027 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00028 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
00029 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00030 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00031 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00032 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00033 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00034 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00035 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00036 //
00037 //************************************************************************
00038 //@HEADER
00039 
00040 #ifndef _Isorropia_EpetraMatcher_hpp_
00041 #define _Isorropia_EpetraMatcher_hpp_
00042 
00043 #include <Isorropia_Epetra.hpp>
00044 
00045 #include <Epetra_SerialComm.h>
00046 #include <Epetra_Map.h>
00047 #include <Epetra_CrsMatrix.h>
00048 #include <Epetra_Import.h>
00049 
00050 #ifdef ISORROPIA_HAVE_OMP
00051 #include <omp.h>
00052 #endif
00053 
00054 #include <Isorropia_ConfigDefs.hpp>
00055 #include <iostream>
00056 #include <fstream>
00057 #include <string>
00058 #include <vector>
00059 #include <algorithm>
00060 
00061 #ifdef MIN
00062 #undef MIN
00063 #endif
00064 
00065 #define MIN(a,b) ((a)<(b)?(a):(b))
00066 
00067 namespace Isorropia {
00068 namespace Epetra {
00069 
00080 class Matcher {
00081 private:
00082     int* mateU_;
00083     int* mateV_;
00084     int* Queue_;
00085     int* LV_;
00086     int* LU_;
00087     int* unmatchedU_;
00088     int *parent_;
00089     int *lookahead_;
00090     int *CRS_pointers_;
00091     int *CRS_indices_;
00092     double *CRS_vals_;
00093     bool finish_;
00094     int U_,V_,E_,avgDegU_,k_star_,icm_,BFSInd_,numThread_,Qst_,Qend_,matched_,choice_;
00095    const Epetra_CrsMatrix *A_;
00096 
00097 #ifdef ISORROPIA_HAVE_OMP
00098     omp_lock_t *scannedV_;
00099 #endif
00100 
00101     void delete_matched_v();
00102     void complete_nonperfect_permutation();
00103     int SGM();  
00104     int match_dfs();
00105     int match_hk();
00106     int construct_layered_graph();
00107     int find_set_del_M();
00108     int recursive_path_finder(int, int);
00109     int dfs_path_finder(int);
00110     int dfs_augment();
00111     int augment_matching(int);
00112     int DW_phase();
00113 
00114 public:
00123     Matcher(const Epetra_CrsMatrix*, const Teuchos::ParameterList&
00124     paramlist=Teuchos::ParameterList("EmptyParameterList"));
00125     
00134     Matcher(Teuchos::RCP<const Epetra_CrsMatrix>,const Teuchos::ParameterList&
00135     paramlist=Teuchos::ParameterList("EmptyParameterList"));
00136 
00145     Matcher(const Epetra_CrsGraph *,const Teuchos::ParameterList& paramlist=Teuchos::ParameterList("EmptyParameterList"));
00146     
00155     Matcher(Teuchos::RCP<const Epetra_CrsGraph>,const Teuchos::ParameterList& paramlist=Teuchos::ParameterList("EmptyParameterList"));
00156     
00160      virtual ~Matcher();
00161 
00170     void getMatchedColumnsForRowsCopy(int, int&, int* ) const;
00171 
00180     void getMatchedRowsForColumnsCopy(int, int&, int*) const;
00181 
00182     /* @ingroup matching_grp
00183     Returns the number of matched vertices from Maximum Cardinality
00184      Matching set
00185     */
00186     int getNumberOfMatchedVertices();
00187 
00192     Teuchos::RCP<Epetra_CrsMatrix> applyRowPermutation();
00193 
00198     Teuchos::RCP<Epetra_CrsMatrix> applyColumnPermutation();
00199 
00200     //Epetra_Map* getPermutedRowMap();
00201 
00202     /* @ingroup matching_grp
00203     Provides the row map which is actually the complete row permutation
00204     */
00205     //Epetra_Map* getPermutedColumnMap();
00206 
00215     int match();
00216 };
00217 }
00218 }
00219 #endif