[boost] [parameter] Boost.Graph program not responding at run-time

Subject: [boost] [parameter] Boost.Graph program not responding at run-time
From: Lorenzo Caminiti (lorcaminiti_at_[hidden])
Date: 2011-12-03 08:09:37

Hello all,

If I move the call to boost::depth_first_search into a template
depth_first_search_impl and out of the Boost.Parameter function body,
the code compiles (both MSVC and GCC with latest Boost from trunk) but
the executable runs forever and prints nothing to cout... What am I
doing wrong?

#include <boost/parameter.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/range/irange.hpp>
#include <boost/pending/indirect_cmp.hpp>
#include <boost/type_traits/is_convertible.hpp>
#include <boost/type_traits/is_integral.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/mpl/and.hpp>
#include <boost/mpl/placeholders.hpp>
#include <iostream>

namespace graphs {

template< typename G >
struct vertex_descriptor
{
    typedef typename boost::graph_traits<G>::vertex_descriptor type;
};

template< typename T >
struct is_incidence_and_vertex_list_graph :
    boost::mpl::and_<
          boost::is_convertible<
              typename boost::graph_traits<T>::traversal_category
            , boost::incidence_graph_tag
          >
        , boost::is_convertible<
              typename boost::graph_traits<T>::traversal_category
            , boost::vertex_list_graph_tag
          >
    >
{};

template< typename T, typename Key >
struct is_property_map_of_key :
    boost::is_same<Key, typename boost::property_traits<T>::key_type>
{};

template< typename T, typename Key >
struct is_integral_property_map_of_key
{
    typedef typename boost::mpl::and_<
          boost::is_integral<typename boost::property_traits<T>::value_type>
        , is_property_map_of_key<T, typename Key::type>
    >::type type;
    static const bool value = type::value;
};

template< typename Size, typename IndexMap >
boost::iterator_property_map<boost::default_color_type*, IndexMap,
        boost::default_color_type, boost::default_color_type&>
default_color_map ( Size const& num_vertices, IndexMap const& index_map )
{
    std::vector<boost::default_color_type> colors(num_vertices);
    return &colors[0];
}

template< typename graph_type, typename visitor_type,
        typename root_vertex_type, typename index_map_type,
        typename color_map_type >
void depth_first_search_impl ( graph_type graph, visitor_type visitor,
        root_vertex_type root_vertex, index_map_type index_map,
        color_map_type color_map )
{
    boost::depth_first_search(graph, boost::visitor(visitor).
            color_map(color_map).root_vertex(root_vertex).
            vertex_index_map(index_map));
}

BOOST_PARAMETER_NAME(graph)
BOOST_PARAMETER_NAME(visitor)
BOOST_PARAMETER_NAME(root_vertex)
BOOST_PARAMETER_NAME(index_map)
BOOST_PARAMETER_NAME(color_map)

BOOST_PARAMETER_FUNCTION(
    (void),
    depth_first_search,
    tag,
    (required
        (graph, *(is_incidence_and_vertex_list_graph<boost::mpl::_>))
    )
    (optional
        (visitor, *, boost::dfs_visitor<>())
        (root_vertex,
                (vertex_descriptor<tag::graph::_>),
                *boost::vertices(graph).first)
        (index_map,
                *(is_integral_property_map_of_key< boost::mpl::_,
                        vertex_descriptor<tag::graph::_> >),
                boost::get(boost::vertex_index, graph))
        (in_out(color_map),
                *(is_property_map_of_key< boost::mpl::_,
                        vertex_descriptor<tag::graph::_> >),
                default_color_map(boost::num_vertices(graph), index_map))
    )
) {
    return depth_first_search_impl<graph_type, visitor_type, root_vertex_type,
            index_map_type, color_map_type>(graph, visitor, root_vertex,
            index_map, color_map);
}

} // namespace graphs

template< typename TimeMap >
struct dfs_time_visitor : public boost::default_dfs_visitor
{
    typedef typename boost::property_traits<TimeMap>::value_type T;

    dfs_time_visitor ( TimeMap dmap, TimeMap fmap, T& t )
        : dmap_(dmap), fmap_(fmap), time_(t)
    {}

    template< typename V, typename G >
    void discover_vertex ( V u, G const& g ) const { put(dmap_, u, time_++); }

    template< typename V, typename G >
    void finish_vertex ( V u, G const& g ) const { put(fmap_, u, time_++); }

private:
    TimeMap dmap_;
    TimeMap fmap_;
    T& time_;
};

int main ( void )
{
    typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS> G;
    typedef boost::graph_traits<G>::vertices_size_type size_type;

    enum {u, v, w, x, y, z, N};
    char names[] = {'u', 'v', 'w', 'x', 'y', 'z'};
    typedef std::pair<int, int> E;
    E edges[] = {E(u, v), E(u, x), E(x, v), E(y, x), E(v, y), E(w, y), E(w, z),
            E(z, z)};
    G g(edges, edges + sizeof(edges) / sizeof(E), N);

    std::vector<size_type> dtime(boost::num_vertices(g));
    std::vector<size_type> ftime(boost::num_vertices(g));
    size_type t = 0;
    dfs_time_visitor<size_type*> vis(&dtime[0], &ftime[0], t);

    graphs::depth_first_search(g, vis);

    std::vector<size_type> dorder(N);
    boost::integer_range<size_type> r(0, N);
    std::copy(r.begin(), r.end(), dorder.begin());
    std::sort(dorder.begin(), dorder.end(),
            boost::indirect_cmp<size_type*, std::less<size_type> >(&dtime[0]));
    std::cout << "order of discovery: ";
    for(int i = 0; i < N; ++i) std::cout << names[dorder[i]] << " ";
    std::cout << std::endl;

    std::vector<size_type> forder(N);
    std::copy(r.begin(), r.end(), forder.begin());
    std::sort(forder.begin(), forder.end(),
            boost::indirect_cmp<size_type*, std::less<size_type> >(&ftime[0]));
    std::cout << "order of finish: ";
    for(int i = 0; i < N; ++i) std::cout << names[forder[i]] << " ";
    std::cout << std::endl;

    return 0;
}

Thanks.
--Lorenzo