50 #ifndef _ZOLTAN2_PARTITIONINGPROBLEM_HPP_ 51 #define _ZOLTAN2_PARTITIONINGPROBLEM_HPP_ 71 #ifdef HAVE_ZOLTAN2_OVIS 100 template<
typename Adapter>
106 typedef typename Adapter::gno_t
gno_t;
107 typedef typename Adapter::lno_t
lno_t;
112 #ifdef HAVE_ZOLTAN2_MPI 113 typedef Teuchos::OpaqueWrapper<MPI_Comm> mpiWrapper_t;
117 Problem<Adapter>(A,p,comm), solution_(),
118 problemComm_(), problemCommConst_(),
120 graphFlags_(), idFlags_(), coordFlags_(), algName_(),
121 numberOfWeights_(), partIds_(), partSizes_(),
122 numberOfCriteria_(), levelNumberParts_(), hierarchical_(false),
123 metricsRequested_(false), metrics_(), graphMetrics_()
132 Problem<Adapter>(A,p), solution_(),
133 problemComm_(), problemCommConst_(),
135 graphFlags_(), idFlags_(), coordFlags_(), algName_(),
137 partIds_(), partSizes_(), numberOfCriteria_(),
138 levelNumberParts_(), hierarchical_(false),
139 metricsRequested_(false), metrics_(), graphMetrics_()
147 RCP<
const Teuchos::Comm<int> > &comm):
148 Problem<Adapter>(A,p,comm), solution_(),
149 problemComm_(), problemCommConst_(),
151 graphFlags_(), idFlags_(), coordFlags_(), algName_(),
153 partIds_(), partSizes_(), numberOfCriteria_(),
154 levelNumberParts_(), hierarchical_(false),
155 metricsRequested_(false), metrics_(), graphMetrics_()
182 void solve(
bool updateInputData=
true );
189 return *(solution_.getRawPtr());
202 if (!metrics_.is_null())
203 metrics_->getWeightImbalance(imb, idx);
213 if (metrics_.is_null()){
214 ArrayRCP<const MetricValues<scalar_t> > emptyMetrics;
218 return metrics_->getMetrics();
226 if (graphMetrics_.is_null()){
227 ArrayRCP<const GraphMetricValues<scalar_t> > emptyMetrics;
231 return graphMetrics_->getGraphMetrics();
240 if (metrics_.is_null())
241 os <<
"No metrics available." << std::endl;
243 metrics_->printMetrics(os);
252 if (graphMetrics_.is_null())
253 os <<
"No metrics available." << std::endl;
255 graphMetrics_->printGraphMetrics(os);
337 scalar_t *partSizes,
bool makeCopy=
true) ;
358 void initializeProblem();
360 void createPartitioningProblem(
bool newData);
362 RCP<PartitioningSolution<Adapter> > solution_;
364 RCP<MachineRepresentation <typename Adapter::base_adapter_t::scalar_t> > machine_;
366 RCP<Comm<int> > problemComm_;
367 RCP<const Comm<int> > problemCommConst_;
377 std::string algName_;
379 int numberOfWeights_;
390 ArrayRCP<ArrayRCP<part_t> > partIds_;
391 ArrayRCP<ArrayRCP<scalar_t> > partSizes_;
392 int numberOfCriteria_;
396 ArrayRCP<int> levelNumberParts_;
401 bool metricsRequested_;
402 RCP<const EvaluatePartition<Adapter> > metrics_;
403 RCP<const EvaluatePartition<Adapter> > graphMetrics_;
415 template <
typename Adapter>
422 if (getenv(
"DEBUGME")){
424 std::cout << getpid() << std::endl;
427 std::cout << _getpid() << std::endl;
432 #ifdef HAVE_ZOLTAN2_OVIS 433 ovis_enabled(this->
comm_->getRank());
438 problemComm_ = this->
comm_->duplicate();
439 problemCommConst_ = rcp_const_cast<
const Comm<int> > (problemComm_);
446 numberOfWeights_ = this->
inputAdapter_->getNumWeightsPerID();
448 numberOfCriteria_ = (numberOfWeights_ > 1) ? numberOfWeights_ : 1;
455 ArrayRCP<part_t> *noIds =
new ArrayRCP<part_t> [numberOfCriteria_];
456 ArrayRCP<scalar_t> *noSizes =
new ArrayRCP<scalar_t> [numberOfCriteria_];
458 partIds_ = arcp(noIds, 0, numberOfCriteria_,
true);
459 partSizes_ = arcp(noSizes, 0, numberOfCriteria_,
true);
462 std::ostringstream msg;
463 msg << problemComm_->getSize() <<
" procs," 464 << numberOfWeights_ <<
" user-defined weights\n";
468 this->
env_->memory(
"After initializeProblem");
471 template <
typename Adapter>
473 int criteria,
int len,
part_t *partIds,
scalar_t *partSizes,
bool makeCopy)
475 this->
env_->localInputAssertion(__FILE__, __LINE__,
"invalid length",
478 this->
env_->localInputAssertion(__FILE__, __LINE__,
"invalid criteria",
482 partIds_[criteria] = ArrayRCP<part_t>();
483 partSizes_[criteria] = ArrayRCP<scalar_t>();
487 this->
env_->localInputAssertion(__FILE__, __LINE__,
"invalid arrays",
494 part_t *z2_partIds = NULL;
496 bool own_memory =
false;
499 z2_partIds =
new part_t [len];
501 this->
env_->localMemoryAssertion(__FILE__, __LINE__, len, z2_partSizes);
502 memcpy(z2_partIds, partIds, len *
sizeof(
part_t));
503 memcpy(z2_partSizes, partSizes, len *
sizeof(
scalar_t));
507 z2_partIds = partIds;
508 z2_partSizes = partSizes;
511 partIds_[criteria] = arcp(z2_partIds, 0, len, own_memory);
512 partSizes_[criteria] = arcp(z2_partSizes, 0, len, own_memory);
515 template <
typename Adapter>
524 createPartitioningProblem(updateInputData);
536 if (algName_ == std::string(
"multijagged")) {
541 else if (algName_ == std::string(
"zoltan")) {
546 else if (algName_ == std::string(
"parma")) {
551 else if (algName_ == std::string(
"scotch")) {
556 else if (algName_ == std::string(
"parmetis")) {
561 else if (algName_ == std::string(
"pulp")) {
566 else if (algName_ == std::string(
"block")) {
570 else if (algName_ == std::string(
"forTestingOnly")) {
580 throw std::logic_error(
"partitioning algorithm not supported");
591 this->
envConst_, problemCommConst_, numberOfWeights_,
592 partIds_.view(0, numberOfCriteria_),
593 partSizes_.view(0, numberOfCriteria_), this->
algorithm_);
597 solution_ = rcp(soln);
600 this->
env_->memory(
"After creating Solution");
610 const Teuchos::ParameterEntry *pe = this->
envConst_->getParameters().getEntryPtr(
"mapping_type");
611 int mapping_type = -1;
613 mapping_type = pe->getValue(&mapping_type);
617 if (mapping_type == 0){
623 problemComm_.getRawPtr(),
624 machine_.getRawPtr(),
626 solution_.getRawPtr(),
634 else if (mapping_type == 1){
638 if (metricsRequested_){
643 psq_t *quality = NULL;
644 RCP<const ps_t> solutionConst = rcp_const_cast<
const ps_t>(solution_);
651 quality =
new psq_t(this->
envConst_, problemCommConst_,
654 Z2_FORWARD_EXCEPTIONS
656 psq_t *graphQuality = NULL;
659 graphQuality =
new psq_t(this->
envConst_, problemCommConst_,
663 Z2_FORWARD_EXCEPTIONS
665 graphMetrics_ = rcp(graphQuality);
669 quality =
new psq_t(this->
envConst_, problemCommConst_,
672 Z2_FORWARD_EXCEPTIONS
675 metrics_ = rcp(quality);
681 template <
typename Adapter>
685 "PartitioningProblem::createPartitioningProblem");
687 using Teuchos::ParameterList;
698 prevModelAvail[i] = modelAvail_[i];
703 modelFlag_t previousIdentifierModelFlags = idFlags_;
704 modelFlag_t previousCoordinateModelFlags = coordFlags_;
709 modelAvail_[i] =
false;
739 std::string defString(
"default");
744 const Teuchos::ParameterEntry *pe = pl.getEntryPtr(
"compute_metrics");
746 yesNo = pe->getValue<
int>(&yesNo);
747 metricsRequested_ =
true;
752 std::string model(defString);
753 pe = pl.getEntryPtr(
"model");
755 model = pe->getValue<std::string>(&model);
759 std::string algorithm(defString);
760 pe = pl.getEntryPtr(
"algorithm");
762 algorithm = pe->getValue<std::string>(&algorithm);
766 bool needConsecutiveGlobalIds =
false;
767 bool removeSelfEdges=
false;
773 if (algorithm != defString)
777 if (algorithm == std::string(
"block") ||
778 algorithm == std::string(
"random") ||
779 algorithm == std::string(
"cyclic") ){
784 algName_ = algorithm;
786 else if (algorithm == std::string(
"zoltan") ||
787 algorithm == std::string(
"parma") ||
788 algorithm == std::string(
"forTestingOnly"))
790 algName_ = algorithm;
792 else if (algorithm == std::string(
"rcb") ||
793 algorithm == std::string(
"rib") ||
794 algorithm == std::string(
"hsfc"))
797 Teuchos::ParameterList &zparams = pl.sublist(
"zoltan_parameters",
false);
798 zparams.set(
"LB_METHOD", algorithm);
799 if (numberOfWeights_ > 0) {
801 sprintf(strval,
"%d", numberOfWeights_);
802 zparams.set(
"OBJ_WEIGHT_DIM", strval);
804 algName_ = std::string(
"zoltan");
806 else if (algorithm == std::string(
"multijagged"))
811 algName_ = algorithm;
813 else if (algorithm == std::string(
"metis") ||
814 algorithm == std::string(
"parmetis") ||
815 algorithm == std::string(
"scotch") ||
816 algorithm == std::string(
"ptscotch"))
822 algName_ = algorithm;
823 removeSelfEdges =
true;
824 needConsecutiveGlobalIds =
true;
826 else if (algorithm == std::string(
"pulp"))
828 algName_ = algorithm;
830 else if (algorithm == std::string(
"patoh") ||
831 algorithm == std::string(
"phg"))
841 algName_ = algorithm;
843 #ifdef INCLUDE_ZOLTAN2_EXPERIMENTAL_WOLF 844 else if (algorithm == std::string(
"nd"))
848 algName_ = algorithm;
854 throw std::logic_error(
"parameter list algorithm is invalid");
857 else if (model != defString)
860 if (model == std::string(
"hypergraph"))
865 if (problemComm_->getSize() > 1)
866 algName_ = std::string(
"phg");
868 algName_ = std::string(
"patoh");
870 else if (model == std::string(
"graph"))
875 #ifdef HAVE_ZOLTAN2_SCOTCH 876 if (problemComm_->getSize() > 1)
877 algName_ = std::string(
"ptscotch");
879 algName_ = std::string(
"scotch");
880 removeSelfEdges =
true;
881 needConsecutiveGlobalIds =
true;
883 #ifdef HAVE_ZOLTAN2_PARMETIS 884 if (problemComm_->getSize() > 1)
885 algName_ = std::string(
"parmetis");
887 algName_ = std::string(
"metis");
888 removeSelfEdges =
true;
889 needConsecutiveGlobalIds =
true;
891 #ifdef HAVE_ZOLTAN2_PULP 896 algName_ = std::string(
"pulp");
898 if (problemComm_->getSize() > 1)
899 algName_ = std::string(
"phg");
901 algName_ = std::string(
"patoh");
906 else if (model == std::string(
"geometry"))
911 algName_ = std::string(
"multijagged");
913 else if (model == std::string(
"ids"))
918 algName_ = std::string(
"block");
938 if (problemComm_->getSize() > 1)
939 algName_ = std::string(
"phg");
941 algName_ = std::string(
"patoh");
949 if (problemComm_->getSize() > 1)
950 algName_ = std::string(
"phg");
952 algName_ = std::string(
"patoh");
959 algName_ = std::string(
"multijagged");
966 algName_ = std::string(
"block");
970 throw std::logic_error(
"input type is invalid");
976 Array<int> valueList;
977 pe = pl.getEntryPtr(
"topology");
980 valueList = pe->getValue<Array<int> >(&valueList);
982 if (!Zoltan2::noValuesAreInRangeList<int>(valueList)){
983 int *n =
new int [valueList.size() + 1];
984 levelNumberParts_ = arcp(n, 0, valueList.size() + 1,
true);
985 int procsPerNode = 1;
986 for (
int i=0; i < valueList.size(); i++){
987 levelNumberParts_[i+1] = valueList[i];
988 procsPerNode *= valueList[i];
991 levelNumberParts_[0] = env.
numProcs_ / procsPerNode;
994 levelNumberParts_[0]++;
998 levelNumberParts_.clear();
1001 hierarchical_ = levelNumberParts_.size() > 0;
1005 std::string objectOfInterest(defString);
1006 pe = pl.getEntryPtr(
"objects_to_partition");
1008 objectOfInterest = pe->getValue<std::string>(&objectOfInterest);
1020 std::string symParameter(defString);
1021 pe = pl.getEntryPtr(
"symmetrize_graph");
1023 symParameter = pe->getValue<std::string>(&symParameter);
1024 if (symParameter == std::string(
"transpose"))
1026 else if (symParameter == std::string(
"bipartite"))
1030 int sgParameter = 0;
1031 pe = pl.getEntryPtr(
"subset_graph");
1033 sgParameter = pe->getValue<
int>(&sgParameter);
1035 if (sgParameter == 1)
1040 if (removeSelfEdges)
1043 if (needConsecutiveGlobalIds)
1049 if (objectOfInterest == defString ||
1050 objectOfInterest == std::string(
"matrix_rows") )
1052 else if (objectOfInterest == std::string(
"matrix_columns"))
1054 else if (objectOfInterest == std::string(
"matrix_nonzeros"))
1059 if (objectOfInterest == defString ||
1060 objectOfInterest == std::string(
"mesh_nodes") )
1062 else if (objectOfInterest == std::string(
"mesh_elements"))
1089 (graphFlags_ != previousGraphModelFlags) ||
1090 (coordFlags_ != previousCoordinateModelFlags) ||
1091 (idFlags_ != previousIdentifierModelFlags))
1103 if(modelAvail_[GraphModelType]==
true)
1114 if(modelAvail_[HypergraphModelType]==
true)
1116 std::cout <<
"Hypergraph model not implemented yet..." << std::endl;
1119 if(modelAvail_[CoordinateModelType]==
true)
1130 if(modelAvail_[IdentifierModelType]==
true)
1141 this->
env_->memory(
"After creating Model");
use columns as graph vertices
RCP< GraphModel< base_adapter_t > > graphModel_
~PartitioningProblem()
Destructor.
ArrayRCP< const MetricValues< scalar_t > > getMetrics() const
Get the array of metrics Metrics were only computed if user requested metrics with a parameter...
const scalar_t getWeightImbalance(int idx=0) const
Returns the imbalance of the solution.
Time an algorithm (or other entity) as a whole.
RCP< const base_adapter_t > baseInputAdapter_
Adapter::scalar_t scalar_t
void setPartSizes(int len, part_t *partIds, scalar_t *partSizes, bool makeCopy=true)
Set or reset relative sizes for the parts that Zoltan2 will create.
use mesh nodes as vertices
fast typical checks for valid arguments
#define Z2_FORWARD_EXCEPTIONS
Forward an exception back through call stack.
algorithm requires consecutive ids
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
PartitioningProblem(Adapter *A, ParameterList *p, RCP< const Teuchos::Comm< int > > &comm)
Constructor where Teuchos communicator is specified.
PartitioningProblem(Adapter *A, ParameterList *p)
Constructor where communicator is the Teuchos default.
model must symmetrize input
model must symmetrize input
RCP< Algorithm< Adapter > > algorithm_
RCP< const Comm< int > > comm_
void resetParameters(ParameterList *params)
Reset the list of parameters.
Defines the PartitioningSolution class.
sub-steps, each method's entry and exit
const RCP< const Environment > & getEnvironment() const
Get the current Environment. Useful for testing.
void resetParameters(ParameterList *params)
Reset the list of parameters.
RCP< IdentifierModel< base_adapter_t > > identifierModel_
void setPartSizesForCriteria(int criteria, int len, part_t *partIds, scalar_t *partSizes, bool makeCopy=true)
Set or reset the relative sizes (per weight) for the parts that Zoltan2 will create.
int numProcs_
number of processes (relative to comm_)
use matrix rows as graph vertices
This class provides geometric coordinates with optional weights to the Zoltan2 algorithm.
Teuchos::ParameterList & getParametersNonConst()
Returns a reference to a non-const copy of the parameters.
algorithm requires no self edges
Defines the IdentifierModel interface.
A PartitioningSolution is a solution to a partitioning problem.
use nonzeros as graph vertices
void printGraphMetrics(std::ostream &os) const
Print the array of metrics.
Defines the EvaluatePartition class.
BaseAdapterType
An enum to identify general types of adapters.
void printMetrics(std::ostream &os) const
Print the array of metrics.
identifier data, just a list of IDs
void localBugAssertion(const char *file, int lineNum, const char *msg, bool ok, AssertionLevel level) const
Test for valid library behavior on local process only.
Problem base class from which other classes (PartitioningProblem, ColoringProblem, OrderingProblem, MatchingProblem, etc.) derive.
The StridedData class manages lists of weights or coordinates.
RCP< const Adapter > inputAdapter_
Defines the Problem base class.
RCP< CoordinateModel< base_adapter_t > > coordinateModel_
The user parameters, debug, timing and memory profiling output objects, and error checking methods...
MachineRepresentation Class Finds the coordinate of the processor. Used to find the processor coordin...
ArrayRCP< const GraphMetricValues< scalar_t > > getGraphMetrics() const
Get the array of graphMetrics Graph metrics were only computed if user requested graph metrics with a...
Adapter::base_adapter_t base_adapter_t
Define IntegerRangeList validator.
const PartitioningSolution< Adapter > & getSolution()
Get the solution to the problem.
PartitioningProblem sets up partitioning problems for the user.
use mesh elements as vertices
GraphModel defines the interface required for graph models.
The base class for all model classes.
IdentifierModel defines the interface for all identifier models.
Defines the GraphModel interface.
RCP< const Model< base_adapter_t > > baseModel_
A class that computes and returns quality metrics.
void solve(bool updateInputData=true)
Direct the problem to create a solution.
RCP< const Environment > envConst_
Multi Jagged coordinate partitioning algorithm.