Isorropia: Partitioning, Load Balancing and more
Isorropia_EpetraMatcher.hpp
Go to the documentation of this file.
1 //@HEADER
2 //************************************************************************
3 //
4 // Isorropia: Partitioning and Load Balancing Package
5 // Copyright (2006) Sandia Corporation
6 //
7 //Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
8 //license for use of this work by or on behalf of the U.S. Government.
9 //
10 // Redistribution and use in source and binary forms, with or without
11 // modification, are permitted provided that the following conditions are
12 // met:
13 //
14 // 1. Redistributions of source code must retain the above copyright
15 // notice, this list of conditions and the following disclaimer.
16 //
17 // 2. Redistributions in binary form must reproduce the above copyright
18 // notice, this list of conditions and the following disclaimer in the
19 // documentation and/or other materials provided with the distribution.
20 //
21 // 3. Neither the name of the Corporation nor the names of the
22 // contributors may be used to endorse or promote products derived from
23 // this software without specific prior written permission.
24 //
25 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
26 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
29 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
30 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
31 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
32 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
33 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
34 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
35 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 //
37 //************************************************************************
38 //@HEADER
39 
40 #ifndef _Isorropia_EpetraMatcher_hpp_
41 #define _Isorropia_EpetraMatcher_hpp_
42 
43 #include <Isorropia_Epetra.hpp>
44 
45 #include <Epetra_SerialComm.h>
46 #include <Epetra_Map.h>
47 #include <Epetra_CrsMatrix.h>
48 #include <Epetra_Import.h>
49 
50 #ifdef ISORROPIA_HAVE_OMP
51 #include <omp.h>
52 #endif
53 
54 #include <Isorropia_ConfigDefs.hpp>
55 #include <iostream>
56 #include <fstream>
57 #include <string>
58 #include <vector>
59 #include <algorithm>
60 
61 #ifdef MIN
62 #undef MIN
63 #endif
64 
65 #define MIN(a,b) ((a)<(b)?(a):(b))
66 
67 namespace Isorropia {
68 namespace Epetra {
69 
80 class Matcher {
81 private:
82  int* mateU_;
83  int* mateV_;
84  int* Queue_;
85  int* LV_;
86  int* LU_;
88  int *parent_;
89  int *lookahead_;
92  double *CRS_vals_;
93  bool finish_;
95  const Epetra_CrsMatrix *A_;
96 
97 #ifdef ISORROPIA_HAVE_OMP
98  omp_lock_t *scannedV_;
99 #endif
100 
101  void delete_matched_v();
103  int SGM();
104  int match_dfs();
105  int match_hk();
107  int find_set_del_M();
108  int recursive_path_finder(int, int);
109  int dfs_path_finder(int);
110  int dfs_augment();
111  int augment_matching(int);
112  int DW_phase();
113 
114 public:
123  Matcher(const Epetra_CrsMatrix*, const Teuchos::ParameterList&
124  paramlist=Teuchos::ParameterList("EmptyParameterList"));
125 
134  Matcher(Teuchos::RCP<const Epetra_CrsMatrix>,const Teuchos::ParameterList&
135  paramlist=Teuchos::ParameterList("EmptyParameterList"));
136 
145  Matcher(const Epetra_CrsGraph *,const Teuchos::ParameterList& paramlist=Teuchos::ParameterList("EmptyParameterList"));
146 
155  Matcher(Teuchos::RCP<const Epetra_CrsGraph>,const Teuchos::ParameterList& paramlist=Teuchos::ParameterList("EmptyParameterList"));
156 
160  virtual ~Matcher();
161 
170  void getMatchedColumnsForRowsCopy(int, int&, int* ) const;
171 
180  void getMatchedRowsForColumnsCopy(int, int&, int*) const;
181 
182  /* @ingroup matching_grp
183  Returns the number of matched vertices from Maximum Cardinality
184  Matching set
185  */
187 
192  Teuchos::RCP<Epetra_CrsMatrix> applyRowPermutation();
193 
198  Teuchos::RCP<Epetra_CrsMatrix> applyColumnPermutation();
199 
200  //Epetra_Map* getPermutedRowMap();
201 
202  /* @ingroup matching_grp
203  Provides the row map which is actually the complete row permutation
204  */
205  //Epetra_Map* getPermutedColumnMap();
206 
215  int match();
216 };
217 }
218 }
219 #endif
220 
221 #if defined(Isorropia_SHOW_DEPRECATED_WARNINGS)
222 #ifdef __GNUC__
223 #warning "The Isorropia package is deprecated"
224 #endif
225 #endif
226 
const Epetra_CrsMatrix * A_
Definition: Isorropia_EpetraMatcher.hpp:95
int * LV_
Definition: Isorropia_EpetraMatcher.hpp:85
int icm_
Definition: Isorropia_EpetraMatcher.hpp:94
int * lookahead_
Definition: Isorropia_EpetraMatcher.hpp:89
int * mateV_
Definition: Isorropia_EpetraMatcher.hpp:83
int recursive_path_finder(int, int)
int * Queue_
Definition: Isorropia_EpetraMatcher.hpp:84
int U_
Definition: Isorropia_EpetraMatcher.hpp:94
int * parent_
Definition: Isorropia_EpetraMatcher.hpp:88
bool finish_
Definition: Isorropia_EpetraMatcher.hpp:93
Teuchos::RCP< Epetra_CrsMatrix > applyColumnPermutation()
Applies the column permutation from matching and returns a new matrix.
virtual ~Matcher()
Destructor.
int * LU_
Definition: Isorropia_EpetraMatcher.hpp:86
int V_
Definition: Isorropia_EpetraMatcher.hpp:94
void getMatchedColumnsForRowsCopy(int, int &, int *) const
Copies the matched columns corresponding to each row in a user given array.
Teuchos::RCP< Epetra_CrsMatrix > applyRowPermutation()
Applies the row permutation from matching and returns a new matrix.
int Qend_
Definition: Isorropia_EpetraMatcher.hpp:94
int Qst_
Definition: Isorropia_EpetraMatcher.hpp:94
int choice_
Definition: Isorropia_EpetraMatcher.hpp:94
void getMatchedRowsForColumnsCopy(int, int &, int *) const
Copies the matched rows corresponding to each column in a user given array.
int * unmatchedU_
Definition: Isorropia_EpetraMatcher.hpp:87
int avgDegU_
Definition: Isorropia_EpetraMatcher.hpp:94
int match()
Provides the column map which is actually the complete column permutation.
Matcher(const Epetra_CrsMatrix *, const Teuchos::ParameterList &paramlist=Teuchos::ParameterList("EmptyParameterList"))
Constructor.
An implementation of the Matcher interface that operates on Epetra matrices and Graphs.
Definition: Isorropia_EpetraMatcher.hpp:80
int E_
Definition: Isorropia_EpetraMatcher.hpp:94
int * CRS_indices_
Definition: Isorropia_EpetraMatcher.hpp:91
int k_star_
Definition: Isorropia_EpetraMatcher.hpp:94
double * CRS_vals_
Definition: Isorropia_EpetraMatcher.hpp:92
int matched_
Definition: Isorropia_EpetraMatcher.hpp:94
int * mateU_
Definition: Isorropia_EpetraMatcher.hpp:82
int BFSInd_
Definition: Isorropia_EpetraMatcher.hpp:94
int * CRS_pointers_
Definition: Isorropia_EpetraMatcher.hpp:90
int numThread_
Definition: Isorropia_EpetraMatcher.hpp:94