Zoltan2
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
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>
65 
66 
67 namespace Zoltan2 {
68 
70 //
71 // Algorithms do not have to implement all methods in the Algorithm base
72 // class. They should implement only those methods that are relevant.
73 // For example AlgScotch might implement partition() and order(), while
74 // AlgMJ might implement partition() and boxAssign().
75 // Default implementations throw a "not implemented" error
76 
77 template <typename Adapter>
78 class Algorithm {
79 
80 public:
81 
82  typedef typename Adapter::lno_t lno_t;
83  typedef typename Adapter::gno_t gno_t;
84  typedef typename Adapter::scalar_t scalar_t;
85  typedef typename Adapter::part_t part_t;
86 
87  // Virtual destructor needed to avoid undefined behavior and compiler warnings
88  virtual ~Algorithm() {}
89 
91  virtual int localOrder(const RCP<LocalOrderingSolution<lno_t> > &/* solution */)
92  {
94  }
95 
97  virtual int globalOrder(const RCP<GlobalOrderingSolution<gno_t> > &/* solution */)
98  {
100  }
101 
103  virtual void color(const RCP<ColoringSolution<Adapter> > &/* solution */)
104  {
106  }
107 
109  virtual void match() {
111  }
112 
114  virtual void partition(const RCP<PartitioningSolution<Adapter> > &/* solution */)
115  {
117  }
118 
120  virtual void partitionMatrix(const RCP<MatrixPartitioningSolution<Adapter> > &/* solution */)
121  {
123  }
124 
126  virtual void map(const RCP<MappingSolution<Adapter> > &/* solution */)
127  {
129  }
130 
132  virtual bool isPartitioningTreeBinary() const
133  {
135  }
136 
138  virtual void getPartitionTree(part_t /* numParts */,
139  part_t & /* numTreeVerts */,
140  std::vector<part_t> & /* permPartNums */,
141  std::vector<part_t> & /* splitRangeBeg */,
142  std::vector<part_t> & /* splitRangeEnd */,
143  std::vector<part_t> & /* treeVertParents */) const
144  {
146  }
147 
149  // computed parts
150  // Not all partitioning algorithms will support
151  // this method.
152  //
153  virtual std::vector<coordinateModelPartBox> &
155  {
157  }
158 
160  // when a point lies on a part boundary, the lowest part
161  // number on that boundary is returned.
162  // Not all partitioning algorithms will support
163  // this method.
164  //
165  // \param dim : the number of dimensions specified for the point in space
166  // \param point : the coordinates of the point in space; array of size dim
167  // \return the part number of a part overlapping the given point
168  virtual part_t pointAssign(int /* dim */, scalar_t * /* point */) const
169  {
171  }
172 
174  // Return an array of all parts overlapping a given box in space.
175  // This method allocates memory for the return argument, but does not
176  // control that memory. The user is responsible for freeing the
177  // memory.
178  //
179  // \param dim : (in) the number of dimensions specified for the box
180  // \param ptLower : (in) the coordinates of the lower corner of the box;
181  // array of size dim
182  // \param ptUpper : (in) the coordinates of the upper corner of the box;
183  // array of size dim
184  // \param nParts : (out) the number of parts overlapping the box
185  // \param parts : (out) array of parts overlapping the box
186  virtual void boxAssign(int /* dim */, scalar_t * /* lower */, scalar_t * /* upper */,
187  size_t &/* nParts */, part_t ** /* partsFound */) const
188  {
190  }
191 
193  // Returned graph is identical on all processors, and represents the
194  // global communication pattern in the partition.
195  //
196  // \param comXAdj: (out) the offset array: offsets into comAdj
197  // Format is standard CSR format:
198  // # nbor parts of part i = comXAdj[i+1]-comXAdj[i]
199  // That is, comXAdj[i] = Sum of # nbor parts of parts
200  // 0 through i-1
201  // \param comAdj (out) the neighboring parts
202  virtual void getCommunicationGraph(
203  const PartitioningSolution<Adapter> * /* solution */,
204  ArrayRCP<part_t> &/* comXAdj */,
205  ArrayRCP<part_t> &/* comAdj */)
206  // TODO: Should the return args be ArrayViews?
207  {
209  }
210 
212  // \param p: (in) the part for which the rank is sought
213  // This method need not be implemented by every algorithm or, indeed,
214  // for every mapping algorithm. Mapping algorithms may provide this
215  // function to prevent additional memory use in MappingSolution.
216  // For example, AlgContiguousMapping can compute this function implicitly,
217  // with no additional storage. However, Mapping algorithms can skip this
218  // function and, instead, register their results in MappingSolution.
219  virtual int getRankForPart(part_t /* p */)
220  {
222  }
223 
225  // \param numParts: (out) the number of parts assigned to the current rank
226  // \param parts: (out) a view of the assigned parts
227  //
228  // This method need not be implemented by every algorithm or, indeed,
229  // for every mapping algorithm. Mapping algorithms may provide this
230  // function to prevent additional memory use in MappingSolution.
231  // For example, AlgContiguousMapping can compute this function implicitly,
232  // with no additional storage. However, Mapping algorithms can skip this
233  // function and, instead, register their results in MappingSolution.
234  virtual void getMyPartsView(part_t &/* numParts */, part_t *&/* parts */)
235  {
237  }
238 
239 
240 private:
241 };
242 
243 } //namespace Zoltan2
244 
245 #endif
virtual part_t pointAssign(int, scalar_t *) const
pointAssign method: Available only for some partitioning algorithms
virtual void boxAssign(int, scalar_t *, scalar_t *, size_t &, part_t **) const
boxAssign method: Available only for some partitioning algorithms
virtual void partition(const RCP< PartitioningSolution< Adapter > > &)
Partitioning method.
virtual void getCommunicationGraph(const PartitioningSolution< Adapter > *, ArrayRCP< part_t > &, ArrayRCP< part_t > &)
returns serial communication graph of a computed partition
PartitionMapping maps a solution or an input distribution to ranks.
virtual void getMyPartsView(part_t &, part_t *&)
In mapping, returns a view of parts assigned to the current rank.
virtual void map(const RCP< MappingSolution< Adapter > > &)
Mapping method.
Defines the OrderingSolution class.
#define Z2_THROW_NOT_IMPLEMENTED
Defines the PartitioningSolution class.
virtual int globalOrder(const RCP< GlobalOrderingSolution< gno_t > > &)
Ordering method.
virtual std::vector< coordinateModelPartBox > & getPartBoxesView() const
for partitioning methods, return bounding boxes of the
virtual void getPartitionTree(part_t, part_t &, std::vector< part_t > &, std::vector< part_t > &, std::vector< part_t > &, std::vector< part_t > &) const
for partitioning methods, fill arrays with partition tree info
SparseMatrixAdapter_t::part_t part_t
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 void partitionMatrix(const RCP< MatrixPartitioningSolution< Adapter > > &)
Matrix Partitioning method.
Algorithm defines the base class for all algorithms.
virtual int getRankForPart(part_t)
In mapping, returns the rank to which a part is assigned.
Defines the MappingSolution class.
Gathering definitions used in software development.
Defines the ColoringSolution class.
virtual void color(const RCP< ColoringSolution< Adapter > > &)
Coloring method.
virtual int localOrder(const RCP< LocalOrderingSolution< lno_t > > &)
Ordering method.
virtual bool isPartitioningTreeBinary() const
return if algorithm determins tree to be binary
A PartitioningSolution is a solution to a partitioning problem.
The class containing coloring solution.