DOLFIN-X
DOLFIN-X C++ interface
BoostGraphColoring.h
1 // Copyright (C) 2010 Garth N. Wells
2 //
3 // This file is part of DOLFINX (https://www.fenicsproject.org)
4 //
5 // SPDX-License-Identifier: LGPL-3.0-or-later
6 
7 #pragma once
8 
9 #include "Graph.h"
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>
14 #include <iostream>
15 #include <vector>
16 
17 namespace dolfinx
18 {
19 
20 class Mesh;
21 
22 namespace graph
23 {
24 
26 
28 {
29 
30 public:
32  template <typename ColorType>
33  static std::size_t
34  compute_local_vertex_coloring(const Graph& graph,
35  std::vector<ColorType>& colors)
36  {
37  Timer timer("Boost graph coloring (from dolfinx::graph)");
38 
39  // Typedef for Boost compressed sparse row graph
40  typedef boost::compressed_sparse_row_graph<
41  boost::directedS, boost::property<boost::vertex_color_t, ColorType>>
42  BoostGraph;
43 
44  // Number of vertices
45  const std::size_t n = graph.size();
46 
47  // Count number of edges
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();
52 
53  // Build list of graph edges
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)
58  {
59  for (edge = vertex->begin(); edge != vertex->end(); ++edge)
60  {
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));
64  }
65  }
66  // Build Boost graph
67  const BoostGraph g(boost::edges_are_unsorted_multi_pass, edges.begin(),
68  edges.end(), n);
69 
70  // Resize vector to hold colors
71  colors.resize(n);
72 
73  // Perform coloring
74  return compute_local_vertex_coloring(g, colors);
75  }
76 
78  template <typename T, typename ColorType>
79  static std::size_t
80  compute_local_vertex_coloring(const T& graph, std::vector<ColorType>& colors)
81  {
82  Timer timer("Boost graph coloring");
83 
84  // Number of vertices in graph
85  const std::size_t num_vertices = boost::num_vertices(graph);
86  assert(num_vertices == colors.size());
87 
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
90  vert_index_map;
91 
92  // Resize to hold colors
93  colors.resize(num_vertices);
94 
95  // Color 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);
100 
101  // Copy colors and return
102  std::copy(_colors.begin(), _colors.end(), colors.begin());
103  return num_colors;
104  }
105 };
106 } // namespace graph
107 } // namespace dolfinx
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