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)
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  gno_t const *nborIds=NULL;
519  lno_t const *offsets=NULL;
520 
521  if (!ia->avail2ndAdjs(primaryEType, secondAdjEType)) {
522  // KDDKDD TODO Want to do this differently for local and global graphs?
523  // KDDKDD TODO Currently getting global 2nd Adjs and filtering them for
524  // KDDKDD TODO local graphs. That approach is consistent with other
525  // KDDKDD TODO adapters, but is more expensive -- why build them just to
526  // KDDKDD TODO throw them away? Instead, perhaps should build
527  // KDDKDD TODO only local adjacencies.
528  // KDDKDD TODO Does it suffice to pass a serial comm for local graph?
529  try {
530  get2ndAdjsViewFromAdjs(ia, comm_, primaryEType, secondAdjEType, offsets,
531  nborIds);
532  }
534  }
535  else { // avail2ndAdjs
536  // Get the edges
537  try {
538  ia->get2ndAdjsView(primaryEType, secondAdjEType, offsets, nborIds);
539  }
541  }
542 
543  // Save the pointers from the input adapter
544  nLocalEdges_ = offsets[nLocalVertices_];
545  eGids_ = arcp_const_cast<gno_t>(
546  arcp<const gno_t>(nborIds, 0, nLocalEdges_, false));
547  eOffsets_ = arcp_const_cast<lno_t>(
548  arcp<const lno_t>(offsets, 0, nLocalVertices_+1, false));
549 
550  // Edge weights
551  // Cannot specify edge weights if Zoltan2 computes the second adjacencies;
552  // there's no way to know the correct order for the adjacencies and weights.
553  // InputAdapter must provide 2nd adjs in order for edge weights to be used.
554  if (ia->avail2ndAdjs(primaryEType, secondAdjEType)) {
555  nWeightsPerEdge_ = ia->getNumWeightsPer2ndAdj(primaryEType, secondAdjEType);
556  if (nWeightsPerEdge_ > 0){
557  input_t *wgts = new input_t [nWeightsPerEdge_];
558  eWeights_ = arcp(wgts, 0, nWeightsPerEdge_, true);
559  }
560 
561  for (int w=0; w < nWeightsPerEdge_; w++){
562  const scalar_t *ewgts=NULL;
563  int stride=0;
564 
565  ia->get2ndAdjWeightsView(primaryEType, secondAdjEType,
566  ewgts, stride, w);
567 
568  ArrayRCP<const scalar_t> wgtArray(ewgts, 0,
569  nLocalEdges_*stride, false);
570  eWeights_[w] = input_t(wgtArray, stride);
571  }
572  }
573 
574  // Do constructor common to all adapters
575  shared_constructor(ia, modelFlags);
576 
577  // Get vertex coordinates
578  typedef MeshAdapter<user_t> adapterWithCoords_t;
579  shared_GetVertexCoords<adapterWithCoords_t>(&(*ia));
580 
581  env_->timerStop(MACRO_TIMERS, "GraphModel constructed from MeshAdapter");
582  print();
583 }
584 
585 
587 template <typename Adapter>
589  const RCP<const Adapter> &ia,
590  modelFlag_t &modelFlags)
591 {
592  // Model creation flags
593  bool consecutiveIdsRequired = modelFlags.test(GENERATE_CONSECUTIVE_IDS);
594  bool removeSelfEdges = modelFlags.test(REMOVE_SELF_EDGES);
595  bool subsetGraph = modelFlags.test(BUILD_SUBSET_GRAPH);
596 
597  // May modify the graph provided from input adapter; save pointers to
598  // the input adapter's data.
599  size_t adapterNLocalEdges = nLocalEdges_;
600  ArrayRCP<gno_t> adapterVGids = vGids_; // vertices of graph from adapter
601  ArrayRCP<gno_t> adapterEGids = eGids_; // edges of graph from adapter
602  ArrayRCP<lno_t> adapterEOffsets = eOffsets_; // edge offsets from adapter
603  ArrayRCP<input_t> adapterEWeights = eWeights_; // edge weights from adapter
604 
605  if (localGraph_) {
606  // Local graph is requested.
607  // Renumber vertices 0 to nLocalVertices_-1
608  // Filter out off-process edges
609  // Renumber edge neighbors to be in range [0,nLocalVertices_-1]
610 
611  // Allocate new space for local graph info
612  // Note that eGids_ and eWeights_[w] may be larger than needed;
613  // we would have to pre-count the number of local edges to avoid overalloc
614  vGids_ = arcp(new gno_t[nLocalVertices_],
615  0, nLocalVertices_, true);
616  eGids_ = arcp(new gno_t[adapterNLocalEdges],
617  0, adapterNLocalEdges, true);
618  eOffsets_ = arcp(new lno_t[nLocalVertices_+1],
619  0, nLocalVertices_+1, true);
620 
621  scalar_t **tmpEWeights = NULL;
622  if (nWeightsPerEdge_ > 0){
623  eWeights_ = arcp(new input_t[nWeightsPerEdge_], 0,
624  nWeightsPerEdge_, true);
625  // Need to use temporary array because StridedData has const data
626  // so we can't write to it.
627  tmpEWeights = new scalar_t*[nWeightsPerEdge_];
628  for (int w = 0; w < nWeightsPerEdge_; w++)
629  tmpEWeights[w] = new scalar_t[adapterNLocalEdges];
630  }
631 
632  // Build map between global and local vertex numbers
633  std::unordered_map<gno_t, lno_t> globalToLocal(nLocalVertices_);
634  for (size_t i = 0; i < nLocalVertices_; i++)
635  globalToLocal[adapterVGids[i]] = i;
636 
637  // Loop over edges; keep only those that are local (i.e., on-rank)
638  eOffsets_[0] = 0;
639  lno_t ecnt = 0;
640  for (size_t i = 0; i < nLocalVertices_; i++) {
641  vGids_[i] = gno_t(i);
642  for (lno_t j = adapterEOffsets[i]; j < adapterEOffsets[i+1]; j++) {
643 
644  if (removeSelfEdges && (adapterEGids[j] == adapterVGids[i]))
645  continue; // Skipping self edge
646 
647  // Determine whether neighbor vertex is local
648  typename std::unordered_map<gno_t, lno_t>::iterator localidx;
649  if ((localidx = globalToLocal.find(adapterEGids[j])) !=
650  globalToLocal.end()) {
651  // neighbor vertex is local
652  // Keep the edge and its weights
653  eGids_[ecnt] = localidx->second;
654  for (int w = 0; w < nWeightsPerEdge_; w++)
655  tmpEWeights[w][ecnt] = adapterEWeights[w][j];
656 
657  ecnt++;
658  }
659  }
660  eOffsets_[i+1] = ecnt;
661  }
662  nLocalEdges_ = eOffsets_[nLocalVertices_];
663  if (nWeightsPerEdge_) {
664  for (int w = 0; w < nWeightsPerEdge_; w++) {
665  ArrayRCP<const scalar_t> wgtArray(tmpEWeights[w],
666  0, adapterNLocalEdges, true);
667  eWeights_[w] = input_t(wgtArray, 0);
668  }
669  delete [] tmpEWeights;
670  }
671  } // localGraph_
672 
673  else if (consecutiveIdsRequired || removeSelfEdges || subsetGraph) {
674  // Build a Global graph
675  // If we are here, we expect SOMETHING in the graph to change from input:
676  // removing self edges, or converting to consecutive IDs, or subsetting
677  // the graph.
678 
679 
680  // Determine vertex GIDs for the global GraphModel
681  if (consecutiveIdsRequired) {
682  // Allocate new memory for vertices for consecutiveIds
683  vGids_ = arcp(new gno_t[nLocalVertices_], 0, nLocalVertices_, true);
684 
685  // Build vtxDist_ array with starting vGid on each rank
686  int np = comm_->getSize();
687  vtxDist_ = arcp(new size_t[np+1], 0, np+1, true);
688  vtxDist_[0] = 0;
689  Teuchos::gatherAll(*comm_, 1, &nLocalVertices_, np, &vtxDist_[1]);
690  for (int i = 0; i < np; i++)
691  vtxDist_[i+1] += vtxDist_[i];
692  }
693 
694  // Allocate new memory for edges and offsets, as needed
695  // Note that eGids_ may or may not be larger than needed;
696  // would have to pre-count number of edges kept otherwise
697  eGids_ = arcp(new gno_t[adapterNLocalEdges],
698  0, adapterNLocalEdges, true);
699 
700  scalar_t **tmpEWeights = NULL;
701  if (subsetGraph || removeSelfEdges) {
702  // May change number of edges and, thus, the offsets
703  eOffsets_ = arcp(new lno_t[nLocalVertices_+1],
704  0, nLocalVertices_+1, true);
705  eOffsets_[0] = 0;
706 
707  // Need to copy weights if remove edges
708  if (nWeightsPerEdge_ > 0){
709  eWeights_ = arcp(new input_t[nWeightsPerEdge_], 0,
710  nWeightsPerEdge_, true);
711  // Need to use temporary array because StridedData has const data
712  // so we can't write to it.
713  tmpEWeights = new scalar_t*[nWeightsPerEdge_];
714  for (int w = 0; w < nWeightsPerEdge_; w++)
715  tmpEWeights[w] = new scalar_t[adapterNLocalEdges];
716  }
717  }
718 
719  // If needed, determine the owning ranks and its local index off-proc
720  Teuchos::ArrayRCP<int> edgeRemoteRanks;
721  Teuchos::ArrayRCP<lno_t> edgeRemoteLids;
722  std::unordered_map<gno_t, size_t> edgeRemoteUniqueMap;
723 
724  if (subsetGraph || consecutiveIdsRequired) {
725  gno_t dummy = Teuchos::OrdinalTraits<gno_t>::invalid();
726  Tpetra::Map<lno_t,gno_t> vtxMap(dummy, adapterVGids(), 0, comm_);
727 
728  // Need to filter requested edges to make a unique list,
729  // as Tpetra::Map does not return correct info for duplicated entries
730  // (See bug 6412)
731  // The local filter may be more efficient anyway -- fewer communicated
732  // values in the Tpetra directory
733  Teuchos::ArrayRCP<gno_t> edgeRemoteUniqueGids =
734  arcp(new gno_t[adapterNLocalEdges], 0, adapterNLocalEdges, true);
735 
736  size_t nEdgeUnique = 0;
737  for (size_t i = 0; i < adapterNLocalEdges; i++) {
738  if (edgeRemoteUniqueMap.find(adapterEGids[i]) ==
739  edgeRemoteUniqueMap.end()) {
740  edgeRemoteUniqueGids[nEdgeUnique] = adapterEGids[i];
741  edgeRemoteUniqueMap[adapterEGids[i]] = nEdgeUnique;
742  nEdgeUnique++;
743  }
744  }
745 
746  edgeRemoteRanks = arcp(new int[nEdgeUnique], 0, nEdgeUnique, true);
747  edgeRemoteLids = arcp(new lno_t[nEdgeUnique], 0, nEdgeUnique, true);
748  vtxMap.getRemoteIndexList(edgeRemoteUniqueGids(0, nEdgeUnique),
749  edgeRemoteRanks(), edgeRemoteLids());
750  }
751 
752  // Renumber and/or filter the edges and vertices
753  lno_t ecnt = 0;
754  int me = comm_->getRank();
755  for (size_t i = 0; i < nLocalVertices_; i++) {
756 
757  if (consecutiveIdsRequired)
758  vGids_[i] = vtxDist_[me] + i;
759 
760  for (lno_t j = adapterEOffsets[i]; j < adapterEOffsets[i+1]; j++) {
761 
762  if (removeSelfEdges && (adapterVGids[i] == adapterEGids[j]))
763  continue; // Skipping self edge
764 
765  size_t remoteIdx = edgeRemoteUniqueMap[adapterEGids[j]];
766 
767  if (subsetGraph && (edgeRemoteRanks[remoteIdx] == -1))
768  continue; // Skipping edge with neighbor vertex that was not found
769  // in communicator
770 
771  if (consecutiveIdsRequired)
772  // Renumber edge using local number on remote rank plus first
773  // vtx number for remote rank
774  eGids_[ecnt] = edgeRemoteLids[remoteIdx]
775  + vtxDist_[edgeRemoteRanks[remoteIdx]];
776  else
777  eGids_[ecnt] = adapterEGids[j];
778 
779  if (subsetGraph || removeSelfEdges) {
780  // Need to copy weights only if number of edges might change
781  for (int w = 0; w < nWeightsPerEdge_; w++)
782  tmpEWeights[w][ecnt] = adapterEWeights[w][j];
783  }
784 
785  ecnt++;
786  }
787  if (subsetGraph || removeSelfEdges)
788  eOffsets_[i+1] = ecnt;
789  }
790  nLocalEdges_ = ecnt;
791  if (nWeightsPerEdge_ && (subsetGraph || removeSelfEdges)) {
792  for (int w = 0; w < nWeightsPerEdge_; w++) {
793  ArrayRCP<const scalar_t> wgtArray(tmpEWeights[w],
794  0, nLocalEdges_, true);
795  eWeights_[w] = input_t(wgtArray, 1);
796  }
797  delete [] tmpEWeights;
798  }
799  }
800 
801  // Vertex weights
802  nWeightsPerVertex_ = ia->getNumWeightsPerID();
803 
804  if (nWeightsPerVertex_ > 0){
805  input_t *weightInfo = new input_t [nWeightsPerVertex_];
806  env_->localMemoryAssertion(__FILE__, __LINE__, nWeightsPerVertex_,
807  weightInfo);
808 
809  for (int idx=0; idx < nWeightsPerVertex_; idx++){
810  bool useNumNZ = ia->useDegreeAsWeight(idx);
811  if (useNumNZ){
812  scalar_t *wgts = new scalar_t [nLocalVertices_];
813  env_->localMemoryAssertion(__FILE__, __LINE__, nLocalVertices_, wgts);
814  ArrayRCP<const scalar_t> wgtArray = arcp(wgts,
815  0, nLocalVertices_, true);
816  for (size_t i=0; i < nLocalVertices_; i++)
817  wgts[i] = eOffsets_[i+1] - eOffsets_[i];
818  weightInfo[idx] = input_t(wgtArray, 1);
819  }
820  else{
821  const scalar_t *weights=NULL;
822  int stride=0;
823  ia->getWeightsView(weights, stride, idx);
824  ArrayRCP<const scalar_t> wgtArray = arcp(weights, 0,
825  stride*nLocalVertices_,
826  false);
827  weightInfo[idx] = input_t(wgtArray, stride);
828  }
829  }
830 
831  vWeights_ = arcp<input_t>(weightInfo, 0, nWeightsPerVertex_, true);
832  }
833 
834  // Compute global values
835  if (localGraph_) {
836  nGlobalVertices_ = nLocalVertices_;
837  nGlobalEdges_ = nLocalEdges_;
838  }
839  else {
840  reduceAll<int, size_t>(*comm_, Teuchos::REDUCE_SUM, 1,
841  &nLocalVertices_, &nGlobalVertices_);
842  reduceAll<int, size_t>(*comm_, Teuchos::REDUCE_SUM, 1,
843  &nLocalEdges_, &nGlobalEdges_);
844  }
845 
846  env_->memory("After construction of graph model");
847 }
848 
850 
851 template <typename Adapter>
852 template <typename AdapterWithCoords>
853 void GraphModel<Adapter>::shared_GetVertexCoords(const AdapterWithCoords *ia)
854 {
855  // get pointers to vertex coordinates from input adapter
856 
857  vCoordDim_ = ia->getDimension();
858 
859  if (vCoordDim_ > 0){
860  input_t *coordInfo = new input_t [vCoordDim_];
861  env_->localMemoryAssertion(__FILE__, __LINE__, vCoordDim_, coordInfo);
862 
863  for (int dim=0; dim < vCoordDim_; dim++){
864  const scalar_t *coords=NULL;
865  int stride=0;
866  ia->getCoordinatesView(coords, stride, dim);
867  ArrayRCP<const scalar_t> coordArray = arcp(coords, 0,
868  stride*nLocalVertices_,
869  false);
870  coordInfo[dim] = input_t(coordArray, stride);
871  }
872 
873  vCoords_ = arcp<input_t>(coordInfo, 0, vCoordDim_, true);
874  }
875 }
876 
878  template <typename Adapter>
880 {
881 // if (env_->getDebugLevel() < VERBOSE_DETAILED_STATUS)
882 // return;
883 
884  std::ostream *os = env_->getDebugOStream();
885 
886  int me = comm_->getRank();
887 
888  *os << me
889  << " " << (localGraph_ ? "LOCAL GRAPH " : "GLOBAL GRAPH ")
890  << " Nvtx " << nLocalVertices_
891  << " Nedge " << nLocalEdges_
892  << " NVWgt " << nWeightsPerVertex_
893  << " NEWgt " << nWeightsPerEdge_
894  << " CDim " << vCoordDim_
895  << std::endl;
896 
897  for (size_t i = 0; i < nLocalVertices_; i++) {
898  *os << me << " " << i << " GID " << vGids_[i] << ": ";
899  for (lno_t j = eOffsets_[i]; j < eOffsets_[i+1]; j++)
900  *os << eGids_[j] << " " ;
901  *os << std::endl;
902  }
903 
904  if (nWeightsPerVertex_) {
905  for (size_t i = 0; i < nLocalVertices_; i++) {
906  *os << me << " " << i << " VWGTS " << vGids_[i] << ": ";
907  for (int j = 0; j < nWeightsPerVertex_; j++)
908  *os << vWeights_[j][i] << " ";
909  *os << std::endl;
910  }
911  }
912 
913  if (nWeightsPerEdge_) {
914  for (size_t i = 0; i < nLocalVertices_; i++) {
915  *os << me << " " << i << " EWGTS " << vGids_[i] << ": ";
916  for (lno_t j = eOffsets_[i]; j < eOffsets_[i+1]; j++) {
917  *os << eGids_[j] << " (";
918  for (int w = 0; w < nWeightsPerEdge_; w++)
919  *os << eWeights_[w][j] << " ";
920  *os << ") ";
921  }
922  *os << std::endl;
923  }
924  }
925 
926  if (vCoordDim_) {
927  for (size_t i = 0; i < nLocalVertices_; i++) {
928  *os << me << " " << i << " COORDS " << vGids_[i] << ": ";
929  for (int j = 0; j < vCoordDim_; j++)
930  *os << vCoords_[j][i] << " ";
931  *os << std::endl;
932  }
933  }
934  else
935  *os << me << " NO COORDINATES AVAIL " << std::endl;
936 }
937 
938 } // namespace Zoltan2
939 
940 
941 #endif
942 
use columns as graph vertices
size_t getLocalNumEdges() const
Returns the number of edges on this process. In global or subset graphs, includes off-process edges...
size_t getVertexList(ArrayView< const gno_t > &Ids, ArrayView< input_t > &wgts) const
Sets pointers to this process&#39; vertex Ids and their weights.
Time an algorithm (or other entity) as a whole.
IdentifierAdapter defines the interface for identifiers.
ignore invalid neighbors
int getNumWeightsPerVertex() const
Returns the number (0 or greater) of weights per vertex.
size_t getGlobalNumObjects() const
Return the global number of objects.
void getVertexDist(ArrayView< size_t > &vtxdist)
Return the vtxDist array Array of size comm->getSize() + 1 Array[n+1] - Array[n] is number of vertice...
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
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.
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
size_t getGlobalNumVertices() const
Returns the global number vertices.
Defines helper functions for use in the models.
algorithm requires no self edges
int getCoordinateDim() const
Returns the dimension (0 to 3) of vertex coordinates.
size_t getVertexCoords(ArrayView< input_t > &xyz) const
Sets pointers to this process&#39; vertex coordinates, if available. Order of coordinate info matches tha...
void get2ndAdjsViewFromAdjs(const Teuchos::RCP< const MeshAdapter< User > > &ia, const RCP< const Comm< int > > comm, Zoltan2::MeshEntityType sourcetarget, Zoltan2::MeshEntityType through, const typename MeshAdapter< User >::lno_t *&offsets, const typename MeshAdapter< User >::gno_t *&adjacencyIds)
use nonzeros as graph 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.
size_t getGlobalNumEdges() const
Returns the global number edges. For local graphs, the number of global edges is the number of local ...
VectorAdapter defines the interface for vector input.
The StridedData class manages lists of weights or coordinates.
Traits for application input objects.
size_t getLocalNumVertices() const
Returns the number vertices on this process.
GraphModel defines the interface required for graph models.
MeshEntityType
Enumerate entity types for meshes: Regions, Faces, Edges, or Vertices.
size_t getLocalNumObjects() const
Return the local number of objects.
Defines the MatrixAdapter interface.
The base class for all model classes.
int getNumWeightsPerEdge() const
Returns the number (0 or greater) of weights per edge.
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.