45 #ifndef _ZOLTAN2_ALGSERIALGREEDY_HPP_ 46 #define _ZOLTAN2_ALGSERIALGREEDY_HPP_ 58 template <
typename Adapter>
62 typedef typename Adapter::lno_t lno_t;
63 typedef typename Adapter::gno_t gno_t;
64 typedef typename Adapter::scalar_t scalar_t;
66 RCP<GraphModel<typename Adapter::base_adapter_t> > model_;
67 RCP<Teuchos::ParameterList> pl_;
68 RCP<Environment> env_;
69 RCP<const Teuchos::Comm<int> > comm_;
74 const RCP<Teuchos::ParameterList> &pl,
75 const RCP<Environment> &env,
76 const RCP<
const Teuchos::Comm<int> > &comm
77 ) : model_(model), pl_(pl), env_(env), comm_(comm)
90 ArrayView<const gno_t> edgeIds;
91 ArrayView<const lno_t> offsets;
92 ArrayView<StridedData<lno_t, scalar_t> > wgts;
94 const size_t nVtx = model_->getLocalNumVertices();
95 model_->getEdgeList(edgeIds, offsets, wgts);
99 cout <<
"Debug: Local graph from getLocalEdgeList" << endl;
100 cout <<
"rank " << comm_->getRank() <<
": nVtx= " << nVtx << endl;
101 cout <<
"rank " << comm_->getRank() <<
": edgeIds: " << edgeIds << endl;
102 cout <<
"rank " << comm_->getRank() <<
": offsets: " << offsets << endl;
107 ArrayRCP<int> colors = solution->getColorsRCP();
108 for (
size_t i=0; i<nVtx; i++){
122 ArrayView<const gno_t> edgeIds,
123 ArrayView<const lno_t> offsets,
131 for (
size_t i=0; i<nVtx; i++){
132 if (offsets[i+1]-offsets[i] > maxDegree)
133 maxDegree = offsets[i+1]-offsets[i];
142 Teuchos::Array<int> forbidden(maxDegree+2, 0);
145 Teuchos::Array<lno_t> numVerticesWithColor(maxDegree+2, 0);
148 Teuchos::ParameterList &pl = env_->getParametersNonConst();
149 std::string colorChoice = pl.get<std::string>(
"color_choice",
"FirstFit");
151 for (
size_t i=0; i<nVtx; i++){
154 for (lno_t j=offsets[v]; j<offsets[v+1]; j++){
155 gno_t nbor = edgeIds[j];
157 if (colors[nbor] > 0){
159 forbidden[colors[nbor]] = v;
166 if ((colors[v]==0) || ((colors[v]>0) && forbidden[colors[v]] == v)){
168 if (colorChoice.compare(
"FirstFit")){
170 for (
int c=1; c <= maxColor+1; c++){
171 if (forbidden[c] != v){
177 else if (colorChoice.compare(
"Random")){
181 Teuchos::Array<int> avail(maxColor+1);
182 for (
int c=1; c < maxColor+1; c++){
183 if (forbidden[c] != v){
184 avail[numAvail++] = c;
188 colors[v] = maxColor+1;
190 colors[v] = avail[rand()%numAvail];
192 else if (colorChoice.compare(
"RandomFast")){
194 bool foundColor =
false;
195 int r = (rand() % maxColor) +1;
196 for (
int c=r; c <= maxColor; c++){
197 if (forbidden[c] != v){
204 for (
int c=1; c < r; c++){
205 if (forbidden[c] != v){
212 if (!foundColor) colors[v] = maxColor+1;
214 else if (colorChoice.compare(
"LeastUsed")){
217 int leastUsedColor = 1;
218 lno_t leastUsedNumber = numVerticesWithColor[1];
219 for (
int c=1; c <= maxColor; c++){
220 if (forbidden[c] != v){
221 if (numVerticesWithColor[c] < leastUsedColor){
223 leastUsedNumber = numVerticesWithColor[c];
227 colors[v] = leastUsedColor;
230 numVerticesWithColor[colors[v]]++;
233 if ((v==0) && colors[v]==0) colors[v]=1;
236 if (colors[v] > maxColor){
237 maxColor = colors[v];
249 RCP<Teuchos::StringValidator> color_choice_Validator = Teuchos::rcp(
250 new Teuchos::StringValidator(
251 Teuchos::tuple<std::string>(
252 "FirstFit",
"Random",
"RandomFast",
"LeastUsed" )));
253 pl.set(
"color_choice",
"FirstFit",
"selection criterion for coloring",
254 color_choice_Validator);
Time an algorithm (or other entity) as a whole.
void colorCrsGraph(const size_t nVtx, ArrayView< const gno_t > edgeIds, ArrayView< const lno_t > offsets, ArrayRCP< int > colors)
void color(const RCP< ColoringSolution< Adapter > > &solution)
Coloring method.
AlgSerialGreedy(const RCP< GraphModel< typename Adapter::base_adapter_t > > &model, const RCP< Teuchos::ParameterList > &pl, const RCP< Environment > &env, const RCP< const Teuchos::Comm< int > > &comm)
Algorithm defines the base class for all algorithms.
GraphModel defines the interface required for graph models.
Defines the ColoringSolution class.
Defines the GraphModel interface.
static void getValidParameters(ParameterList &pl)
Set up validators specific to this algorithm.
The class containing coloring solution.