Zoltan2
Loading...
Searching...
No Matches
Zoltan2_AlgSerialGreedy.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#ifndef _ZOLTAN2_ALGSERIALGREEDY_HPP_
46#define _ZOLTAN2_ALGSERIALGREEDY_HPP_
47
48#include <Zoltan2_Algorithm.hpp>
51
55
56namespace Zoltan2{
57
58template <typename Adapter>
59class AlgSerialGreedy : public Algorithm<Adapter>
60{
61 private:
62 typedef typename Adapter::lno_t lno_t;
63 typedef typename Adapter::gno_t gno_t;
64 typedef typename Adapter::offset_t offset_t;
65 typedef typename Adapter::scalar_t scalar_t;
66 // Class member variables
67 const RCP<const typename Adapter::base_adapter_t> adapter_;
68 RCP<Teuchos::ParameterList> pl_;
69 RCP<Environment> env_;
70 RCP<const Teuchos::Comm<int> > comm_;
71 modelFlag_t graphFlags_;
72
73 public:
75 const RCP<const typename Adapter::base_adapter_t> &adapter,
76 const RCP<Teuchos::ParameterList> &pl,
77 const RCP<Environment> &env,
78 const RCP<const Teuchos::Comm<int> > &comm,
79 modelFlag_t graphFlags
80 ) : adapter_(adapter), pl_(pl), env_(env), comm_(comm), graphFlags_(graphFlags)
81 {
82 }
83
84 // Main entry point for graph coloring.
85 void color(
86 const RCP<ColoringSolution<Adapter> > &solution
87 )
88 {
89 HELLO;
90
91 // Color local graph. Global coloring is supported in Zoltan (not Zoltan2).
92 // Get local graph.
93 ArrayView<const gno_t> edgeIds;
94 ArrayView<const offset_t> offsets;
95 ArrayView<StridedData<lno_t, scalar_t> > wgts; // Not used; needed by getLocalEdgeList
96
97 const auto model = rcp(new GraphModel<typename Adapter::base_adapter_t>(adapter_, env_, comm_, graphFlags_));
98 const size_t nVtx = model->getLocalNumVertices(); // Assume (0,nvtx-1)
99 model->getEdgeList(edgeIds, offsets, wgts); // Don't need wgts
100
101#if 0
102 // Debug
103 cout << "Debug: Local graph from getLocalEdgeList" << endl;
104 cout << "rank " << comm_->getRank() << ": nVtx= " << nVtx << endl;
105 cout << "rank " << comm_->getRank() << ": edgeIds: " << edgeIds << endl;
106 cout << "rank " << comm_->getRank() << ": offsets: " << offsets << endl;
107#endif
108
109 // Get color array to fill.
110 // TODO: Allow user to input an old coloring.
111 ArrayRCP<int> colors = solution->getColorsRCP();
112 for (size_t i=0; i<nVtx; i++){
113 colors[i] = 0;
114 }
115
116 // Let colorCrsGraph do the real work.
117 env_->timerStart(MACRO_TIMERS, "Coloring algorithm");
118 colorCrsGraph(nVtx, edgeIds, offsets, colors);
119 env_->timerStop(MACRO_TIMERS, "Coloring algorithm");
120 return;
121 }
122
123 // Color graph given by two arrays. API may change. Expert users only!
125 const size_t nVtx,
126 ArrayView<const gno_t> edgeIds,
127 ArrayView<const offset_t> offsets,
128 ArrayRCP<int> colors
129 )
130 {
131 HELLO;
132
133 // Find max degree, since (max degree)+1 is an upper bound.
134 offset_t maxDegree = 0;
135 for (size_t i=0; i<nVtx; i++){
136 if (offsets[i+1]-offsets[i] > maxDegree)
137 maxDegree = offsets[i+1]-offsets[i];
138 }
139
140 // Greedy coloring.
141 // Use natural order for now.
142 // TODO: Support better orderings (e.g., Smallest-Last)
143 int maxColor = 0;
144
145 // array of size #colors: forbidden[i]=v means color[v]=i so i is forbidden
146 Teuchos::Array<int> forbidden(maxDegree+2, 0);
147
148 // LeastUsed: need array of size #colors
149 Teuchos::Array<lno_t> numVerticesWithColor(maxDegree+2, 0);
150
151 // Get colorChoice from parameter list.
152 Teuchos::ParameterList &pl = env_->getParametersNonConst();
153 std::string colorChoice = pl.get<std::string>("color_choice", "FirstFit");
154
155 for (size_t i=0; i<nVtx; i++){
156 //std::cout << "Debug: i= " << i << std::endl;
157 lno_t v=i; // TODO: Use ordering here.
158 for (offset_t j=offsets[v]; j<offsets[v+1]; j++){
159 gno_t nbor = edgeIds[j];
160 //std::cout << "Debug: nbor= " << nbor << ", color= " << colors[nbor] << std::endl;
161 if (colors[nbor] > 0){
162 // Neighbors' colors are forbidden
163 forbidden[colors[nbor]] = v;
164 }
165 }
166
167 // Pick color for v
168
169 // Keep colors[v] if possible, otherwise find valid color.
170 if ((colors[v]==0) || ((colors[v]>0) && forbidden[colors[v]] == v)){
171
172 if (colorChoice.compare("FirstFit")){
173 // Pick first (smallest) available color > 0
174 for (int c=1; c <= maxColor+1; c++){
175 if (forbidden[c] != v){
176 colors[v] = c;
177 break;
178 }
179 }
180 }
181 else if (colorChoice.compare("Random")){
182 // Pick random available color.
183 // Truely random is slow, please consider RandomFast instead.
184 int numAvail = 0;
185 Teuchos::Array<int> avail(maxColor+1);
186 for (int c=1; c < maxColor+1; c++){
187 if (forbidden[c] != v){
188 avail[numAvail++] = c;
189 }
190 }
191 if (numAvail==0)
192 colors[v] = maxColor+1;
193 else
194 colors[v] = avail[rand()%numAvail];
195 }
196 else if (colorChoice.compare("RandomFast")){
197 // Pick random color, then find first available color after that.
198 bool foundColor = false;
199 int r = (rand() % maxColor) +1;
200 for (int c=r; c <= maxColor; c++){
201 if (forbidden[c] != v){
202 colors[v] = c;
203 foundColor = true;
204 break;
205 }
206 }
207 if (!foundColor){ // Look for colors in [1, r)
208 for (int c=1; c < r; c++){
209 if (forbidden[c] != v){
210 colors[v] = c;
211 foundColor = true;
212 break;
213 }
214 }
215 }
216 if (!foundColor) colors[v] = maxColor+1;
217 }
218 else if (colorChoice.compare("LeastUsed")){
219 // Pick least used available color.
220 // Simple linear algorithm; could maintain a priority queue but not sure any faster?
221 int leastUsedColor = 1;
222 for (int c=1; c <= maxColor; c++){
223 if (forbidden[c] != v){
224 if (numVerticesWithColor[c] < leastUsedColor){
225 leastUsedColor = c;
226 }
227 }
228 }
229 colors[v] = leastUsedColor;
230
231 // Update color counts
232 numVerticesWithColor[colors[v]]++;
233 }
234
235 if ((v==0) && colors[v]==0) colors[v]=1; // Corner case for first vertex
236
237 // If we used a new color, increase maxColor.
238 if (colors[v] > maxColor){
239 maxColor = colors[v];
240 }
241 }
242 }
243
244 return;
245 }
246
249 static void getValidParameters(ParameterList & pl)
250 {
251 RCP<Teuchos::StringValidator> color_choice_Validator = Teuchos::rcp(
252 new Teuchos::StringValidator(
253 Teuchos::tuple<std::string>(
254 "FirstFit", "Random", "RandomFast", "LeastUsed" )));
255 pl.set("color_choice", "FirstFit", "selection criterion for coloring",
256 color_choice_Validator);
257 }
258};
259}
260#endif
Defines the ColoringSolution class.
Defines the GraphModel interface.
#define HELLO
void color(const RCP< ColoringSolution< Adapter > > &solution)
Coloring method.
static void getValidParameters(ParameterList &pl)
Set up validators specific to this algorithm.
AlgSerialGreedy(const RCP< const typename Adapter::base_adapter_t > &adapter, const RCP< Teuchos::ParameterList > &pl, const RCP< Environment > &env, const RCP< const Teuchos::Comm< int > > &comm, modelFlag_t graphFlags)
void colorCrsGraph(const size_t nVtx, ArrayView< const gno_t > edgeIds, ArrayView< const offset_t > offsets, ArrayRCP< int > colors)
Algorithm defines the base class for all algorithms.
Created by mbenlioglu on Aug 31, 2020.
std::bitset< NUM_MODEL_FLAGS > modelFlag_t