Boost Graph Library and Visitors

Question

I'm writing a library for manipulating bond graphs, and I'm using the Boost Graph Library to store the data for me. Unfortunately, I can't seem to figure out how to implement a proper visitor pattern using it, as you can't subclass out vertices - you must rely on 'properties' instead. The visitor framework provided in the library seems heavily geared towards working with certain algorithms where vertices are all of the same type, but store different information. In my problem, the vertices are of differing types and store differing types of information - some vertices are resistors, while some are capacitors, etc. How do I go about writing a visitor pattern that works based on a property of a vertex, instead of the vertex itself?

My only thought so far has been to write a small class to represent the type of an object that points back to the original vertex that I need to get the graph information. However, this seems very kludgy, and evil to work with.

Answer 1

Maybe you could use boost::variant to construct a disjoint sum of the vertex types, then combine the BGL visitor with a boost::variant visitor at each vertex?

Answer 2

What do you mean, you can't subclass out vertices? You can use your own vertex class, it's just a matter of specifying it in the Graph typedef. You can even use members as properties when working with BGL algorithms.

As for the other way around (which is harder IMO), you need to create a vertex property list and access it using a vertex descriptor... I think.

Edit: You specify vertex/edge classes when defining your graph type:

struct Vertex {
    double some_property;
};

struct Edge {
    double weight;
};

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::undirectedS, Vertex, Edge
> Graph; //sorry about the formatting

Graph g;

From where on g[vertex_descriptor] should return a reference to Vertex, e.g.:

//add 100 vertices
for (int i=0; i<100; ++i) {
    Graph::vertex_descriptor v = add_vertex(g);
    g[v].some_property = -1.0;
}

//zero some_property for all vertices
for (Graph::vertex_iterator i = vertices(g).first;
                            i != vertices(g).second;
                            ++i)
{
    g[*i].some_property = 0.0;
}

I couldn't find my visitor code making use of these properties but I did find the relevant part of the BGL documentation:

1) The part about Internal Properties, which recommends you use instead:
2) Bundled Properties

The second link seems to have a Boost function making use of bundled properties using a member pointer.

Does this help?

Answer 3

If anyone cares, after 2 months, here is a visitor that looks at the property.

class demo_visitor : public default_bfs_visitor {
public:
    template <typename Vertex, typename Graph>
    void discover_vertex( Vertex u, Graph& g)
    {
     printf("Visited vertex %d with property %f\n",
      u, g[u].some_property);
    }
};

If the visitor needs to modify the properties, then things are lightly more complicated. For the issues - click here