19#ifndef OPM_GRAPHCOLORING_HEADER_INCLUDED
20#define OPM_GRAPHCOLORING_HEADER_INCLUDED
22#include <opm/common/TimingMacros.hpp>
24#include <opm/grid/utility/SparseTable.hpp>
40 std::deque<typename Graph::VertexDescriptor>& orderedVertices,
41 std::vector<int>& colors,
45 std::vector<int> forbidden(noVertices,
false);
46 std::size_t noColored = 0;
48 for (
auto vertex = orderedVertices.begin(),
49 vertexEnd = orderedVertices.end(); vertex != vertexEnd; ++vertex) {
51 while (vertex != vertexEnd && forbidden[*vertex])
53 if (vertex == vertexEnd) {
58 colors[*vertex] = color;
61 for (
auto edge = graph.beginEdges(*vertex),
62 endEdge = graph.endEdges(*vertex); edge != endEdge; ++edge) {
63 forbidden[edge.target()] =
true;
67 using Vertex =
typename Graph::VertexDescriptor;
68 auto newEnd = std::remove_if(orderedVertices.begin(),
69 orderedVertices.end(),
70 [&forbidden](
const Vertex& vertex) { return !forbidden[vertex]; });
71 orderedVertices.resize(newEnd - orderedVertices.begin());
75template <
class Graph,
class Functor>
77 typename Graph::VertexDescriptor root,
80 std::vector<int> visited(graph.maxVertex() + 1,
false);
81 using Vertex =
typename Graph::VertexDescriptor;
82 std::queue<Vertex> nextVertices;
83 std::size_t noVisited = 0;
84 nextVertices.push(root);
87 while (!nextVertices.empty()) {
88 auto current = nextVertices.front();
89 for (
auto edge = graph.beginEdges(current),
90 endEdge = graph.endEdges(current); edge != endEdge; ++edge) {
91 if (!visited[edge.target()]) {
92 visited[edge.target()] =
true;
93 nextVertices.push(edge.target());
94 functor(edge.target());
111template <
class Graph>
112std::tuple<std::vector<int>, int, std::vector<std::size_t>>
115 using Vertex =
typename Graph::VertexDescriptor;
116 std::deque<Vertex> orderedVertices;
117 auto noVertices = graph.maxVertex() + 1;
118 std::vector<int> degrees(noVertices, 0);
120 std::ptrdiff_t firstDegreeChange = 0;
123 for (
auto vertex = graph.begin(),
124 endVertex = graph.end(); vertex != endVertex; ++vertex) {
125 auto currentVertex = *vertex;
126 auto& degree = degrees[currentVertex];
128 for (
auto edge = graph.beginEdges(currentVertex),
129 endEdge = graph.endEdges(currentVertex); edge != endEdge; ++edge) {
133 if (degree >= maxDegree) {
134 orderedVertices.emplace_front(currentVertex);
136 if (degree > maxDegree) {
137 firstDegreeChange = 1;
141 orderedVertices.emplace_back(currentVertex);
146 std::stable_sort(orderedVertices.begin() + firstDegreeChange,
147 orderedVertices.end(),
148 [°rees](
const Vertex& v1,
const Vertex& v2)
149 { return degrees[v1] > degrees[v2]; });
152 auto& colors = degrees;
153 std::fill(colors.begin(), colors.end(), -1);
156 std::vector<std::size_t> verticesPerColor;
157 verticesPerColor.reserve(10);
159 while (!orderedVertices.empty()) {
161 colors, color++, noVertices));
163 return std::make_tuple(colors, color, verticesPerColor);
167template <
class Graph>
168std::vector<std::size_t>
171 const std::vector<std::size_t>& verticesPerColor,
174 std::vector<std::size_t> colorIndex(noColors, 0);
175 std::vector<std::size_t> indices(graph.maxVertex() + 1);
176 std::partial_sum(verticesPerColor.begin(),
177 verticesPerColor.begin() + verticesPerColor.size() - 1,
178 colorIndex.begin() + 1);
180 for (
const auto& vertex : graph) {
181 indices[vertex] = colorIndex[colors[vertex]]++;
187template <
class Graph>
188std::vector<std::size_t>
191 const std::vector<std::size_t>& verticesPerColor,
193 typename Graph::VertexDescriptor root)
195 std::vector<std::size_t> colorIndex(noColors, 0);
196 const auto notVisitedTag = std::numeric_limits<std::size_t>::max();
197 std::vector<std::size_t> indices(graph.maxVertex() + 1, notVisitedTag);
198 using Vertex =
typename Graph::VertexDescriptor;
199 std::partial_sum(verticesPerColor.begin(),
200 verticesPerColor.begin() + verticesPerColor.size() - 1,
201 colorIndex.begin() + 1);
202 std::size_t noVisited = 0;
203 auto numberer = [&colorIndex, &colors, &indices](Vertex vertex)
205 indices[vertex] = colorIndex[colors[vertex]]++;
208 while (noVisited < graph.maxVertex() + 1) {
212 if (noVisited < graph.maxVertex() + 1) {
214 for (
auto vertex : graph) {
215 if (indices[vertex] == notVisitedTag) {
247Opm::SparseTable<std::size_t>
250 OPM_TIMEBLOCK(createMatrix);
252 std::vector<std::size_t> color(matrix.N(), 0);
253 std::vector<std::size_t> rowIndices(matrix.N(), 0);
255 std::iota(rowIndices.begin(), rowIndices.end(), 0);
257 std::vector<std::size_t> colorCnt;
262 for (
auto i = matrix.begin(); i != matrix.end(); ++i) {
263 for (
auto a_ij = i->begin(); a_ij.index() != i.index(); ++a_ij) {
264 auto a_ji = matrix[a_ij.index()].find(i.index());
265 if (a_ji != matrix[a_ij.index()].end()) {
266 color[i.index()] = std::max({color[i.index()], color[a_ij.index()] + 1});
269 if (color[i.index()] >= colorCnt.size()) {
270 colorCnt.push_back(1);
272 ++colorCnt[color[i.index()]];
276 for (
auto i = matrix.beforeEnd(); i != matrix.beforeBegin(); --i) {
277 for (
auto a_ij = ++(i->find(i.index())); a_ij != i->end(); ++a_ij) {
278 color[i.index()] = std::max({color[i.index()], color[a_ij.index()] + 1});
280 if (color[i.index()] >= colorCnt.size()) {
281 colorCnt.push_back(1);
283 ++colorCnt[color[i.index()]];
287 for (
auto i = matrix.begin(); i != matrix.end(); ++i) {
288 for (
auto a_ij = i->begin(); a_ij.index() != i.index(); ++a_ij) {
289 color[i.index()] = std::max({color[i.index()], color[a_ij.index()] + 1});
291 if (color[i.index()] >= colorCnt.size()) {
292 colorCnt.push_back(1);
294 ++colorCnt[color[i.index()]];
299 std::stable_sort(rowIndices.begin(),
301 [&color](
const std::size_t a,
const std::size_t b)
302 { return color[a] < color[b]; });
304 return {rowIndices.data(), rowIndices.data() + rowIndices.size(),
305 colorCnt.data(), colorCnt.data() + colorCnt.size()};
std::size_t breadthFirstSearch(const Graph &graph, typename Graph::VertexDescriptor root, Functor functor)
Definition: GraphColoring.hpp:76
std::size_t colorGraphWelshPowell(const Graph &graph, std::deque< typename Graph::VertexDescriptor > &orderedVertices, std::vector< int > &colors, int color, int noVertices)
Definition: GraphColoring.hpp:39
Definition: blackoilboundaryratevector.hh:37
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:169
ColoringType
Specify coloring type.
Definition: GraphColoring.hpp:234
Opm::SparseTable< std::size_t > getMatrixRowColoring(const M &matrix, ColoringType coloringType)
Given a matrix and dependecy type, returns a SparseTable grouping the rows by which can be executed i...
Definition: GraphColoring.hpp:248
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:189
std::tuple< std::vector< int >, int, std::vector< std::size_t > > colorVerticesWelshPowell(const Graph &graph)
Color the vertices of graph.
Definition: GraphColoring.hpp:113