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