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<const 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<const 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 = solution->getPermutationView();
92  if (perm==0){
93  // Throw exception
94  std::cerr << "perm is NULL" << std::endl;
95  ierr = -1;
96  }
97 
98  // Get local graph.
99  const size_t nVtx = model->getLocalNumVertices();
100  ArrayView<const gno_t> edgeIds;
101  ArrayView<const lno_t> offsets;
102  ArrayView<StridedData<lno_t, scalar_t> > wgts;
103  model->getEdgeList(edgeIds, offsets, wgts);
104 
105  // Store degrees together with index so we can sort.
106  Teuchos::Array<std::pair<lno_t, size_t> > degrees(nVtx);
107  for (lno_t i=0; i<(lno_t)nVtx; i++){
108  degrees[i].first = i;
109  degrees[i].second = offsets[i+1] - offsets[i];
110  }
111 
112  // Sort degrees.
114  bool inc = true; // TODO: Add user parameter
115  zort.sort(degrees, inc);
116 
117  // Copy permuted indices to perm.
118  for (lno_t i=0; i<(lno_t)nVtx; i++){
119  perm[i] = degrees[i].first;
120  }
121 
122  solution->setHavePerm(true);
123  return ierr;
124  }
125 
126 };
127 }
128 #endif
#define HELLO
AlgSortedDegree(const RCP< GraphModel< Adapter > > &model__, const RCP< Teuchos::ParameterList > &pl__, const RCP< const 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)