Zoltan2
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Zoltan2_ColoringProblem.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_COLORINGPROBLEM_HPP_
51 #define _ZOLTAN2_COLORINGPROBLEM_HPP_
52 
53 #include <Zoltan2_Standards.hpp>
54 
55 #include <Zoltan2_Problem.hpp>
58 
59 #include <Zoltan2_GraphModel.hpp>
60 #include <string>
61 
62 #include <bitset>
63 
64 namespace Zoltan2{
65 
67 
87 template<typename Adapter>
88 class ColoringProblem : public Problem<Adapter>
89 {
90 public:
91 
92  typedef typename Adapter::scalar_t scalar_t;
93  typedef typename Adapter::gno_t gno_t;
94  typedef typename Adapter::lno_t lno_t;
95  typedef typename Adapter::user_t user_t;
97 
98 #ifdef HAVE_ZOLTAN2_MPI
99  typedef Teuchos::OpaqueWrapper<MPI_Comm> mpiWrapper_t;
100 #endif
101 
104  virtual ~ColoringProblem() {};
105 
108  ColoringProblem(Adapter *A, ParameterList *p,
109  const Teuchos::RCP<const Teuchos::Comm<int> > &comm) :
110  Problem<Adapter>(A, p, comm)
111  {
112  HELLO;
113  createColoringProblem();
114  };
115 
116 #ifdef HAVE_ZOLTAN2_MPI
117 
119  ColoringProblem(Adapter *A, ParameterList *p, MPI_Comm mpicomm) :
120  ColoringProblem(A, p,
121  rcp<const Comm<int> >(new Teuchos::MpiComm<int>(
122  Teuchos::opaqueWrapper(mpicomm))))
123  {}
124 #endif
125 
128  ColoringProblem(Adapter *A, ParameterList *p) :
129  ColoringProblem(A, p, Tpetra::getDefaultComm())
130  {}
131 
134  static void getValidParameters(ParameterList & pl)
135  {
136  RCP<Teuchos::StringValidator> color_method_Validator = Teuchos::rcp(
137  new Teuchos::StringValidator(
138  Teuchos::tuple<std::string>( "SerialGreedy","D1","D1-2GL","D2","PD2" )));
139  pl.set("color_method", "SerialGreedy", "coloring algorithm",
140  color_method_Validator);
141  pl.set("verbose", false, "print all output", Environment::getBoolValidator());
142  pl.set("timing", false, "print timing data", Environment::getBoolValidator());
143  pl.set("serial_threshold",0,"vertices to recolor in serial",Environment::getAnyIntValidator());
144  pl.set("recolor_degrees",true,"recolor based on vertex degrees",Environment::getBoolValidator());
145  }
146 
148  //
149  // \param updateInputData If true this indicates that either
150  // this is the first attempt at solution, or that we
151  // are computing a new solution and the input data has
152  // changed since the previous solution was computed.
153  // If false, this indicates that we are computing a
154  // new solution using the same input data was used for
155  // the previous solution, even though the parameters
156  // may have been changed.
157  //
158  // For the sake of performance, we ask the caller to set \c updateInputData
159  // to false if he/she is computing a new solution using the same input data,
160  // but different problem parameters, than that which was used to compute
161  // the most recent solution.
162 
163  void solve(bool updateInputData=true);
164 
166  //
167  // \return a reference to the solution to the most recent solve().
168 
170  // Get the raw ptr from the rcp
171  return solution_.getRawPtr();
172  };
173 
174 private:
175  void createColoringProblem();
176 
177  RCP<ColoringSolution<Adapter> > solution_;
178  size_t localNumObjects_;
179 };
180 
181 
183 template <typename Adapter>
185 {
186  HELLO;
187 
188  try
189  {
190  this->solution_ = rcp(new ColoringSolution<Adapter>(localNumObjects_));
191  }
193 
194  // Determine which algorithm to use based on defaults and parameters.
195  // Need some exception handling here, too.
196 
197  std::string method = this->params_->template get<std::string>("color_method", "SerialGreedy");
198 
199  try
200  {
201  // TODO: Ignore case
202  if (method.compare("SerialGreedy") == 0)
203  {
204  modelFlag_t graphFlags;
205  graphFlags.set(REMOVE_SELF_EDGES);
206  graphFlags.set(BUILD_LOCAL_GRAPH);
207 
208  AlgSerialGreedy<Adapter> alg(this->inputAdapter_, this->params_,
209  this->env_, this->comm_, graphFlags);
210  alg.color(this->solution_);
211  }
212  else if (method.compare("D1") == 0)
213  {
214  AlgDistance1<Adapter> alg(this->inputAdapter_, this->params_,
215  this->env_, this->comm_);
216  alg.color(this->solution_);
217  }
218  else if (method.compare("D1-2GL") == 0)
219  {
220  AlgDistance1TwoGhostLayer<Adapter> alg(this->inputAdapter_,this->params_,
221  this->env_, this->comm_);
222  alg.color(this->solution_);
223  } else if(method.compare("D2") == 0)
224  {
225  AlgDistance2<Adapter> alg(this->inputAdapter_, this->params_,
226  this->env_, this->comm_);
227  alg.color(this->solution_);
228  } else if (method.compare("PD2") == 0)
229  {
230  AlgPartialDistance2<Adapter> alg(this->inputAdapter_, this->params_,
231  this->env_, this->comm_);
232  alg.color(this->solution_);
233  }
234  }
236 }
237 
239 //template <typename Adapter>
240 //void ColoringProblem<Adapter>::redistribute()
241 //{
242 // HELLO;
243 //}
244 
247 // Method with common functionality for creating a ColoringProblem.
248 // Individual constructors do appropriate conversions of input, etc.
249 // This method does everything that all constructors must do.
250 
251 template <typename Adapter>
253 {
254  HELLO;
255  using Teuchos::ParameterList;
256 
257 // std::cout << __func__zoltan2__ << " input adapter type "
258 // << this->inputAdapter_->inputAdapterType() << " "
259 // << this->inputAdapter_->inputAdapterName() << std::endl;
260 
261  // Create a copy of the user's communicator.
262 
263  // Only graph model supported.
264  // TODO: Allow hypergraph later?
265 
266  ModelType modelType = GraphModelType;
267  const auto adapterType = this->baseInputAdapter_->adapterType();
268 
269  // Select Model based on parameters and InputAdapter type
270 
271  switch (modelType)
272  {
273 
274  case GraphModelType:
275  {
276  switch (adapterType)
277  {
278  case MatrixAdapterType:
279  {
280  localNumObjects_ = this->baseInputAdapter_->getLocalNumIDs();
281  }
282  break;
283 
284  case GraphAdapterType:
285  {
286  const auto ia = dynamic_cast<const GraphAdapter<user_t> *>(&(*(this->baseInputAdapter_)));
287  localNumObjects_ = ia->getLocalNumVertices();
288  }
289  break;
290 
291  case MeshAdapterType:
292  {
293  const auto ia = dynamic_cast<const MeshAdapter<user_t> *>(&(*(this->baseInputAdapter_)));
294  localNumObjects_ = ia->getLocalNumOf(ia->getPrimaryEntityType());
295  }
296  break;
297 
298  default:
299  {
300  // Avoid warning
301  }
302  }
303  }
304  break;
305 
306  case IdentifierModelType:
307  case HypergraphModelType:
308  case CoordinateModelType:
309  std::cout << __func__zoltan2__ << " Model type " << modelType
310  << " not yet supported." << std::endl;
311  break;
312 
313  default:
314  std::cout << __func__zoltan2__ << " Invalid model" << modelType
315  << std::endl;
316  break;
317  }
318 }
319 } //namespace Zoltan2
320 
321 #endif
#define HELLO
Zoltan2::BaseAdapter< userTypes_t > base_adapter_t
ColoringProblem(Adapter *A, ParameterList *p, const Teuchos::RCP< const Teuchos::Comm< int > > &comm)
Constructor that uses a Teuchos::Comm.
ColoringProblem sets up coloring problems for the user.
ModelType
An identifier for the general type of model.
#define Z2_FORWARD_EXCEPTIONS
Forward an exception back through call stack.
static RCP< Teuchos::BoolParameterEntryValidator > getBoolValidator()
Exists to make setting up validators less cluttered.
void solve(bool updateInputData=true)
Direct the problem to create a solution.
ColoringSolution< Adapter > * getSolution()
Get the solution to the problem.
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
map_t::global_ordinal_type gno_t
Definition: mapRemotes.cpp:18
Adapter::base_adapter_t base_adapter_t
void color(const RCP< ColoringSolution< Adapter > > &solution)
Coloring method.
algorithm requires no self edges
void color(const RCP< ColoringSolution< Adapter > > &solution)
Coloring method.
void color(const RCP< ColoringSolution< Adapter > > &solution)
Coloring method.
Problem base class from which other classes (PartitioningProblem, ColoringProblem, OrderingProblem, MatchingProblem, etc.) derive.
Defines the Problem base class.
map_t::local_ordinal_type lno_t
Definition: mapRemotes.cpp:17
static RCP< Teuchos::AnyNumberParameterEntryValidator > getAnyIntValidator()
Exists to make setting up validators less cluttered.
static void getValidParameters(ParameterList &pl)
Set up validators specific to this Problem.
Gathering definitions used in software development.
Defines the ColoringSolution class.
ColoringProblem(Adapter *A, ParameterList *p)
Constructor that uses a default communicator.
Defines the GraphModel interface.
model represents graph within only one rank
#define __func__zoltan2__
virtual ~ColoringProblem()
Destructor.
The class containing coloring solution.
Zoltan2::BasicUserTypes< zscalar_t, zlno_t, zgno_t > user_t
Definition: Metric.cpp:74