Найти вершину Boost BGL по ключу

Я ищу способ доступа к свойствам вершины с помощью ключа вместо самой ссылки на вершину. Например, если у меня есть

class Data
{
  public:
    std::string  name;
    unsigned int value; 
}; 
typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::directedS, Data > Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;

вместо использования

Vertex vertex1 = boost::add_vertex( g );
g[vertex1].name  = "Alpha";
g[vertex1].value = 10;

Я бы хотел

g["Alpha"].name  = "Alpha";
g["Alpha"].value = 10;

Существует ли готовый к использованию механизм?


c++ boost graph boost-graph
person Serge C    schedule 11.02.2010    source источник

Ответы (2)


arrow_upward
34
arrow_downward

Кажется, я нашел такой механизм. Он называется labeled_graph и является частью BGL. Вместо использования adjacency_list можно использовать предопределенную оболочку labeled_graph:

typedef boost::labeled_graph<
    boost::adjacency_list< boost::vecS, boost::vecS, boost::directedS, Data >,
    std::string
> Graph;

После определения такого графа можно получить доступ к вершинам следующим образом:

Graph g;

boost::add_vertex( "Alpha", g );
g["Alpha"].name  = "Alpha";
g["Alpha"].value = 10;

boost::add_vertex( "Beta", g );
g["Beta"].name  = "Beta";
g["Beta"].value = 20;

boost::add_edge_by_label( "Alpha", "Beta", g );

Побочным эффектом этого является то, что для работы некоторых алгоритмов необходимо использовать функцию-член graph():

std::vector< Graph::vertex_descriptor > container;
boost::topological_sort( g.graph(), std::back_inserter( container ) ) ;

По какой-то причине labeled_graph не описан в документации BGL, но он есть в папке примера.

Спасибо за ответ, Серж

person Serge C    schedule 11.02.2010
comment
Глядя на историю адаптера labeled_graph.hpp, похоже, что файл относительно новый. (Начал появляться в версии библиотеки Boost 1.40). Наверное, поэтому его пока нет в документации, - person Serge C; 13.02.2010

arrow_upward
1
arrow_downward

Готового к использованию механизма не существует, поскольку концепция adjacency_list не может знать, что вы хотите получить доступ к свойству вершины через поле в структуре.

Я бы предпочел иметь дополнительную карту, которая сопоставляет имя данных с соответствующей вершиной. Далее вы можете инкапсулировать свой алгоритм в класс или функцию, чтобы при добавлении новой вершины карта заполнялась автоматически.

person Mathias Soeken    schedule 11.02.2010