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
31namespace Opm
32{
33
34namespace Detail
35{
36template<class Graph>
37std::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}
77template<class Graph, class Functor>
78std::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
116template<class Graph>
117std::tuple<std::vector<int>, int, std::vector<std::size_t> >
118colorVerticesWelshPowell(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
184template<class Graph>
185std::vector<std::size_t>
186reorderVerticesPreserving(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
204template<class Graph>
205std::vector<std::size_t>
206reorderVerticesSpheres(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:27
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