19#ifndef OPM_GRAPHCOLORING_HEADER_INCLUDED
20#define OPM_GRAPHCOLORING_HEADER_INCLUDED
37std::size_t colorGraphWelshPowell(
const Graph& graph,
38 std::deque<typename Graph::VertexDescriptor>& orderedVertices,
39 std::vector<int>& colors,
40 int color,
int noVertices)
42 std::vector<int> forbidden(noVertices,
false);
43 std::size_t noColored = 0;
45 for(
auto vertex = orderedVertices.begin(),
46 vertexEnd = orderedVertices.end();
47 vertex != vertexEnd; ++vertex)
50 while(vertex != vertexEnd && forbidden[*vertex])
52 if ( vertex == vertexEnd )
58 colors[*vertex] = color;
61 for(
auto edge = graph.beginEdges(*vertex), endEdge = graph.endEdges(*vertex);
62 edge != endEdge; ++edge)
64 forbidden[edge.target()] =
true;
68 using Vertex =
typename Graph::VertexDescriptor;
69 auto newEnd = std::remove_if(orderedVertices.begin(), orderedVertices.end(),
70 [&forbidden](
const Vertex& vertex)
72 return !forbidden[vertex];
74 orderedVertices.resize(newEnd-orderedVertices.begin());
77template<
class Graph,
class Functor>
78std::size_t breadthFirstSearch(
const Graph& graph,
typename Graph::VertexDescriptor root,
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);
88 while( !nextVertices.empty() )
90 auto current = nextVertices.front();
91 for(
auto edge = graph.beginEdges(current),
92 endEdge = graph.endEdges(current);
93 edge != endEdge; ++edge)
95 if ( ! visited[edge.target()] )
97 visited[edge.target()] =
true;
98 nextVertices.push(edge.target());
99 functor(edge.target());
117std::tuple<std::vector<int>, int, std::vector<std::size_t> >
120 using Vertex =
typename Graph::VertexDescriptor;
121 std::deque<Vertex> orderedVertices;
122 auto noVertices = graph.maxVertex()+1;
123 std::vector<int> degrees(noVertices, 0);
125 std::ptrdiff_t firstDegreeChange = 0;
128 for(
auto vertex = graph.begin(), endVertex = graph.end();
129 vertex != endVertex; ++vertex)
131 auto currentVertex = *vertex;
132 auto& degree = degrees[currentVertex];
134 for(
auto edge = graph.beginEdges(currentVertex),
135 endEdge = graph.endEdges(currentVertex);
136 edge != endEdge; ++edge)
142 if( degree >= maxDegree )
144 orderedVertices.emplace_front(currentVertex);
146 if(degree > maxDegree)
148 firstDegreeChange = 1;
154 orderedVertices.emplace_back(currentVertex);
159 std::stable_sort(orderedVertices.begin() + firstDegreeChange,
160 orderedVertices.end(),
161 [°rees](
const Vertex& v1,
const Vertex& v2)
163 return degrees[v1] > degrees[v2];
167 auto& colors = degrees;
168 std::fill(colors.begin(), colors.end(), -1);
171 std::vector<std::size_t> verticesPerColor;
172 verticesPerColor.reserve(10);
174 while(!orderedVertices.empty())
177 .push_back(Detail::colorGraphWelshPowell(graph, orderedVertices, colors,
178 color++, noVertices));
180 return std::make_tuple(colors, color, verticesPerColor);
185std::vector<std::size_t>
187 const std::vector<std::size_t>& verticesPerColor,
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);
196 for(
const auto& vertex: graph)
198 indices[vertex] = colorIndex[colors[vertex]]++;
205std::vector<std::size_t>
207 const std::vector<std::size_t>& verticesPerColor,
209 typename Graph::VertexDescriptor root)
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)
221 indices[vertex] = colorIndex[colors[vertex]]++;
224 while ( noVisited < graph.maxVertex() + 1 )
228 noVisited += Detail::breadthFirstSearch(graph, root, numberer);
229 if ( noVisited < graph.maxVertex() + 1 )
232 for(
auto vertex: graph)
234 if ( indices[vertex] == notVisitedTag )
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