Zoltan2
Loading...
Searching...
No Matches
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
#define Z2_THROW_EXPERIMENTAL(mystr)
Throw an error when experimental code is requested but not compiled.
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)
Gathering definitions used in software development.
map_t::local_ordinal_type lno_t
Definition: mapRemotes.cpp:17