undirected DFS: how can I provide color maps as exterior properties?

Question

I am using the undirected DFS (Depth First Search) algorithm implemented in boost::graph.

This algorithm needs color values on vertices and edges to keep track of the ones that have been parsed. In the provided example, the code stores these colors values as internal properties of the graph:

typedef adjacency_list<
    vecS,
    vecS,
    undirectedS,
    no_property,       // vertex properties
    property<edge_color_t, default_color_type> // edge colors
> graph_t;

And the call is done using the "named properties" version:

undirected_dfs(g, root_vertex(vertex_t(0)).visitor(vis)
             .edge_color_map(get(edge_color, g)));

My problem is that I have custom values for vertices and edges. I use what seems to be the preferred way of doing, which is called "bundled properties":

struct my_vertex { int a1; float a2; }
struct my_edge   { int b1; float b2; }
typedef adjacency_list<
    vecS,
    vecS,
    undirectedS,
    my_vertex,       // vertex properties
    my_edge          // edge properties
> graph_t;

Of course, the previous DFS function call does not work with this graph type definition. For vertices, the manual states that a default is provided, and it does build fine with only specific vertex type and the edges type as shown above. But if I want a specific edge type, I came to the conclusion that I need to provide separatly the colors needed by the algorithm, as I can't use the properties as shown in the example code. So I assume this can be done by providing them as "exterior properties".

My problem is: how do I do that ?

Manual excerpt:

UTIL: edge_color_map(EdgeColorMap edge_color) This is used by the algorithm to keep track of which edges have been visited. The type EdgeColorMap must be a model of Read/Write Property Map and its key type must be the graph's edge descriptor type and the value type of the color map must model ColorValue.

This is unclear to me, I have tried to read the part about property maps, but I just cant get it.

With the help of this answer, I tried this below, but this fails: (uses the "unnamed parameter" version)

std::vector<int> edge_color(   boost::num_edges(g), 0);
std::vector<int> vertex_color( boost::num_vertices(g), 0 );

boost::undirected_dfs(
    g,
    boost::visitor( boost::default_dfs_visitor() ),
    boost::vertex_color_map( vertex_color ),
    boost::edge_color_map( edge_color ),
    boost::root_vertex( vertex_t(0) )
);

If somebody could point me in the right direction...

Answer 1

You need to satisfy the exact parameter requirements documented: http://www.boost.org/doc/libs/1_63_0/libs/graph/doc/undirected_dfs.html

This means you /can/ get away with a vector for the vertex colors, but the edge colors need to be in an associative container, because the edge descriptor isn't integral like the vertex descriptor is for your graph type.

std::vector<default_color_type> vertex_color(num_vertices(g));
std::map<graph_t::edge_descriptor, default_color_type> edge_color;

auto idmap = get(vertex_index, g);
auto vcmap = make_iterator_property_map(vertex_color.begin(), idmap);
auto ecmap = make_assoc_property_map(edge_color);

graph_t::vertex_descriptor const start = 0;

Now you can invoke either the fixed-argument version of the algorithm:

undirected_dfs(g, vis, vcmap, ecmap, start);

Alternatively, invoke the exact same using the named-argument version:

undirected_dfs(g, 
        root_vertex(graph_t::vertex_descriptor(0))
        .visitor(vis)
        .vertex_color_map(vcmap)
        .edge_color_map(ecmap)
    );

DEMO

Live On Coliru

#include <iostream>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/undirected_dfs.hpp>
#include <boost/graph/adjacency_list.hpp>

using namespace boost;

struct my_vertex { int a1; float a2; };
struct my_edge   { int b1; float b2; };

struct detect_loops : public boost::dfs_visitor<> {
    template <class Edge, class Graph>
    void back_edge(Edge e, const Graph& g) {
        std::cout << g[source(e,g)].a1 << " -- " << g[target(e,g)].a1 << "\n";
    }
};


typedef adjacency_list<vecS, vecS, undirectedS, my_vertex, my_edge> graph_t;

int main() {
    detect_loops vis;

    graph_t g;

    std::vector<default_color_type> vertex_color(num_vertices(g));
    std::map<graph_t::edge_descriptor, default_color_type> edge_color;

    auto idmap = get(vertex_index, g);
    auto vcmap = make_iterator_property_map(vertex_color.begin(), idmap);
    auto ecmap = make_assoc_property_map(edge_color);

    graph_t::vertex_descriptor const start = 0;

    undirected_dfs(g, vis, vcmap, ecmap, start);

    undirected_dfs(g, 
            root_vertex(graph_t::vertex_descriptor(0))
            .visitor(vis)
            .vertex_color_map(vcmap)
            .edge_color_map(ecmap)
        );
}