Zoltan2
Zoltan2_GraphModel.hpp
Go to the documentation of this file.
1 // @HEADER
2 //
3 // ***********************************************************************
4 //
5 // Zoltan2: A package of combinatorial algorithms for scientific computing
6 // Copyright 2012 Sandia Corporation
7 //
8 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
9 // the U.S. Government retains certain rights in this software.
10 //
11 // Redistribution and use in source and binary forms, with or without
12 // modification, are permitted provided that the following conditions are
13 // met:
14 //
15 // 1. Redistributions of source code must retain the above copyright
16 // notice, this list of conditions and the following disclaimer.
17 //
18 // 2. Redistributions in binary form must reproduce the above copyright
19 // notice, this list of conditions and the following disclaimer in the
20 // documentation and/or other materials provided with the distribution.
21 //
22 // 3. Neither the name of the Corporation nor the names of the
23 // contributors may be used to endorse or promote products derived from
24 // this software without specific prior written permission.
25 //
26 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
27 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
30 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37 //
38 // Questions? Contact Karen Devine (kddevin@sandia.gov)
39 // Erik Boman (egboman@sandia.gov)
40 // Siva Rajamanickam (srajama@sandia.gov)
41 //
42 // ***********************************************************************
43 //
44 // @HEADER
45 
50 #ifndef _ZOLTAN2_GRAPHMODEL_HPP_
51 #define _ZOLTAN2_GRAPHMODEL_HPP_
52 
53 #include <Zoltan2_Model.hpp>
54 #include <Zoltan2_ModelHelpers.hpp>
55 #include <Zoltan2_InputTraits.hpp>
57 #include <Zoltan2_GraphAdapter.hpp>
60 #include <Zoltan2_MeshAdapter.hpp>
61 #include <Zoltan2_StridedData.hpp>
62 #include <unordered_map>
63 
64 namespace Zoltan2 {
65 
67 
79 template <typename Adapter>
80 class GraphModel : public Model<Adapter>
81 {
82 public:
83 
84 #ifndef DOXYGEN_SHOULD_SKIP_THIS
85  typedef typename Adapter::scalar_t scalar_t;
86  typedef typename Adapter::gno_t gno_t;
87  typedef typename Adapter::lno_t lno_t;
88  typedef typename Adapter::node_t node_t;
89  typedef typename Adapter::user_t user_t;
90  typedef typename Adapter::userCoord_t userCoord_t;
91  typedef StridedData<lno_t, scalar_t> input_t;
92 #endif
93 
96 
108  GraphModel(const RCP<const MatrixAdapter<user_t,userCoord_t> > &ia,
109  const RCP<const Environment> &env, const RCP<const Comm<int> > &comm,
110  modelFlag_t &modelFlags);
111 
112  GraphModel(const RCP<const GraphAdapter<user_t,userCoord_t> > &ia,
113  const RCP<const Environment> &env, const RCP<const Comm<int> > &comm,
114  modelFlag_t &modelFlags);
115 
116  GraphModel(const RCP<const MeshAdapter<user_t> > &ia,
117  const RCP<const Environment> &env, const RCP<const Comm<int> > &comm,
118  modelFlag_t &modelflags);
119 
120  GraphModel(const RCP<const VectorAdapter<userCoord_t> > &ia,
121  const RCP<const Environment> &env, const RCP<const Comm<int> > &comm,
122  modelFlag_t &flags)
123  {
124  throw std::runtime_error("cannot build GraphModel from VectorAdapter");
125  }
126 
127  GraphModel(const RCP<const IdentifierAdapter<user_t> > &ia,
128  const RCP<const Environment> &env, const RCP<const Comm<int> > &comm,
129  modelFlag_t &flags)
130  {
131  throw std::runtime_error("cannot build GraphModel from IdentifierAdapter");
132  }
133 
136  const RCP<const Comm<int> > getComm() { return comm_; }
137 
140  size_t getLocalNumVertices() const { return nLocalVertices_; }
141 
144  size_t getGlobalNumVertices() const { return nGlobalVertices_; }
145 
149  size_t getLocalNumEdges() const { return nLocalEdges_; }
150 
154  size_t getGlobalNumEdges() const { return nGlobalEdges_; }
155 
158  int getNumWeightsPerVertex() const { return nWeightsPerVertex_; }
159 
162  int getNumWeightsPerEdge() const { return nWeightsPerEdge_; }
163 
166  int getCoordinateDim() const { return vCoordDim_; }
167 
177  ArrayView<const gno_t> &Ids,
178  ArrayView<input_t> &wgts) const
179  {
180  Ids = vGids_.view(0, nLocalVertices_);
181  wgts = vWeights_.view(0, nWeightsPerVertex_);
182  return nLocalVertices_;
183  }
184 
191  size_t getVertexCoords(ArrayView<input_t> &xyz) const
192  {
193  xyz = vCoords_.view(0, vCoordDim_);
194  return nLocalVertices_;
195  }
196 
208  // Implied Vertex LNOs from getVertexList are used as indices to offsets
209  // array.
210  // Vertex GNOs are returned as neighbors in edgeIds.
211 
212  size_t getEdgeList( ArrayView<const gno_t> &edgeIds,
213  ArrayView<const lno_t> &offsets,
214  ArrayView<input_t> &wgts) const
215  {
216  edgeIds = eGids_.view(0, nLocalEdges_);
217  offsets = eOffsets_.view(0, nLocalVertices_+1);
218  wgts = eWeights_.view(0, nWeightsPerEdge_);
219  return nLocalEdges_;
220  }
221 
226  inline void getVertexDist(ArrayView<size_t> &vtxdist) const
227  {
228  vtxdist = vtxDist_();
229  if (vtxDist_.size() == 0) {
230  throw std::runtime_error("getVertexDist is available only "
231  "when consecutiveIdsRequired");
232  }
233  }
234 
236  // The Model interface.
238 
239  size_t getLocalNumObjects() const { return nLocalVertices_; }
240 
241  size_t getGlobalNumObjects() const { return nGlobalVertices_; }
242 
243 private:
244 
245  void shared_constructor(const RCP<const Adapter>&ia, modelFlag_t &modelFlags);
246 
247  template <typename AdapterWithCoords>
248  void shared_GetVertexCoords(const AdapterWithCoords *ia);
249 
250  void print(); // For debugging
251 
252  const RCP<const Environment > env_;
253  const RCP<const Comm<int> > comm_;
254 
255  bool localGraph_; // Flag indicating whether this graph is
256  // LOCAL with respect to the process;
257  // if !localGraph_, graph is GLOBAL with respect to
258  // the communicator.
259 
260 
261  size_t nLocalVertices_; // # local vertices in built graph
262  size_t nGlobalVertices_; // # global vertices in built graph
263  ArrayRCP<gno_t> vGids_; // vertices of graph built in model;
264  // may be same as adapter's input
265  // or may be renumbered 0 to (N-1).
266 
267  int nWeightsPerVertex_;
268  ArrayRCP<input_t> vWeights_;
269 
270  int vCoordDim_;
271  ArrayRCP<input_t> vCoords_;
272 
273  // Note: in some cases, size of these arrays
274  // may be larger than nLocalEdges_. So do not use .size().
275  // Use nLocalEdges_, nGlobalEdges_
276 
277  size_t nLocalEdges_; // # local edges in built graph
278  size_t nGlobalEdges_; // # global edges in built graph
279  ArrayRCP<gno_t> eGids_; // edges of graph built in model
280  ArrayRCP<lno_t> eOffsets_; // edge offsets build in model
281  // May be same as adapter's input
282  // or may differ
283  // due to renumbering, self-edge
284  // removal, or local graph.
285 
286  int nWeightsPerEdge_;
287  ArrayRCP<input_t> eWeights_; // edge weights in built graph
288  // May be same as adapter's input
289  // or may differ due to self-edge
290  // removal, or local graph.
291 
292  ArrayRCP<size_t> vtxDist_; // If consecutiveIdsRequired,
293  // vtxDist (as needed by ParMETIS
294  // and Scotch) is also created.
295  // Otherwise, it is Teuchos::null.
296 };
297 
298 
300 // GraphModel from MatrixAdapter
301 template <typename Adapter>
303  const RCP<const MatrixAdapter<user_t,userCoord_t> > &ia,
304  const RCP<const Environment> &env,
305  const RCP<const Comm<int> > &comm,
306  modelFlag_t &modelFlags):
307  env_(env),
308  comm_(comm),
309  localGraph_(false),
310  nLocalVertices_(0),
311  nGlobalVertices_(0),
312  vGids_(),
313  nWeightsPerVertex_(0),
314  vWeights_(),
315  vCoordDim_(0),
316  vCoords_(),
317  nLocalEdges_(0),
318  nGlobalEdges_(0),
319  eGids_(),
320  eOffsets_(),
321  nWeightsPerEdge_(0),
322  eWeights_(),
323  vtxDist_()
324 {
325  // Model creation flags
326  localGraph_ = modelFlags.test(BUILD_LOCAL_GRAPH);
327 
328  bool symTranspose = modelFlags.test(SYMMETRIZE_INPUT_TRANSPOSE);
329  bool symBipartite = modelFlags.test(SYMMETRIZE_INPUT_BIPARTITE);
330  bool vertexCols = modelFlags.test(VERTICES_ARE_MATRIX_COLUMNS);
331  bool vertexNz = modelFlags.test(VERTICES_ARE_MATRIX_NONZEROS);
332 
333  if (symTranspose || symBipartite || vertexCols || vertexNz){
334  throw std::runtime_error("graph build option not yet implemented");
335  }
336 
337  // Get the matrix from the input adapter
338  gno_t const *vtxIds=NULL, *nborIds=NULL;
339  lno_t const *offsets=NULL;
340  try{
341  nLocalVertices_ = ia->getLocalNumIDs();
342  ia->getIDsView(vtxIds);
343  }
345  try{
346  if (ia->CRSViewAvailable()) {
347  ia->getCRSView(offsets, nborIds);
348  }
349  else {
350  // TODO: Add support for CCS matrix layout
351  throw std::runtime_error("Only MatrixAdapter::getCRSView is supported "
352  "in graph model");
353  }
354  }
356 
357  // Save the pointers from the input adapter
358  nLocalEdges_ = offsets[nLocalVertices_];
359  vGids_ = arcp_const_cast<gno_t>(
360  arcp<const gno_t>(vtxIds, 0, nLocalVertices_, false));
361  eGids_ = arcp_const_cast<gno_t>(
362  arcp<const gno_t>(nborIds, 0, nLocalEdges_, false));
363  eOffsets_ = arcp_const_cast<lno_t>(
364  arcp<const lno_t>(offsets, 0, nLocalVertices_+1, false));
365 
366  // Edge weights
367  nWeightsPerEdge_ = 0; // no edge weights from a matrix yet.
368  // TODO: use matrix values as edge weights
369 
370  // Do constructor common to all adapters
371  shared_constructor(ia, modelFlags);
372 
373  // Get vertex coordinates, if available
374  if (ia->coordinatesAvailable()) {
375  typedef VectorAdapter<userCoord_t> adapterWithCoords_t;
376  shared_GetVertexCoords<adapterWithCoords_t>(ia->getCoordinateInput());
377  }
378  // print();
379 }
380 
381 
383 // GraphModel from GraphAdapter
384 template <typename Adapter>
386  const RCP<const GraphAdapter<user_t,userCoord_t> > &ia,
387  const RCP<const Environment> &env,
388  const RCP<const Comm<int> > &comm,
389  modelFlag_t &modelFlags):
390  env_(env),
391  comm_(comm),
392  localGraph_(false),
393  nLocalVertices_(0),
394  nGlobalVertices_(0),
395  vGids_(),
396  nWeightsPerVertex_(0),
397  vWeights_(),
398  vCoordDim_(0),
399  vCoords_(),
400  nLocalEdges_(0),
401  nGlobalEdges_(0),
402  eGids_(),
403  eOffsets_(),
404  nWeightsPerEdge_(0),
405  eWeights_(),
406  vtxDist_()
407 {
408  // Model creation flags
409  localGraph_ = modelFlags.test(BUILD_LOCAL_GRAPH);
410 
411  // This GraphModel is built with vertices == GRAPH_VERTEX from GraphAdapter.
412  // It is not ready to use vertices == GRAPH_EDGE from GraphAdapter.
413  env_->localInputAssertion(__FILE__, __LINE__,
414  "GraphModel from GraphAdapter is implemented only for "
415  "Graph Vertices as primary object, not for Graph Edges",
416  ia->getPrimaryEntityType() == Zoltan2::GRAPH_VERTEX, BASIC_ASSERTION);
417 
418  // Get the graph from the input adapter
419 
420  gno_t const *vtxIds=NULL, *nborIds=NULL;
421  lno_t const *offsets=NULL;
422  try{
423  nLocalVertices_ = ia->getLocalNumVertices();
424  ia->getVertexIDsView(vtxIds);
425  ia->getEdgesView(offsets, nborIds);
426  }
428 
429  // Save the pointers from the input adapter
430  nLocalEdges_ = offsets[nLocalVertices_];
431  vGids_ = arcp_const_cast<gno_t>(
432  arcp<const gno_t>(vtxIds, 0, nLocalVertices_, false));
433  eGids_ = arcp_const_cast<gno_t>(
434  arcp<const gno_t>(nborIds, 0, nLocalEdges_, false));
435  eOffsets_ = arcp_const_cast<lno_t>(
436  arcp<const lno_t>(offsets, 0, nLocalVertices_+1, false));
437 
438  // Edge weights
439  nWeightsPerEdge_ = ia->getNumWeightsPerEdge();
440  if (nWeightsPerEdge_ > 0){
441  input_t *wgts = new input_t [nWeightsPerEdge_];
442  eWeights_ = arcp(wgts, 0, nWeightsPerEdge_, true);
443  }
444 
445  for (int w=0; w < nWeightsPerEdge_; w++){
446  const scalar_t *ewgts=NULL;
447  int stride=0;
448 
449  ia->getEdgeWeightsView(ewgts, stride, w);
450 
451  ArrayRCP<const scalar_t> wgtArray(ewgts, 0, nLocalEdges_, false);
452  eWeights_[w] = input_t(wgtArray, stride);
453  }
454 
455  // Do constructor common to all adapters
456  shared_constructor(ia, modelFlags);
457 
458  // Get vertex coordinates, if available
459  if (ia->coordinatesAvailable()) {
460  typedef VectorAdapter<userCoord_t> adapterWithCoords_t;
461  shared_GetVertexCoords<adapterWithCoords_t>(ia->getCoordinateInput());
462  }
463  // print();
464 }
465 
467 // GraphModel from MeshAdapter
468 template <typename Adapter>
470  const RCP<const MeshAdapter<user_t> > &ia,
471  const RCP<const Environment> &env,
472  const RCP<const Comm<int> > &comm,
473  modelFlag_t &modelFlags):
474  env_(env),
475  comm_(comm),
476  localGraph_(false),
477  nLocalVertices_(0),
478  nGlobalVertices_(0),
479  vGids_(),
480  nWeightsPerVertex_(0),
481  vWeights_(),
482  vCoordDim_(0),
483  vCoords_(),
484  nLocalEdges_(0),
485  nGlobalEdges_(0),
486  eGids_(),
487  eOffsets_(),
488  nWeightsPerEdge_(0),
489  eWeights_(),
490  vtxDist_()
491 {
492  env_->timerStart(MACRO_TIMERS, "GraphModel constructed from MeshAdapter");
493 
494  // Model creation flags
495  localGraph_ = modelFlags.test(BUILD_LOCAL_GRAPH);
496 
497  // This GraphModel is built with vertices == ia->getPrimaryEntityType()
498  // from MeshAdapter.
499 
500  // Get the graph from the input adapter
501 
502  Zoltan2::MeshEntityType primaryEType = ia->getPrimaryEntityType();
503  Zoltan2::MeshEntityType secondAdjEType = ia->getSecondAdjacencyEntityType();
504 
505  // Get the IDs of the primary entity type; these are graph vertices
506 
507  gno_t const *vtxIds=NULL;
508  try {
509  nLocalVertices_ = ia->getLocalNumOf(primaryEType);
510  ia->getIDsViewOf(primaryEType, vtxIds);
511  }
513 
514  vGids_ = arcp_const_cast<gno_t>(
515  arcp<const gno_t>(vtxIds, 0, nLocalVertices_, false));
516 
517  // Get the second adjacencies to construct edges of the dual graph.
518 
519  if (!ia->avail2ndAdjs(primaryEType, secondAdjEType)) {
520  // KDDKDD TODO Want to do this differently for local and global graphs?
521  // KDDKDD TODO Currently getting global 2nd Adjs and filtering them for
522  // KDDKDD TODO local graphs. That approach is consistent with other
523  // KDDKDD TODO adapters, but is more expensive -- why build them just to
524  // KDDKDD TODO throw them away? Instead, perhaps should build
525  // KDDKDD TODO only local adjacencies.
526  // KDDKDD TODO Does it suffice to pass a serial comm for local graph?
527  try {
528  get2ndAdjsViewFromAdjs(ia, comm_, primaryEType, secondAdjEType, eOffsets_,
529  eGids_);
530  nLocalEdges_ = eOffsets_[nLocalVertices_];
531  }
533  }
534  else { // avail2ndAdjs
535  // Get the edges
536  try {
537  gno_t const *nborIds=NULL;
538  lno_t const *offsets=NULL;
539 
540  ia->get2ndAdjsView(primaryEType, secondAdjEType, offsets, nborIds);
541  // Save the pointers from the input adapter; we do not control the
542  // offsets and nborIds memory
543  nLocalEdges_ = offsets[nLocalVertices_];
544  eGids_ = arcp_const_cast<gno_t>(
545  arcp<const gno_t>(nborIds, 0, nLocalEdges_, false));
546  eOffsets_ = arcp_const_cast<lno_t>(
547  arcp<const lno_t>(offsets, 0, nLocalVertices_+1, false));
548  }
550  }
551 
552 
553  // Edge weights
554  // Cannot specify edge weights if Zoltan2 computes the second adjacencies;
555  // there's no way to know the correct order for the adjacencies and weights.
556  // InputAdapter must provide 2nd adjs in order for edge weights to be used.
557  if (ia->avail2ndAdjs(primaryEType, secondAdjEType)) {
558  nWeightsPerEdge_ = ia->getNumWeightsPer2ndAdj(primaryEType, secondAdjEType);
559  if (nWeightsPerEdge_ > 0){
560  input_t *wgts = new input_t [nWeightsPerEdge_];
561  eWeights_ = arcp(wgts, 0, nWeightsPerEdge_, true);
562  }
563 
564  for (int w=0; w < nWeightsPerEdge_; w++){
565  const scalar_t *ewgts=NULL;
566  int stride=0;
567 
568  ia->get2ndAdjWeightsView(primaryEType, secondAdjEType,
569  ewgts, stride, w);
570 
571  ArrayRCP<const scalar_t> wgtArray(ewgts, 0,
572  nLocalEdges_*stride, false);
573  eWeights_[w] = input_t(wgtArray, stride);
574  }
575  }
576 
577  // Do constructor common to all adapters
578  shared_constructor(ia, modelFlags);
579 
580  // Get vertex coordinates
581  typedef MeshAdapter<user_t> adapterWithCoords_t;
582  shared_GetVertexCoords<adapterWithCoords_t>(&(*ia));
583 
584  env_->timerStop(MACRO_TIMERS, "GraphModel constructed from MeshAdapter");
585  // print();
586 }
587 
588 
590 template <typename Adapter>
592  const RCP<const Adapter> &ia,
593  modelFlag_t &modelFlags)
594 {
595  // Model creation flags
596  bool consecutiveIdsRequired = modelFlags.test(GENERATE_CONSECUTIVE_IDS);
597  bool removeSelfEdges = modelFlags.test(REMOVE_SELF_EDGES);
598  bool subsetGraph = modelFlags.test(BUILD_SUBSET_GRAPH);
599 
600  // May modify the graph provided from input adapter; save pointers to
601  // the input adapter's data.
602  size_t adapterNLocalEdges = nLocalEdges_;
603  ArrayRCP<gno_t> adapterVGids = vGids_; // vertices of graph from adapter
604  ArrayRCP<gno_t> adapterEGids = eGids_; // edges of graph from adapter
605  ArrayRCP<lno_t> adapterEOffsets = eOffsets_; // edge offsets from adapter
606  ArrayRCP<input_t> adapterEWeights = eWeights_; // edge weights from adapter
607 
608  if (localGraph_) {
609  // Local graph is requested.
610  // Renumber vertices 0 to nLocalVertices_-1
611  // Filter out off-process edges
612  // Renumber edge neighbors to be in range [0,nLocalVertices_-1]
613 
614  // Allocate new space for local graph info
615  // Note that eGids_ and eWeights_[w] may be larger than needed;
616  // we would have to pre-count the number of local edges to avoid overalloc
617  vGids_ = arcp(new gno_t[nLocalVertices_],
618  0, nLocalVertices_, true);
619  eGids_ = arcp(new gno_t[adapterNLocalEdges],
620  0, adapterNLocalEdges, true);
621  eOffsets_ = arcp(new lno_t[nLocalVertices_+1],
622  0, nLocalVertices_+1, true);
623 
624  scalar_t **tmpEWeights = NULL;
625  if (nWeightsPerEdge_ > 0){
626  eWeights_ = arcp(new input_t[nWeightsPerEdge_], 0,
627  nWeightsPerEdge_, true);
628  // Need to use temporary array because StridedData has const data
629  // so we can't write to it.
630  tmpEWeights = new scalar_t*[nWeightsPerEdge_];
631  for (int w = 0; w < nWeightsPerEdge_; w++)
632  tmpEWeights[w] = new scalar_t[adapterNLocalEdges];
633  }
634 
635  // Build map between global and local vertex numbers
636  std::unordered_map<gno_t, lno_t> globalToLocal(nLocalVertices_);
637  for (size_t i = 0; i < nLocalVertices_; i++)
638  globalToLocal[adapterVGids[i]] = i;
639 
640  // Loop over edges; keep only those that are local (i.e., on-rank)
641  eOffsets_[0] = 0;
642  lno_t ecnt = 0;
643  for (size_t i = 0; i < nLocalVertices_; i++) {
644  vGids_[i] = gno_t(i);
645  for (lno_t j = adapterEOffsets[i]; j < adapterEOffsets[i+1]; j++) {
646 
647  if (removeSelfEdges && (adapterEGids[j] == adapterVGids[i]))
648  continue; // Skipping self edge
649 
650  // Determine whether neighbor vertex is local
651  typename std::unordered_map<gno_t, lno_t>::iterator localidx;
652  if ((localidx = globalToLocal.find(adapterEGids[j])) !=
653  globalToLocal.end()) {
654  // neighbor vertex is local
655  // Keep the edge and its weights
656  eGids_[ecnt] = localidx->second;
657  for (int w = 0; w < nWeightsPerEdge_; w++)
658  tmpEWeights[w][ecnt] = adapterEWeights[w][j];
659 
660  ecnt++;
661  }
662  }
663  eOffsets_[i+1] = ecnt;
664  }
665  nLocalEdges_ = eOffsets_[nLocalVertices_];
666  if (nWeightsPerEdge_) {
667  for (int w = 0; w < nWeightsPerEdge_; w++) {
668  ArrayRCP<const scalar_t> wgtArray(tmpEWeights[w],
669  0, adapterNLocalEdges, true);
670  eWeights_[w] = input_t(wgtArray, 0);
671  }
672  delete [] tmpEWeights;
673  }
674  } // localGraph_
675 
676  else if (consecutiveIdsRequired || removeSelfEdges || subsetGraph) {
677  // Build a Global graph
678  // If we are here, we expect SOMETHING in the graph to change from input:
679  // removing self edges, or converting to consecutive IDs, or subsetting
680  // the graph.
681 
682 
683  // Determine vertex GIDs for the global GraphModel
684  if (consecutiveIdsRequired) {
685  // Allocate new memory for vertices for consecutiveIds
686  vGids_ = arcp(new gno_t[nLocalVertices_], 0, nLocalVertices_, true);
687 
688  // Build vtxDist_ array with starting vGid on each rank
689  int np = comm_->getSize();
690  vtxDist_ = arcp(new size_t[np+1], 0, np+1, true);
691  vtxDist_[0] = 0;
692  Teuchos::gatherAll(*comm_, 1, &nLocalVertices_, np, &vtxDist_[1]);
693  for (int i = 0; i < np; i++)
694  vtxDist_[i+1] += vtxDist_[i];
695  }
696 
697  // Allocate new memory for edges and offsets, as needed
698  // Note that eGids_ may or may not be larger than needed;
699  // would have to pre-count number of edges kept otherwise
700  eGids_ = arcp(new gno_t[adapterNLocalEdges],
701  0, adapterNLocalEdges, true);
702 
703  scalar_t **tmpEWeights = NULL;
704  if (subsetGraph || removeSelfEdges) {
705  // May change number of edges and, thus, the offsets
706  eOffsets_ = arcp(new lno_t[nLocalVertices_+1],
707  0, nLocalVertices_+1, true);
708  eOffsets_[0] = 0;
709 
710  // Need to copy weights if remove edges
711  if (nWeightsPerEdge_ > 0){
712  eWeights_ = arcp(new input_t[nWeightsPerEdge_], 0,
713  nWeightsPerEdge_, true);
714  // Need to use temporary array because StridedData has const data
715  // so we can't write to it.
716  tmpEWeights = new scalar_t*[nWeightsPerEdge_];
717  for (int w = 0; w < nWeightsPerEdge_; w++)
718  tmpEWeights[w] = new scalar_t[adapterNLocalEdges];
719  }
720  }
721 
722  // If needed, determine the owning ranks and its local index off-proc
723  Teuchos::ArrayRCP<int> edgeRemoteRanks;
724  Teuchos::ArrayRCP<lno_t> edgeRemoteLids;
725  std::unordered_map<gno_t, size_t> edgeRemoteUniqueMap;
726 
727  if (subsetGraph || consecutiveIdsRequired) {
728  gno_t dummy = Teuchos::OrdinalTraits<gno_t>::invalid();
729  Tpetra::Map<lno_t,gno_t> vtxMap(dummy, adapterVGids(), 0, comm_);
730 
731  // Need to filter requested edges to make a unique list,
732  // as Tpetra::Map does not return correct info for duplicated entries
733  // (See bug 6412)
734  // The local filter may be more efficient anyway -- fewer communicated
735  // values in the Tpetra directory
736  Teuchos::ArrayRCP<gno_t> edgeRemoteUniqueGids =
737  arcp(new gno_t[adapterNLocalEdges], 0, adapterNLocalEdges, true);
738 
739  size_t nEdgeUnique = 0;
740  for (size_t i = 0; i < adapterNLocalEdges; i++) {
741  if (edgeRemoteUniqueMap.find(adapterEGids[i]) ==
742  edgeRemoteUniqueMap.end()) {
743  edgeRemoteUniqueGids[nEdgeUnique] = adapterEGids[i];
744  edgeRemoteUniqueMap[adapterEGids[i]] = nEdgeUnique;
745  nEdgeUnique++;
746  }
747  }
748 
749  edgeRemoteRanks = arcp(new int[nEdgeUnique], 0, nEdgeUnique, true);
750  edgeRemoteLids = arcp(new lno_t[nEdgeUnique], 0, nEdgeUnique, true);
751  vtxMap.getRemoteIndexList(edgeRemoteUniqueGids(0, nEdgeUnique),
752  edgeRemoteRanks(), edgeRemoteLids());
753  }
754 
755  // Renumber and/or filter the edges and vertices
756  lno_t ecnt = 0;
757  int me = comm_->getRank();
758  for (size_t i = 0; i < nLocalVertices_; i++) {
759 
760  if (consecutiveIdsRequired)
761  vGids_[i] = vtxDist_[me] + i;
762 
763  for (lno_t j = adapterEOffsets[i]; j < adapterEOffsets[i+1]; j++) {
764 
765  if (removeSelfEdges && (adapterVGids[i] == adapterEGids[j]))
766  continue; // Skipping self edge
767 
768  size_t remoteIdx = edgeRemoteUniqueMap[adapterEGids[j]];
769 
770  if (subsetGraph && (edgeRemoteRanks[remoteIdx] == -1))
771  continue; // Skipping edge with neighbor vertex that was not found
772  // in communicator
773 
774  if (consecutiveIdsRequired)
775  // Renumber edge using local number on remote rank plus first
776  // vtx number for remote rank
777  eGids_[ecnt] = edgeRemoteLids[remoteIdx]
778  + vtxDist_[edgeRemoteRanks[remoteIdx]];
779  else
780  eGids_[ecnt] = adapterEGids[j];
781 
782  if (subsetGraph || removeSelfEdges) {
783  // Need to copy weights only if number of edges might change
784  for (int w = 0; w < nWeightsPerEdge_; w++)
785  tmpEWeights[w][ecnt] = adapterEWeights[w][j];
786  }
787 
788  ecnt++;
789  }
790  if (subsetGraph || removeSelfEdges)
791  eOffsets_[i+1] = ecnt;
792  }
793  nLocalEdges_ = ecnt;
794  if (nWeightsPerEdge_ && (subsetGraph || removeSelfEdges)) {
795  for (int w = 0; w < nWeightsPerEdge_; w++) {
796  ArrayRCP<const scalar_t> wgtArray(tmpEWeights[w],
797  0, nLocalEdges_, true);
798  eWeights_[w] = input_t(wgtArray, 1);
799  }
800  delete [] tmpEWeights;
801  }
802  }
803 
804  // Vertex weights
805  nWeightsPerVertex_ = ia->getNumWeightsPerID();
806 
807  if (nWeightsPerVertex_ > 0){
808  input_t *weightInfo = new input_t [nWeightsPerVertex_];
809  env_->localMemoryAssertion(__FILE__, __LINE__, nWeightsPerVertex_,
810  weightInfo);
811 
812  for (int idx=0; idx < nWeightsPerVertex_; idx++){
813  bool useNumNZ = ia->useDegreeAsWeight(idx);
814  if (useNumNZ){
815  scalar_t *wgts = new scalar_t [nLocalVertices_];
816  env_->localMemoryAssertion(__FILE__, __LINE__, nLocalVertices_, wgts);
817  ArrayRCP<const scalar_t> wgtArray = arcp(wgts,
818  0, nLocalVertices_, true);
819  for (size_t i=0; i < nLocalVertices_; i++)
820  wgts[i] = eOffsets_[i+1] - eOffsets_[i];
821  weightInfo[idx] = input_t(wgtArray, 1);
822  }
823  else{
824  const scalar_t *weights=NULL;
825  int stride=0;
826  ia->getWeightsView(weights, stride, idx);
827  ArrayRCP<const scalar_t> wgtArray = arcp(weights, 0,
828  stride*nLocalVertices_,
829  false);
830  weightInfo[idx] = input_t(wgtArray, stride);
831  }
832  }
833 
834  vWeights_ = arcp<input_t>(weightInfo, 0, nWeightsPerVertex_, true);
835  }
836 
837  // Compute global values
838  if (localGraph_) {
839  nGlobalVertices_ = nLocalVertices_;
840  nGlobalEdges_ = nLocalEdges_;
841  }
842  else {
843  reduceAll<int, size_t>(*comm_, Teuchos::REDUCE_SUM, 1,
844  &nLocalVertices_, &nGlobalVertices_);
845  reduceAll<int, size_t>(*comm_, Teuchos::REDUCE_SUM, 1,
846  &nLocalEdges_, &nGlobalEdges_);
847  }
848 
849  env_->memory("After construction of graph model");
850 }
851 
853 
854 template <typename Adapter>
855 template <typename AdapterWithCoords>
856 void GraphModel<Adapter>::shared_GetVertexCoords(const AdapterWithCoords *ia)
857 {
858  // get pointers to vertex coordinates from input adapter
859 
860  vCoordDim_ = ia->getDimension();
861 
862  if (vCoordDim_ > 0){
863  input_t *coordInfo = new input_t [vCoordDim_];
864  env_->localMemoryAssertion(__FILE__, __LINE__, vCoordDim_, coordInfo);
865 
866  for (int dim=0; dim < vCoordDim_; dim++){
867  const scalar_t *coords=NULL;
868  int stride=0;
869  ia->getCoordinatesView(coords, stride, dim);
870  ArrayRCP<const scalar_t> coordArray = arcp(coords, 0,
871  stride*nLocalVertices_,
872  false);
873  coordInfo[dim] = input_t(coordArray, stride);
874  }
875 
876  vCoords_ = arcp<input_t>(coordInfo, 0, vCoordDim_, true);
877  }
878 }
879 
881  template <typename Adapter>
882 void GraphModel<Adapter>::print()
883 {
884 // if (env_->getDebugLevel() < VERBOSE_DETAILED_STATUS)
885 // return;
886 
887  std::ostream *os = env_->getDebugOStream();
888 
889  int me = comm_->getRank();
890 
891  *os << me
892  << " " << (localGraph_ ? "LOCAL GRAPH " : "GLOBAL GRAPH ")
893  << " Nvtx " << nLocalVertices_
894  << " Nedge " << nLocalEdges_
895  << " NVWgt " << nWeightsPerVertex_
896  << " NEWgt " << nWeightsPerEdge_
897  << " CDim " << vCoordDim_
898  << std::endl;
899 
900  for (size_t i = 0; i < nLocalVertices_; i++) {
901  *os << me << " " << i << " GID " << vGids_[i] << ": ";
902  for (lno_t j = eOffsets_[i]; j < eOffsets_[i+1]; j++)
903  *os << eGids_[j] << " " ;
904  *os << std::endl;
905  }
906 
907  if (nWeightsPerVertex_) {
908  for (size_t i = 0; i < nLocalVertices_; i++) {
909  *os << me << " " << i << " VWGTS " << vGids_[i] << ": ";
910  for (int j = 0; j < nWeightsPerVertex_; j++)
911  *os << vWeights_[j][i] << " ";
912  *os << std::endl;
913  }
914  }
915 
916  if (nWeightsPerEdge_) {
917  for (size_t i = 0; i < nLocalVertices_; i++) {
918  *os << me << " " << i << " EWGTS " << vGids_[i] << ": ";
919  for (lno_t j = eOffsets_[i]; j < eOffsets_[i+1]; j++) {
920  *os << eGids_[j] << " (";
921  for (int w = 0; w < nWeightsPerEdge_; w++)
922  *os << eWeights_[w][j] << " ";
923  *os << ") ";
924  }
925  *os << std::endl;
926  }
927  }
928 
929  if (vCoordDim_) {
930  for (size_t i = 0; i < nLocalVertices_; i++) {
931  *os << me << " " << i << " COORDS " << vGids_[i] << ": ";
932  for (int j = 0; j < vCoordDim_; j++)
933  *os << vCoords_[j][i] << " ";
934  *os << std::endl;
935  }
936  }
937  else
938  *os << me << " NO COORDINATES AVAIL " << std::endl;
939 }
940 
941 } // namespace Zoltan2
942 
943 
944 #endif
945 
use columns as graph vertices
size_t getLocalNumObjects() const
Return the local number of objects.
Time an algorithm (or other entity) as a whole.
int getNumWeightsPerVertex() const
Returns the number (0 or greater) of weights per vertex.
size_t getGlobalNumEdges() const
Returns the global number edges. For local graphs, the number of global edges is the number of local ...
IdentifierAdapter defines the interface for identifiers.
ignore invalid neighbors
fast typical checks for valid arguments
#define Z2_FORWARD_EXCEPTIONS
Forward an exception back through call stack.
GraphModel(const RCP< const VectorAdapter< userCoord_t > > &ia, const RCP< const Environment > &env, const RCP< const Comm< int > > &comm, modelFlag_t &flags)
MatrixAdapter defines the adapter interface for matrices.
Defines the Model interface.
GraphAdapter defines the interface for graph-based user data.
algorithm requires consecutive ids
size_t getLocalNumVertices() const
Returns the number vertices on this process.
Defines the MeshAdapter interface.
MeshAdapter defines the interface for mesh input.
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
model must symmetrize input
Defines the IdentifierAdapter interface.
size_t getLocalNumEdges() const
Returns the number of edges on this process. In global or subset graphs, includes off-process edges...
Defines the VectorAdapter interface.
GraphModel(const RCP< const MatrixAdapter< user_t, userCoord_t > > &ia, const RCP< const Environment > &env, const RCP< const Comm< int > > &comm, modelFlag_t &modelFlags)
Constructor.
model must symmetrize input
static ArrayRCP< ArrayRCP< zscalar_t > > weights
void get2ndAdjsViewFromAdjs(const Teuchos::RCP< const MeshAdapter< User > > &ia, const RCP< const Comm< int > > comm, Zoltan2::MeshEntityType sourcetarget, Zoltan2::MeshEntityType through, Teuchos::ArrayRCP< typename MeshAdapter< User >::lno_t > &offsets, Teuchos::ArrayRCP< typename MeshAdapter< User >::gno_t > &adjacencyIds)
size_t getGlobalNumVertices() const
Returns the global number vertices.
size_t getEdgeList(ArrayView< const gno_t > &edgeIds, ArrayView< const lno_t > &offsets, ArrayView< input_t > &wgts) const
Sets pointers to this process&#39; edge (neighbor) global Ids, including off-process edges.
Defines helper functions for use in the models.
algorithm requires no self edges
int getNumWeightsPerEdge() const
Returns the number (0 or greater) of weights per edge.
use nonzeros as graph vertices
void getVertexDist(ArrayView< size_t > &vtxdist) const
Return the vtxDist array Array of size comm->getSize() + 1 Array[n+1] - Array[n] is number of vertice...
VectorAdapter defines the interface for vector input.
The StridedData class manages lists of weights or coordinates.
Traits for application input objects.
size_t getVertexList(ArrayView< const gno_t > &Ids, ArrayView< input_t > &wgts) const
Sets pointers to this process&#39; vertex Ids and their weights.
GraphModel defines the interface required for graph models.
MeshEntityType
Enumerate entity types for meshes: Regions, Faces, Edges, or Vertices.
Defines the MatrixAdapter interface.
The base class for all model classes.
size_t getGlobalNumObjects() const
Return the global number of objects.
size_t getVertexCoords(ArrayView< input_t > &xyz) const
Sets pointers to this process&#39; vertex coordinates, if available. Order of coordinate info matches tha...
Defines the GraphAdapter interface.
GraphModel(const RCP< const IdentifierAdapter< user_t > > &ia, const RCP< const Environment > &env, const RCP< const Comm< int > > &comm, modelFlag_t &flags)
const RCP< const Comm< int > > getComm()
Return the communicator used by the model.
model represents graph within only one rank
This file defines the StridedData class.
int getCoordinateDim() const
Returns the dimension (0 to 3) of vertex coordinates.