Boost Graph with custom vertices and edges

Question

I'm creating a custom boost graph with my own node and edges properties. I defined the graph as follows:

class NavGraph : public boost::adjacency_list < boost::vecS, boost::vecS, boost::undirectedS, NodeInfo, EdgeInfo > {

public:
  typedef boost::graph_traits<NavGraph>::vertex_descriptor Vertex;
  typedef boost::graph_traits<NavGraph>::edge_descriptor Edge;

  NavGraph(){}

      void init(const std::vector<NodeInfo>& nodes, const std::vector<EdgeInfo>& edges);
}

What I'm trying to do now is to initialize this graph from a list of node and edge properties (in the init method). NodeInfo and EdgeInfo are simple structures with primitive types. So far I've done this:

void NavGraph::init(const std::vector<NodeInfo>& nodes, const std::vector<EdgeInfo>& edges){

  //Add the Vertices
    for (std::vector<NodeInfo>::const_iterator it = nodes.begin() ; it != nodes.end(); ++it){

        Vertex u = boost::add_vertex(*this);
        (*this)[u].nodeIndex = (*it).nodeIndex;
        (*this)[u].x = (*it).x;
        (*this)[u].y = (*it).y;
        (*this)[u].z = (*it).z;

    }

    //Add the edges
    for (std::vector<EdgeInfo>::const_iterator it = edges.begin() ; it != edges.end(); ++it){

    //To be implemented
    }

 }

So, I manage to add the vertices and set the properties (hope it is right). Now, every EdgeInfo has a source and target id, which identify the two nodes of the edge. The problem is that I need to retrieve them by Id from the graph (with the nodeIndex property that I set before), so that I can call the add_edge method. I don't really know how to do this. Hope you guys can help me.

ravenspoint ravenspoint · Accepted Answer · 2014-04-23T12:38:53

Starting at the top: it is NOT a good idea to specialize the adjacency list and add you own methods to it.

Instead you should create an instance of the boost::adjacency_list class as a member of a new class that you can then write methods for.

class cNavGraph {
  public:
  boost::adjacency_list < boost::vecS,
  boost::vecS,
  boost::undirectedS, 
  NodeInfo, EdgeInfo > myNavGraph;

...

Now, to retrieve vertices from the graph by the vertex property nodeIndex you have two options:

Search the vertices for the nodeIndex you want. This is simple but will be slow if the graph is very large.
Create a map from nodeIndex to vertex as you add the vertices, then do a lookup on the map when you need to get the vertex from the nodeIndex. This needs more code and memory, but will be much faster for large graphs.

As a more radical sugestion, I propose redesigning things so that you make the NodeIndex and the vertex descriptor identical, like this

for (std::vector<EdgeInfo>::const_iterator it = edges.begin() ;
   it != edges.end(); ++it)
{
   add_edge( it->first_node_index,
             it->second_node_index,
             myGraph );

Note, in reply to your comment, that the call to add_edge will automatically add the two vertices, if they are not already present, with vertex descriptors equal to the node indices specified. Do not call add_vertex!

When you have completed adding all the edges, you can iterate the through the nodes, adding the properties ( as many as you want ).

Boost Graph with custom vertices and edges

1 Answers