[boost] Fw: [BGL] graph coloring

From: Wang Weiwei (wwwang_at_[hidden])
Date: 2006-07-19 01:31:46

>Hello,
>
>I'm coloring my graph with the following code:
>
>	typedef std::set<std::pair<int, int> > panel_conn_set_t;
>	panel_conn_set_t panel_conn_set;
>
>	for(...)
>	{
>		// get the information of vertices connectivities
>		// vertices are referred to with int
>		panel_conn_set.insert(std::make_pair([some int], [some int]));
>	}
>
>	typedef boost::adjacency_list<boost::vecS, boost::vecS, 
>		boost::undirectedS, 
>		// use the default color map
>		property<vertex_color_t, default_color_type>,	
>		no_property> graph_t;
>	typedef property_map<graph_t, vertex_color_t>::type vertex_color_map_t;
>	typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_descriptor;
>	typedef boost::graph_traits<graph_t>::edge_descriptor edge_descriptor;
>	typedef boost::graph_traits<graph_t>::vertex_iterator vertex_iterator;
>	typedef boost::graph_traits<graph_t>::vertices_size_type vertices_size_type;
>
>	// the only graph object
>	graph_t g;
>
>	vertex_color_map_t& vertex_color_map = boost::get(vertex_color, g);
>
>	for(panel_conn_set_t::const_iterator it=panel_conn_set.begin(); it!=panel_conn_set.end(); ++it)
>	{
>		// using int directly as vecter descriptor
>		boost::add_edge((*it).first, (*it).second, g);
>	}
>
>	// ****** method A ******
>	vertices_size_type num_colors = boost::sequential_vertex_coloring(g, vertex_color_map);
>
>	// ****** method B ******
>	std::vector<vertices_size_type> color_vec(boost::num_vertices(g));
>	boost::iterator_property_map<vertices_size_type*, vertex_index_map>
>		color(&color_vec.front(), get(vertex_index, g));
>	vertices_size_type num_colors = boost::sequential_vertex_coloring(g, color);
>
>The code for 'method A' does not compile, but those for 'method B'(borrowed from the BGL doc, 
>seems to be an exterior property map implementation) works well.
>
>Why? Any help will be appreciated.
>
>Max
>
Or, the question may be, how to make the method A code work? that means I want to use an
internal color property map associated to the graph obj.

Another question here is, as was told in the doc, the result from the above code would not necessarily
be the optimum/minimum number of colors. And in the 'Graph Coloring ' section of the doc, an ordering
implementation, smallest_last_ordering(), is introduced. Unfortunately, I don't know how to make the 
code to co-operate with above code to get a better result.

As information for your reference, one of my graph running in my program has about 28000 vertices, the 
result I got from the above code, for this example, is that I can color all of the vertices with 9 
distinctive colors. 
Even though it's not optimum, but it's a fairly good result for me. Of course, any better number will be
prefered.

Thanks for you concern and help.

P.S. Probably, I think I've still not clearly understood that how the boot.PropertyMap lib works with
BGL, but definitely I will get it.

Thanks again.

Max