My Project
GraphColoring.hpp
1 /*
2  Copyright 2018 Equinor
3 
4  This file is part of the Open Porous Media project (OPM).
5 
6  OPM is free software: you can redistribute it and/or modify
7  it under the terms of the GNU General Public License as published by
8  the Free Software Foundation, either version 3 of the License, or
9  (at your option) any later version.
10 
11  OPM is distributed in the hope that it will be useful,
12  but WITHOUT ANY WARRANTY; without even the implied warranty of
13  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  GNU General Public License for more details.
15 
16  You should have received a copy of the GNU General Public License
17  along with OPM. If not, see <http://www.gnu.org/licenses/>.
18 */
19 #ifndef OPM_GRAPHCOLORING_HEADER_INCLUDED
20 #define OPM_GRAPHCOLORING_HEADER_INCLUDED
21 
22 #include <vector>
23 #include <deque>
24 #include <tuple>
25 #include <algorithm>
26 #include <numeric>
27 #include <queue>
28 #include <cstddef>
29 #include <limits>
30 
31 namespace Opm
32 {
33 
34 namespace Detail
35 {
36 template<class Graph>
37 std::size_t colorGraphWelshPowell(const Graph& graph,
38  std::deque<typename Graph::VertexDescriptor>& orderedVertices,
39  std::vector<int>& colors,
40  int color, int noVertices)
41 {
42  std::vector<int> forbidden(noVertices, false);
43  std::size_t noColored = 0;
44 
45  for(auto vertex = orderedVertices.begin(),
46  vertexEnd = orderedVertices.end();
47  vertex != vertexEnd; ++vertex)
48  {
49  // Skip forbidden vertices
50  while(vertex != vertexEnd && forbidden[*vertex])
51  ++vertex;
52  if ( vertex == vertexEnd )
53  {
54  break;
55  }
56 
57  // Color Vertex
58  colors[*vertex] = color;
59  ++noColored;
60  // Forbid neighors
61  for(auto edge = graph.beginEdges(*vertex), endEdge = graph.endEdges(*vertex);
62  edge != endEdge; ++edge)
63  {
64  forbidden[edge.target()] = true;
65  }
66  }
67  // forbidden vertices will be colored next for coloring
68  using Vertex = typename Graph::VertexDescriptor;
69  auto newEnd = std::remove_if(orderedVertices.begin(), orderedVertices.end(),
70  [&forbidden](const Vertex& vertex)
71  {
72  return !forbidden[vertex];
73  });
74  orderedVertices.resize(newEnd-orderedVertices.begin());
75  return noColored;
76 }
77 template<class Graph, class Functor>
78 std::size_t breadthFirstSearch(const Graph& graph, typename Graph::VertexDescriptor root,
79  Functor functor)
80 {
81  std::vector<int> visited(graph.maxVertex() + 1, false);
82  using Vertex = typename Graph::VertexDescriptor;
83  std::queue<Vertex> nextVertices;
84  std::size_t noVisited = 0;
85  nextVertices.push(root);
86  visited[root] = true; // We do not visit root.
87 
88  while( !nextVertices.empty() )
89  {
90  auto current = nextVertices.front();
91  for(auto edge = graph.beginEdges(current),
92  endEdge = graph.endEdges(current);
93  edge != endEdge; ++edge)
94  {
95  if ( ! visited[edge.target()] )
96  {
97  visited[edge.target()] = true;
98  nextVertices.push(edge.target());
99  functor(edge.target());
100  ++noVisited;
101  }
102  }
103  nextVertices.pop();
104  }
105  return noVisited;
106 }
107 } // end namespace Detail
108 
109 
116 template<class Graph>
117 std::tuple<std::vector<int>, int, std::vector<std::size_t> >
118 colorVerticesWelshPowell(const Graph& graph)
119 {
120  using Vertex = typename Graph::VertexDescriptor;
121  std::deque<Vertex> orderedVertices;
122  auto noVertices = graph.maxVertex()+1;
123  std::vector<int> degrees(noVertices, 0);
124  int maxDegree = 0;
125  std::ptrdiff_t firstDegreeChange = 0;
126 
127  // populate deque
128  for( auto vertex = graph.begin(), endVertex = graph.end();
129  vertex != endVertex; ++vertex)
130  {
131  auto currentVertex = *vertex;
132  auto& degree = degrees[currentVertex];
133 
134  for(auto edge = graph.beginEdges(currentVertex),
135  endEdge = graph.endEdges(currentVertex);
136  edge != endEdge; ++edge)
137  {
138  ++degree;
139  }
140 
141 
142  if( degree >= maxDegree )
143  {
144  orderedVertices.emplace_front(currentVertex);
145  ++firstDegreeChange;
146  if(degree > maxDegree)
147  {
148  firstDegreeChange = 1;
149  maxDegree = degree;
150  }
151  }
152  else
153  {
154  orderedVertices.emplace_back(currentVertex);
155  }
156  }
157 
158  // order deque by descending degree
159  std::stable_sort(orderedVertices.begin() + firstDegreeChange,
160  orderedVertices.end(),
161  [&degrees](const Vertex& v1, const Vertex& v2)
162  {
163  return degrees[v1] > degrees[v2];
164  });
165 
166  // Overwrite degree with color
167  auto& colors = degrees;
168  std::fill(colors.begin(), colors.end(), -1);
169 
170  int color = 0;
171  std::vector<std::size_t> verticesPerColor;
172  verticesPerColor.reserve(10);
173 
174  while(!orderedVertices.empty())
175  {
176  verticesPerColor
177  .push_back(Detail::colorGraphWelshPowell(graph, orderedVertices, colors,
178  color++, noVertices));
179  }
180  return std::make_tuple(colors, color, verticesPerColor);
181 }
182 
184 template<class Graph>
185 std::vector<std::size_t>
186 reorderVerticesPreserving(const std::vector<int>& colors, int noColors,
187  const std::vector<std::size_t>& verticesPerColor,
188  const Graph& graph)
189 {
190  std::vector<std::size_t> colorIndex(noColors, 0);
191  std::vector<std::size_t> indices(graph.maxVertex() + 1);
192  std::partial_sum(verticesPerColor.begin(),
193  verticesPerColor.begin()+verticesPerColor.size() - 1,
194  colorIndex.begin() + 1);
195 
196  for(const auto& vertex: graph)
197  {
198  indices[vertex] = colorIndex[colors[vertex]]++;
199  }
200  return indices;
201 }
202 
204 template<class Graph>
205 std::vector<std::size_t>
206 reorderVerticesSpheres(const std::vector<int>& colors, int noColors,
207  const std::vector<std::size_t>& verticesPerColor,
208  const Graph& graph,
209  typename Graph::VertexDescriptor root)
210 {
211  std::vector<std::size_t> colorIndex(noColors, 0);
212  const auto notVisitedTag = std::numeric_limits<std::size_t>::max();
213  std::vector<std::size_t> indices(graph.maxVertex() + 1, notVisitedTag);
214  using Vertex = typename Graph::VertexDescriptor;
215  std::partial_sum(verticesPerColor.begin(),
216  verticesPerColor.begin()+verticesPerColor.size() - 1,
217  colorIndex.begin() + 1);
218  std::size_t noVisited = 0;
219  auto numberer = [&colorIndex, &colors, &indices](Vertex vertex)
220  {
221  indices[vertex] = colorIndex[colors[vertex]]++;
222  };
223 
224  while ( noVisited < graph.maxVertex() + 1 )
225  {
226  numberer(root);
227  ++noVisited; //root node already visited and not visited in BFS
228  noVisited += Detail::breadthFirstSearch(graph, root, numberer);
229  if ( noVisited < graph.maxVertex() + 1 )
230  {
231  // Graph is disconnected search for not yet visited node
232  for(auto vertex: graph)
233  {
234  if ( indices[vertex] == notVisitedTag )
235  {
236  // \todo make sure that this is a peripheral node!
237  root = vertex;
238  break;
239  }
240  }
241  }
242  }
243  return indices;
244 }
245 } // end namespace Opm
246 #endif
This file contains a set of helper functions used by VFPProd / VFPInj.
Definition: BlackoilPhases.hpp:26
std::vector< std::size_t > reorderVerticesPreserving(const std::vector< int > &colors, int noColors, const std::vector< std::size_t > &verticesPerColor, const Graph &graph)
! Reorder colored graph preserving order of vertices with the same color.
Definition: GraphColoring.hpp:186
std::vector< std::size_t > reorderVerticesSpheres(const std::vector< int > &colors, int noColors, const std::vector< std::size_t > &verticesPerColor, const Graph &graph, typename Graph::VertexDescriptor root)
! Reorder Vetrices in spheres
Definition: GraphColoring.hpp:206
std::tuple< std::vector< int >, int, std::vector< std::size_t > > colorVerticesWelshPowell(const Graph &graph)
Color the vertices of graph.
Definition: GraphColoring.hpp:118