21 #ifndef __DOLFIN_BOOST_GRAPH_INTERFACE_H
22 #define __DOLFIN_BOOST_GRAPH_INTERFACE_H
27 #include <boost/graph/adjacency_list.hpp>
28 #include <boost/graph/compressed_sparse_row_graph.hpp>
29 #include <boost/graph/sequential_vertex_coloring.hpp>
30 #include <dolfin/common/Timer.h>
46 template<
typename ColorType>
48 std::vector<ColorType>& colors)
50 Timer timer(
"Boost graph coloring (from dolfin::Graph)");
53 typedef boost::compressed_sparse_row_graph<boost::directedS,
54 boost::property<boost::vertex_color_t, ColorType> > BoostGraph;
57 const std::size_t n = graph.size();
60 Graph::const_iterator vertex;
61 std::size_t num_edges = 0;
62 for (vertex = graph.begin(); vertex != graph.end(); ++vertex)
63 num_edges += vertex->size();
66 std::vector<std::pair<std::size_t, std::size_t> > edges;
67 edges.reserve(num_edges);
69 for (vertex = graph.begin(); vertex != graph.end(); ++vertex)
71 for (edge = vertex->begin(); edge != vertex->end(); ++edge)
73 const std::size_t vertex_index = vertex - graph.begin();
74 if (vertex_index != (std::size_t) *edge)
75 edges.push_back(std::make_pair(vertex_index, *edge));
79 const BoostGraph g(boost::edges_are_unsorted_multi_pass,
80 edges.begin(), edges.end(), n);
90 template<
typename T,
typename ColorType>
92 std::vector<ColorType>& colors)
94 Timer timer(
"Boost graph coloring");
97 const std::size_t num_vertices = boost::num_vertices(graph);
98 dolfin_assert(num_vertices == colors.size());
100 typedef typename boost::graph_traits<T>::vertices_size_type
102 typedef typename boost::property_map<T,
103 boost::vertex_index_t>::const_type vert_index_map;
106 colors.resize(num_vertices);
109 std::vector<vert_size_type> _colors(num_vertices);
110 boost::iterator_property_map<vert_size_type*, vert_index_map>
111 color(&_colors.front(), get(boost::vertex_index, graph));
112 const vert_size_type num_colors = sequential_vertex_coloring(graph,
116 std::copy(_colors.begin(), _colors.end(), colors.begin());