Modifying vertex properties in a Boost::Graph

Question

I am trying to figure out how to use boost::graph to store some information. However, there is information I want tied to each vertex. Staring at the documentation for the library reveals either(a)badly written documentation, or (b), I'm obviously not as good at C++ as I thought. Pick two.

I am looking for either a tutorial on assigning properties, or a simple example use.

Answer 1

I consider Boost.Graph to have a very good documentation, but not truly for beginners on the matter. So here goes an example that i hope is simple enough !

//includes

// Create a name for your information
struct VertexInformation
{
  typedef boost::vertex_property_type type;
};

// Graph type, customize it to your needs
// This is when you decide what information will be attached to vertices and/or edges
// of MyGraph objects
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS,
  boost::property<VertexInformation, double> > MyGraph;

int main()
{
  MyGraph graph;

  // Create accessor for information
  typedef boost::property_map<MyGraph, VertexInformation>::type  InformationAccessor;
  InformationAccessor information( get( VertexInformation(), graph ) );

  // Create a vertex (for example purpose)
  typedef boost::graph_traits<MyGraph>::vertex_descriptor MyVertex;
  MyVertex vertex = add_vertex( graph );

  // Now you can access your information
  put( information, vertex, 1. );

  // returns 1 !
  get( information, vertex );
  return 0;
}

Answer 2

Below is code I used to attach some properties to vertices, edges, and graphs. Note that vertex name and graph name are predefined properties (see boost/properties.hpp for a complete list) so that vertex_name_t and graph_name_t are already defined. However, vertex_location_t, edge_length_t, and graph_notes_t are my own properties and hence need definition. I cobbled together this code from various examples and documentation, and I'm not sure exactly what BOOST_INSTALL_PROPERTY does, but the code seems to work fine.

// Define custom properties
enum vertex_location_t { vertex_location };
enum edge_length_t     { edge_length     };
enum graph_notes_t     { graph_notes     };

namespace boost
{
    BOOST_INSTALL_PROPERTY(vertex, location);
    BOOST_INSTALL_PROPERTY(edge,   length  );
    BOOST_INSTALL_PROPERTY(graph,  notes   );
}

// Define vertex properties:  vertex name and location
typedef property<vertex_name_t,     string,
        property<vertex_location_t, Point3> >
VertexProperties;

// Define edge properties:  length
typedef property<edge_length_t, double> EdgeProperties;

// Define graph properties:  graph name and notes
typedef property<graph_name_t,  string,
        property<graph_notes_t, string> >
GraphProperties;

// Define a graph type
typedef adjacency_list
<
    vecS,       // edge container type
    vecS,       // vertex container type
    undirectedS,
    VertexProperties,
    EdgeProperties,
    GraphProperties
> Graph;

Answer 3

I found the examples pretty useful. On windows it will be in your \Program Files\boost\boost_1_38\libs\graph\example directory.

kevin_bacon2.cpp uses vertex properties to store the names of actors.

Your vertex and edge properties can be stored in regular structs or classes.

Answer 4

I don't like the nested-template property approach of boost::graph, so I wrote a small wrapper around everything, that basically allows to put any struct/class as a vertex/edge property. One can access properties accessing the struct members.

To keep it flexible these structs are defined as template parameter.

Here the Code:

/* definition of basic boost::graph properties */
enum vertex_properties_t { vertex_properties };
enum edge_properties_t { edge_properties };
namespace boost {
 BOOST_INSTALL_PROPERTY(vertex, properties);
 BOOST_INSTALL_PROPERTY(edge, properties);
}


/* the graph base class template */
template < typename VERTEXPROPERTIES, typename EDGEPROPERTIES >
class Graph
{
public:

 /* an adjacency_list like we need it */
 typedef adjacency_list<
  setS, // disallow parallel edges
  listS, // vertex container
  bidirectionalS, // directed graph
  property<vertex_properties_t, VERTEXPROPERTIES>,
  property<edge_properties_t, EDGEPROPERTIES>
 > GraphContainer;


 /* a bunch of graph-specific typedefs */
 typedef typename graph_traits<GraphContainer>::vertex_descriptor Vertex;
 typedef typename graph_traits<GraphContainer>::edge_descriptor Edge;
 typedef std::pair<Edge, Edge> EdgePair;

 typedef typename graph_traits<GraphContainer>::vertex_iterator vertex_iter;
 typedef typename graph_traits<GraphContainer>::edge_iterator edge_iter;
 typedef typename graph_traits<GraphContainer>::adjacency_iterator adjacency_iter;
 typedef typename graph_traits<GraphContainer>::out_edge_iterator out_edge_iter;

