45 #ifndef _ZOLTAN2_ALGSERIALGREEDY_HPP_
46 #define _ZOLTAN2_ALGSERIALGREEDY_HPP_
58 template <
typename Adapter>
64 typedef typename Adapter::offset_t offset_t;
65 typedef typename Adapter::scalar_t scalar_t;
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_;
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)
93 ArrayView<const gno_t> edgeIds;
94 ArrayView<const offset_t> offsets;
95 ArrayView<StridedData<lno_t, scalar_t> > wgts;
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++){
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];
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);
Time an algorithm (or other entity) as a whole.
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
map_t::global_ordinal_type gno_t
void color(const RCP< ColoringSolution< Adapter > > &solution)
Coloring method.
Algorithm defines the base class for all algorithms.
map_t::local_ordinal_type lno_t
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.
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)
The class containing coloring solution.