Граф Boost со строковыми вершинами

Я знаю, как создать в Boost Graph граф с целочисленными или символьными вершинами (см. прокомментированный код ниже). Вопрос в том, как переписать этот код для работы со строковыми вершинами?

#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;
}

Программа выше компилируется с ошибкой:

/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]

c++ boost graph boost-graph
person cpp    schedule 16.09.2013    source источник

Ответы (1)


arrow_upward
5
arrow_downward

Я думаю, что это работает с int и char, потому что эти два типа используются в качестве индексов вершин. Однако в вашем закомментированном коде вы добавляете ребра, начинающиеся с вершины 8, в граф, содержащий 4 вершины...

Явный метод может дать вам правильный результат. Если вы хотите, чтобы свойства вершин сохранялись самим графом, вы должны объявить это свойство и связать его с типом графа. Вы также должны получить доступ к вершинам с их индексом, что невозможно сделать напрямую из их свойства (разные вершины могут иметь одно и то же свойство).

#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;
}
person Raffi    schedule 16.09.2013