boost::filtered_graph filtering on vertex color... if I only had a colormap
Lets say I have a graph g (of type graph_t) and a color map (boy I wish I had a colormap): typedef boost::property_map<graph_t, boost::vertex_color_t>::type color_map_t; or is it? auto indexmap = boost::get(boost::vertex_index, g); auto colors = boost::make_vector_property_map<boost::default_color_type>(indexmap); or maybe? auto indexmap = boost::get(boost::vertex_index, g); auto colors = boost::make_vector_property_map<boost::vertex_color_t>(indexmap); or possibly some goop found on the internet? boost::make_iterator_property_map(color_map.begin(), boost::get(boost::vertex_index, data_->g), color_map[0]) or other internet goop? typedef boost::property_map<GraphType, boost::vertex_color_t>::type color_map_t; color_map_t colorMap; boost::color_map(colorMap)) or other internet goop?? std::vector<int> colorMap(num_vertices(g), boost::white_color); so confused... (certainly not surprised why bgl is not a part of stl) Can someone help explain the various types and ways of specifying colormaps and the logic for each way and means? and a function (if I could get that far without VS syntax highlighter going bonkers and gobs of compiler errors.. you know the type): make_pretty(g, colormap ) which colors the graph colormap and a filter struct for boost::filtered_graph<Graph, EdgePredicate, VertexPredicate> (where I wonder why if I only want to filter vertices I have to set boost::keep_all for EdgePredicate... sigh... I know the answer... and also know how long it found me to find/figure out boost::keep_all - and if you are looking for boost::keep_all and found it here... your welcome ;-) ) and modifying (probably incorrectly) boost::filtered_graph example to: template <typename ColorMap> struct vertex_color_filter_eq { vertex_color_filter_eq() { } vertex_color_filter_eq(ColorMap colormap/*, boost::default_color_type c*/) : m_colormap(colormap)/*, m_c(c)*/ { } template <typename Vertex> bool operator()(const Vertex& v) const { return 0 < get(m_colormap, v); //return c < get(m_colormap, v); } ColorMap m_colormap; //boost::default_color_type m_c; }; auto indexmap = boost::get(boost::vertex_index, g); auto colors = boost::make_vector_property_map<boost::default_color_type>(indexmap); // some where here I would call make_pretty(g, colors) typedef property_map<graph_t, boost::vertex_color_t>::type ColorMap_t; vertex_color_filter<ColorMap_t> filter(colors); // boost::filtered_graph<graph_t, boost::keep_all, VertexPredicate> boost::filtered_graph<graph_t, boost::keep_all, vertex_color_filter> fg(g, filter); // Later say if I could get it compile and better if it compiled and worked I could move on and auto color = boost::red_color; typedef property_map<graph_t, boost::vertex_color_t>::type ColorMap_t; vertex_color_filter<ColorMap_t> filter(colors, color); boost::filtered_graph<graph_t, boost::keep_all, vertex_color_filter> fg(g, filter); Maybe if I color them yellow, I can then reach the wizard pull back the curtain and ask how to create a color map... If I only had a color map.
From: Boost-users [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Brian Davis via Boost-users Lets say I have a graph g (of type graph_t) and a color map (boy I wish I had a colormap):
There is not one single color_map class, it is a concept. Any object that has the following defined will do as a color map: Color c = get(my_color_map, vertex); // get the color of a vertex put(my_color_map, vertex, c); // set the color of a vertex my_color_map[vertex] = c; // get the color of a vertex (for an LValue property map) c = my_color_map[vertex]; // set the color of a vertex (for an LValue property map)
typedef boost::property_map<graph_t, boost::vertex_color_t>::type color_map_t; or is it?
That would only work if your graph type have a vertex_color property embedded in it, which is probably doesn't. If It did you could simply write auto colormap = boost::get(boost::vertex_color, g); The following that you propose look perfectly fine
auto indexmap = boost::get(boost::vertex_index, g); auto colors = boost::make_vector_property_map<boost::default_color_type>(indexmap);
This looks good and would the preferred approach if you do not know the number of vertices when you construct the map, why did it not work? If you do know the number of vertices, use shared_array_property_map instead. Your code example is a bit garbled, but I think the problem is that you are constructing the filter with only two arguments (graph,vertex predicate), whereas the constructor expects (graph, edge predicate, vertex predicate) or (graph, edge predicate). It is a pity that BGL does not have the enthusiastic support anymore that it used to have. Once you get used to it, it is very powerful. The following compiles and runs correctly for me: #include <boost/graph/adjacency_list.hpp> #include <boost/graph/filtered_graph.hpp> #include <boost/graph/properties.hpp> #include <boost/graph/graph_utility.hpp> #include <boost/property_map/property_map.hpp> #include <iostream> template<class ColorMap> struct is_white { is_white() {} is_white(ColorMap cm) : m_cm(cm) {} using key_type = typename boost::property_traits<ColorMap>::key_type; bool operator()(const key_type& v) const { return get(m_cm, v) != boost::default_color_type::white_color; } ColorMap m_cm; }; int main() { using graph_type = boost::adjacency_list<>; graph_type g(5); add_edge(0, 1, g); add_edge(0, 2, g); add_edge(2, 3, g); add_edge(2, 4, g); add_edge(3, 1, g); add_edge(4, 2, g); auto index_map = boost::get(boost::vertex_index, g); auto color_map = boost::make_vector_property_map<boost::default_color_type>(index_map); using color_map_type = decltype(color_map); using edge_predicate = boost::keep_all; using vertex_predicate = is_white<color_map_type>; color_map[0] = boost::default_color_type::black_color; color_map[1] = boost::default_color_type::white_color; color_map[2] = boost::default_color_type::black_color; color_map[3] = boost::default_color_type::black_color; color_map[4] = boost::default_color_type::black_color; using filtered_graph_type = boost::filtered_graph<graph_type, edge_predicate, vertex_predicate>; filtered_graph_type fg(g, edge_predicate(), vertex_predicate(color_map)); std::cout << "unfiltered edges: " << std::endl; boost::print_graph(g, "01234"); std::cout << "filtered edges:" << std::endl; boost::print_graph(fg, "012345"); return 0; }
Since my graph, g, of type graph_t is: typedef boost::property <boost::edge_weight_t, float > edge_properties; //typedef boost::property<boost::vertex_first_name_t, std::string> vertex_properties; typedef boost::property<boost::vertex_index1_t, size_t, boost::property<boost::vertex_component_t, int> > vertex_properties; typedef boost::property<boost::vertex_color_t, boost::default_color_type> color_properties; //typedef boost::property<boost::vertex_index1_t, size_t, // boost::property<boost::vertex_component_t, int, // boost::property<boost::vertex_color_t, boost::default_color_type>> > vertex_properties; #define USE_BOOST_GRAPH_VECS typedef boost::adjacency_list< #ifdef USE_BOOST_GRAPH_VECS // !NOTE: see:https://stackoverflow.com/ questions/15649166/bgl-depth-first-search-error-with-color-map#15654246 // This is the important part of the "sea of errors". // Only adjacency_list that have vecS as the VertexList // template parameter have a default internal vertex_index // property and this property is used by the default color // map(you are using listS). boost::vecS, boost::vecS, //boost::vecS, boost::listS, //boost::setS, boost::listS, #else // !Note: See http://www.boost.org/doc/libs/1_62_0/libs/graph/doc/ adjacency_list.html // Iterator and Descriptor Stability/Invalidation regarding iterator stability when using // the vector and list containers. boost::listS, boost::listS, #endif boost::undirectedS, //boost::bidirectionalS, //boost::no_property, vertex_properties, edge_properties, //color_properties, boost::vecS > graph_t; graph_t g; and is/was created without color properties (color_properties or vertex_color_t). When trying to create a colormap with: property_map<graph_t, boost::vertex_color_t>::type colors = get(vertex_color_t(), g); the error is generated by VS: boost-1_60\boost/graph/detail/adjacency_list.hpp(2584): error C2182: 'reference' : illegal use of type 'void' which is ofcourse not real clear what is generating the error but after finding the actual offending line 5 lines later in the error console as is the power of template meta programing. The "illegal use of type 'void'" error is a result of the graph not having an internal property that can be accessed by get: template <class PropertyTag> property_map<filtered_graph, PropertyTag>::type get(PropertyTag, filtered_graph& g) Adding the property internal to the graph by commenting out: typedef boost::property<boost::vertex_index1_t, size_t, boost::property<boost::vertex_component_t, int> > vertex_properties; And uncommenting (putting it it place of above): typedef boost::property<boost::vertex_index1_t, size_t, boost::property<boost::vertex_component_t, int, boost::property<boost::vertex_color_t, boost::default_color_type>> > vertex_properties The property is now internal and so a vertex colormap can be generated using: property_map<graph_t, boost::vertex_color_t>::type colors = get(vertex_color_t(), g); However an external colormap could be used: typedef std::vector<int> ColorMap_t; ColorMap_t colors(num_vertices(g)); vertex_color_filter_eq<ColorMap_t> filter(colors); // boost::filtered_graph<graph_t, boost::keep_all, VertexPredicate> boost::filtered_graph<graph_t, boost::keep_all, vertex_color_filter_eq<ColorMap_t>> fg(g, boost::keep_all(), filter); Note now the successful attempt to use boost::keep_all and boost::keep_all()
Adding the property internal to the graph by commenting out:
typedef boost::property<boost::vertex_index1_t, size_t, boost::property<boost::vertex_component_t, int> > vertex_properties;
I would recommend using external property maps where possible. It makes life easier, because there is less magic and it will simplify debugging your code.
Hello, everybody, I have followed your conversation and since I have a similar problem, I would be happy if you could help me. At the moment I am really lost. The problem is to create the color map that can be used in Depth_First_Search. A special feature that I have is that I want to change the Vertex color of DFS to modify the DFS. For example like this: If I make the color map global and pass it to the visitor, everything works: If the color map is not global but external, I can write the map, but it is not the same as the DFS color map and therefore I cannot manipulate the DFS algorithm: I then tried to create an internal map and work with the get() and put() functions, but I didn't succeed: I'd be so grateful for any hint. Best Juergen -- Sent from: http://boost.2283326.n4.nabble.com/Boost-Users-f2553780.html
Sorry in my last post, the code was not insert... Hello, everybody, I have followed your conversation and since I have a similar problem, I would be happy if you could help me. At the moment I am really lost. The problem is to create the color map that can be used in Depth_First_Search. A special feature that I have is that I want to change the Vertex color of DFS to modify the DFS. For example like this: template < typename Vertex, typename Graph > void finish_vertex(Vertex u, const Graph & g) { diGraph::vertex_descriptor vertex; vertex = boost::vertex(u, g); if (u == m_destination) { *m_result = true; //save current path m_allPaths->insert(std::make_pair(m_numPaths, m_spath)); m_numPaths++; } if (u == m_source) { for (auto vd : boost::make_iterator_range(vertices(g))) { vertex_coloring[vd] = boost::black_color; } } } If I make the color map global and pass it to the visitor, everything works: //global version (working) typedef boost::property< boost::vertex_name_t, std::string, boost::property<boost::vertex_index_t, int> > vertex_properties; typedef boost::property< boost::edge_weight_t, float, boost::property<boost::edge_index_t, int > > edge_properties; typedef boost::adjacency_list < boost::vecS, boost::vecS, boost::directedS, vertex_properties, edge_properties> diGraph; //global version (working) typedef std::map<diGraph::vertex_descriptor, default_color_type> colormap; colormap vertex_coloring; my_vis vis(0, 3, &foundDestination, &tempPaths); //global version (working version) //depth_first_search(ee_archi, vis, boost::make_assoc_property_map(vertex_coloring),0); If the color map is not global but external, I can write the map, but it is not the same as the DFS color map and therefore I cannot manipulate the DFS algorithm: //external map typedef boost::property< boost::vertex_color_t, boost::default_color_type> color_properties; typedef boost::property< boost::vertex_name_t, std::string, boost::property<boost::vertex_index_t, int > > vertex_properties; typedef boost::property< boost::edge_weight_t, float, boost::property<boost::edge_index_t, int > > edge_properties; typedef boost::adjacency_list < boost::vecS, boost::vecS, boost::directedS, vertex_properties, edge_properties, color_properties> diGraph; struct my_vis : default_dfs_visitor { //internal map using colormap = std::map<diGraph::vertex_descriptor, default_color_type>; colormap vertex_coloring; ….}; //not working my_vis vis(0, 3, &foundDestination, &tempPaths); depth_first_search(ee_archi, vis, boost::make_assoc_property_map(vis.vertex_coloring),0); I then tried to create an internal map and work with the get() and put() functions, but I didn't succeed: //internal map typedef boost::property< boost::vertex_name_t, std::string, boost::property<boost::vertex_index_t, int, boost::property< boost::vertex_color_t, boost::default_color_type> > > vertex_properties; typedef boost::property< boost::edge_weight_t, float, boost::property<boost::edge_index_t, int > > edge_properties; typedef boost::adjacency_list < boost::vecS, boost::vecS, boost::directedS, vertex_properties, edge_properties> diGraph; I'd be so grateful if you'd give me a hint. -- Sent from: http://boost.2283326.n4.nabble.com/Boost-Users-f2553780.html
//not working depth_first_search(ee_archi, vis, boost::make_assoc_property_map(vis.vertex_coloring),0);
The visitor is passed to depth_first_search by value, and hence a copy of vis is made and you are then working on two colormaps. You need to change your visitor to have reference semantics so that a copy of the visitor still points to the same color_map. This should work: struct my_vis : default_dfs_visitor { using colormap = boost::associative_property_map<std::map<diGraph::vertex_descriptor, default_color_type> >; colormap vertex_coloring; };
participants (4)
-
Alex Hagen-Zanker -
Alex HighViz -
Brian Davis -
Juergen