10 #include <boost/graph/adjacency_list.hpp>
11 #include <boost/graph/compressed_sparse_row_graph.hpp>
12 #include <boost/graph/sequential_vertex_coloring.hpp>
13 #include <dolfinx/common/Timer.h>
32 template <
typename ColorType>
35 std::vector<ColorType>& colors)
37 Timer timer(
"Boost graph coloring (from dolfinx::graph)");
40 typedef boost::compressed_sparse_row_graph<
41 boost::directedS, boost::property<boost::vertex_color_t, ColorType>>
45 const std::size_t n = graph.size();
48 Graph::const_iterator vertex;
49 std::size_t num_edges = 0;
50 for (vertex = graph.begin(); vertex != graph.end(); ++vertex)
51 num_edges += vertex->size();
54 std::vector<std::pair<std::size_t, std::size_t>> edges;
55 edges.reserve(num_edges);
56 graph_set_type::const_iterator edge;
57 for (vertex = graph.begin(); vertex != graph.end(); ++vertex)
59 for (edge = vertex->begin(); edge != vertex->end(); ++edge)
61 const std::size_t vertex_index = vertex - graph.begin();
62 if (vertex_index != (std::size_t)*edge)
63 edges.push_back(std::pair(vertex_index, *edge));
67 const BoostGraph g(boost::edges_are_unsorted_multi_pass, edges.begin(),
78 template <
typename T,
typename ColorType>
82 Timer timer(
"Boost graph coloring");
85 const std::size_t num_vertices = boost::num_vertices(graph);
86 assert(num_vertices == colors.size());
88 typedef typename boost::graph_traits<T>::vertices_size_type vert_size_type;
89 typedef typename boost::property_map<T, boost::vertex_index_t>::const_type
93 colors.resize(num_vertices);
96 std::vector<vert_size_type> _colors(num_vertices);
97 boost::iterator_property_map<vert_size_type*, vert_index_map> color(
98 &_colors.front(), get(boost::vertex_index, graph));
99 const vert_size_type num_colors = sequential_vertex_coloring(graph, color);
102 std::copy(_colors.begin(), _colors.end(), colors.begin());
This class colors a graph using the Boost Graph Library.
Definition: BoostGraphColoring.h:28
static std::size_t compute_local_vertex_coloring(const T &graph, std::vector< ColorType > &colors)
Compute vertex colors.
Definition: BoostGraphColoring.h:80
static std::size_t compute_local_vertex_coloring(const Graph &graph, std::vector< ColorType > &colors)
Compute vertex colors.
Definition: BoostGraphColoring.h:34