Isorropia: Partitioning, Load Balancing and more
ispatest_lbeval_utils.hpp
Go to the documentation of this file.
00001 //@HEADER
00002 /*
00003 ************************************************************************
00004 
00005               Isorropia: Partitioning and Load Balancing Package
00006                 Copyright (2006) 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 _ispatest_lbeval_utils_hpp_
00031 #define _ispatest_lbeval_utils_hpp_
00032 
00033 #include <Isorropia_ConfigDefs.hpp>
00034 #include <vector>
00035 
00036 #ifdef HAVE_EPETRA
00037 
00038 #include <Epetra_CrsGraph.h>
00039 #include <Epetra_CrsMatrix.h>
00040 #include <Epetra_Vector.h>
00041 #include <Epetra_LinearProblem.h>
00042 #include <Isorropia_EpetraCostDescriber.hpp>
00043 
00044 /*  Load balance evaluation (As calculated in Zoltan_LB_Eval)
00045 
00046   Given an Epetra graph and possible vertex and hyperedge weights,
00047   calculate the hypergraph balance, cutn and cutl.  We think of
00048   the rows of the graph as the objects (vertices) to be partitioned
00049   and the columns of the graph as the hyperedges.
00050 
00051   ====================================
00052 
00053   Definition of hypergraph balance:
00054 
00055   Suppose Size_p is target size of partition p.  (Sum of all Size_p is 1.0)
00056   (For now Size_p is always 1/p in isorropia - we don't have an interface
00057   to set different desired partition sizes.)
00058 
00059   Let W_p be the total row weight on process p and WT be the sum of the
00060   row weights on all processes.  Then
00061 
00062   imbalance on process p =   |W_p - Size_p*WT| / Size_p*WT
00063 
00064   balance = (1 + maximum imbalance over all processes p)
00065 
00066   ====================================
00067 
00068   Definition of hypergraph cutn and cutl:
00069 
00070   Suppose Cut_k is the number of cuts in column k.  (So column k is in 
00071   Cut_k + 1 different partitions.)  Suppose W_k is the weight of column k.
00072 
00073   cutn = Sum over all k of W_K * ((Cut_k > 0) ? 1 : 0)
00074 
00075   cutl = Sum over all k of Cut_k * W_k
00076 
00077   ====================================
00078 
00079   TODO explain metrics computed in compute_graph_metrics
00080 */
00081 namespace ispatest {
00082 
00088 int compute_balance(const Epetra_Vector &wgts, double myGoalWeight,
00089                               double &min, double &max, double &avg);
00090 
00096 int compute_hypergraph_metrics(const Epetra_CrsGraph &graph,
00097             Isorropia::Epetra::CostDescriber &costs,
00098             double &myGoalWeight,
00099             double &balance, double &cutn, double &cutl);
00100 
00106 int compute_hypergraph_metrics(const Epetra_RowMatrix &matrix,
00107             Isorropia::Epetra::CostDescriber &costs,
00108             double &myGoalWeight,
00109             double &balance, double &cutn, double &cutl);
00110 
00126 int compute_graph_metrics(const Epetra_RowMatrix &matrix,
00127             Isorropia::Epetra::CostDescriber &costs,
00128             double &myGoalWeight,
00129             double &balance, int &numCuts, double &cutWgt, double &cutn, double &cutl);
00130 
00146 int compute_graph_metrics(const Epetra_CrsGraph &graph,
00147             Isorropia::Epetra::CostDescriber &costs,
00148             double &myGoalWeight,
00149             double &balance, int &numCuts, double &cutWgt, double &cutn, double &cutl);
00150 
00155 void show_matrix(const char *txt, const Epetra_RowMatrix &matrix, const Epetra_Comm &comm);
00156 
00161 void show_matrix(const char *txt, const Epetra_CrsGraph &graph, const Epetra_Comm &comm);
00162 
00167 void show_matrix(const char *txt, const Epetra_LinearProblem &problem, const Epetra_Comm &comm);
00168 
00169 
00170 
00171 }//namespace ispatest
00172 
00173 #endif //HAVE_EPTERA
00174 
00175 #endif
00176