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,
80 ) : adapter_(adapter), pl_(pl), env_(env), comm_(comm), graphFlags_(graphFlags)
86 const RCP<ColoringSolution<Adapter> > &solution
93 ArrayView<const gno_t> edgeIds;
94 ArrayView<const offset_t> offsets;
95 ArrayView<StridedData<lno_t, scalar_t> > wgts;
97 const auto model = rcp(
new GraphModel<typename Adapter::base_adapter_t>(adapter_, env_, comm_, graphFlags_));
98 const size_t nVtx = model->getLocalNumVertices();
99 model->getEdgeList(edgeIds, offsets, wgts);
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;
111 ArrayRCP<int> colors = solution->getColorsRCP();
112 for (
size_t i=0; i<nVtx; i++){
117 env_->timerStart(MACRO_TIMERS,
"Coloring algorithm");
119 env_->timerStop(MACRO_TIMERS,
"Coloring algorithm");
126 ArrayView<const gno_t> edgeIds,
127 ArrayView<const offset_t> offsets,
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];
146 Teuchos::Array<int> forbidden(maxDegree+2, 0);
149 Teuchos::Array<lno_t> numVerticesWithColor(maxDegree+2, 0);
152 Teuchos::ParameterList &pl = env_->getParametersNonConst();
153 std::string colorChoice = pl.get<std::string>(
"color_choice",
"FirstFit");
155 for (
size_t i=0; i<nVtx; i++){
158 for (offset_t j=offsets[v]; j<offsets[v+1]; j++){
159 gno_t nbor = edgeIds[j];
161 if (colors[nbor] > 0){
163 forbidden[colors[nbor]] = v;
170 if ((colors[v]==0) || ((colors[v]>0) && forbidden[colors[v]] == v)){
172 if (colorChoice.compare(
"FirstFit")){
174 for (
int c=1; c <= maxColor+1; c++){
175 if (forbidden[c] != v){
181 else if (colorChoice.compare(
"Random")){
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;
192 colors[v] = maxColor+1;
194 colors[v] = avail[rand()%numAvail];
196 else if (colorChoice.compare(
"RandomFast")){
198 bool foundColor =
false;
199 int r = (rand() % maxColor) +1;
200 for (
int c=r; c <= maxColor; c++){
201 if (forbidden[c] != v){
208 for (
int c=1; c < r; c++){
209 if (forbidden[c] != v){
216 if (!foundColor) colors[v] = maxColor+1;
218 else if (colorChoice.compare(
"LeastUsed")){
221 int leastUsedColor = 1;
222 for (
int c=1; c <= maxColor; c++){
223 if (forbidden[c] != v){
224 if (numVerticesWithColor[c] < leastUsedColor){
229 colors[v] = leastUsedColor;
232 numVerticesWithColor[colors[v]]++;
235 if ((v==0) && colors[v]==0) colors[v]=1;
238 if (colors[v] > maxColor){
239 maxColor = colors[v];