Zoltan2_componentMetrics.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_COMPONENTMETRICS_HPP_
#define _ZOLTAN2_COMPONENTMETRICS_HPP_

#include <Zoltan2_Standards.hpp>
#include <Zoltan2_GraphModel.hpp>
#include <Teuchos_Comm.hpp>
#include <queue>

namespace Zoltan2
{

template <typename Adapter>
class perProcessorComponentMetrics{

public:
  typedef typename Adapter::lno_t lno_t;
  typedef typename Adapter::gno_t gno_t;
  typedef typename Adapter::offset_t offset_t;
  typedef typename Adapter::scalar_t scalar_t;

  perProcessorComponentMetrics(const Adapter &ia,
                               const Teuchos::Comm<int> &comm);

#ifdef HAVE_ZOLTAN2_MPI
  // Wrap MPI_Comm as a Teuchos::Comm, then call Teuchos::Comm constructor
  // Uses delegating constructor feature of C++11.
  perProcessorComponentMetrics(const Adapter &ia, const MPI_Comm mpicomm) :
  perProcessorComponentMetrics(ia, 
                       Teuchos::MpiComm<int>(Teuchos::opaqueWrapper(mpicomm)))
  {}
#endif

  ~perProcessorComponentMetrics() {}

  inline size_t getNumComponents() {return nComponent;}
  inline size_t getMaxComponentSize() {return maxComponentSize;}
  inline size_t getMinComponentSize() {return minComponentSize;}
  inline double getAvgComponentSize() {return avgComponentSize;}

private:
  size_t nComponent;    // number of components
  size_t maxComponentSize;  // size of largest component
  size_t minComponentSize;  // size of smalled component
  double avgComponentSize;  // average component size

  inline void markAndEnqueue(std::queue<gno_t> &q, bool *mark,
                             size_t &nUnmarkedVtx, size_t &cSize, gno_t vtx) {
    // insert vtx into the queue
    q.push(vtx);

    // mark vtx
    nUnmarkedVtx--;
    mark[vtx] = true;

    // increment component size
    cSize++;
  }
};

template <typename Adapter>
perProcessorComponentMetrics<Adapter>::perProcessorComponentMetrics(
  const Adapter &ia, const Teuchos::Comm<int> &comm) :
  nComponent(0), maxComponentSize(0), minComponentSize(0),
  avgComponentSize(0.)
{
  // build local graph model from input adapter
  std::bitset<NUM_MODEL_FLAGS> graphFlags;
  graphFlags.set(REMOVE_SELF_EDGES);
  graphFlags.set(BUILD_LOCAL_GRAPH);  // Local graph; 
                                      // all vertex numbering is 0 to nVtx-1

  Teuchos::RCP<const Teuchos::Comm<int> > tcomm = rcp(&comm, false);
  Teuchos::RCP<const Zoltan2::Environment> env = 
               rcp(new Zoltan2::Environment(tcomm));

  typedef typename Adapter::base_adapter_t base_adapter_t;
  Teuchos::RCP<const base_adapter_t> ria = rcp(&ia, false);
  Zoltan2::GraphModel<base_adapter_t> graph(ria, env, tcomm, graphFlags);

  // get graph from model
  const size_t nVtx = graph.getLocalNumVertices();
  ArrayView<const gno_t> adj;
  ArrayView<const offset_t> offset;
  ArrayView<StridedData<lno_t, scalar_t> > wgts;  // unused
  graph.getEdgeList(adj, offset, wgts);

  // do a simple BFS on the graph; 
  // can replace later with KokkosKernels or other TPL
  size_t nUnmarkedVtx = nVtx;
  bool *mark = new bool[nUnmarkedVtx];
  for (size_t i = 0; i < nUnmarkedVtx; i++) mark[i] = false;
  size_t startVtx = 0;

  std::queue<gno_t> q;

  // until all vertices are marked...
  while (nUnmarkedVtx > 0) {

    // Find the next component
    size_t cSize = 0;
    nComponent++;

    // Find an unmarked vertex; put it in the queue
    while (mark[startVtx]) startVtx++;
    markAndEnqueue(q, mark, nUnmarkedVtx, cSize, startVtx);

    while (!q.empty()) {
      gno_t vtx = q.front();
      q.pop();

      // Add neighbors of vtx to queue.
      for (offset_t j = offset[vtx]; j < offset[vtx+1]; j++) {
        if (!mark[adj[j]]) {
          markAndEnqueue(q, mark, nUnmarkedVtx, cSize, adj[j]);
        }
      }
    }

    // update stats
    if (nComponent == 1) {
      maxComponentSize = cSize;
      minComponentSize = cSize;
    }
    else {
      if (cSize > maxComponentSize) maxComponentSize = cSize;
      if (cSize < minComponentSize) minComponentSize = cSize;
    }
  }

  // update stats
  if (nComponent) avgComponentSize = double(nVtx) / double(nComponent);

  delete [] mark;
}


}                   // namespace Zoltan2
#endif