Zoltan2
Loading...
Searching...
No Matches
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
60#include <string>
61
62#include <bitset>
63
64namespace Zoltan2{
65
67
87template<typename Adapter>
88class ColoringProblem : public Problem<Adapter>
89{
90public:
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;
96 typedef typename Adapter::base_adapter_t base_adapter_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
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
169 ColoringSolution<Adapter> *getSolution() {
170 // Get the raw ptr from the rcp
171 return solution_.getRawPtr();
172 };
173
174private:
175 void createColoringProblem();
176
177 RCP<ColoringSolution<Adapter> > solution_;
178 size_t localNumObjects_;
179};
180
181
183template <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
251template <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 {
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
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
Defines the ColoringSolution class.
#define Z2_FORWARD_EXCEPTIONS
Forward an exception back through call stack.
#define __func__zoltan2__
Defines the GraphModel interface.
Defines the Problem base class.
Gathering definitions used in software development.
#define HELLO
ColoringProblem sets up coloring problems for the user.
Adapter::base_adapter_t base_adapter_t
void solve(bool updateInputData=true)
Direct the problem to create a solution.
ColoringProblem(Adapter *A, ParameterList *p, const Teuchos::RCP< const Teuchos::Comm< int > > &comm)
Constructor that uses a Teuchos::Comm.
static void getValidParameters(ParameterList &pl)
Set up validators specific to this Problem.
ColoringSolution< Adapter > * getSolution()
Get the solution to the problem.
ColoringProblem(Adapter *A, ParameterList *p)
Constructor that uses a default communicator.
static RCP< Teuchos::BoolParameterEntryValidator > getBoolValidator()
Exists to make setting up validators less cluttered.
static RCP< Teuchos::AnyNumberParameterEntryValidator > getAnyIntValidator()
Exists to make setting up validators less cluttered.
Problem base class from which other classes (PartitioningProblem, ColoringProblem,...
Created by mbenlioglu on Aug 31, 2020.
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
ModelType
An identifier for the general type of model.
@ IdentifierModelType
@ HypergraphModelType
@ CoordinateModelType
@ GraphAdapterType
graph data
@ MatrixAdapterType
matrix data
@ MeshAdapterType
mesh data
@ REMOVE_SELF_EDGES
algorithm requires no self edges
@ BUILD_LOCAL_GRAPH
model represents graph within only one rank