mercredi 18 avril 2018

C++: getting min/max values of boost::graph attributes

Just spend "some" time on some stupid issue on this problem, so I though I might as well post that here, if it can be useful to someone.

Say you have a boost::graph using so-called "bundled properties" (aka "inner properties) and you want to find the minimum and maximum value of the attributes. The standard library has this nice minmax_element() algorithm.

But... how can I use it on a graph inner properties ?

Say you have this kind of vertex, used in a graph definition (here undirected, but should also work for a directed graph):

struct vertex_properties
{
  int val;
};

typedef boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::undirectedS,
    vertex_properties
> graph_t;

typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_t;

As an example, consider this program, creating a 3 vertices graph (and, yes, no edges here):

graph_t g;
    
vertex_t v1 = boost::add_vertex(g);
vertex_t v2 = boost::add_vertex(g);
vertex_t v3 = boost::add_vertex(g);
    
// Set vertex properties
g[v1].val = 1;
g[v2].val = 2;
g[v3].val = 3;

To find the min/max value of the attributes, just call the algorithm with the right lambda function:

auto pit = boost::vertices( g );
auto result = std::minmax_element(
 pit.first,
 pit.second,
 [&]                                              // lambda
 ( vertex_t v1, vertex_t v2 )
 {
  return( g[v1].val < g[v2].val );
 }
);

This will return a pair of iterators on the min and max graph indexes. So, to get the results:

    std::cout << "min=" << g[*result.first].val
     << " max=" << g[*result.second].val << '\n';