Zoltan2_PartitioningSolutionQuality.hpp

Go to the documentation of this file.

// @HEADER
//
// ***********************************************************************
//
//   Zoltan2: A package of combinatorial algorithms for scientific computing
//                  Copyright 2012 Sandia Corporation
//
// Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
// the U.S. Government retains certain rights in this software.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// 1. Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
//
// 3. Neither the name of the Corporation nor the names of the
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// Questions? Contact Karen Devine      (kddevin@sandia.gov)
//                    Erik Boman        (egboman@sandia.gov)
//                    Siva Rajamanickam (srajama@sandia.gov)
//
// ***********************************************************************
//
// @HEADER

#ifndef ZOLTAN2_SOLUTIONQUALITY_HPP
#define ZOLTAN2_SOLUTIONQUALITY_HPP

#include <Zoltan2_Metric.hpp>
#include <Zoltan2_PartitioningSolution.hpp>

namespace Zoltan2{

template <typename Adapter>
  class PartitioningSolutionQuality {

private:

  typedef typename Adapter::lno_t lno_t;
  typedef typename Adapter::part_t part_t;
  typedef typename Adapter::scalar_t scalar_t;

  const RCP<const Environment> env_;

  part_t numGlobalParts_;           // desired
  part_t targetGlobalParts_;        // actual
  part_t numNonEmpty_;              // of actual

  ArrayRCP<MetricValues<scalar_t> > metrics_;
  ArrayRCP<const MetricValues<scalar_t> > metricsConst_;

public:

  PartitioningSolutionQuality(const RCP<const Environment> &env,
    const RCP<const Comm<int> > &problemComm,
    const RCP<const Adapter> &ia, 
    const RCP<const PartitioningSolution<Adapter> > &soln);

  ArrayRCP<const MetricValues<scalar_t> > getMetrics() const{
    //BDD return metricsConst_;
      if(metricsConst_.is_null()) return metrics_;
      return metricsConst_;
  }

  void getObjectCountImbalance(scalar_t &imbalance) const{
    imbalance = metrics_[0].getMaxImbalance();
  }

  void getNormedImbalance(scalar_t &imbalance) const{
    if (metrics_.size() > 1)
      imbalance = metrics_[1].getMaxImbalance();
    else 
      imbalance = metrics_[0].getMaxImbalance();
  }

  void getWeightImbalance(scalar_t &imbalance, int idx=0) const{
    imbalance = 0;
    if (metrics_.size() > 2)  // idx of multiple weights
      imbalance = metrics_[idx+2].getMaxImbalance();
    else if (metrics_.size() == 2)   //  only one weight
      imbalance = metrics_[1].getMaxImbalance();
    else                       // no weights, return object count imbalance
      imbalance = metrics_[0].getMaxImbalance();
  }  

  void printMetrics(std::ostream &os) const {
    Zoltan2::printMetrics<scalar_t, part_t>(os, 
      targetGlobalParts_, numGlobalParts_, numNonEmpty_, 
      metrics_.view(0, metrics_.size()));
  }
};

template <typename Adapter>
  class GraphPartitioningSolutionQuality {

private:

  typedef typename Adapter::lno_t lno_t;
  typedef typename Adapter::part_t part_t;
  typedef typename Adapter::scalar_t scalar_t;

  const RCP<const Environment> env_;

  part_t numGlobalParts_;           // desired
  part_t targetGlobalParts_;        // actual

  ArrayRCP<GraphMetricValues<scalar_t> > metrics_;
  ArrayRCP<const GraphMetricValues<scalar_t> > metricsConst_;

public:

  GraphPartitioningSolutionQuality(const RCP<const Environment> &env,
    const RCP<const Comm<int> > &problemComm,
    const RCP<const GraphModel<typename Adapter::base_adapter_t> > &graph,
    const RCP<const Adapter> &ia, 
    const RCP<const PartitioningSolution<Adapter> > &soln);

  ArrayRCP<const GraphMetricValues<scalar_t> > getGraphMetrics() const{
      if(metricsConst_.is_null()) return metrics_;
      return metricsConst_;
  }

