Zoltan2
Zoltan2_AlgRandom.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_ALGRANDOM_HPP_
46 #define _ZOLTAN2_ALGRANDOM_HPP_
47 
48 #include <Zoltan2_Algorithm.hpp>
51 
52 
53 namespace Zoltan2{
54 
59 
60 template <typename Adapter>
61 class AlgRandom : public Algorithm<Adapter>
62 {
63  private:
64 
65  const RCP<IdentifierModel<Adapter> > model;
66  const RCP<Teuchos::ParameterList> pl;
67  const RCP<const Teuchos::Comm<int> > comm;
68 
69  public:
70 
71  typedef typename Adapter::lno_t lno_t;
72  typedef typename Adapter::gno_t gno_t;
73 
75  const RCP<IdentifierModel<Adapter> > &model__,
76  const RCP<Teuchos::ParameterList> &pl__,
77  const RCP<const Teuchos::Comm<int> > &comm__
78  ) : model(model__), pl(pl__), comm(comm__)
79  {
80  }
81 
82  int order(const RCP<OrderingSolution<lno_t, gno_t> > &solution)
83  {
84 
85  int ierr= 0;
86 
87  HELLO;
88 
89  // This is the Fisher-Yates shuffle (aka Knuth shuffle).
90  // References:
91  // R.A. Fisher, F. Yates, (1948) [1938], Statistical tables for biological, agricultural and medical research (3rd ed.).
92  // R. Durstenfeld, "Algorithm 235: Random permutation", CACM, vol. 7, 1964.
93  // D.E. Knuth, "The Art of Computer Programming", volume 2, 1969.
94 
95  // Start with the identity permutation.
96  const size_t n = model->getLocalNumIdentifiers();
97  lno_t *perm;
98  perm = (lno_t *) (solution->getPermutationRCP().getRawPtr());
99  if (perm){
100  for (size_t i=0; i<n; i++){
101  perm[i] = i;
102  }
103  }
104  else
105  // throw exception?
106  ierr = -1;
107 
108  // Swap random pairs of indices in perm.
109  lno_t j, temp;
110  for (lno_t i=n-1; i>0; i--){
111  // Choose j randomly in [0,i]
112  j = rand() % (i+1);
113  // Swap (perm[i], perm[j])
114  temp = perm[i];
115  perm[i] = perm[j];
116  perm[j] = temp;
117  }
118 
119  solution->setHavePerm(true);
120  return ierr;
121 
122  }
123 
124 };
125 }
126 #endif
#define HELLO
Defines the OrderingSolution class.
Defines the IdentifierModel interface.
Algorithm defines the base class for all algorithms.
IdentifierModel defines the interface for all identifier models.
The class containing ordering solutions.
AlgRandom(const RCP< IdentifierModel< Adapter > > &model__, const RCP< Teuchos::ParameterList > &pl__, const RCP< const Teuchos::Comm< int > > &comm__)
int order(const RCP< OrderingSolution< lno_t, gno_t > > &solution)
Ordering method.