A Boost graph with string vertexes

Question

I know how to create in Boost Graph a graph with integer or char vertexes (see commented code below). The question is how to rewrite this code to work with string vertexes?

#include <string>
#include <boost/graph/adjacency_list.hpp>

using namespace boost;

int main (int argc, char **argv)
{
        typedef adjacency_list <vecS, vecS, undirectedS> vector_graph_t;

        //works
        //typedef std::pair <int, int> E;
        //E edges[] = { E (2, 5), E (5, 3), E (3, 1), E (5, 1)};
        //vector_graph_t g (&edges[0],&edges[0] + sizeof(edges) / sizeof(E), 4);

        //works
        //typedef std::pair <char, char> E;
        //E edges[] = { E ('a', 'b'), E ('a', 'c'), E ('x', 'a'), E ('b', 'x')};
        //vector_graph_t g (&edges[0],&edges[0] + sizeof(edges) / sizeof(E), 4);

        //does not work
        typedef std::pair <std::string, std::string> E;
        E edges[] = { E ("aaa", "bbb"), E ("bbb", "ccc"), E ("aaa", "xxx"), E ("bbb", "ccc")};
        vector_graph_t g (&edges[0],&edges[0] + sizeof(edges) / sizeof(E), 4); 

        return 0;
}

The program above compiles with error:

/usr/local/include/boost/graph/detail/adjacency_list.hpp:2076: error: no matching function for call to ‘add_edge(std::basic_string<char, std::char_traits<char>, std::allocator<char> >&, std::basic_string<char, std::char_traits<char>, std::allocator<char> >&, boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>&)’
/usr/local/include/boost/graph/detail/adjacency_list.hpp:1030: note: candidates are: std::pair<typename Config::edge_descriptor, bool> boost::add_edge(typename Config::vertex_descriptor, typename Config::vertex_descriptor, boost::undirected_graph_helper<C>&) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::vecS, boost::vecS, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>::config]

Answer 1

I think it works with int and char because these two types are used as vertex indexes. However, in your commented code, you add edges starting at vertex 8 to a graph containing 4 vertices...

The explicit method may give you the correct result. If you want the vertices properties be stored by the graph itself, you should declare the property and link it to the graph type. You also should access to the vertices with their index, which cannot be done directly from their property (different vertices may have the same property).

#include <string>
#include <map>
#include <boost/graph/adjacency_list.hpp>

using namespace boost;

int main (int argc, char **argv)
{
  typedef property<vertex_name_t, std::string> VertexProperty;

  typedef adjacency_list <vecS, vecS, undirectedS, VertexProperty> vector_graph_t;

  typedef std::pair <std::string, std::string> E;
  E edges[] = { E ("aaa", "bbb"), E ("bbb", "ccc"), E ("aaa", "xxx"), E ("bbb", "ccc")};

  const char* vertices[] = {"aaa", "bbb", "ccc", "xxx"};
  std::map<std::string, vector_graph_t::vertex_descriptor> indexes;

  const int nb_vertices = sizeof(vertices)/sizeof(vertices[0]);

  // creates a graph with 4 vertices
  vector_graph_t g (nb_vertices); 

  // fills the property 'vertex_name_t' of the vertices
  for(int i = 0; i < nb_vertices; i++)
  {
    boost::put(vertex_name_t(), g, i, vertices[i]); // set the property of a vertex
    indexes[vertices[i]] = boost::vertex(i, g);     // retrives the associated vertex descriptor
  }

  // adds the edges
  // indexes[edges[0].first] maps "aaa" to the associated vertex index
  for(int i = 0; i < sizeof(edges)/sizeof(edges[0]); i++)
  {
    boost::add_edge(indexes[edges[i].first], indexes[edges[i].second], g);
  }

  return 0;
}