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

18 Nov 2008

      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

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

Alex Brooks