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;
98  typedef typename Adapter::base_adapter_t base_adapter_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 
129  //
130  // \param updateInputData If true this indicates that either
131  // this is the first attempt at solution, or that we
132  // are computing a new solution and the input data has
133  // changed since the previous solution was computed.
134  // If false, this indicates that we are computing a
135  // new solution using the same input data was used for
136  // the previous solution, even though the parameters
137  // may have been changed.
138  //
139  // For the sake of performance, we ask the caller to set \c updateInputData
140  // to false if he/she is computing a new solution using the same input data,
141  // but different problem parameters, than that which was used to compute
142  // the most recent solution.
143 
144  void solve(bool updateInputData=true);
145 
147  //
148  // \return a reference to the solution to the most recent solve().
149 
151  // Get the raw ptr from the rcp
152  return solution_.getRawPtr();
153  };
154 
155 private:
156  void createColoringProblem();
157 
158  RCP<ColoringSolution<Adapter> > solution_;
159 
160  RCP<Comm<int> > problemComm_;
161  RCP<const Comm<int> > problemCommConst_;
162 
163 };
164 
165 
167 template <typename Adapter>
169 {
170  HELLO;
171 
172  size_t nVtx = this->baseModel_->getLocalNumObjects();
173 
174  try
175  {
176  this->solution_ = rcp(new ColoringSolution<Adapter>(nVtx));
177  }
179 
180  // Determine which algorithm to use based on defaults and parameters.
181  // Need some exception handling here, too.
182 
183  std::string method = this->params_->template get<std::string>("color_method", "SerialGreedy");
184 
185  try
186  {
187  // TODO: Ignore case
188  if (method.compare("SerialGreedy") == 0)
189  {
191  this->env_, problemComm_);
192  alg.color(this->solution_);
193  }
194 #if 0 // TODO later
195  else if (method.compare("speculative") == 0) // Gebremedhin-Manne
196  {
197  AlgGM<base_adapter_t> alg(this->graphModel_, problemComm_);
198  alg.color(this->solution_, this->params_);
199  }
200 #endif
201  }
203 }
204 
206 //template <typename Adapter>
207 //void ColoringProblem<Adapter>::redistribute()
208 //{
209 // HELLO;
210 //}
211 
214 // Method with common functionality for creating a ColoringProblem.
215 // Individual constructors do appropriate conversions of input, etc.
216 // This method does everything that all constructors must do.
217 
218 template <typename Adapter>
220 {
221  HELLO;
222  using Teuchos::ParameterList;
223 
224 // std::cout << __func__zoltan2__ << " input adapter type "
225 // << this->inputAdapter_->inputAdapterType() << " "
226 // << this->inputAdapter_->inputAdapterName() << std::endl;
227 
228  // Create a copy of the user's communicator.
229 
230  problemComm_ = this->comm_->duplicate();
231  problemCommConst_ = rcp_const_cast<const Comm<int> > (problemComm_);
232 
233  // Only graph model supported.
234  // TODO: Allow hypergraph later?
235 
236  ModelType modelType = GraphModelType;
237 
238  // Select Model based on parameters and InputAdapter type
239 
240  std::bitset<NUM_MODEL_FLAGS> graphFlags;
241  std::bitset<NUM_MODEL_FLAGS> idFlags;
242 
243  switch (modelType) {
244 
245  case GraphModelType:
246  graphFlags.set(REMOVE_SELF_EDGES);
247  graphFlags.set(BUILD_LOCAL_GRAPH);
248  this->graphModel_ = rcp(new GraphModel<base_adapter_t>(
249  this->baseInputAdapter_, this->envConst_, problemCommConst_, graphFlags));
250 
251  this->baseModel_ = rcp_implicit_cast<const Model<base_adapter_t> >(
252  this->graphModel_);
253 
254  break;
255 
256 
257  case IdentifierModelType:
258  case HypergraphModelType:
259  case CoordinateModelType:
260  std::cout << __func__zoltan2__ << " Model type " << modelType
261  << " not yet supported." << std::endl;
262  break;
263 
264  default:
265  std::cout << __func__zoltan2__ << " Invalid model" << modelType
266  << std::endl;
267  break;
268  }
269 }
270 } //namespace Zoltan2
271 
272 #endif
RCP< GraphModel< base_adapter_t > > graphModel_
#define HELLO
RCP< const base_adapter_t > baseInputAdapter_
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
RCP< const Comm< int > > comm_
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.
GraphModel defines the interface required for graph models.
RCP< Environment > env_
Gathering definitions used in software development.
The base class for all model classes.
RCP< ParameterList > params_
Defines the ColoringSolution class.
ColoringProblem(Adapter *A, ParameterList *p)
Constructor that uses a default communicator.
Defines the GraphModel interface.
RCP< const Model< base_adapter_t > > baseModel_
model represents graph within only one rank
RCP< const Environment > envConst_
#define __func__zoltan2__
virtual ~ColoringProblem()
Destructor.
The class containing coloring solution.