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));
519 if (!ia->avail2ndAdjs(primaryEType, secondAdjEType)) {
530 nLocalEdges_ = eOffsets_[nLocalVertices_];
537 gno_t
const *nborIds=NULL;
538 lno_t
const *offsets=NULL;
540 ia->get2ndAdjsView(primaryEType, secondAdjEType, offsets, nborIds);
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));
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);
564 for (
int w=0; w < nWeightsPerEdge_; w++){
565 const scalar_t *ewgts=NULL;
568 ia->get2ndAdjWeightsView(primaryEType, secondAdjEType,
571 ArrayRCP<const scalar_t> wgtArray(ewgts, 0,
572 nLocalEdges_*stride,
false);
573 eWeights_[w] = input_t(wgtArray, stride);
578 shared_constructor(ia, modelFlags);
582 shared_GetVertexCoords<adapterWithCoords_t>(&(*ia));
584 env_->timerStop(
MACRO_TIMERS,
"GraphModel constructed from MeshAdapter");
590 template <
typename Adapter>
592 const RCP<const Adapter> &ia,
602 size_t adapterNLocalEdges = nLocalEdges_;
603 ArrayRCP<gno_t> adapterVGids = vGids_;
604 ArrayRCP<gno_t> adapterEGids = eGids_;
605 ArrayRCP<lno_t> adapterEOffsets = eOffsets_;
606 ArrayRCP<input_t> adapterEWeights = eWeights_;
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);
624 scalar_t **tmpEWeights = NULL;
625 if (nWeightsPerEdge_ > 0){
626 eWeights_ = arcp(
new input_t[nWeightsPerEdge_], 0,
627 nWeightsPerEdge_,
true);
630 tmpEWeights =
new scalar_t*[nWeightsPerEdge_];
631 for (
int w = 0; w < nWeightsPerEdge_; w++)
632 tmpEWeights[w] =
new scalar_t[adapterNLocalEdges];
636 std::unordered_map<gno_t, lno_t> globalToLocal(nLocalVertices_);
637 for (
size_t i = 0; i < nLocalVertices_; i++)
638 globalToLocal[adapterVGids[i]] = i;
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++) {
647 if (removeSelfEdges && (adapterEGids[j] == adapterVGids[i]))
651 typename std::unordered_map<gno_t, lno_t>::iterator localidx;
652 if ((localidx = globalToLocal.find(adapterEGids[j])) !=
653 globalToLocal.end()) {
656 eGids_[ecnt] = localidx->second;
657 for (
int w = 0; w < nWeightsPerEdge_; w++)
658 tmpEWeights[w][ecnt] = adapterEWeights[w][j];
663 eOffsets_[i+1] = ecnt;
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);
672 delete [] tmpEWeights;
676 else if (consecutiveIdsRequired || removeSelfEdges || subsetGraph) {
684 if (consecutiveIdsRequired) {
686 vGids_ = arcp(
new gno_t[nLocalVertices_], 0, nLocalVertices_,
true);
689 int np = comm_->getSize();
690 vtxDist_ = arcp(
new size_t[np+1], 0, np+1,
true);
692 Teuchos::gatherAll(*comm_, 1, &nLocalVertices_, np, &vtxDist_[1]);
693 for (
int i = 0; i < np; i++)
694 vtxDist_[i+1] += vtxDist_[i];
700 eGids_ = arcp(
new gno_t[adapterNLocalEdges],
701 0, adapterNLocalEdges,
true);
703 scalar_t **tmpEWeights = NULL;
704 if (subsetGraph || removeSelfEdges) {
706 eOffsets_ = arcp(
new lno_t[nLocalVertices_+1],
707 0, nLocalVertices_+1,
true);
711 if (nWeightsPerEdge_ > 0){
712 eWeights_ = arcp(
new input_t[nWeightsPerEdge_], 0,
713 nWeightsPerEdge_,
true);
716 tmpEWeights =
new scalar_t*[nWeightsPerEdge_];
717 for (
int w = 0; w < nWeightsPerEdge_; w++)
718 tmpEWeights[w] =
new scalar_t[adapterNLocalEdges];
723 Teuchos::ArrayRCP<int> edgeRemoteRanks;
724 Teuchos::ArrayRCP<lno_t> edgeRemoteLids;
725 std::unordered_map<gno_t, size_t> edgeRemoteUniqueMap;
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_);
736 Teuchos::ArrayRCP<gno_t> edgeRemoteUniqueGids =
737 arcp(
new gno_t[adapterNLocalEdges], 0, adapterNLocalEdges,
true);
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;
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());
757 int me = comm_->getRank();
758 for (
size_t i = 0; i < nLocalVertices_; i++) {
760 if (consecutiveIdsRequired)
761 vGids_[i] = vtxDist_[me] + i;
763 for (lno_t j = adapterEOffsets[i]; j < adapterEOffsets[i+1]; j++) {
765 if (removeSelfEdges && (adapterVGids[i] == adapterEGids[j]))
768 size_t remoteIdx = edgeRemoteUniqueMap[adapterEGids[j]];
770 if (subsetGraph && (edgeRemoteRanks[remoteIdx] == -1))
774 if (consecutiveIdsRequired)
777 eGids_[ecnt] = edgeRemoteLids[remoteIdx]
778 + vtxDist_[edgeRemoteRanks[remoteIdx]];
780 eGids_[ecnt] = adapterEGids[j];
782 if (subsetGraph || removeSelfEdges) {
784 for (
int w = 0; w < nWeightsPerEdge_; w++)
785 tmpEWeights[w][ecnt] = adapterEWeights[w][j];
790 if (subsetGraph || removeSelfEdges)
791 eOffsets_[i+1] = 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);
800 delete [] tmpEWeights;
805 nWeightsPerVertex_ = ia->getNumWeightsPerID();
807 if (nWeightsPerVertex_ > 0){
808 input_t *weightInfo =
new input_t [nWeightsPerVertex_];
809 env_->localMemoryAssertion(__FILE__, __LINE__, nWeightsPerVertex_,
812 for (
int idx=0; idx < nWeightsPerVertex_; idx++){
813 bool useNumNZ = ia->useDegreeAsWeight(idx);
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);
826 ia->getWeightsView(
weights, stride, idx);
827 ArrayRCP<const scalar_t> wgtArray = arcp(
weights, 0,
828 stride*nLocalVertices_,
830 weightInfo[idx] = input_t(wgtArray, stride);
834 vWeights_ = arcp<input_t>(weightInfo, 0, nWeightsPerVertex_,
true);
839 nGlobalVertices_ = nLocalVertices_;
840 nGlobalEdges_ = nLocalEdges_;
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_);
849 env_->memory(
"After construction of graph model");
854 template <
typename Adapter>
855 template <
typename AdapterWithCoords>
856 void GraphModel<Adapter>::shared_GetVertexCoords(
const AdapterWithCoords *ia)
860 vCoordDim_ = ia->getDimension();
863 input_t *coordInfo =
new input_t [vCoordDim_];
864 env_->localMemoryAssertion(__FILE__, __LINE__, vCoordDim_, coordInfo);
866 for (
int dim=0; dim < vCoordDim_; dim++){
867 const scalar_t *coords=NULL;
869 ia->getCoordinatesView(coords, stride, dim);
870 ArrayRCP<const scalar_t> coordArray = arcp(coords, 0,
871 stride*nLocalVertices_,
873 coordInfo[dim] = input_t(coordArray, stride);
876 vCoords_ = arcp<input_t>(coordInfo, 0, vCoordDim_,
true);
881 template <
typename Adapter>
882 void GraphModel<Adapter>::print()
887 std::ostream *os = env_->getDebugOStream();
889 int me = comm_->getRank();
892 <<
" " << (localGraph_ ?
"LOCAL GRAPH " :
"GLOBAL GRAPH ")
893 <<
" Nvtx " << nLocalVertices_
894 <<
" Nedge " << nLocalEdges_
895 <<
" NVWgt " << nWeightsPerVertex_
896 <<
" NEWgt " << nWeightsPerEdge_
897 <<
" CDim " << vCoordDim_
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] <<
" " ;
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] <<
" ";
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] <<
" ";
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] <<
" ";
938 *os << me <<
" NO COORDINATES AVAIL " << std::endl;
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.
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
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' 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.
size_t getVertexList(ArrayView< const gno_t > &Ids, ArrayView< input_t > &wgts) const
Sets pointers to this process' 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' 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.