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<Teuchos::Comm<int> > comm_;
74 const RCP<Teuchos::ParameterList> &pl,
75 const RCP<Environment> &env,
76 const RCP<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];
Time an algorithm (or other entity) as a whole.
AlgSerialGreedy(const RCP< GraphModel< typename Adapter::base_adapter_t > > &model, const RCP< Teuchos::ParameterList > &pl, const RCP< Environment > &env, const RCP< Teuchos::Comm< int > > &comm)
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.
Algorithm defines the base class for all algorithms.
GraphModel defines the interface required for graph models.
Defines the ColoringSolution class.
Defines the GraphModel interface.
The class containing coloring solution.