Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Color map in boost graph breadth_first_visit

I want to use boosts breadth_first_visit method and i'd like to provide it with my own "external" color map. I defined the graph as follows

typedef boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, 
  boost::property<boost::vertex_index_t, int, 
  boost::property<boost::vertex_color_t, boost::default_color_type, 
  Node_t>>>  GraphType;

where Node_t is a struct, defining the properties for the vertices. However, i can't find out how i can provide the BFS with my own color map. I'd like to store the vertex colors in a vector, so my definition looks like

std::vector<boost::default_color_type> colors;

but i can't figure it out, how to use this for the bfs.

Neither

boost::breadth_first_search(g, *boost::vertices(g).first, 
  boost::color_map(colors));

nor

boost::breadth_first_search(g, *boost::vertices(g).first, 
  boost::color_map(&colors[0]));

is working. While the first gives me a bunch of different compiler errors (e.g. default-int is not supported, "boost::color_traits" use of class type requires type argument list) the second compile aborts with only C2664 : 'boost::put' cannot convert parameter 2 from 'void*' to 'ptrdiff_t'.

So the question is: How can i use my own color-mapping-structure. An additional question would be: How can i get the color-value for a specific vertex_descriptor?

like image 480
AquilaRapax Avatar asked Jul 26 '12 09:07

AquilaRapax


1 Answers

Ok, i used another approach but solved my problem. For those who are as confused as i was about color maps in boost or those who are interested:

The Type of the color map, as bfs uses it is:

typedef boost::property_map<GraphType, boost::vertex_color_t>::type color_map_t;
color_map_t colorMap; //Create a color map

This maps vertex_descriptor to (in my case) default_color_type. The appropriate call to boost's bfs would be

boost::breadth_first_visit(g, *boost::vertices(g).first, boost::color_map(colorMap));

Given a color_names structure that maps the color number like

const char* color_names[] = {"white", "gray", "green", "red", "black"};

one could iterate through the colors by iterating over all vertices in the graph and using the vertex_descriptor of the current vertex as an argument for the []-operator in the color map:

GraphType::vertex_iterator it, itEnd;
for (boost::tie(it, itEnd) = boost::vertices(g); it != itEnd; it++)
{
  std::cout << "Color of node " << *it << " is " << color_names[colorMap[*it]] << std::endl;
}
like image 98
AquilaRapax Avatar answered Oct 26 '22 23:10

AquilaRapax