Zoltan2
Zoltan2_Algorithm.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 
50 #ifndef _ZOLTAN2_ALGORITHM_HPP_
51 #define _ZOLTAN2_ALGORITHM_HPP_
52 
53 namespace Zoltan2 {
54 template <typename Adapter>
55 class Algorithm;
56 }
57 
58 #include <Zoltan2_Standards.hpp>
64 
65 
66 namespace Zoltan2 {
67 
69 //
70 // Algorithms do not have to implement all methods in the Algorithm base
71 // class. They should implement only those methods that are relevant.
72 // For example AlgScotch might implement partition() and order(), while
73 // AlgMJ might implement partition() and boxAssign().
74 // Default implementations throw a "not implemented" error
75 
76 template <typename Adapter>
77 class Algorithm {
78 
79 public:
80 
81  typedef typename Adapter::lno_t lno_t;
82  typedef typename Adapter::gno_t gno_t;
83  typedef typename Adapter::scalar_t scalar_t;
84  typedef typename Adapter::part_t part_t;
85 
86  // Virtual destructor needed to avoid undefined behavior and compiler warnings
87  virtual ~Algorithm() {}
88 
90  virtual int order(const RCP<OrderingSolution<lno_t, gno_t> > &solution)
91  {
93  }
94 
96  virtual void color(const RCP<ColoringSolution<Adapter> > &solution)
97  {
99  }
100 
102  virtual void match() {
104  }
105 
107  virtual void partition(const RCP<PartitioningSolution<Adapter> > &solution)
108  {
110  }
111 
113  virtual void map(const RCP<MappingSolution<Adapter> > &solution)
114  {
116  }
117 
119  // computed parts
120  // Not all partitioning algorithms will support
121  // this method.
122  //
123  virtual std::vector<coordinateModelPartBox<scalar_t, part_t> > &
125  {
127  }
128 
130  // when a point lies on a part boundary, the lowest part
131  // number on that boundary is returned.
132  // Not all partitioning algorithms will support
133  // this method.
134  //
135  // \param dim : the number of dimensions specified for the point in space
136  // \param point : the coordinates of the point in space; array of size dim
137  // \return the part number of a part overlapping the given point
138  virtual part_t pointAssign(int dim, scalar_t *point) const
139  {
141  }
142 
144  // Return an array of all parts overlapping a given box in space.
145  // This method allocates memory for the return argument, but does not
146  // control that memory. The user is responsible for freeing the
147  // memory.
148  //
149  // \param dim : (in) the number of dimensions specified for the box
150  // \param ptLower : (in) the coordinates of the lower corner of the box;
151  // array of size dim
152  // \param ptUpper : (in) the coordinates of the upper corner of the box;
153  // array of size dim
154  // \param nParts : (out) the number of parts overlapping the box
155  // \param parts : (out) array of parts overlapping the box
156  virtual void boxAssign(int dim, scalar_t *lower, scalar_t *upper,
157  size_t &nParts, part_t **partsFound) const
158  {
160  }
161 
163  // Returned graph is identical on all processors, and represents the
164  // global communication pattern in the partition.
165  //
166  // \param comXAdj: (out) the offset array: offsets into comAdj
167  // Format is standard CSR format:
168  // # nbor parts of part i = comXAdj[i+1]-comXAdj[i]
169  // That is, comXAdj[i] = Sum of # nbor parts of parts
170  // 0 through i-1
171  // \param comAdj (out) the neighboring parts
172  virtual void getCommunicationGraph(
173  const PartitioningSolution<Adapter> *solution,
174  ArrayRCP<part_t> &comXAdj,
175  ArrayRCP<part_t> &comAdj)
176  // TODO: Should the return args be ArrayViews?
177  {
179  }
180 
182  // \param p: (in) the part for which the rank is sought
183  // This method need not be implemented by every algorithm or, indeed,
184  // for every mapping algorithm. Mapping algorithms may provide this
185  // function to prevent additional memory use in MappingSolution.
186  // For example, AlgContiguousMapping can compute this function implicitly,
187  // with no additional storage. However, Mapping algorithms can skip this
188  // function and, instead, register their results in MappingSolution.
189  virtual int getRankForPart(part_t p)
190  {
192  }
193 
195  // \param numParts: (out) the number of parts assigned to the current rank
196  // \param parts: (out) a view of the assigned parts
197  //
198  // This method need not be implemented by every algorithm or, indeed,
199  // for every mapping algorithm. Mapping algorithms may provide this
200  // function to prevent additional memory use in MappingSolution.
201  // For example, AlgContiguousMapping can compute this function implicitly,
202  // with no additional storage. However, Mapping algorithms can skip this
203  // function and, instead, register their results in MappingSolution.
204  virtual void getMyPartsView(part_t &numParts, part_t *&parts)
205  {
207  }
208 
209 
210 private:
211 };
212 
213 } //namespace Zoltan2
214 
215 #endif
virtual void map(const RCP< MappingSolution< Adapter > > &solution)
Mapping method.
virtual std::vector< coordinateModelPartBox< scalar_t, part_t > > & getPartBoxesView() const
for partitioning methods, return bounding boxes of the
virtual void getCommunicationGraph(const PartitioningSolution< Adapter > *solution, ArrayRCP< part_t > &comXAdj, ArrayRCP< part_t > &comAdj)
returns serial communication graph of a computed partition
PartitionMapping maps a solution or an input distribution to ranks.
virtual part_t pointAssign(int dim, scalar_t *point) const
pointAssign method: Available only for some partitioning algorithms
Defines the OrderingSolution class.
#define Z2_THROW_NOT_IMPLEMENTED
Defines the PartitioningSolution class.
virtual void getMyPartsView(part_t &numParts, part_t *&parts)
In mapping, returns a view of parts assigned to the current rank.
Adapter::scalar_t scalar_t
A PartitioningSolution is a solution to a partitioning problem.
virtual void match()
Matching method.
Adapter::part_t part_t
virtual int getRankForPart(part_t p)
In mapping, returns the rank to which a part is assigned.
Algorithm defines the base class for all algorithms.
virtual int order(const RCP< OrderingSolution< lno_t, gno_t > > &solution)
Ordering method.
virtual void partition(const RCP< PartitioningSolution< Adapter > > &solution)
Partitioning method.
Defines the MappingSolution class.
virtual void color(const RCP< ColoringSolution< Adapter > > &solution)
Coloring method.
virtual void boxAssign(int dim, scalar_t *lower, scalar_t *upper, size_t &nParts, part_t **partsFound) const
boxAssign method: Available only for some partitioning algorithms
Gathering definitions used in software development.
Defines the ColoringSolution class.
#define nParts
The class containing ordering solutions.
The class containing coloring solution.