Search code examples
c++boostboost-graph

Boost dominator tree for graph with custom vertex properties

I'm trying to use boost::lengauer_tarjan_dominator_tree with a graph with custom vertex properties, but can't get even a simple example to compile:

#include <vector>
#include <iterator>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dominator_tree.hpp>
#include <boost/property_map/property_map.hpp> 

struct GraphNode
{
    explicit GraphNode(unsigned i) : index {i} {}
    unsigned index;
};

using Graph = boost::adjacency_list<boost::listS, boost::listS, 
                            boost::bidirectionalS, GraphNode, boost::no_property>;

using Vertex = boost::graph_traits<Graph>::vertex_descriptor;

int main()
{
    Graph g {};

    const auto u = boost::add_vertex(GraphNode {0}, g);
    const auto v = boost::add_vertex(GraphNode {1}, g);
    const auto x = boost::add_vertex(GraphNode {2}, g);
    const auto y = boost::add_vertex(GraphNode {3}, g);
    const auto z = boost::add_vertex(GraphNode {4}, g);

    boost::add_edge(u, v, g);
    boost::add_edge(u, x, g);
    boost::add_edge(v, y, g);
    boost::add_edge(x, y, g);
    boost::add_edge(y, z, g);

    const auto index_map = boost::get(&GraphNode::index, g);

    std::vector<Vertex> dom_tree_pred_vector(boost::num_vertices(g),
                                             boost::graph_traits<Graph>::null_vertex());

    auto dom_tree_pred_map = boost::make_iterator_property_map(std::begin(dom_tree_pred_vector),
                                index_map);

    boost::lengauer_tarjan_dominator_tree(g, u, dom_tree_pred_map);
}

Which I tried to adapt from the example given in the docs.

Here is part of the error message:

/usr/local/include/boost/graph/detail/adjacency_list.hpp:2544:33: error: cannot form a reference to 'void'
        typedef const value_type& const_reference;
                                ^
/usr/local/include/boost/graph/dominator_tree.hpp:355:31: error: no matching function for call to 'get'
    const IndexMap indexMap = get(vertex_index, g);

I've also tried to pass in the index map explicitly using the second form of the method, without success. I've noticed this methods interface seems a little different from other graph methods, such as depth_first_search, where the vertex_index_map is a named parameter.

Is it possible to use this method with custom vertex properties?

Solution

  • The problem - as ever - is with using something other than vecS for the vertex container. You lose the builtin vertex_index property, making it mandatory to supply it to the API.

    Sadly this algorithm doesn't support custom vertex index maps well. You tried - correctly - by using index_map, but internally the algorithm still looks for vertex_index_t tagged property.

    The only two ways in which I can see this work is,

    1. to do the DFS stage manually (as even the all-argument overload of lengauer_tarjan* fails to forward the correct index map into the DFS). Then you could call the lengauer_tarjan_dominator_tree_without_dfs implementation and have the result.

    2. Alternatively you could tell the library about your graph's index map.

    (Lastly, you could accept fate and use vecS as the vertex container selector. I suspect this is explicitly not what you wanted.)

    DEMO

    Using the second approach, which may be the most elegant. Here are the specializations/overloads to add:

    namespace boost {
    template <>
        struct property_map<Graph, vertex_index_t> {
            typedef typename property_map<Graph, size_t GraphNode::*>::type type;
            typedef typename property_map<Graph, size_t GraphNode::*>::const_type const_type;
        };

    static auto get(vertex_index_t, Graph& g)       { return get(&GraphNode::index, g); }
    static auto get(vertex_index_t, Graph const& g) { return get(&GraphNode::index, g); }
}

    Live On Coliru

    #include <vector>
#include <iterator>
#include <iostream>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dominator_tree.hpp>
#include <boost/property_map/property_map.hpp> 

struct GraphNode
{
    explicit GraphNode(size_t i) : index {i} {}
    size_t index;
};

using Graph = boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS, GraphNode, boost::no_property>;

namespace boost {
    template <>
        struct property_map<Graph, vertex_index_t> {
            typedef typename property_map<Graph, size_t GraphNode::*>::type type;
            typedef typename property_map<Graph, size_t GraphNode::*>::const_type const_type;
        };

    static property_map<Graph, vertex_index_t>::type       get(vertex_index_t, Graph& g)       { return get(&GraphNode::index, g); }
    static property_map<Graph, vertex_index_t>::const_type get(vertex_index_t, Graph const& g) { return get(&GraphNode::index, g); }
}

using Vertex = boost::graph_traits<Graph>::vertex_descriptor;

int main()
{
    Graph g {};

    const auto u = boost::add_vertex(GraphNode {0}, g);
    const auto v = boost::add_vertex(GraphNode {1}, g);
    const auto x = boost::add_vertex(GraphNode {2}, g);
    const auto y = boost::add_vertex(GraphNode {3}, g);
    const auto z = boost::add_vertex(GraphNode {4}, g);

    boost::add_edge(u, v, g);
    boost::add_edge(u, x, g);
    boost::add_edge(v, y, g);
    boost::add_edge(x, y, g);
    boost::add_edge(y, z, g);

    std::vector<Vertex> dom_pred(num_vertices(g), boost::graph_traits<Graph>::null_vertex());

    auto index_map = boost::get(&GraphNode::index, g); // equivalent to vertex_index_t now
    auto dom_tree_pred_map (boost::make_iterator_property_map(std::begin(dom_pred), index_map));

    // Run main algorithm
    boost::lengauer_tarjan_dominator_tree(g, u, dom_tree_pred_map);

    std::cout << "Result: ";
    for (auto v : dom_pred) {
        if (v == boost::graph_traits<Graph>::null_vertex())
            std::cout << "(root) "; 
        else
            std::cout << g[v].index << " "; 
    }
}

    Prints

    Result: (root) 0 0 0 3