50 #ifndef _ZOLTAN2_GRAPHMODEL_HPP_ 51 #define _ZOLTAN2_GRAPHMODEL_HPP_ 62 #include <unordered_map> 79 template <
typename Adapter>
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;
109 const RCP<const Environment> &env,
const RCP<
const Comm<int> > &comm,
113 const RCP<const Environment> &env,
const RCP<
const Comm<int> > &comm,
117 const RCP<const Environment> &env,
const RCP<
const Comm<int> > &comm,
121 const RCP<const Environment> &env,
const RCP<
const Comm<int> > &comm,
124 throw std::runtime_error(
"cannot build GraphModel from VectorAdapter");
128 const RCP<const Environment> &env,
const RCP<
const Comm<int> > &comm,
131 throw std::runtime_error(
"cannot build GraphModel from IdentifierAdapter");
136 const RCP<const Comm<int> >
getComm() {
return comm_; }
177 ArrayView<const gno_t> &Ids,
178 ArrayView<input_t> &wgts)
const 180 Ids = vGids_.view(0, nLocalVertices_);
181 wgts = vWeights_.view(0, nWeightsPerVertex_);
182 return nLocalVertices_;
193 xyz = vCoords_.view(0, vCoordDim_);
194 return nLocalVertices_;
213 ArrayView<const lno_t> &offsets,
214 ArrayView<input_t> &wgts)
const 216 edgeIds = eGids_.view(0, nLocalEdges_);
217 offsets = eOffsets_.view(0, nLocalVertices_+1);
218 wgts = eWeights_.view(0, nWeightsPerEdge_);
228 vtxdist = vtxDist_();
229 if (vtxDist_.size() == 0) {
230 throw std::runtime_error(
"getVertexDist is available only " 231 "when consecutiveIdsRequired");
245 void shared_constructor(
const RCP<const Adapter>&ia,
modelFlag_t &modelFlags);
247 template <
typename AdapterWithCoords>
248 void shared_GetVertexCoords(
const AdapterWithCoords *ia);
252 const RCP<const Environment > env_;
253 const RCP<const Comm<int> > comm_;
261 size_t nLocalVertices_;
262 size_t nGlobalVertices_;
263 ArrayRCP<gno_t> vGids_;
267 int nWeightsPerVertex_;
268 ArrayRCP<input_t> vWeights_;
271 ArrayRCP<input_t> vCoords_;
278 size_t nGlobalEdges_;
279 ArrayRCP<gno_t> eGids_;
280 ArrayRCP<lno_t> eOffsets_;
286 int nWeightsPerEdge_;
287 ArrayRCP<input_t> eWeights_;
292 ArrayRCP<size_t> vtxDist_;
301 template <
typename Adapter>
304 const RCP<const Environment> &env,
305 const RCP<
const Comm<int> > &comm,
313 nWeightsPerVertex_(0),
333 if (symTranspose || symBipartite || vertexCols || vertexNz){
334 throw std::runtime_error(
"graph build option not yet implemented");
338 gno_t
const *vtxIds=NULL, *nborIds=NULL;
339 lno_t
const *offsets=NULL;
341 nLocalVertices_ = ia->getLocalNumIDs();
342 ia->getIDsView(vtxIds);
346 if (ia->CRSViewAvailable()) {
347 ia->getCRSView(offsets, nborIds);
351 throw std::runtime_error(
"Only MatrixAdapter::getCRSView is supported " 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));
367 nWeightsPerEdge_ = 0;
371 shared_constructor(ia, modelFlags);
374 if (ia->coordinatesAvailable()) {
376 shared_GetVertexCoords<adapterWithCoords_t>(ia->getCoordinateInput());
384 template <
typename Adapter>
387 const RCP<const Environment> &env,
388 const RCP<
const Comm<int> > &comm,
396 nWeightsPerVertex_(0),
413 env_->localInputAssertion(__FILE__, __LINE__,
414 "GraphModel from GraphAdapter is implemented only for " 415 "Graph Vertices as primary object, not for Graph Edges",
420 gno_t
const *vtxIds=NULL, *nborIds=NULL;
421 lno_t
const *offsets=NULL;
423 nLocalVertices_ = ia->getLocalNumVertices();
424 ia->getVertexIDsView(vtxIds);
425 ia->getEdgesView(offsets, nborIds);
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));
439 nWeightsPerEdge_ = ia->getNumWeightsPerEdge();
440 if (nWeightsPerEdge_ > 0){
441 input_t *wgts =
new input_t [nWeightsPerEdge_];
442 eWeights_ = arcp(wgts, 0, nWeightsPerEdge_,
true);
445 for (
int w=0; w < nWeightsPerEdge_; w++){
446 const scalar_t *ewgts=NULL;
449 ia->getEdgeWeightsView(ewgts, stride, w);
451 ArrayRCP<const scalar_t> wgtArray(ewgts, 0, nLocalEdges_,
false);
452 eWeights_[w] = input_t(wgtArray, stride);
456 shared_constructor(ia, modelFlags);
459 if (ia->coordinatesAvailable()) {
461 shared_GetVertexCoords<adapterWithCoords_t>(ia->getCoordinateInput());
468 template <
typename Adapter>
471 const RCP<const Environment> &env,
472 const RCP<
const Comm<int> > &comm,
480 nWeightsPerVertex_(0),
492 env_->timerStart(
MACRO_TIMERS,
"GraphModel constructed from MeshAdapter");
507 gno_t
const *vtxIds=NULL;
509 nLocalVertices_ = ia->getLocalNumOf(primaryEType);
510 ia->getIDsViewOf(primaryEType, vtxIds);
514 vGids_ = arcp_const_cast<gno_t>(
515 arcp<const gno_t>(vtxIds, 0, nLocalVertices_,
false));
518 gno_t
const *nborIds=NULL;
519 lno_t
const *offsets=NULL;
521 if (!ia->avail2ndAdjs(primaryEType, secondAdjEType)) {
538 ia->get2ndAdjsView(primaryEType, secondAdjEType, offsets, nborIds);
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));
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);
561 for (
int w=0; w < nWeightsPerEdge_; w++){
562 const scalar_t *ewgts=NULL;
565 ia->get2ndAdjWeightsView(primaryEType, secondAdjEType,
568 ArrayRCP<const scalar_t> wgtArray(ewgts, 0,
569 nLocalEdges_*stride,
false);
570 eWeights_[w] = input_t(wgtArray, stride);
575 shared_constructor(ia, modelFlags);
579 shared_GetVertexCoords<adapterWithCoords_t>(&(*ia));
581 env_->timerStop(
MACRO_TIMERS,
"GraphModel constructed from MeshAdapter");
587 template <
typename Adapter>
589 const RCP<const Adapter> &ia,
599 size_t adapterNLocalEdges = nLocalEdges_;
600 ArrayRCP<gno_t> adapterVGids = vGids_;
601 ArrayRCP<gno_t> adapterEGids = eGids_;
602 ArrayRCP<lno_t> adapterEOffsets = eOffsets_;
603 ArrayRCP<input_t> adapterEWeights = eWeights_;
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);
621 scalar_t **tmpEWeights = NULL;
622 if (nWeightsPerEdge_ > 0){
623 eWeights_ = arcp(
new input_t[nWeightsPerEdge_], 0,
624 nWeightsPerEdge_,
true);
627 tmpEWeights =
new scalar_t*[nWeightsPerEdge_];
628 for (
int w = 0; w < nWeightsPerEdge_; w++)
629 tmpEWeights[w] =
new scalar_t[adapterNLocalEdges];
633 std::unordered_map<gno_t, lno_t> globalToLocal(nLocalVertices_);
634 for (
size_t i = 0; i < nLocalVertices_; i++)
635 globalToLocal[adapterVGids[i]] = i;
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++) {
644 if (removeSelfEdges && (adapterEGids[j] == adapterVGids[i]))
648 typename std::unordered_map<gno_t, lno_t>::iterator localidx;
649 if ((localidx = globalToLocal.find(adapterEGids[j])) !=
650 globalToLocal.end()) {
653 eGids_[ecnt] = localidx->second;
654 for (
int w = 0; w < nWeightsPerEdge_; w++)
655 tmpEWeights[w][ecnt] = adapterEWeights[w][j];
660 eOffsets_[i+1] = ecnt;
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);
669 delete [] tmpEWeights;
673 else if (consecutiveIdsRequired || removeSelfEdges || subsetGraph) {
681 if (consecutiveIdsRequired) {
683 vGids_ = arcp(
new gno_t[nLocalVertices_], 0, nLocalVertices_,
true);
686 int np = comm_->getSize();
687 vtxDist_ = arcp(
new size_t[np+1], 0, np+1,
true);
689 Teuchos::gatherAll(*comm_, 1, &nLocalVertices_, np, &vtxDist_[1]);
690 for (
int i = 0; i < np; i++)
691 vtxDist_[i+1] += vtxDist_[i];
697 eGids_ = arcp(
new gno_t[adapterNLocalEdges],
698 0, adapterNLocalEdges,
true);
700 scalar_t **tmpEWeights = NULL;
701 if (subsetGraph || removeSelfEdges) {
703 eOffsets_ = arcp(
new lno_t[nLocalVertices_+1],
704 0, nLocalVertices_+1,
true);
708 if (nWeightsPerEdge_ > 0){
709 eWeights_ = arcp(
new input_t[nWeightsPerEdge_], 0,
710 nWeightsPerEdge_,
true);
713 tmpEWeights =
new scalar_t*[nWeightsPerEdge_];
714 for (
int w = 0; w < nWeightsPerEdge_; w++)
715 tmpEWeights[w] =
new scalar_t[adapterNLocalEdges];
720 Teuchos::ArrayRCP<int> edgeRemoteRanks;
721 Teuchos::ArrayRCP<lno_t> edgeRemoteLids;
722 std::unordered_map<gno_t, size_t> edgeRemoteUniqueMap;
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_);
733 Teuchos::ArrayRCP<gno_t> edgeRemoteUniqueGids =
734 arcp(
new gno_t[adapterNLocalEdges], 0, adapterNLocalEdges,
true);
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;
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());
754 int me = comm_->getRank();
755 for (
size_t i = 0; i < nLocalVertices_; i++) {
757 if (consecutiveIdsRequired)
758 vGids_[i] = vtxDist_[me] + i;
760 for (lno_t j = adapterEOffsets[i]; j < adapterEOffsets[i+1]; j++) {
762 if (removeSelfEdges && (adapterVGids[i] == adapterEGids[j]))
765 size_t remoteIdx = edgeRemoteUniqueMap[adapterEGids[j]];
767 if (subsetGraph && (edgeRemoteRanks[remoteIdx] == -1))
771 if (consecutiveIdsRequired)
774 eGids_[ecnt] = edgeRemoteLids[remoteIdx]
775 + vtxDist_[edgeRemoteRanks[remoteIdx]];
777 eGids_[ecnt] = adapterEGids[j];
779 if (subsetGraph || removeSelfEdges) {
781 for (
int w = 0; w < nWeightsPerEdge_; w++)
782 tmpEWeights[w][ecnt] = adapterEWeights[w][j];
787 if (subsetGraph || removeSelfEdges)
788 eOffsets_[i+1] = 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);
797 delete [] tmpEWeights;
802 nWeightsPerVertex_ = ia->getNumWeightsPerID();
804 if (nWeightsPerVertex_ > 0){
805 input_t *weightInfo =
new input_t [nWeightsPerVertex_];
806 env_->localMemoryAssertion(__FILE__, __LINE__, nWeightsPerVertex_,
809 for (
int idx=0; idx < nWeightsPerVertex_; idx++){
810 bool useNumNZ = ia->useDegreeAsWeight(idx);
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);
823 ia->getWeightsView(weights, stride, idx);
824 ArrayRCP<const scalar_t> wgtArray = arcp(weights, 0,
825 stride*nLocalVertices_,
827 weightInfo[idx] = input_t(wgtArray, stride);
831 vWeights_ = arcp<input_t>(weightInfo, 0, nWeightsPerVertex_,
true);
836 nGlobalVertices_ = nLocalVertices_;
837 nGlobalEdges_ = nLocalEdges_;
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_);
846 env_->memory(
"After construction of graph model");
851 template <
typename Adapter>
852 template <
typename AdapterWithCoords>
857 vCoordDim_ = ia->getDimension();
860 input_t *coordInfo =
new input_t [vCoordDim_];
861 env_->localMemoryAssertion(__FILE__, __LINE__, vCoordDim_, coordInfo);
863 for (
int dim=0; dim < vCoordDim_; dim++){
864 const scalar_t *coords=NULL;
866 ia->getCoordinatesView(coords, stride, dim);
867 ArrayRCP<const scalar_t> coordArray = arcp(coords, 0,
868 stride*nLocalVertices_,
870 coordInfo[dim] = input_t(coordArray, stride);
873 vCoords_ = arcp<input_t>(coordInfo, 0, vCoordDim_,
true);
878 template <
typename Adapter>
884 std::ostream *os = env_->getDebugOStream();
886 int me = comm_->getRank();
889 <<
" " << (localGraph_ ?
"LOCAL GRAPH " :
"GLOBAL GRAPH ")
890 <<
" Nvtx " << nLocalVertices_
891 <<
" Nedge " << nLocalEdges_
892 <<
" NVWgt " << nWeightsPerVertex_
893 <<
" NEWgt " << nWeightsPerEdge_
894 <<
" CDim " << vCoordDim_
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] <<
" " ;
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] <<
" ";
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] <<
" ";
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] <<
" ";
935 *os << me <<
" NO COORDINATES AVAIL " << std::endl;
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' vertex Ids and their weights.
Time an algorithm (or other entity) as a whole.
IdentifierAdapter defines the interface for identifiers.
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
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' 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' 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.
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.