Zoltan2
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Zoltan2_RebalanceColoring.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_REBALANCECOLORING_HPP_
46 #define _ZOLTAN2_REBALANCECOLORING_HPP_
47 
48 #include <Zoltan2_Standards.hpp>
49 
50 // Given a valid coloring of a graph, rebalance the colors
51 // such that either:
52 // (a) color classes are as balanced as possible, or
53 // (b) every color class has at least minSize vertices.
54 // This function can be called as a post-processing after any initial
55 // coloring.
56 // This is a greedy heuristic so there is no guarantee of success,
57 // though in practice we believe it will work well.
59  const lno_t nVtx,
60  ArrayView<const lno_t> edgeIds,
61  ArrayView<const offset_t> offsets,
62  ArrayRCP<int> colors,
63  const int balanceColors,
64  const lno_t minSize
65  )
66  {
67 #ifndef INCLUDE_ZOLTAN2_EXPERIMENTAL
68  Z2_THROW_EXPERIMENTAL("Zoltan2 rebalanceColoring is experimental and not tested");
69 #else
70  // Experimental: Not tested yet!
71  //
72  // Count size of each color class.
73  // No vertex weights, may add in future.
74  lno_t maxColor = 0;
75  Teuchos::Array<lno_t> colorSize(nVtx,0);
76  for (lno_t i=0; i < nVtx; i++){
77  if (colors[i] > maxColor)
78  maxColor = colors[i];
79  }
80  for (lno_t i=0; i < nVtx; i++){
81  colorSize[colors[i]]++;
82  }
83  lno_t targetSize = 0;
84  if (balanceColors > 0)
85  targetSize = nVtx/maxColor;
86  else
87  targetSize = minSize;
88 
89  // Vertex-centric version: Loop over vertices
90  // and move it to different color if needed.
91  Teuchos::Array<int> forbidden(maxDegree+2, 0);
92  for (lno_t i=0; i < nVtx; i++){
93  if (colorSize[colors[i]] > targetSize){
94  // Find first available color that is not full yet
95  for (offset_t j=offsets[i]; j<offsets[i+1]; j++){
96  lno_t nbor = edgeIds[j];
97  if (colors[nbor] > 0){
98  // Neighbors' colors are forbidden
99  forbidden[colors[nbor]] = i;
100  }
101  }
102  // Pick first (smallest) underfull color > 0.
103  // If no such color, just keep colors[i].
104  int newcolor = colors[i];
105  for (int c=1; c <= maxColor; c++){
106  if ((forbidden[c] != i) && (colorSize[c]<targetSize)){
107  newcolor = c;
108  break;
109  }
110  }
111 
112  // Move vertex i to underfull color.
113  colorSize[colors[i]]--;
114  colorSize[newcolor]++;
115  colors[i] = newcolor;
116  }
117  }
118 
119 #endif
120  }
121 
122 #endif
map_t::local_ordinal_type lno_t
Definition: mapRemotes.cpp:17
#define Z2_THROW_EXPERIMENTAL(mystr)
Throw an error when experimental code is requested but not compiled.
Gathering definitions used in software development.
int rebalanceColoring(const lno_t nVtx, ArrayView< const lno_t > edgeIds, ArrayView< const offset_t > offsets, ArrayRCP< int > colors, const int balanceColors, const lno_t minSize)