Zoltan2
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 using Teuchos::rcp_dynamic_cast;
65 
66 namespace Zoltan2{
67 
69 
89 template<typename Adapter>
90 class ColoringProblem : public Problem<Adapter>
91 {
92 public:
93 
94  typedef typename Adapter::scalar_t scalar_t;
95  typedef typename Adapter::gno_t gno_t;
96  typedef typename Adapter::lno_t lno_t;
97  typedef typename Adapter::user_t user_t;
99 
100 #ifdef HAVE_ZOLTAN2_MPI
101  typedef Teuchos::OpaqueWrapper<MPI_Comm> mpiWrapper_t;
102 #endif
103 
106  virtual ~ColoringProblem() {};
107 
108 
109 #ifdef HAVE_ZOLTAN2_MPI
110 
112  ColoringProblem(Adapter *A, ParameterList *p, MPI_Comm comm)
113  : Problem<Adapter>(A, p, comm)
114  {
115  HELLO;
116  createColoringProblem();
117  };
118 #endif
119 
122  ColoringProblem(Adapter *A, ParameterList *p) : Problem<Adapter>(A, p)
123  {
124  HELLO;
125  createColoringProblem();
126  };
127 
130  static void getValidParameters(ParameterList & pl)
131  {
132  RCP<Teuchos::StringValidator> color_method_Validator = Teuchos::rcp(
133  new Teuchos::StringValidator(
134  Teuchos::tuple<std::string>( "SerialGreedy" )));
135  pl.set("color_method", "SerialGreedy", "coloring algorithm",
136  color_method_Validator);
137  }
138 
140  //
141  // \param updateInputData If true this indicates that either
142  // this is the first attempt at solution, or that we
143  // are computing a new solution and the input data has
144  // changed since the previous solution was computed.
145  // If false, this indicates that we are computing a
146  // new solution using the same input data was used for
147  // the previous solution, even though the parameters
148  // may have been changed.
149  //
150  // For the sake of performance, we ask the caller to set \c updateInputData
151  // to false if he/she is computing a new solution using the same input data,
152  // but different problem parameters, than that which was used to compute
153  // the most recent solution.
154 
155  void solve(bool updateInputData=true);
156 
158  //
159  // \return a reference to the solution to the most recent solve().
160 
162  // Get the raw ptr from the rcp
163  return solution_.getRawPtr();
164  };
165 
166 private:
167  void createColoringProblem();
168 
169  RCP<ColoringSolution<Adapter> > solution_;
170 };
171 
172 
174 template <typename Adapter>
176 {
177  HELLO;
178 
179  size_t nVtx = this->baseModel_->getLocalNumObjects();
180 
181  try
182  {
183  this->solution_ = rcp(new ColoringSolution<Adapter>(nVtx));
184  }
186 
187  // Determine which algorithm to use based on defaults and parameters.
188  // Need some exception handling here, too.
189 
190  std::string method = this->params_->template get<std::string>("color_method", "SerialGreedy");
191 
192  try
193  {
194  // TODO: Ignore case
195  if (method.compare("SerialGreedy") == 0)
196  {
197  AlgSerialGreedy<Adapter> alg(this->graphModel_, this->params_,
198  this->env_, this->comm_);
199  alg.color(this->solution_);
200  }
201 #if 0 // TODO later
202  else if (method.compare("speculative") == 0) // Gebremedhin-Manne
203  {
204  AlgGM<base_adapter_t> alg(this->graphModel_, this->comm_);
205  alg.color(this->solution_, this->params_);
206  }
207 #endif
208  }
210 }
211 
213 //template <typename Adapter>
214 //void ColoringProblem<Adapter>::redistribute()
215 //{
216 // HELLO;
217 //}
218 
221 // Method with common functionality for creating a ColoringProblem.
222 // Individual constructors do appropriate conversions of input, etc.
223 // This method does everything that all constructors must do.
224 
225 template <typename Adapter>
227 {
228  HELLO;
229  using Teuchos::ParameterList;
230 
231 // std::cout << __func__zoltan2__ << " input adapter type "
232 // << this->inputAdapter_->inputAdapterType() << " "
233 // << this->inputAdapter_->inputAdapterName() << std::endl;
234 
235  // Create a copy of the user's communicator.
236 
237  // Only graph model supported.
238  // TODO: Allow hypergraph later?
239 
240  ModelType modelType = GraphModelType;
241 
242  // Select Model based on parameters and InputAdapter type
243 
244  std::bitset<NUM_MODEL_FLAGS> graphFlags;
245  std::bitset<NUM_MODEL_FLAGS> idFlags;
246 
247  switch (modelType) {
248 
249  case GraphModelType:
250  graphFlags.set(REMOVE_SELF_EDGES);
251  graphFlags.set(BUILD_LOCAL_GRAPH);
252  this->graphModel_ = rcp(new GraphModel<base_adapter_t>(
253  this->baseInputAdapter_, this->envConst_, this->comm_, graphFlags));
254 
255  this->baseModel_ = rcp_implicit_cast<const Model<base_adapter_t> >(
256  this->graphModel_);
257 
258  break;
259 
260 
261  case IdentifierModelType:
262  case HypergraphModelType:
263  case CoordinateModelType:
264  std::cout << __func__zoltan2__ << " Model type " << modelType
265  << " not yet supported." << std::endl;
266  break;
267 
268  default:
269  std::cout << __func__zoltan2__ << " Invalid model" << modelType
270  << std::endl;
271  break;
272  }
273 }
274 } //namespace Zoltan2
275 
276 #endif
#define HELLO
Zoltan2::BaseAdapter< userTypes_t > base_adapter_t
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.