boost::filtered_graph filtering on vertex color... if I only had a colormap

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

boost::filtered_graph filtering on vertex color... if I only had a colormap

Boost - Users mailing list

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. 






_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: boost::filtered_graph filtering on vertex color... if I only had a colormap

Boost - Users mailing list


> From: Boost-users [mailto:[hidden email]] 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;
}
_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: boost::filtered_graph filtering on vertex color... if I only had a colormap

Boost - Users mailing list
In reply to this post by Boost - Users mailing list

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()



_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: boost::filtered_graph filtering on vertex color... if I only had a colormap

Boost - Users mailing list



>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.


_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users