Zoltan2
Zoltan2_AlgSortedDegree.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 #ifndef _ZOLTAN2_SORTEDDEGREE_HPP_
46 #define _ZOLTAN2_SORTEDDEGREE_HPP_
47 
48 #include <Zoltan2_Algorithm.hpp>
49 #include <Zoltan2_GraphModel.hpp>
51 #include <Zoltan2_Sort.hpp>
52 #include <algorithm>
53 
54 
59 
60 namespace Zoltan2{
61 
62 template <typename Adapter>
63 class AlgSortedDegree : public Algorithm<Adapter>
64 {
65  private:
66 
67  const RCP<GraphModel<Adapter> > model;
68  const RCP<Teuchos::ParameterList> pl;
69  const RCP<Teuchos::Comm<int> > comm;
70 
71  public:
72 
73  typedef typename Adapter::lno_t lno_t;
74  typedef typename Adapter::gno_t gno_t;
75  typedef typename Adapter::scalar_t scalar_t;
76 
78  const RCP<GraphModel<Adapter> > &model__,
79  const RCP<Teuchos::ParameterList> &pl__,
80  const RCP<Teuchos::Comm<int> > &comm__
81  ) : model(model__), pl(pl__), comm(comm__)
82  {
83  }
84 
85  int order(const RCP<OrderingSolution<lno_t, gno_t> > &solution)
86  {
87  int ierr= 0;
88 
89  HELLO;
90 
91  lno_t *perm;
92  perm = (lno_t *) (solution->getPermutation());
93  if (perm==0){
94  // Throw exception
95  std::cerr << "perm is NULL" << std::endl;
96  ierr = -1;
97  }
98 
99  // Get local graph.
100  const size_t nVtx = model->getLocalNumVertices();
101  ArrayView<const gno_t> edgeIds;
102  ArrayView<const lno_t> offsets;
103  ArrayView<StridedData<lno_t, scalar_t> > wgts;
104  model->getEdgeList(edgeIds, offsets, wgts);
105 
106  // Store degrees together with index so we can sort.
107  Teuchos::Array<std::pair<lno_t, size_t> > degrees(nVtx);
108  for (lno_t i=0; i<(lno_t)nVtx; i++){
109  degrees[i].first = i;
110  degrees[i].second = offsets[i+1] - offsets[i];
111  }
112 
113  // Sort degrees.
115  bool inc = true; // TODO: Add user parameter
116  zort.sort(degrees, inc);
117 
118  // Copy permuted indices to perm.
119  for (lno_t i=0; i<(lno_t)nVtx; i++){
120  perm[i] = degrees[i].first;
121  }
122 
123  solution->setHavePerm(true);
124  return ierr;
125  }
126 
127 };
128 }
129 #endif
#define HELLO
AlgSortedDegree(const RCP< GraphModel< Adapter > > &model__, const RCP< Teuchos::ParameterList > &pl__, const RCP< Teuchos::Comm< int > > &comm__)
Defines the OrderingSolution class.
Algorithm defines the base class for all algorithms.
Sort vector of pairs (key, value) by value.
GraphModel defines the interface required for graph models.
int order(const RCP< OrderingSolution< lno_t, gno_t > > &solution)
Ordering method.
Defines the GraphModel interface.
The class containing ordering solutions.
void sort(Teuchos::Array< std::pair< key_t, value_t > > &listofPairs, bool inc=true)