 typedef typename graph_traits<GraphContainer>::degree_size_type degree_t;

 typedef std::pair<adjacency_iter, adjacency_iter> adjacency_vertex_range_t;
 typedef std::pair<out_edge_iter, out_edge_iter> out_edge_range_t;
 typedef std::pair<vertex_iter, vertex_iter> vertex_range_t;
 typedef std::pair<edge_iter, edge_iter> edge_range_t;


 /* constructors etc. */
 Graph()
 {}

 Graph(const Graph& g) :
  graph(g.graph)
 {}

 virtual ~Graph()
 {}


 /* structure modification methods */
 void Clear()
 {
  graph.clear();
 }

 Vertex AddVertex(const VERTEXPROPERTIES& prop)
 {
  Vertex v = add_vertex(graph);
  properties(v) = prop;
  return v;
 }

 void RemoveVertex(const Vertex& v)
 {
  clear_vertex(v, graph);
  remove_vertex(v, graph);
 }

 EdgePair AddEdge(const Vertex& v1, const Vertex& v2, const EDGEPROPERTIES& prop_12, const EDGEPROPERTIES& prop_21)
 {
  /* TODO: maybe one wants to check if this edge could be inserted */
  Edge addedEdge1 = add_edge(v1, v2, graph).first;
  Edge addedEdge2 = add_edge(v2, v1, graph).first;

  properties(addedEdge1) = prop_12;
  properties(addedEdge2) = prop_21;

  return EdgePair(addedEdge1, addedEdge2);
 }


 /* property access */
 VERTEXPROPERTIES& properties(const Vertex& v)
 {
  typename property_map<GraphContainer, vertex_properties_t>::type param = get(vertex_properties, graph);
  return param[v];
 }

 const VERTEXPROPERTIES& properties(const Vertex& v) const
 {
  typename property_map<GraphContainer, vertex_properties_t>::const_type param = get(vertex_properties, graph);
  return param[v];
 }

 EDGEPROPERTIES& properties(const Edge& v)
 {
  typename property_map<GraphContainer, edge_properties_t>::type param = get(edge_properties, graph);
  return param[v];
 }

 const EDGEPROPERTIES& properties(const Edge& v) const
 {
  typename property_map<GraphContainer, edge_properties_t>::const_type param = get(edge_properties, graph);
  return param[v];
 }


 /* selectors and properties */
 const GraphContainer& getGraph() const
 {
  return graph;
 }

 vertex_range_t getVertices() const
 {
  return vertices(graph);
 }

 adjacency_vertex_range_t getAdjacentVertices(const Vertex& v) const
 {
  return adjacent_vertices(v, graph);
 }

 int getVertexCount() const
 {
  return num_vertices(graph);
 }

 int getVertexDegree(const Vertex& v) const
 {
  return out_degree(v, graph);
 }


 /* operators */
 Graph& operator=(const Graph &rhs)
 {
  graph = rhs.graph;
  return *this;
 }

protected:
 GraphContainer graph;
};

Using this you can access properties like this:

struct VertexProperties {
 int i;
};

struct EdgeProperties {
};

typedef Graph<VertexProperties, EdgeProperties> MyGraph;

MyGraph g;

VertexProperties vp;
vp.i = 42;

MyGraph::Vertex v = g.AddVertex(vp);

g.properties(v).i = 23;

Of course you may have other needs for your graph's structure, but modification of the code above should be pretty easy.

Answer 5

I really like the solution of gre, using structs to specify Vertex and Edge properties. It's very convenient and also flexible. However, with all the typedef in the class, I don't find a way to access the information from outside the class. Like, when I want another class to use the information stored on a vertex, I can't do: OtherClass::printVertexInfo(Vertex v); // e.g. v = Graph::getFirstVertex(); because "Vertex" is unknown to the OtherClass, obviously. So how can I achieve this, conserving the templated-way of Graph? Thanks.

Answer 6

What about using bundled properties?

using namespace boost;

struct vertex_info { 
    std::string whatever; 
    int othervalue; 
    std::vector<int> some_values; 
};

typedef adjacency_list<vecS, vecS, undirectedS, vertex_info> graph_t;

graph_t g(n);

g[0].whatever = "Vertex 0";

[...]

and so on.

I use BGL a lot and I think that working with bundled properties (http://www.boost.org/doc/libs/1_42_0/libs/graph/doc/bundles.html) is really straightforward (if your compiler supports partial template specialization).

The other type of vertex property that I like are external properties. You can declare std::vectors of the appropriate size and use them as properties in most of the algorithms.