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" )));
139  pl.set("color_method", "SerialGreedy", "coloring algorithm",
140  color_method_Validator);
141  }
142 
144  //
145  // \param updateInputData If true this indicates that either
146  // this is the first attempt at solution, or that we
147  // are computing a new solution and the input data has
148  // changed since the previous solution was computed.
149  // If false, this indicates that we are computing a
150  // new solution using the same input data was used for
151  // the previous solution, even though the parameters
152  // may have been changed.
153  //
154  // For the sake of performance, we ask the caller to set \c updateInputData
155  // to false if he/she is computing a new solution using the same input data,
156  // but different problem parameters, than that which was used to compute
157  // the most recent solution.
158 
159  void solve(bool updateInputData=true);
160 
162  //
163  // \return a reference to the solution to the most recent solve().
164 
166  // Get the raw ptr from the rcp
167  return solution_.getRawPtr();
168  };
169 
170 private:
171  void createColoringProblem();
172 
173  RCP<ColoringSolution<Adapter> > solution_;
174 };
175 
176 
178 template <typename Adapter>
180 {
181  HELLO;
182 
183  size_t nVtx = this->baseModel_->getLocalNumObjects();
184 
185  try
186  {
187  this->solution_ = rcp(new ColoringSolution<Adapter>(nVtx));
188  }
190 
191  // Determine which algorithm to use based on defaults and parameters.
192  // Need some exception handling here, too.
193 
194  std::string method = this->params_->template get<std::string>("color_method", "SerialGreedy");
195 
196  try
197  {
198  // TODO: Ignore case
199  if (method.compare("SerialGreedy") == 0)
200  {
201  AlgSerialGreedy<Adapter> alg(this->graphModel_, this->params_,
202  this->env_, this->comm_);
203  alg.color(this->solution_);
204  }
205 #if 0 // TODO later
206  else if (method.compare("speculative") == 0) // Gebremedhin-Manne
207  {
208  AlgGM<base_adapter_t> alg(this->graphModel_, this->comm_);
209  alg.color(this->solution_, this->params_);
210  }
211 #endif
212  }
214 }
215 
217 //template <typename Adapter>
218 //void ColoringProblem<Adapter>::redistribute()
219 //{
220 // HELLO;
221 //}
222 
225 // Method with common functionality for creating a ColoringProblem.
226 // Individual constructors do appropriate conversions of input, etc.
227 // This method does everything that all constructors must do.
228 
229 template <typename Adapter>
231 {
232  HELLO;
233  using Teuchos::ParameterList;
234 
235 // std::cout << __func__zoltan2__ << " input adapter type "
236 // << this->inputAdapter_->inputAdapterType() << " "
237 // << this->inputAdapter_->inputAdapterName() << std::endl;
238 
239  // Create a copy of the user's communicator.
240 
241  // Only graph model supported.
242  // TODO: Allow hypergraph later?
243 
244  ModelType modelType = GraphModelType;
245 
246  // Select Model based on parameters and InputAdapter type
247 
248  std::bitset<NUM_MODEL_FLAGS> graphFlags;
249  std::bitset<NUM_MODEL_FLAGS> idFlags;
250 
251  switch (modelType) {
252 
253  case GraphModelType:
254  graphFlags.set(REMOVE_SELF_EDGES);
255  graphFlags.set(BUILD_LOCAL_GRAPH);
256  this->graphModel_ = rcp(new GraphModel<base_adapter_t>(
257  this->baseInputAdapter_, this->envConst_, this->comm_, graphFlags));
258 
259  this->baseModel_ = rcp_implicit_cast<const Model<base_adapter_t> >(
260  this->graphModel_);
261 
262  break;
263 
264 
265  case IdentifierModelType:
266  case HypergraphModelType:
267  case CoordinateModelType:
268  std::cout << __func__zoltan2__ << " Model type " << modelType
269  << " not yet supported." << std::endl;
270  break;
271 
272  default:
273  std::cout << __func__zoltan2__ << " Invalid model" << modelType
274  << std::endl;
275  break;
276  }
277 }
278 } //namespace Zoltan2
279 
280 #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.
void solve(bool updateInputData=true)
Direct the problem to create a solution.
ColoringSolution< Adapter > * getSolution()
Get the solution to the problem.
Adapter::base_adapter_t base_adapter_t
void color(const RCP< ColoringSolution< Adapter > > &solution)
Coloring method.
algorithm requires no self edges
Problem base class from which other classes (PartitioningProblem, ColoringProblem, OrderingProblem, MatchingProblem, etc.) derive.
Defines the Problem base class.
static void getValidParameters(ParameterList &pl)
Set up validators specific to this Problem.
GraphModel defines the interface required for graph models.
Gathering definitions used in software development.
The base class for all model classes.
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