sequential_vertex_coloring with ordering in Boost graph library C++

user_15917690 0
Viewed 33

I'm a novice with the boost graph library. I'm trying to use the sequential_vertex_coloring algorithm (https://live.boost.org/doc/libs/1_79_0/libs/graph/doc/sequential_vertex_coloring.html) and have working code using the default for the order parameter. But I would like to pass in an order property map that lists the vertices of my graph in max degree order (so that my coloring algorithm is Welsh-Powell). The example in the documentation above does not show how to do this. Could someone give a minimal example of how to create such a property map.

boost-graph boost c++
1 Answers

Firstly, I have to make assumptions about the code you're not showing. Let's assume this for the default-order invocation:

Live On Compiler Explorer

#include <boost/graph/sequential_vertex_coloring.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <iostream>

using Graph =
    boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS>;

using V  = boost::graph_traits<Graph>::vertex_descriptor;

using Edge = std::pair<int, int>;
enum nodes { A, B, C, D, E, n };

int main() {
    Edge  edges[] = {{A, C}, {B, B}, {B, D}, {B, E}, {C, B},
                    {C, D}, {D, E}, {E, A}, {E, B}};
    Graph g(std::begin(edges), std::end(edges), n);

    std::vector<unsigned> color_vec(num_vertices(g));
    auto index_map = get(boost::vertex_index, g);

    // default order
    auto color_map = make_safe_iterator_property_map(
            color_vec.begin(), color_vec.size(), index_map);

    auto num_colors = sequential_vertex_coloring(g, color_map);

    std::cout << "num_colors: " << num_colors << "\n";
}

Prints

num_colors: 2

Degree Order

You pass a property map (just like the color_map) that satisfies the documented criteria:

A mapping from integers in the range [0, num_vertices(g)) to the vertices of the graph.

So, let's create a vector of vertex descriptors:

std::vector<V> ordering;

And fill it with the natural order:

auto vv = vertices(g);
ordering.assign(vv.first, vv.second);

Then sort by degree (descending):

sort(begin(ordering), end(ordering),
     [&g](V v, V u) { return degree(v, g) > degree(u, g); });

Now we create a property map from the vector in the same way as for color map:

auto order_map = make_safe_iterator_property_map(
        ordering.begin(), ordering.size(), index_map);

Now all that's left is passing it as an argument to the other overload of sequential_vertex_coloring:

auto num_colors = sequential_vertex_coloring(g, order_map, color_map);

Live On Compiler Explorer

num_colors: 2
num_colors: 2

BONUS

With a bit of Boost Range magic the lines

std::vector<V> ordering;
{
    auto vv = vertices(g);
    ordering.assign(vv.first, vv.second);
    sort(begin(ordering), end(ordering),
         [&g](V v, V u) { return degree(v, g) > degree(u, g); });
}

Can be simplified to

auto ordering = boost::copy_range<std::vector<V>>(vertices(g));
sort(begin(ordering), end(ordering),
     [&g](V v, V u) { return degree(v, g) > degree(u, g); });

And then, with std::ranges even more:

auto ordering = boost::copy_range<std::vector<V>>(vertices(g));
std::ranges::sort(ordering, std::greater<>{},
                  [&g](V v) { return degree(v, g); });

Just for comparison, see that when ordering by min degree results in more colors being needed:

Live On Compiler Explorer

num_colors: 2
num_colors: 3
user_853710
Related