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>
39std::size_t colorGraphWelshPowell(
const Graph&
graph,
67 using Vertex =
typename Graph::VertexDescriptor;
75template <
class Graph,
class Functor>
76std::size_t breadthFirstSearch(
const Graph&
graph,
77 typename Graph::VertexDescriptor
root,
81 using Vertex =
typename Graph::VertexDescriptor;
111template <
class Graph>
112std::tuple<std::vector<int>,
int, std::vector<std::size_t>>
115 using Vertex =
typename Graph::VertexDescriptor;
149 { return degrees[v1] > degrees[v2]; });
167template <
class Graph>
168std::vector<std::size_t>
175 std::vector<std::size_t> indices(
graph.maxVertex() + 1);
187template <
class Graph>
188std::vector<std::size_t>
193 typename Graph::VertexDescriptor
root)
196 const auto notVisitedTag = std::numeric_limits<std::size_t>::max();
198 using Vertex =
typename Graph::VertexDescriptor;
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);
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()) {
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) {
287 for (
auto i = matrix.begin(); i != matrix.end(); ++i) {
288 for (
auto a_ij = i->begin();
a_ij.index() != i.index(); ++
a_ij) {
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(),
This file contains a set of helper functions used by VFPProd / VFPInj.
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)
This coloring algorithm interprets the sparsity structure of a matrix as a graph.
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
constexpr auto getPropValue()
get the value data member of a property
Definition propertysystem.hh:242
std::tuple< std::vector< int >, int, std::vector< std::size_t > > colorVerticesWelshPowell(const Graph &graph)
Color the vertices of graph.
Definition GraphColoring.hpp:113