Isorropia: Partitioning, Load Balancing and more
Public Member Functions | Private Member Functions | Private Attributes | List of all members
Isorropia::Epetra::Matcher Class Reference

An implementation of the Matcher interface that operates on Epetra matrices and Graphs. More...

#include <Isorropia_EpetraMatcher.hpp>

Public Member Functions

 Matcher (const Epetra_CrsMatrix *, const Teuchos::ParameterList &paramlist=Teuchos::ParameterList("EmptyParameterList"))
 Constructor.
 
 Matcher (Teuchos::RCP< const Epetra_CrsMatrix >, const Teuchos::ParameterList &paramlist=Teuchos::ParameterList("EmptyParameterList"))
 Constructor.
 
 Matcher (const Epetra_CrsGraph *, const Teuchos::ParameterList &paramlist=Teuchos::ParameterList("EmptyParameterList"))
 Constructor.
 
 Matcher (Teuchos::RCP< const Epetra_CrsGraph >, const Teuchos::ParameterList &paramlist=Teuchos::ParameterList("EmptyParameterList"))
 Constructor.
 
virtual ~Matcher ()
 Destructor.
 
void getMatchedColumnsForRowsCopy (int, int &, int *) const
 Copies the matched columns corresponding to each row in a user given array.
 
void getMatchedRowsForColumnsCopy (int, int &, int *) const
 Copies the matched rows corresponding to each column in a user given array.
 
int getNumberOfMatchedVertices ()
 
Teuchos::RCP< Epetra_CrsMatrix > applyRowPermutation ()
 Applies the row permutation from matching and returns a new matrix.
 
Teuchos::RCP< Epetra_CrsMatrix > applyColumnPermutation ()
 Applies the column permutation from matching and returns a new matrix.
 
int match ()
 Provides the column map which is actually the complete column permutation.
 

Private Member Functions

void delete_matched_v ()
 
void complete_nonperfect_permutation ()
 
int SGM ()
 
int match_dfs ()
 
int match_hk ()
 
int construct_layered_graph ()
 
int find_set_del_M ()
 
int recursive_path_finder (int, int)
 
int dfs_path_finder (int)
 
int dfs_augment ()
 
int augment_matching (int)
 
int DW_phase ()
 

Private Attributes

int * mateU_
 
int * mateV_
 
int * Queue_
 
int * LV_
 
int * LU_
 
int * unmatchedU_
 
int * parent_
 
int * lookahead_
 
int * CRS_pointers_
 
int * CRS_indices_
 
double * CRS_vals_
 
bool finish_
 
int U_
 
int V_
 
int E_
 
int avgDegU_
 
int k_star_
 
int icm_
 
int BFSInd_
 
int numThread_
 
int Qst_
 
int Qend_
 
int matched_
 
int choice_
 
const Epetra_CrsMatrix * A_
 

Detailed Description

An implementation of the Matcher interface that operates on Epetra matrices and Graphs.

One of the use of Maximum Cardinality Matching is that it provides nonzero diagonal for the sparse matrices. This multithreaded version of the matching algorithms provides an interface to solve the Bipartite Matching problem as well as it also provides permutation to get zero free diagonal for input sparse matrices.

Member Function Documentation

◆ delete_matched_v()

void Isorropia::Epetra::Matcher::delete_matched_v ( )
private

◆ complete_nonperfect_permutation()

void Isorropia::Epetra::Matcher::complete_nonperfect_permutation ( )
private

◆ SGM()

int Isorropia::Epetra::Matcher::SGM ( )
private

◆ match_dfs()

int Isorropia::Epetra::Matcher::match_dfs ( )
private

◆ match_hk()

int Isorropia::Epetra::Matcher::match_hk ( )
private

◆ construct_layered_graph()

int Isorropia::Epetra::Matcher::construct_layered_graph ( )
private

◆ find_set_del_M()

int Isorropia::Epetra::Matcher::find_set_del_M ( )
private

◆ recursive_path_finder()

int Isorropia::Epetra::Matcher::recursive_path_finder ( int  ,
int   
)
private

◆ dfs_path_finder()

int Isorropia::Epetra::Matcher::dfs_path_finder ( int  )
private

◆ dfs_augment()

int Isorropia::Epetra::Matcher::dfs_augment ( )
private

◆ augment_matching()

int Isorropia::Epetra::Matcher::augment_matching ( int  )
private

◆ DW_phase()

int Isorropia::Epetra::Matcher::DW_phase ( )
private

◆ getNumberOfMatchedVertices()

int Isorropia::Epetra::Matcher::getNumberOfMatchedVertices ( )

Member Data Documentation

◆ mateU_

int* Isorropia::Epetra::Matcher::mateU_
private

◆ mateV_

int* Isorropia::Epetra::Matcher::mateV_
private

◆ Queue_

int* Isorropia::Epetra::Matcher::Queue_
private

◆ LV_

int* Isorropia::Epetra::Matcher::LV_
private

◆ LU_

int* Isorropia::Epetra::Matcher::LU_
private

◆ unmatchedU_

int* Isorropia::Epetra::Matcher::unmatchedU_
private

◆ parent_

int* Isorropia::Epetra::Matcher::parent_
private

◆ lookahead_

int* Isorropia::Epetra::Matcher::lookahead_
private

◆ CRS_pointers_

int* Isorropia::Epetra::Matcher::CRS_pointers_
private

◆ CRS_indices_

int* Isorropia::Epetra::Matcher::CRS_indices_
private

◆ CRS_vals_

double* Isorropia::Epetra::Matcher::CRS_vals_
private

◆ finish_

bool Isorropia::Epetra::Matcher::finish_
private

◆ U_

int Isorropia::Epetra::Matcher::U_
private

◆ V_

int Isorropia::Epetra::Matcher::V_
private

◆ E_

int Isorropia::Epetra::Matcher::E_
private

◆ avgDegU_

int Isorropia::Epetra::Matcher::avgDegU_
private

◆ k_star_

int Isorropia::Epetra::Matcher::k_star_
private

◆ icm_

int Isorropia::Epetra::Matcher::icm_
private

◆ BFSInd_

int Isorropia::Epetra::Matcher::BFSInd_
private

◆ numThread_

int Isorropia::Epetra::Matcher::numThread_
private

◆ Qst_

int Isorropia::Epetra::Matcher::Qst_
private

◆ Qend_

int Isorropia::Epetra::Matcher::Qend_
private

◆ matched_

int Isorropia::Epetra::Matcher::matched_
private

◆ choice_

int Isorropia::Epetra::Matcher::choice_
private

◆ A_

const Epetra_CrsMatrix* Isorropia::Epetra::Matcher::A_
private

The documentation for this class was generated from the following file: