Zoltan2 Version of the Day
Zoltan2_GraphModel.hpp
Go to the documentation of this file.
00001 // @HEADER
00002 //
00003 // ***********************************************************************
00004 //
00005 //   Zoltan2: A package of combinatorial algorithms for scientific computing
00006 //                  Copyright 2012 Sandia Corporation
00007 //
00008 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
00009 // the U.S. Government retains certain rights in this software.
00010 //
00011 // Redistribution and use in source and binary forms, with or without
00012 // modification, are permitted provided that the following conditions are
00013 // met:
00014 //
00015 // 1. Redistributions of source code must retain the above copyright
00016 // notice, this list of conditions and the following disclaimer.
00017 //
00018 // 2. Redistributions in binary form must reproduce the above copyright
00019 // notice, this list of conditions and the following disclaimer in the
00020 // documentation and/or other materials provided with the distribution.
00021 //
00022 // 3. Neither the name of the Corporation nor the names of the
00023 // contributors may be used to endorse or promote products derived from
00024 // this software without specific prior written permission.
00025 //
00026 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
00027 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00028 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00029 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
00030 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00031 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00032 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00033 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00034 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00035 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00036 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00037 //
00038 // Questions? Contact Karen Devine      (kddevin@sandia.gov)
00039 //                    Erik Boman        (egboman@sandia.gov)
00040 //                    Siva Rajamanickam (srajama@sandia.gov)
00041 //
00042 // ***********************************************************************
00043 //
00044 // @HEADER
00045 
00050 #ifndef _ZOLTAN2_GRAPHMODEL_HPP_
00051 #define _ZOLTAN2_GRAPHMODEL_HPP_
00052 
00053 #include <Zoltan2_Model.hpp>
00054 #include <Zoltan2_InputTraits.hpp>
00055 #include <Zoltan2_MatrixInput.hpp>
00056 #include <Zoltan2_GraphInput.hpp>
00057 #include <Zoltan2_IdentifierInput.hpp>
00058 #include <Zoltan2_CoordinateInput.hpp>
00059 #include <Zoltan2_VectorInput.hpp>
00060 #include <Zoltan2_StridedData.hpp>
00061 
00062 #include <vector>
00063 #include <Teuchos_Hashtable.hpp>
00064 
00065 namespace Zoltan2 {
00066 
00067 
00104 template <typename User> size_t removeUndesiredEdges(
00105   const RCP<const Environment> &env,
00106   int myRank,
00107   bool removeSelfEdges,
00108   bool removeOffProcessEdges,
00109   bool removeOffGroupEdges,
00110   ArrayView<const typename InputTraits<User>::gid_t> &gids,
00111   ArrayView<const typename InputTraits<User>::gid_t> &gidNbors,
00112   ArrayView<const int> &procIds,
00113   ArrayView<StridedData<typename InputTraits<User>::lno_t,
00114     typename InputTraits<User>::scalar_t> > &edgeWeights,
00115   ArrayView<const typename InputTraits<User>::lno_t> &offsets,
00116   ArrayRCP<const typename InputTraits<User>::gid_t> &newGidNbors, // out
00117   typename InputTraits<User>::scalar_t **&newWeights,       // out
00118   ArrayRCP<const typename InputTraits<User>::lno_t> &newOffsets)  // out
00119 {
00120   typedef typename InputTraits<User>::gid_t gid_t;
00121   typedef typename InputTraits<User>::scalar_t scalar_t;
00122   typedef typename InputTraits<User>::lno_t lno_t;
00123   typedef StridedData<lno_t, scalar_t> input_t;
00124   size_t numKeep = 0;
00125 
00126   size_t numVtx = offsets.size() - 1;
00127   size_t numNbors = gidNbors.size();
00128 
00129   env->localInputAssertion(__FILE__, __LINE__, "need more input",
00130     (!removeSelfEdges ||
00131       gids.size() >=
00132        static_cast<typename ArrayView<const gid_t>::size_type>(numVtx))
00133       &&
00134     (!removeOffProcessEdges ||
00135       procIds.size() >=
00136        static_cast<typename ArrayView<const int>::size_type>(numNbors)) &&
00137     (!removeOffGroupEdges ||
00138       procIds.size() >=
00139        static_cast<typename ArrayView<const int>::size_type>(numNbors)),
00140     BASIC_ASSERTION);
00141 
00142   // initialize edge weight array
00143 
00144   newWeights = NULL;
00145   int eDim = edgeWeights.size();
00146   std::vector<bool> uniformWeight;
00147   if (eDim > 0){
00148     for (int i=0; i < eDim; i++)
00149       uniformWeight[i] = (edgeWeights[i].size() == 0);
00150   }
00151 
00152   // count desired edges
00153 
00154   lno_t *offs = new lno_t [numVtx + 1];
00155   env->localMemoryAssertion(__FILE__, __LINE__, numVtx+1, offs);
00156   ArrayRCP<const lno_t> offArray = arcp(offs, 0, numVtx+1, true);
00157 
00158   const lno_t *allOffs = offsets.getRawPtr();
00159   const gid_t *allIds = gidNbors.getRawPtr();
00160 
00161   const gid_t *vtx = NULL;
00162   const int *proc = NULL;
00163 
00164   if (gids.size() > 0)
00165     vtx = gids.getRawPtr();
00166 
00167   if (procIds.size() > 0)
00168     proc = procIds.getRawPtr();
00169 
00170   offs[0] = 0;
00171   for (size_t i=0; i < numVtx; i++){
00172     offs[i+1] = 0;
00173     int vid = vtx ? vtx[i] : 0;
00174     for (lno_t j=allOffs[i]; j < allOffs[i+1]; j++){
00175       int owner = proc ? proc[j] : 0;
00176       bool keep = (!removeSelfEdges || vid != allIds[j]) &&
00177                (!removeOffProcessEdges || owner == myRank) &&
00178                (!removeOffGroupEdges || owner >= 0);
00179 
00180       if (keep)
00181         offs[i+1]++;
00182     }
00183   }
00184 
00185   // from counters to offsets
00186 
00187   for (size_t i=1; i < numVtx; i++)
00188     offs[i+1] += offs[i];
00189 
00190   numKeep = offs[numVtx];
00191 
00192   // do we need a new neighbor list?
00193 
00194   if (numNbors == numKeep){
00195     newGidNbors = Teuchos::arcpFromArrayView(gidNbors);
00196     newOffsets = Teuchos::arcpFromArrayView(offsets);
00197     return numNbors;
00198   }
00199   else if (numKeep == 0){
00200     newGidNbors = ArrayRCP<const gid_t>(Teuchos::null);
00201     newOffsets = ArrayRCP<const lno_t>(Teuchos::null);
00202     return 0;
00203   }
00204 
00205   // Build the subset neighbor lists (id, weight, and offset).
00206 
00207   gid_t *newGids = new gid_t [numKeep];
00208   env->localMemoryAssertion(__FILE__, __LINE__, numKeep, newGids);
00209 
00210   newGidNbors = arcp(newGids, 0, numKeep, true);
00211   newOffsets = offArray;
00212 
00213   if (eDim > 0){
00214     newWeights = new scalar_t * [eDim];
00215     env->localMemoryAssertion(__FILE__, __LINE__, eDim, newWeights);
00216 
00217     for (int w=0; w < eDim; w++){
00218       if (uniformWeight[w])
00219         newWeights[w] = NULL;  // implies uniform
00220       else{
00221         newWeights[w] = new scalar_t [numKeep];
00222         env->localMemoryAssertion(__FILE__, __LINE__, numKeep, newWeights[w]);
00223       }
00224     }
00225   }
00226 
00227   size_t next = 0;
00228   for (size_t i=0; i < numVtx && next < numKeep; i++){
00229     int vid = vtx ? vtx[i] : 0;
00230     for (lno_t j=allOffs[i]; j < allOffs[i+1]; j++){
00231       int owner = proc ? proc[j] : 0;
00232       bool keep = (!removeSelfEdges || vid != allIds[j]) &&
00233                (!removeOffProcessEdges || owner == myRank) &&
00234                (!removeOffGroupEdges || owner >= 0);
00235 
00236       if (keep){
00237         newGids[next] = allIds[j];
00238         if (eDim > 0){
00239           for (int w=0; w < eDim; w++){
00240             if (!uniformWeight[w])
00241               newWeights[w][next] = edgeWeights[w][j];
00242           }
00243         }
00244         next++;
00245         if (next == numKeep)
00246           break;
00247 
00248       }  // if (keep)
00249     }
00250   }
00251 
00252   return numKeep;
00253 }
00254 
00259 template <typename User> size_t computeLocalEdgeList(
00260   const RCP<const Environment> &env, int rank,
00261   size_t numLocalEdges,           // local edges
00262   size_t numLocalGraphEdges,      // edges in "local" graph
00263   RCP<const IdentifierMap<User> > &idMap,
00264   ArrayRCP<const typename InputTraits<User>::gid_t> &allEdgeIds, // in
00265   ArrayRCP<int> &allProcs,                                 // in
00266   ArrayRCP<const typename InputTraits<User>::lno_t> &allOffs,    // in
00267   ArrayRCP<StridedData<typename InputTraits<User>::lno_t,
00268     typename InputTraits<User>::scalar_t> > &allWeights,         // in
00269   ArrayRCP<const typename InputTraits<User>::lno_t> &edgeLocalIds, //
00270   ArrayRCP<const typename InputTraits<User>::lno_t> &offsets,      // out
00271   ArrayRCP<StridedData<typename InputTraits<User>::lno_t,
00272     typename InputTraits<User>::scalar_t> > &eWeights)             // out
00273 {
00274   typedef typename InputTraits<User>::gid_t gid_t;
00275   typedef typename InputTraits<User>::gno_t gno_t;
00276   typedef typename InputTraits<User>::scalar_t scalar_t;
00277   typedef typename InputTraits<User>::lno_t lno_t;
00278   typedef StridedData<lno_t, scalar_t> input_t;
00279 
00280   bool gnosAreGids = idMap->gnosAreGids();
00281 
00282   edgeLocalIds = ArrayRCP<const lno_t>(Teuchos::null);
00283   offsets = ArrayRCP<const lno_t>(Teuchos::null);
00284   eWeights = ArrayRCP<input_t>(Teuchos::null);
00285 
00286   if (numLocalGraphEdges == 0)
00287     return 0;
00288 
00289   if (numLocalGraphEdges == numLocalEdges){
00290 
00291     // Entire graph is local.
00292 
00293     lno_t *lnos = new lno_t [numLocalEdges];
00294     env->localMemoryAssertion(__FILE__, __LINE__,numLocalEdges, lnos);
00295     for (size_t i=0; i < numLocalEdges; i++)
00296       lnos[i] = i;
00297     edgeLocalIds = arcp(lnos, 0, numLocalEdges, true);
00298     offsets = allOffs;
00299     eWeights = allWeights;
00300   }
00301   else{
00302 
00303     // Create subset list of local graph edges, offsets and weights.
00304 
00305     int eWeightDim = allWeights.size();
00306 
00307     ArrayRCP<const gid_t> newEgids;
00308     scalar_t **newWeights = NULL;
00309 
00310     ArrayView<const gid_t> dummyVtx;
00311     ArrayView<const gid_t> nborView= allEdgeIds.view(0, numLocalEdges);
00312     ArrayView<const int> nborOwner = allProcs.view(0, numLocalEdges);
00313     ArrayView<input_t> eWgts = allWeights.view(0, eWeightDim);
00314     ArrayView<const lno_t> offView = allOffs.view(0, allOffs.size());
00315 
00316     try{
00317       numLocalEdges = removeUndesiredEdges<User>(
00318         env, rank,
00319         false, true, false,
00320         dummyVtx,
00321         nborView,
00322         nborOwner,
00323         eWgts,
00324         offView,
00325         newEgids,
00326         newWeights,
00327         offsets);
00328     }
00329     Z2_FORWARD_EXCEPTIONS;
00330 
00331     env->localBugAssertion(__FILE__, __LINE__, "local graph miscalculation",
00332       numLocalEdges == numLocalGraphEdges, BASIC_ASSERTION);
00333 
00334     // offsets array was set by removeUndesiredEdges.  Create weight array.
00335 
00336     if (eWeightDim > 0){
00337       input_t *wgts = new input_t [eWeightDim];
00338       for (int w=0; w < eWeightDim; w++){
00339         if (newWeights[w]){
00340           ArrayRCP<const scalar_t> wgtArray(
00341             newWeights[w], 0, numLocalGraphEdges, true);
00342           wgts[w] = input_t(wgtArray, 1);
00343         }
00344       }
00345       eWeights = arcp(wgts, 0, eWeightDim);
00346     }
00347 
00348     // Create local ID array.  First translate gid to gno.
00349 
00350     ArrayRCP<gno_t> gnoArray;
00351 
00352     if (gnosAreGids){
00353       ArrayRCP<const gno_t> gnosConst =
00354         arcp_reinterpret_cast<const gno_t>(newEgids);
00355       gnoArray = arcp_const_cast<gno_t>(gnosConst);
00356     }
00357     else{
00358 
00359       ArrayRCP<gid_t> gidArray = arcp_const_cast<gid_t>(newEgids);
00360       gno_t *gnoList= new gno_t [numLocalGraphEdges];
00361       env->localMemoryAssertion(__FILE__, __LINE__, numLocalGraphEdges,
00362         gnoList);
00363       gnoArray = arcp(gnoList, 0, numLocalGraphEdges, true);
00364 
00365       try {
00366         idMap->gidTranslate(
00367           gidArray.view(0,numLocalGraphEdges),
00368           gnoArray.view(0,numLocalGraphEdges),
00369           TRANSLATE_APP_TO_LIB);
00370       }
00371       Z2_FORWARD_EXCEPTIONS;
00372     }
00373 
00374     // translate gno to lno
00375 
00376     lno_t *lnoList = new lno_t [numLocalGraphEdges];
00377     env->localMemoryAssertion(__FILE__, __LINE__, numLocalGraphEdges,
00378       lnoList);
00379     ArrayView<lno_t> lnoView(lnoList, numLocalGraphEdges);
00380 
00381     try {
00382       idMap->lnoTranslate(
00383         lnoView,
00384         gnoArray.view(0,numLocalGraphEdges),
00385         TRANSLATE_LIB_TO_APP);
00386     }
00387     Z2_FORWARD_EXCEPTIONS;
00388     edgeLocalIds = arcp<const lno_t>(lnoList, 0, numLocalGraphEdges, true);
00389   }
00390 
00391   return numLocalGraphEdges;
00392 }
00393 
00403 template <typename Adapter>
00404 class GraphModel : public Model<Adapter>
00405 {
00406 public:
00407 
00408 #ifndef DOXYGEN_SHOULD_SKIP_THIS
00409   typedef typename Adapter::scalar_t  scalar_t;
00410   typedef typename Adapter::gno_t     gno_t;
00411   typedef typename Adapter::lno_t     lno_t;
00412   typedef StridedData<lno_t, scalar_t> input_t;
00413 #endif
00414 
00426   GraphModel(const Adapter *ia,
00427     const RCP<const Environment> &env, const RCP<const Comm<int> > &comm,
00428     modelFlag_t &modelFlags)
00429   {
00430     throw std::logic_error("in non-specialized GraphModel");
00431   }
00432 
00435   size_t getLocalNumVertices() const { return 0; }
00436 
00439   size_t getGlobalNumVertices() const { return 0; }
00440 
00444   size_t getLocalNumGlobalEdges() const { return 0; }
00445 
00449   size_t getLocalNumLocalEdges() const { return 0; }
00450 
00453   size_t getGlobalNumEdges() const { return 0; }
00454 
00457   int getVertexWeightDim() const { return 0; }
00458 
00461   int getEdgeWeightDim() const { return 0; }
00462 
00465   int getCoordinateDim() const { return 0; }
00466 
00477   size_t getVertexList( ArrayView<const gno_t> &Ids,
00478     ArrayView<input_t> &xyz,
00479     ArrayView<input_t> &wgts) const {return 0;}
00480 
00494   // Implied Vertex LNOs from getVertexList are used as indices to offsets
00495   // array.
00496   // Vertex GNOs are returned as neighbors in edgeIds.
00497 
00498   size_t getEdgeList( ArrayView<const gno_t> &edgeIds,
00499     ArrayView<const int> &procIds, ArrayView<const lno_t> &offsets,
00500     ArrayView<input_t> &wgts) const {return 0;}
00501 
00525   size_t getLocalEdgeList( ArrayView<const lno_t> &edgeIds,
00526     ArrayView<const lno_t> &offsets,
00527     ArrayView<input_t> &wgts) {return 0;}
00528 
00530   // The Model interface.
00532 
00533   size_t getLocalNumObjects() const { return 0;}
00534 
00535   size_t getGlobalNumObjects() const { return 0;}
00536 
00537   void getGlobalObjectIds(ArrayView<const gno_t> &gnos) const { return; }
00538 };
00539 
00540 #ifndef DOXYGEN_SHOULD_SKIP_THIS
00541 
00543 // Graph model derived from MatrixInput.
00545 
00546 template <typename User>
00547 class GraphModel<MatrixInput<User> > : public Model<MatrixInput<User> >
00548 {
00549 public:
00550 
00551   typedef typename InputTraits<User>::scalar_t  scalar_t;
00552   typedef typename InputTraits<User>::gno_t     gno_t;
00553   typedef typename InputTraits<User>::lno_t     lno_t;
00554   typedef typename InputTraits<User>::gid_t     gid_t;
00555   typedef StridedData<lno_t, scalar_t> input_t;
00556   typedef IdentifierMap<User>     idmap_t;
00557 
00567   GraphModel(const MatrixInput<User> *ia,
00568     const RCP<const Environment> &env, const RCP<const Comm<int> > &comm,
00569     modelFlag_t &modelFlags);
00570 
00572   ~GraphModel() { }
00573 
00574   // // // // // // // // // // // // // // // // // // // // // /
00575   // The GraphModel interface.
00576   // // // // // // // // // // // // // // // // // // // // // /
00577 
00578   size_t getLocalNumVertices() const { return numLocalVertices_; }
00579 
00580   size_t getGlobalNumVertices() const { return numGlobalVertices_; }
00581 
00582   size_t getLocalNumGlobalEdges() const { return numLocalEdges_; }
00583 
00584   size_t getLocalNumLocalEdges() const { return numLocalGraphEdges_; }
00585 
00586   size_t getGlobalNumEdges() const { return numGlobalEdges_; }
00587 
00588   int getVertexWeightDim() const { return vWeightDim_; }
00589 
00590   int getEdgeWeightDim() const { return eWeightDim_; }
00591 
00592   int getCoordinateDim() const { return vCoordDim_; }
00593 
00594   size_t getVertexList( ArrayView<const gno_t> &Ids,
00595     ArrayView<input_t> &xyz, ArrayView<input_t> &wgts) const;
00596 
00597   size_t getEdgeList( ArrayView<const gno_t> &edgeIds,
00598     ArrayView<const int> &procIds, ArrayView<const lno_t> &offsets,
00599     ArrayView<input_t> &wgts) const;
00600 
00601   size_t getLocalEdgeList( ArrayView<const lno_t> &edgeIds,
00602     ArrayView<const lno_t> &offsets,
00603     ArrayView<input_t> &wgts){
00604 
00605     if (localGraphEdgeLnos_.size() <
00606         static_cast<typename ArrayRCP<const lno_t>::size_type>(numLocalGraphEdges_)){
00607 
00608       RCP<const IdentifierMap<User> > idmap = this->getIdentifierMap();
00609 
00610       computeLocalEdgeList<User>(env_, comm_->getRank(),
00611         numLocalEdges_, numLocalGraphEdges_,
00612         idmap, edgeGids_, procIds_, offsets_, eWeights_,
00613         localGraphEdgeLnos_, localGraphEdgeOffsets_, localGraphEdgeWeights_);
00614     }
00615 
00616     edgeIds = localGraphEdgeLnos_();
00617     offsets = localGraphEdgeOffsets_();
00618     wgts = localGraphEdgeWeights_();
00619 
00620     return numLocalGraphEdges_;
00621   }
00622 
00624   // The Model interface.
00626 
00627   size_t getLocalNumObjects() const { return numLocalVertices_; }
00628 
00629   size_t getGlobalNumObjects() const { return numGlobalVertices_; }
00630 
00631   void getGlobalObjectIds(ArrayView<const gno_t> &gnos) const
00632   {
00633     ArrayView<input_t> xyz, wgts;
00634     getVertexList(gnos, xyz, wgts);
00635   }
00636 
00637 private:
00638 
00639   const RCP<const Environment > env_;
00640   const RCP<const Comm<int> > comm_;
00641 
00642   ArrayRCP<const gid_t> gids_;        // rows
00643   ArrayRCP<gno_t> gnos_;
00644 
00645   int vWeightDim_;
00646   ArrayRCP<input_t> vWeights_;
00647 
00648   int vCoordDim_;
00649   ArrayRCP<input_t> vCoords_;
00650 
00651   // Note: in case of graph subsetting, size of these arrays
00652   // may be larger than numLocalEdges_.  So do not use .size().
00653 
00654   ArrayRCP<const gid_t> edgeGids_;
00655   ArrayRCP<gno_t> edgeGnos_;
00656   ArrayRCP<int> procIds_;
00657   ArrayRCP<const lno_t> offsets_;
00658 
00659   int eWeightDim_;
00660   ArrayRCP<input_t> eWeights_;
00661 
00662   ArrayRCP<const gno_t> gnosConst_;
00663   ArrayRCP<const gno_t> edgeGnosConst_;
00664   ArrayRCP<const int> procIdsConst_;
00665 
00666   bool gnosAreGids_;
00667 
00668   // For local graphs (graph restricted to local process).  We only
00669   // create these arrays if required by the algorithm.
00670 
00671   ArrayRCP<const lno_t> localGraphEdgeLnos_;
00672   ArrayRCP<const lno_t> localGraphEdgeOffsets_;
00673   ArrayRCP<input_t> localGraphEdgeWeights_;
00674 
00675   // For convenience
00676 
00677   size_t numLocalVertices_;
00678   size_t numGlobalVertices_;
00679   size_t numLocalEdges_;
00680   size_t numGlobalEdges_;
00681   size_t numLocalGraphEdges_;
00682 };
00683 
00684 template <typename User>
00685   GraphModel<MatrixInput<User> >::GraphModel(const MatrixInput<User> *ia,
00686     const RCP<const Environment> &env, const RCP<const Comm<int> > &comm,
00687     modelFlag_t &modelFlags):
00688      env_(env), comm_(comm),
00689      gids_(), gnos_(),
00690      vWeightDim_(0), vWeights_(),
00691      vCoordDim_(0), vCoords_(),
00692      edgeGids_(), edgeGnos_(), procIds_(), offsets_(),
00693      eWeightDim_(0), eWeights_(),
00694      gnosConst_(), edgeGnosConst_(), procIdsConst_(),
00695      gnosAreGids_(false),
00696      localGraphEdgeLnos_(), localGraphEdgeOffsets_(), localGraphEdgeWeights_(),
00697      numLocalVertices_(0), numGlobalVertices_(0), numLocalEdges_(0),
00698      numGlobalEdges_(0), numLocalGraphEdges_(0)
00699 {
00700   // Model creation flags
00701 
00702   bool symTranspose = modelFlags.test(SYMMETRIZE_INPUT_TRANSPOSE);
00703   bool symBipartite = modelFlags.test(SYMMETRIZE_INPUT_BIPARTITE);
00704   bool vertexCols = modelFlags.test(VERTICES_ARE_MATRIX_COLUMNS);
00705   bool vertexNz = modelFlags.test(VERTICES_ARE_MATRIX_NONZEROS);
00706   bool consecutiveIdsRequired =
00707     modelFlags.test(IDS_MUST_BE_GLOBALLY_CONSECUTIVE);
00708   bool removeSelfEdges = modelFlags.test(SELF_EDGES_MUST_BE_REMOVED);
00709   bool subsetGraph = modelFlags.test(GRAPH_IS_A_SUBSET_GRAPH);
00710 
00711   if (symTranspose || symBipartite || vertexCols || vertexNz){
00712     throw std::runtime_error("graph build option not yet implemented");
00713   }
00714 
00715   // Get the matrix from the input adapter
00716 
00717   gid_t const *vtxIds=NULL, *nborIds=NULL;
00718   lno_t const  *offsets=NULL;
00719   try{
00720     numLocalVertices_ = ia->getRowListView(vtxIds, offsets, nborIds);
00721   }
00722   Z2_FORWARD_EXCEPTIONS;
00723 
00724   numLocalEdges_ = offsets[numLocalVertices_];
00725 
00726   gids_ = arcp<const gid_t>(vtxIds, 0, numLocalVertices_, false);
00727   edgeGids_ = arcp<const gid_t>(nborIds, 0, numLocalEdges_, false);
00728   offsets_ = arcp<const lno_t>(offsets, 0, numLocalVertices_ + 1, false);
00729 
00730   eWeightDim_ = 0;   // no edge weights from a matrix
00731 
00732   // A subset graph is special in that it may contain neighbor
00733   // vertices that are not owned by processes in this communicator.
00734   // We remove these.
00735 
00736   ArrayRCP<const int> nborProcs;
00737 
00738   if (subsetGraph){
00739     RCP<const idmap_t> idMap;
00740     try{
00741       idMap = rcp(new idmap_t(env_, comm_, gids_, false));
00742     }
00743     Z2_FORWARD_EXCEPTIONS;
00744 
00745     ArrayRCP<int> procArray;
00746 
00747     if (numLocalEdges_ > 0){
00748       int *pids = new int [numLocalEdges_];
00749       env_->localMemoryAssertion(__FILE__, __LINE__, numLocalEdges_, pids);
00750       procArray = arcp(pids, 0, numLocalEdges_, true);
00751     }
00752 
00753     ArrayView<gno_t> dummyGno;
00754 
00755     try{
00756       // All processes must make this call.
00757       // procOwner will be -1 if edge Id is not in our communicator.
00758 
00759       idMap->gidGlobalTranslate( edgeGids_.view(0, numLocalEdges_),
00760         dummyGno, procArray.view(0, numLocalEdges_));
00761     }
00762     Z2_FORWARD_EXCEPTIONS;
00763 
00764     int outOfSubset = 0;
00765     for (size_t i=0; i < numLocalEdges_; i++){
00766       if (procArray[i] < 0){
00767         outOfSubset++;
00768         break;
00769       }
00770     }
00771 
00772     if (outOfSubset == 0){
00773       procArray.clear();
00774       subsetGraph = false;
00775     }
00776     else{
00777       nborProcs = arcp_const_cast<const int>(procArray);
00778     }
00779   }
00780 
00781   // Now remove undesired edges.
00782 
00783   if (subsetGraph || removeSelfEdges){
00784 
00785     ArrayRCP<input_t> noEdgeWeights;
00786     ArrayRCP<const gid_t> newEdges;
00787     ArrayRCP<const lno_t> newOffs;
00788     scalar_t **newWeights = NULL;
00789     size_t numNewEdges = 0;
00790 
00791     // Compiler complained of an error if gids_.view(0, n), etc
00792     // was listed directly as a parameter in removeUndesiredEdges.
00793     // So we have to create the ArraView before before the call.
00794 
00795     ArrayView<const gid_t> vtxView= gids_.view(0, numLocalVertices_);
00796     ArrayView<const gid_t> nborView= edgeGids_.view(0, numLocalEdges_);
00797     ArrayView<const int> nborOwner = nborProcs.view(0, nborProcs.size());
00798     ArrayView<input_t> eWgts = noEdgeWeights.view(0, 0);
00799     ArrayView<const lno_t> offView = offsets_.view(0, numLocalVertices_ + 1);
00800 
00801     try{
00802       numNewEdges = Zoltan2::removeUndesiredEdges<User>(env_, comm_->getRank(),
00803         removeSelfEdges,
00804         false,
00805         subsetGraph,
00806         vtxView,
00807         nborView,
00808         nborOwner,
00809         eWgts,
00810         offView,
00811         newEdges,
00812         newWeights,
00813         newOffs);
00814     }
00815     Z2_FORWARD_EXCEPTIONS;
00816 
00817     nborProcs.clear();
00818 
00819     if (numNewEdges < numLocalEdges_){
00820       edgeGids_ = newEdges;
00821       offsets_ = newOffs;
00822       numLocalEdges_ = numNewEdges;
00823     }
00824   }
00825 
00826   // Create an IdentifierMap, which will map the user's global IDs to
00827   //   Zoltan2 internal global numbers if necessary.
00828   //   The map can also give us owners of our vertex neighbors.
00829 
00830   RCP<const idmap_t> idMap;
00831 
00832   try{
00833     idMap = rcp(new idmap_t(env_, comm_, gids_, consecutiveIdsRequired));
00834   }
00835   Z2_FORWARD_EXCEPTIONS;
00836 
00837   // Model base class needs to have IdentifierMap.
00838 
00839   this->setIdentifierMap(idMap);
00840 
00841   numGlobalVertices_ = idMap->getGlobalNumberOfIds();
00842   gnosAreGids_ = idMap->gnosAreGids();
00843 
00844   // Compute internal global numbers if we can not use the
00845   // user's global Ids.  Also find the process owning each
00846   // neighboring vertex.
00847 
00848   ArrayView<const gid_t> gidArray(Teuchos::null);  // edge gid
00849   ArrayView<gno_t> gnoArray(Teuchos::null);        // edge gno
00850   ArrayView<int> procArray(Teuchos::null);         // edge owner
00851 
00852   if (numLocalVertices_){
00853 
00854     if (!gnosAreGids_){   // need vertex global numbers, edge global numbers
00855       gno_t *tmp = new gno_t [numLocalVertices_];
00856       env_->localMemoryAssertion(__FILE__, __LINE__, numLocalVertices_, tmp);
00857       gnos_ = arcp(tmp, 0, numLocalVertices_);
00858 
00859       try{
00860         ArrayRCP<gid_t> tmpGids = arcp_const_cast<gid_t>(gids_);
00861 
00862         idMap->gidTranslate(tmpGids(0,numLocalVertices_),
00863           gnos_(0,numLocalVertices_), TRANSLATE_APP_TO_LIB);
00864       }
00865       Z2_FORWARD_EXCEPTIONS;
00866 
00867       if (numLocalEdges_){
00868         tmp = new gno_t [numLocalEdges_];
00869         env_->localMemoryAssertion(__FILE__, __LINE__, numLocalEdges_, tmp);
00870         edgeGnos_ = arcp(tmp, 0, numLocalEdges_);
00871         gnoArray = edgeGnos_.view(0, numLocalEdges_);
00872       }
00873     }
00874 
00875     if (numLocalEdges_){
00876       gidArray = edgeGids_.view(0, numLocalEdges_);
00877 
00878       int *p = new int [numLocalEdges_];
00879       env_->localMemoryAssertion(__FILE__, __LINE__, numLocalEdges_, p);
00880       procIds_ = arcp(p, 0, numLocalEdges_);
00881       procArray = procIds_.view(0, numLocalEdges_);
00882     }
00883   }
00884 
00885   try{
00886     // All processes must make this call.
00887     idMap->gidGlobalTranslate(gidArray, gnoArray, procArray);
00888   }
00889   Z2_FORWARD_EXCEPTIONS;
00890 
00891   gnosConst_ = arcp_const_cast<const gno_t>(gnos_);
00892   edgeGnosConst_ = arcp_const_cast<const gno_t>(edgeGnos_);
00893   procIdsConst_ = arcp_const_cast<const int>(procIds_);
00894 
00895   // Number of edges such that neighbor is on the local process.
00896   // We only create the list of local graph edges if the user
00897   // calls getLocalEdgeList().
00898 
00899   numLocalGraphEdges_ = 0;
00900   int *pids = procArray.getRawPtr();
00901   for (size_t i=0; i < numLocalEdges_; i++)
00902     if (pids[i] == comm_->getRank())
00903       numLocalGraphEdges_++;
00904 
00905   // Vertex weights
00906 
00907   vWeightDim_ = ia->getRowWeightDimension();
00908 
00909   if (vWeightDim_ > 0){
00910     input_t *weightInfo = new input_t [vWeightDim_];
00911     env_->localMemoryAssertion(__FILE__, __LINE__, vWeightDim_, weightInfo);
00912 
00913     for (int dim=0; dim < vWeightDim_; dim++){
00914       bool useNumNZ = ia->getRowWeightIsNumberOfNonZeros(dim);
00915       if (useNumNZ){
00916         scalar_t *wgts = new scalar_t [numLocalVertices_];
00917         env_->localMemoryAssertion(__FILE__, __LINE__, numLocalVertices_, wgts);
00918         ArrayRCP<const scalar_t> wgtArray =
00919           arcp(wgts, 0, numLocalVertices_, true);
00920         for (size_t i=0; i < numLocalVertices_; i++){
00921           wgts[i] = offsets_[i+1] - offsets_[i];
00922         }
00923         weightInfo[dim] = input_t(wgtArray, 1);
00924       }
00925       else{
00926         const scalar_t *weights=NULL;
00927         int stride=0;
00928         size_t len = ia->getRowWeights(dim, weights, stride);
00929         // If weights is NULL, user wants to use uniform weights
00930         if (weights != NULL){
00931           ArrayRCP<const scalar_t> wgtArray = arcp(weights, 0, len, false);
00932           weightInfo[dim] = input_t(wgtArray, stride);
00933         }
00934       }
00935     }
00936 
00937     vWeights_ = arcp<input_t>(weightInfo, 0, vWeightDim_, true);
00938   }
00939 
00940   // Model base class needs to know if any weights are uniform.
00941 
00942   Array<lno_t> weightArrayLengths(vWeightDim_);
00943   for (int dim=0; dim < vWeightDim_; dim++){
00944     weightArrayLengths[dim] = vWeights_[dim].size();
00945   }
00946   this->setWeightArrayLengths(weightArrayLengths, *comm_);
00947 
00948   // Vertex coordinates
00949 
00950   vCoordDim_ = ia->getCoordinateDimension();
00951 
00952   if (vCoordDim_ > 0){
00953     input_t *coordInfo = new input_t [vCoordDim_];
00954     env_->localMemoryAssertion(__FILE__, __LINE__, vCoordDim_, coordInfo);
00955 
00956     for (int dim=0; dim < vCoordDim_; dim++){
00957       const scalar_t *coords=NULL;
00958       int stride=0;
00959       size_t len = ia->getRowCoordinates(dim, coords, stride);
00960       ArrayRCP<const scalar_t> coordArray = arcp(coords, 0, len, false);
00961       coordInfo[dim] = input_t(coordArray, stride);
00962     }
00963 
00964     vCoords_ = arcp<input_t>(coordInfo, 0, vCoordDim_, true);
00965   }
00966 
00967   reduceAll<int, size_t>(*comm_, Teuchos::REDUCE_SUM, 1,
00968     &numLocalEdges_, &numGlobalEdges_);
00969 
00970   env_->memory("After construction of graph model");
00971 }
00972 
00973 template <typename User>
00974   size_t GraphModel<MatrixInput<User> >::getVertexList(
00975     ArrayView<const gno_t> &Ids, ArrayView<input_t> &xyz,
00976     ArrayView<input_t> &wgts) const
00977   {
00978     size_t nv = gids_.size();
00979 
00980     if (gnosAreGids_)
00981       Ids = gids_.view(0, nv);
00982     else
00983       Ids = gnosConst_.view(0, nv);
00984 
00985     xyz = vCoords_.view(0, vWeightDim_);
00986     wgts = vWeights_.view(0, vCoordDim_);
00987 
00988     return nv;
00989   }
00990 
00991 template <typename User>
00992   size_t GraphModel<MatrixInput<User> >::getEdgeList(
00993     ArrayView<const gno_t> &edgeIds, ArrayView<const int> &procIds,
00994     ArrayView<const lno_t> &offsets, ArrayView<input_t> &wgts) const
00995 {
00996   if (gnosAreGids_)
00997     edgeIds = edgeGids_.view(0, numLocalEdges_);
00998   else
00999     edgeIds = edgeGnosConst_.view(0, numLocalEdges_);
01000 
01001   procIds = procIdsConst_.view(0, numLocalEdges_);
01002   offsets = offsets_.view(0, numLocalVertices_+1);
01003   wgts = eWeights_.view(0, eWeightDim_);
01004 
01005   return numLocalEdges_;
01006 }
01007 
01009 // Graph model derived from GraphInput.
01011 
01012 template <typename User>
01013 class GraphModel<GraphInput<User> > : public Model<GraphInput<User> >
01014 {
01015 public:
01016 
01017   typedef typename GraphInput<User>::scalar_t  scalar_t;
01018   typedef typename GraphInput<User>::gno_t     gno_t;
01019   typedef typename GraphInput<User>::lno_t     lno_t;
01020   typedef typename GraphInput<User>::gid_t     gid_t;
01021   typedef typename GraphInput<User>::node_t    node_t;
01022   typedef IdentifierMap<User>     idmap_t;
01023   typedef StridedData<lno_t, scalar_t> input_t;
01024 
01034   GraphModel(const GraphInput<User> *ia,
01035     const RCP<const Environment> &env, const RCP<const Comm<int> > &comm,
01036     modelFlag_t &modelFlags);
01037 
01039   ~GraphModel() { }
01040 
01041   // // // // // // // // // // // // // // // // // // // // // /
01042   // The GraphModel interface.
01043   // // // // // // // // // // // // // // // // // // // // // /
01044 
01045   size_t getLocalNumVertices() const { return numLocalVertices_; }
01046 
01047   size_t getGlobalNumVertices() const { return numGlobalVertices_; }
01048 
01049   size_t getLocalNumGlobalEdges() const { return numLocalEdges_; }
01050 
01051   size_t getLocalNumLocalEdges() const { return numLocalGraphEdges_; }
01052 
01053   size_t getGlobalNumEdges() const { return numGlobalEdges_; }
01054 
01055   int getVertexWeightDim() const { return vWeightDim_; }
01056 
01057   int getEdgeWeightDim() const { return eWeightDim_; }
01058 
01059   int getCoordinateDim() const { return vCoordDim_; }
01060 
01061   size_t getVertexList( ArrayView<const gno_t> &Ids,
01062     ArrayView<input_t> &xyz, ArrayView<input_t> &wgts) const;
01063 
01064   size_t getEdgeList( ArrayView<const gno_t> &edgeIds,
01065     ArrayView<const int> &procIds, ArrayView<const lno_t> &offsets,
01066     ArrayView<input_t> &wgts) const;
01067 
01068   size_t getLocalEdgeList( ArrayView<const lno_t> &edgeIds,
01069     ArrayView<const lno_t> &offsets,
01070     ArrayView<input_t> &wgts){
01071 
01072     if (localGraphEdgeLnos_.size() < numLocalGraphEdges_){
01073 
01074       RCP<const IdentifierMap<User> > idmap = this->getIdentifierMap();
01075 
01076       computeLocalEdgeList(env_, comm_->getRank(),
01077         numLocalEdges_, numLocalGraphEdges_,
01078         idmap, edgeGids_, procIds_, offsets_, eWeights_,
01079         localGraphEdgeLnos_, localGraphEdgeOffsets_, localGraphEdgeWeights_);
01080     }
01081 
01082     edgeIds = localGraphEdgeLnos_;
01083     offsets = localGraphEdgeOffsets_;
01084     wgts = localGraphEdgeWeights_;
01085 
01086     return numLocalGraphEdges_;
01087   }
01088 
01090   // The Model interface.
01092 
01093   size_t getLocalNumObjects() const { return numLocalVertices_; }
01094 
01095   size_t getGlobalNumObjects() const { return numGlobalVertices_; }
01096 
01097   void getGlobalObjectIds(ArrayView<const gno_t> &gnos) const
01098   {
01099     ArrayView<input_t> xyz, wgts;
01100     getVertexList(gnos, xyz, wgts);
01101   }
01102 
01103 private:
01104 
01105   const RCP<const Environment > env_;
01106   const RCP<const Comm<int> > comm_;
01107 
01108   ArrayRCP<const gid_t> gids_;        // vertices of input graph
01109   ArrayRCP<gno_t> gnos_;
01110 
01111   int vWeightDim_;
01112   ArrayRCP<input_t> vWeights_;
01113 
01114   int vCoordDim_;
01115   ArrayRCP<input_t> vCoords_;
01116 
01117   // Note: in case of graph subsetting, size of these arrays
01118   // may be larger than numLocalEdges_.  So do not use .size().
01119 
01120   ArrayRCP<const gid_t> edgeGids_;
01121   ArrayRCP<gno_t> edgeGnos_;
01122   ArrayRCP<int> procIds_;
01123   ArrayRCP<const lno_t> offsets_;
01124 
01125   int eWeightDim_;
01126   ArrayRCP<input_t> eWeights_;
01127 
01128   ArrayRCP<const gno_t> gnosConst_;
01129   ArrayRCP<const gno_t> edgeGnosConst_;
01130   ArrayRCP<const int> procIdsConst_;
01131 
01132   bool gnosAreGids_;
01133 
01134   // For local graphs (graph restricted to local process).  We only
01135   // create these arrays if required by the algorithm.
01136 
01137   ArrayRCP<const lno_t> localGraphEdgeLnos_;
01138   ArrayRCP<const lno_t> localGraphEdgeOffsets_;
01139   ArrayRCP<input_t> localGraphEdgeWeights_;
01140 
01141   // For convenience
01142 
01143   size_t numLocalVertices_;
01144   size_t numGlobalVertices_;
01145   size_t numLocalEdges_;
01146   size_t numGlobalEdges_;
01147   size_t numLocalGraphEdges_;
01148 
01149 };
01150 
01151 template <typename User>
01152   GraphModel<GraphInput<User> >::GraphModel(const GraphInput<User> *ia,
01153     const RCP<const Environment> &env, const RCP<const Comm<int> > &comm,
01154     modelFlag_t &modelFlags):
01155      env_(env), comm_(comm),
01156      gids_(), gnos_(),
01157      vWeightDim_(0), vWeights_(),
01158      vCoordDim_(0), vCoords_(),
01159      edgeGids_(), edgeGnos_(), procIds_(), offsets_(),
01160      eWeightDim_(0), eWeights_(),
01161      gnosConst_(), edgeGnosConst_(), procIdsConst_(),
01162      gnosAreGids_(false),
01163      localGraphEdgeLnos_(), localGraphEdgeOffsets_(), localGraphEdgeWeights_(),
01164      numLocalVertices_(0), numGlobalVertices_(0), numLocalEdges_(0),
01165      numGlobalEdges_(0), numLocalGraphEdges_(0)
01166 {
01167   // Model creation flags
01168 
01169   bool consecutiveIdsRequired =
01170     modelFlags.test(IDS_MUST_BE_GLOBALLY_CONSECUTIVE);
01171   bool removeSelfEdges = modelFlags.test(SELF_EDGES_MUST_BE_REMOVED);
01172   bool subsetGraph = modelFlags.test(GRAPH_IS_A_SUBSET_GRAPH);
01173 
01174   // Get the graph from the input adapter
01175 
01176   gid_t const *vtxIds=NULL, *nborIds=NULL;
01177   lno_t const  *offsets=NULL;
01178   try{
01179     numLocalVertices_ = ia->getVertexListView(vtxIds, offsets, nborIds);
01180   }
01181   Z2_FORWARD_EXCEPTIONS;
01182 
01183   numLocalEdges_ = offsets[numLocalVertices_];
01184 
01185   gids_ = arcp<const gid_t>(vtxIds, 0, numLocalVertices_, false);
01186   edgeGids_ = arcp<const gid_t>(nborIds, 0, numLocalEdges_, false);
01187   offsets_ = arcp<const lno_t>(offsets, 0, numLocalVertices_ + 1, false);
01188 
01189   eWeightDim_ = ia->getEdgeWeightDimension();
01190 
01191   if (eWeightDim_ > 0){
01192     input_t *wgts = new input_t [eWeightDim_];
01193     eWeights_ = arcp(wgts, 0, eWeightDim_, true);
01194   }
01195 
01196   for (int w=0; w < eWeightDim_; w++){
01197     const scalar_t *ewgts=NULL;
01198     int stride=0;
01199 
01200     ia->getEdgeWeights(w, ewgts, stride);
01201 
01202     ArrayRCP<const scalar_t> wgtArray(ewgts, 0, numLocalEdges_, false);
01203     eWeights_[w] = input_t(wgtArray, stride);
01204   }
01205 
01206   // A subset graph is special in that it may contain neighbor
01207   // vertices that are not owned by processes in this communicator.
01208   // We remove these.
01209 
01210   ArrayRCP<const int> nborProcs;
01211 
01212   if (subsetGraph){
01213     RCP<const idmap_t> idMap;
01214     try{
01215       idMap = rcp(new idmap_t(env_, comm_, gids_, false));
01216     }
01217     Z2_FORWARD_EXCEPTIONS;
01218 
01219     ArrayRCP<int> procArray;
01220 
01221     if (numLocalEdges_ > 0){
01222       int *pids = new int [numLocalEdges_];
01223       env_->localMemoryAssertion(__FILE__, __LINE__, numLocalEdges_, pids);
01224       procArray = arcp(pids, 0, numLocalEdges_, true);
01225     }
01226 
01227     ArrayView<gno_t> dummyGno;
01228 
01229     try{
01230       // All processes must make this call.
01231       // procOwner will be -1 if edge Id is not in our communicator.
01232 
01233       idMap->gidGlobalTranslate( edgeGids_.view(0, numLocalEdges_),
01234         dummyGno, procArray.view(0, numLocalEdges_));
01235     }
01236     Z2_FORWARD_EXCEPTIONS;
01237 
01238     int outOfSubset = 0;
01239     for (size_t i=0; i < numLocalEdges_; i++){
01240       if (procArray[i] < 0){
01241         outOfSubset++;
01242         break;
01243       }
01244     }
01245 
01246     if (outOfSubset == 0){
01247       procArray.clear();
01248       subsetGraph = false;
01249     }
01250     else{
01251       nborProcs = arcp_const_cast<const int>(procArray);
01252     }
01253   }
01254 
01255   // Now remove undesired edges.
01256 
01257   if (subsetGraph || removeSelfEdges){
01258 
01259     ArrayRCP<const gid_t> newEdges;
01260     ArrayRCP<const lno_t> newOffs;
01261     scalar_t **newWeights = NULL;
01262     size_t numNewEdges = 0;
01263 
01264     ArrayView<const gid_t> vtxView = gids_.view(0, numLocalVertices_);
01265     ArrayView<const gid_t> nborView= edgeGids_.view(0, numLocalEdges_);
01266     ArrayView<const int> nborOwner = nborProcs.view(0, nborProcs.size());
01267     ArrayView<input_t> eWgts = eWeights_.view(0, eWeightDim_);
01268     ArrayView<const lno_t> offView = offsets_.view(0, numLocalVertices_ + 1);
01269 
01270     try{
01271       numNewEdges = removeUndesiredEdges<User>(env_, comm_->getRank(),
01272         removeSelfEdges,
01273         false,
01274         subsetGraph,
01275         vtxView,
01276         nborView,
01277         nborOwner,
01278         eWgts,
01279         offView,
01280         newEdges,
01281         newWeights,
01282         newOffs);
01283     }
01284     Z2_FORWARD_EXCEPTIONS;
01285 
01286     nborProcs.clear();
01287 
01288     if (numNewEdges < numLocalEdges_){
01289       edgeGids_ = newEdges;
01290       offsets_ = newOffs;
01291       numLocalEdges_ = numNewEdges;
01292 
01293       for (int w=0; w < eWeightDim_; w++){
01294         if (newWeights[w] != NULL){   // non-uniform weights
01295           ArrayRCP<const scalar_t> wgtArray(newWeights[w],
01296             0, numNewEdges, true);
01297           eWeights_[w] = input_t(wgtArray, 1);
01298         }
01299       }
01300     }
01301   }
01302 
01303   // Create an IdentifierMap, which will map the user's global IDs to
01304   //   Zoltan2 internal global numbers if necessary.
01305   //   The map can also give us owners of our vertex neighbors.
01306 
01307   RCP<const idmap_t> idMap;
01308 
01309   try{
01310     idMap = rcp(new idmap_t(env_, comm_, gids_, consecutiveIdsRequired));
01311   }
01312   Z2_FORWARD_EXCEPTIONS;
01313 
01314   // Model base class needs to have IdentifierMap.
01315 
01316   this->setIdentifierMap(idMap);
01317 
01318   numGlobalVertices_ = idMap->getGlobalNumberOfIds();
01319   gnosAreGids_ = idMap->gnosAreGids();
01320 
01321   // Compute internal global numbers if we can not use the
01322   // user's global Ids.  Also find the process owning each
01323   // neighboring vertex.
01324 
01325   ArrayView<const gid_t> gidArray(Teuchos::null);  // edge gid
01326   ArrayView<gno_t> gnoArray(Teuchos::null);        // edge gno
01327   ArrayView<int> procArray(Teuchos::null);         // edge owner
01328 
01329   if (numLocalVertices_){
01330 
01331     if (!gnosAreGids_){   // need vertex global numbers, edge global numbers
01332       gno_t *tmp = new gno_t [numLocalVertices_];
01333       env_->localMemoryAssertion(__FILE__, __LINE__, numLocalVertices_, tmp);
01334       gnos_ = arcp(tmp, 0, numLocalVertices_);
01335 
01336       try{
01337         ArrayRCP<gid_t> tmpGids = arcp_const_cast<gid_t>(gids_);
01338 
01339         idMap->gidTranslate(tmpGids(0,numLocalVertices_),
01340           gnos_(0,numLocalVertices_), TRANSLATE_APP_TO_LIB);
01341       }
01342       Z2_FORWARD_EXCEPTIONS;
01343 
01344       if (numLocalEdges_){
01345         tmp = new gno_t [numLocalEdges_];
01346         env_->localMemoryAssertion(__FILE__, __LINE__, numLocalEdges_, tmp);
01347         edgeGnos_ = arcp(tmp, 0, numLocalEdges_);
01348         gnoArray = edgeGnos_.view(0, numLocalEdges_);
01349       }
01350     }
01351 
01352     if (numLocalEdges_){
01353       gidArray = edgeGids_.view(0, numLocalEdges_);
01354 
01355       int *p = new int [numLocalEdges_];
01356       env_->localMemoryAssertion(__FILE__, __LINE__, numLocalEdges_, p);
01357       procIds_ = arcp(p, 0, numLocalEdges_);
01358       procArray = procIds_.view(0, numLocalEdges_);
01359     }
01360   }
01361 
01362   try{
01363     // All processes must make this call.
01364     idMap->gidGlobalTranslate(gidArray, gnoArray, procArray);
01365   }
01366   Z2_FORWARD_EXCEPTIONS;
01367 
01368   gnosConst_ = arcp_const_cast<const gno_t>(gnos_);
01369   edgeGnosConst_ = arcp_const_cast<const gno_t>(edgeGnos_);
01370   procIdsConst_ = arcp_const_cast<const int>(procIds_);
01371 
01372   // Number of edges such that neighbor is on the local process.
01373   // We only create the list of local graph edges if the user
01374   // calls getLocalEdgeList().
01375 
01376   numLocalGraphEdges_ = 0;
01377   int *pids = procArray.getRawPtr();
01378   for (lno_t i=0; i < numLocalEdges_; i++)
01379     if (pids[i] == comm_->getRank())
01380       numLocalGraphEdges_++;
01381 
01382   // Vertex weights
01383 
01384   vWeightDim_ = ia->getVertexWeightDimension();
01385 
01386   if (vWeightDim_ > 0){
01387     input_t *weightInfo = new input_t [vWeightDim_];
01388     env_->localMemoryAssertion(__FILE__, __LINE__, vWeightDim_, weightInfo);
01389 
01390     for (int dim=0; dim < vWeightDim_; dim++){
01391       const scalar_t *weights=NULL;
01392       int stride=0;
01393       size_t len = ia->getVertexWeights(dim, weights, stride);
01394       // If weights is NULL, user wants to use uniform weights
01395       if (weights != NULL){
01396         ArrayRCP<const scalar_t> wgtArray = arcp(weights, 0, len, false);
01397         weightInfo[dim] = input_t(wgtArray, stride);
01398       }
01399     }
01400 
01401     vWeights_ = arcp<input_t>(weightInfo, 0, vWeightDim_, true);
01402   }
01403 
01404   // Model base class needs to know if any weights are uniform.
01405 
01406   Array<lno_t> weightArrayLengths(vWeightDim_);
01407   for (int dim=0; dim < vWeightDim_; dim++){
01408     weightArrayLengths[dim] = vWeights_[dim].size();
01409   }
01410   this->setWeightArrayLengths(weightArrayLengths, *comm_);
01411 
01412   // Vertex coordinates
01413 
01414   vCoordDim_ = ia->getCoordinateDimension();
01415 
01416   if (vCoordDim_ > 0){
01417     input_t *coordInfo = new input_t [vCoordDim_];
01418     env_->localMemoryAssertion(__FILE__, __LINE__, vCoordDim_, coordInfo);
01419 
01420     for (int dim=0; dim < vCoordDim_; dim++){
01421       const scalar_t *coords=NULL;
01422       int stride=0;
01423       size_t len = ia->getVertexCoordinates(dim, coords, stride);
01424       ArrayRCP<const scalar_t> coordArray = arcp(coords, 0, len, false);
01425       coordInfo[dim] = input_t(coordArray, stride);
01426     }
01427 
01428     vCoords_ = arcp<input_t>(coordInfo, 0, vCoordDim_, true);
01429   }
01430 
01431   reduceAll<int, size_t>(*comm_, Teuchos::REDUCE_SUM, 1,
01432     &numLocalEdges_, &numGlobalEdges_);
01433 
01434   env_->memory("After construction of graph model");
01435 }
01436 
01437 template <typename User>
01438   size_t GraphModel<GraphInput<User> >::getVertexList(
01439     ArrayView<const gno_t> &Ids, ArrayView<input_t> &xyz,
01440     ArrayView<input_t> &wgts) const
01441   {
01442     size_t nv = gids_.size();
01443 
01444     if (gnosAreGids_)
01445       Ids = gids_.view(0, nv);
01446     else
01447       Ids = gnosConst_.view(0, nv);
01448 
01449     xyz = vCoords_.view(0, vWeightDim_);
01450     wgts = vWeights_.view(0, vCoordDim_);
01451 
01452     return nv;
01453   }
01454 
01455 template <typename User>
01456   size_t GraphModel<GraphInput<User> >::getEdgeList(
01457     ArrayView<const gno_t> &edgeIds, ArrayView<const int> &procIds,
01458     ArrayView<const lno_t> &offsets, ArrayView<input_t> &wgts) const
01459 {
01460   if (gnosAreGids_)
01461     edgeIds = edgeGids_.view(0, numLocalEdges_);
01462   else
01463     edgeIds = edgeGnosConst_.view(0, numLocalEdges_);
01464 
01465   procIds = procIdsConst_.view(0, numLocalEdges_);
01466   offsets = offsets_.view(0, numLocalVertices_+1);
01467   wgts = eWeights_.view(0, eWeightDim_);
01468 
01469   return numLocalEdges_;
01470 }
01471 
01473 // Graph model derived from CoordinateInput.
01474 //
01475 //  We do not build a graph model from coordinates.  We include
01476 //  this definition so that other code will compile.
01478 
01479 template <typename User>
01480 class GraphModel<CoordinateInput<User> > : public Model<CoordinateInput<User> >
01481 {
01482 public:
01483 
01484   typedef typename CoordinateInput<User>::scalar_t  scalar_t;
01485   typedef typename CoordinateInput<User>::gno_t     gno_t;
01486   typedef typename CoordinateInput<User>::lno_t     lno_t;
01487   typedef StridedData<lno_t, scalar_t> input_t;
01488 
01489   GraphModel(const CoordinateInput<User> *ia,
01490     const RCP<const Environment> &env, const RCP<const Comm<int> > &comm,
01491     modelFlag_t &flags)
01492   {
01493     throw std::runtime_error("may not build a graph with identifiers");
01494   }
01495 
01496   // GraphModel interface
01497 
01498   size_t getLocalNumVertices() const { return 0;}
01499   size_t getGlobalNumVertices() const { return 0;}
01500   size_t getLocalNumGlobalEdges() const { return 0;}
01501   size_t getLocalNumLocalEdges() const { return 0;}
01502   size_t getGlobalNumEdges() const {return 0;}
01503   int getVertexWeightDim() const { return 0; }
01504   int getEdgeWeightDim() const { return 0; }
01505   int getCoordinateDim() const { return 0; }
01506   size_t getVertexList( ArrayView<const gno_t> &Ids,
01507     ArrayView<input_t> &xyz,
01508     ArrayView<input_t> &wgts) const { return 0; }
01509   size_t getEdgeList( ArrayView<const gno_t> &edgeIds,
01510     ArrayView<const int> &procIds, ArrayView<const lno_t> &offsets,
01511     ArrayView<input_t> &wgts) const { return 0; }
01512   size_t getLocalEdgeList( ArrayView<const lno_t> &edgeIds,
01513     ArrayView<const lno_t> &offsets,
01514     ArrayView<input_t> &wgts) { return 0; }
01515 
01516   // Model interface
01517 
01518   size_t getLocalNumObjects() const { return 0; }
01519   size_t getGlobalNumObjects() const { return 0; }
01520   void getGlobalObjectIds(ArrayView<const gno_t> &gnos) const {}
01521 
01522 };
01523 
01525 // Graph model derived from VectorInput.
01526 //
01527 //  We do not build a graph model from a vector.  We include
01528 //  this definition so that other code will compile.
01530 
01531 template <typename User>
01532 class GraphModel<VectorInput<User> > : public Model<VectorInput<User> >
01533 {
01534 public:
01535 
01536   typedef typename VectorInput<User>::scalar_t  scalar_t;
01537   typedef typename VectorInput<User>::gno_t     gno_t;
01538   typedef typename VectorInput<User>::lno_t     lno_t;
01539   typedef StridedData<lno_t, scalar_t> input_t;
01540 
01541   GraphModel(const VectorInput<User> *ia,
01542     const RCP<const Environment> &env, const RCP<const Comm<int> > &comm,
01543     modelFlag_t &flags)
01544   {
01545     throw std::runtime_error("can not build a graph from a vector");
01546   }
01547 
01548   // GraphModel interface
01549 
01550   size_t getLocalNumVertices() const { return 0;}
01551   size_t getGlobalNumVertices() const { return 0;}
01552   size_t getLocalNumGlobalEdges() const { return 0;}
01553   size_t getLocalNumLocalEdges() const { return 0;}
01554   size_t getGlobalNumEdges() const {return 0;}
01555   int getVertexWeightDim() const { return 0; }
01556   int getEdgeWeightDim() const { return 0; }
01557   int getCoordinateDim() const { return 0; }
01558   size_t getVertexList( ArrayView<const gno_t> &Ids,
01559     ArrayView<input_t> &xyz,
01560     ArrayView<input_t> &wgts) const { return 0; }
01561   size_t getEdgeList( ArrayView<const gno_t> &edgeIds,
01562     ArrayView<const int> &procIds, ArrayView<const lno_t> &offsets,
01563     ArrayView<input_t> &wgts) const { return 0; }
01564   size_t getLocalEdgeList( ArrayView<const lno_t> &edgeIds,
01565     ArrayView<const lno_t> &offsets,
01566     ArrayView<input_t> &wgts) { return 0; }
01567 
01568   // Model interface
01569 
01570   size_t getLocalNumObjects() const { return 0; }
01571   size_t getGlobalNumObjects() const { return 0; }
01572   void getGlobalObjectIds(ArrayView<const gno_t> &gnos) const {}
01573 
01574 };
01575 
01577 // Graph model derived from IdentifierInput.
01578 //
01579 //  We do not build a graph model from identifiers.  We include
01580 //  this definition so that other code will compile.
01582 
01583 template <typename User>
01584 class GraphModel<IdentifierInput<User> > : public Model<IdentifierInput<User> >
01585 {
01586 public:
01587 
01588   typedef typename IdentifierInput<User>::scalar_t  scalar_t;
01589   typedef typename IdentifierInput<User>::gno_t     gno_t;
01590   typedef typename IdentifierInput<User>::lno_t     lno_t;
01591   typedef StridedData<lno_t, scalar_t> input_t;
01592 
01593   GraphModel(const IdentifierInput<User> *ia,
01594     const RCP<const Environment> &env, const RCP<const Comm<int> > &comm,
01595     modelFlag_t &flags)
01596   {
01597     throw std::runtime_error("can not build a graph with identifiers");
01598   }
01599 
01600   // GraphModel interface
01601 
01602   size_t getLocalNumVertices() const { return 0;}
01603   size_t getGlobalNumVertices() const { return 0;}
01604   size_t getLocalNumGlobalEdges() const { return 0;}
01605   size_t getLocalNumLocalEdges() const { return 0;}
01606   size_t getGlobalNumEdges() const {return 0;}
01607   int getVertexWeightDim() const { return 0; }
01608   int getEdgeWeightDim() const { return 0; }
01609   int getCoordinateDim() const { return 0; }
01610   size_t getVertexList( ArrayView<const gno_t> &Ids,
01611     ArrayView<input_t> &xyz,
01612     ArrayView<input_t> &wgts) const { return 0; }
01613   size_t getEdgeList( ArrayView<const gno_t> &edgeIds,
01614     ArrayView<const int> &procIds, ArrayView<const lno_t> &offsets,
01615     ArrayView<input_t> &wgts) const { return 0; }
01616   size_t getLocalEdgeList( ArrayView<const lno_t> &edgeIds,
01617     ArrayView<const lno_t> &offsets,
01618     ArrayView<input_t> &wgts) { return 0; }
01619 
01620   // Model interface
01621 
01622   size_t getLocalNumObjects() const { return 0; }
01623   size_t getGlobalNumObjects() const { return 0; }
01624   void getGlobalObjectIds(ArrayView<const gno_t> &gnos) const {}
01625 
01626 };
01627 
01628 #endif    // DOXYGEN_SHOULD_SKIP_THIS
01629 
01630 }   // namespace Zoltan2
01631 
01632 #endif
01633