Isorropia: Partitioning, Load Balancing and more
ispatest_lbeval_utils.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 _ispatest_lbeval_utils_hpp_
00041 #define _ispatest_lbeval_utils_hpp_
00042 
00043 #include <Isorropia_ConfigDefs.hpp>
00044 #include <vector>
00045 
00046 #ifdef HAVE_EPETRA
00047 
00048 #include <Epetra_CrsGraph.h>
00049 #include <Epetra_CrsMatrix.h>
00050 #include <Epetra_Vector.h>
00051 #include <Epetra_LinearProblem.h>
00052 #include <Isorropia_EpetraCostDescriber.hpp>
00053 
00054 /*  Load balance evaluation (As calculated in Zoltan_LB_Eval)
00055 
00056   Given an Epetra graph and possible vertex and hyperedge weights,
00057   calculate the hypergraph balance, cutn and cutl.  We think of
00058   the rows of the graph as the objects (vertices) to be partitioned
00059   and the columns of the graph as the hyperedges.
00060 
00061   ====================================
00062 
00063   Definition of hypergraph balance:
00064 
00065   Suppose Size_p is target size of partition p.  (Sum of all Size_p is 1.0)
00066   (For now Size_p is always 1/p in isorropia - we don't have an interface
00067   to set different desired partition sizes.)
00068 
00069   Let W_p be the total row weight on process p and WT be the sum of the
00070   row weights on all processes.  Then
00071 
00072   imbalance on process p =   |W_p - Size_p*WT| / Size_p*WT
00073 
00074   balance = (1 + maximum imbalance over all processes p)
00075 
00076   ====================================
00077 
00078   Definition of hypergraph cutn and cutl:
00079 
00080   Suppose Cut_k is the number of cuts in column k.  (So column k is in 
00081   Cut_k + 1 different partitions.)  Suppose W_k is the weight of column k.
00082 
00083   cutn = Sum over all k of W_K * ((Cut_k > 0) ? 1 : 0)
00084 
00085   cutl = Sum over all k of Cut_k * W_k
00086 
00087   ====================================
00088 
00089   TODO explain metrics computed in compute_graph_metrics
00090 */
00091 namespace ispatest {
00092 
00098 int compute_balance(const Epetra_Vector &wgts, double myGoalWeight,
00099                               double &min, double &max, double &avg);
00100 
00106 int compute_hypergraph_metrics(const Epetra_CrsGraph &graph,
00107             Isorropia::Epetra::CostDescriber &costs,
00108             double &myGoalWeight,
00109             double &balance, double &cutn, double &cutl);
00110 
00116 int compute_hypergraph_metrics(const Epetra_RowMatrix &matrix,
00117             Isorropia::Epetra::CostDescriber &costs,
00118             double &myGoalWeight,
00119             double &balance, double &cutn, double &cutl);
00120 
00136 int compute_graph_metrics(const Epetra_RowMatrix &matrix,
00137             Isorropia::Epetra::CostDescriber &costs,
00138             double &myGoalWeight,
00139             double &balance, int &numCuts, double &cutWgt, double &cutn, double &cutl);
00140 
00156 int compute_graph_metrics(const Epetra_CrsGraph &graph,
00157             Isorropia::Epetra::CostDescriber &costs,
00158             double &myGoalWeight,
00159             double &balance, int &numCuts, double &cutWgt, double &cutn, double &cutl);
00160 
00165 void show_matrix(const char *txt, const Epetra_RowMatrix &matrix, const Epetra_Comm &comm);
00166 
00171 void show_matrix(const char *txt, const Epetra_CrsGraph &graph, const Epetra_Comm &comm);
00172 
00177 void show_matrix(const char *txt, const Epetra_LinearProblem &problem, const Epetra_Comm &comm);
00178 
00179 
00180 
00181 }//namespace ispatest
00182 
00183 #endif //HAVE_EPTERA
00184 
00185 #endif
00186