[Boost-users] [BGL] Bundled properties and property maps

Subject: [Boost-users] [BGL] Bundled properties and property maps
From: Alex Brooks (a.brooks_at_[hidden])
Date: 2008-11-18 06:41:21

Hi,

I've used BGL before for representing graphs, but this is my first time with 
an algorithm.  I've been stuck for many hours trying to define a property map 
with bundled properties, I'd really appreciate some help.  I'm using gcc4.3, 
boost 1.34.  An example program and the compiler error are:

-------------------------------------------------------------
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/astar_search.hpp>

using namespace std;

class Point {
public:
    double p_[2];
};

struct EdgeProp {
    double cost;
};

typedef boost::adjacency_list<boost::vecS,
                              boost::vecS,
                              boost::undirectedS,
                              Point*,
                              EdgeProp> Graph;

typedef boost::graph_traits<Graph>::vertex_descriptor VertexRef;

class AStarHeuristic : public boost::astar_heuristic<Graph, double>
{
public:
    double operator()( VertexRef vertex ) const {return 0.0;}
}; 

// exception for termination
struct FoundGoal {};

//
// A* Visitor that terminates when we reach the goal
//
class AStarVisitor : public boost::default_astar_visitor
{
public:
    AStarVisitor( const VertexRef &goal )
        : goal_(goal) {}

    template <class Graph>
    void examine_vertex( VertexRef vertex, Graph &g )
        {
            if( vertex == goal_ )
                throw FoundGoal();
        }

private:
    VertexRef goal_;
};

bool
searchThroughGraph( const Graph            &graph,
                    VertexRef               start,
                    VertexRef               goal,
                    std::vector<VertexRef> &shortestPath )
{
    AStarHeuristic aStarHeuristic;
    AStarVisitor aStarVisitor( goal );

    typedef boost::property_map<Graph, double EdgeProp::*>::type 
EdgeWeightMap; 
    EdgeWeightMap edgeWeightMap = get(&EdgeProp::cost, graph);

    std::vector<VertexRef> predecessors(num_vertices(graph));
    try {
        astar_search( graph,
                      start,
                      aStarHeuristic,
                      boost::weight_map(edgeWeightMap).
                      predecessor_map(&predecessors[0]).
                      visitor(aStarVisitor) );
    }
    catch ( const FoundGoal& )
    {
        shortestPath.clear();
        for ( VertexRef vertex = goal;; vertex = predecessors[vertex] )
        {
            shortestPath.push_back( vertex );
            if ( predecessors[vertex]==vertex ) break;
        }
        std::reverse( shortestPath.begin(), shortestPath.end() );
        return true;
    }

    // If we get to here, we couldn't reach the goal
    return false;
}

int main()
{
    Graph graph;
    std::vector<VertexRef> path;
    searchThroughGraph(graph,0,1,path);
    return 0;
}

-------------------------------------------------------------

/home/a.brooks/shh/src/libs/prm/test/stupid.cpp: In function ‘bool 
searchThroughGraph(const Graph&, VertexRef, VertexRef, std::vector<unsigned 
int, std::allocator<unsigned int> >&)’:
/home/a.brooks/shh/src/libs/prm/test/stupid.cpp:64: error: conversion 
from ‘boost::bundle_property_map<const boost::adjacency_list<boost::vecS, 
boost::vecS, boost::undirectedS, Point*, EdgeProp, boost::no_property, 
boost::listS>, boost::detail::edge_desc_impl<boost::undirected_tag, unsigned 
int>, EdgeProp, const double>’ to non-scalar type ‘searchThroughGraph(const 
Graph&, VertexRef, VertexRef, std::vector<unsigned int, 
std::allocator<unsigned int> >&)::EdgeWeightMap’ requested

-------------------------------------------------------------

Does anyone know what might be wrong?

More generally, I'm a bit mystefied by the "<Graph, double EdgeProp::*>::type" 
syntax -- can anyone give me any pointers about what this syntax means, or 
where I can look it up? (googling for colon-colon-star doesn't help much).
I also tried pattern-matching from the documentation page about bundled 
properties (the weight_map(get(&Highway::miles, map)) example) but couldn't 
get this to compile either.  Is this example correct?

Thanks very much in advance,

Alex