  void getWeightCut(scalar_t &cut, int idx=0) const{
    if (metrics_.size() < idx)  // idx too high
      cut = metrics_[metrics_.size()-1].getGlobalMax();
    else if (idx < 0)   //  idx too low
      cut = metrics_[0].getGlobalMax();
    else                       // idx weight
      cut = metrics_[idx].getGlobalMax();
  }
};

template <typename Adapter>
  PartitioningSolutionQuality<Adapter>::PartitioningSolutionQuality(
  const RCP<const Environment> &env,
  const RCP<const Comm<int> > &problemComm,
  const RCP<const Adapter> &ia, 
  const RCP<const PartitioningSolution<Adapter> > &soln):
    env_(env), numGlobalParts_(0), targetGlobalParts_(0), numNonEmpty_(0),
    metrics_(),  metricsConst_()
{

  env->debug(DETAILED_STATUS, std::string("Entering PartitioningSolutionQuality"));
  env->timerStart(MACRO_TIMERS, "Computing metrics");

  // When we add parameters for which weights to use, we
  // should check those here.  For now we compute metrics
  // using all weights.

  const Teuchos::ParameterList &pl = env->getParameters();
  multiCriteriaNorm mcnorm = normBalanceTotalMaximum;

  const Teuchos::ParameterEntry *pe = pl.getEntryPtr("partitioning_objective");

  if (pe){
    std::string strChoice = pe->getValue<std::string>(&strChoice);
    if (strChoice == std::string("multicriteria_minimize_total_weight"))
      mcnorm = normMinimizeTotalWeight;
    else if (strChoice == std::string("multicriteria_minimize_maximum_weight"))
      mcnorm = normMinimizeMaximumWeight;
  } 

  try{
    objectMetrics<Adapter>(env, problemComm, mcnorm, ia, soln,
      numGlobalParts_, numNonEmpty_, metrics_);
  }
  Z2_FORWARD_EXCEPTIONS;

  targetGlobalParts_ = soln->getTargetGlobalNumberOfParts();

  env->timerStop(MACRO_TIMERS, "Computing metrics");
  env->debug(DETAILED_STATUS, std::string("Exiting PartitioningSolutionQuality"));
}

template <typename Adapter>
  GraphPartitioningSolutionQuality<Adapter>::GraphPartitioningSolutionQuality(
  const RCP<const Environment> &env,
  const RCP<const Comm<int> > &problemComm,
  const RCP<const GraphModel<typename Adapter::base_adapter_t> > &graph,
  const RCP<const Adapter> &ia, 
  const RCP<const PartitioningSolution<Adapter> > &soln):
    env_(env), numGlobalParts_(0), targetGlobalParts_(0),
    metrics_(),  metricsConst_()
{

  env->debug(DETAILED_STATUS,
       std::string("Entering GraphPartitioningSolutionQuality"));
  env->timerStart(MACRO_TIMERS, "Computing graph metrics");
  // When we add parameters for which weights to use, we
  // should check those here.  For now we compute graph metrics
  // using all weights.

  typedef typename Adapter::part_t part_t;

  // Local number of objects.

  size_t numLocalObjects = ia->getLocalNumIDs();

  // Parts to which objects are assigned.

  const part_t *parts = soln->getPartListView();
  env->localInputAssertion(__FILE__, __LINE__, "parts not set",
         ((numLocalObjects == 0) || parts), BASIC_ASSERTION);
  ArrayView<const part_t> partArray(parts, numLocalObjects);

  ArrayRCP<scalar_t> globalSums;

  try{
    globalWeightedCutsByPart<Adapter>(env,
      problemComm, graph, partArray, numGlobalParts_, metrics_, globalSums);
  }
  Z2_FORWARD_EXCEPTIONS;

  targetGlobalParts_ = soln->getTargetGlobalNumberOfParts();

  env->timerStop(MACRO_TIMERS, "Computing graph metrics");
  env->debug(DETAILED_STATUS,
       std::string("Exiting GraphPartitioningSolutionQuality"));
}

}   // namespace Zoltan2

#endif