Поиск вершины Boost BGL по ключу - PullRequest
Новая
       14

Поиск вершины Boost BGL по ключу

32 голосов
/ 11 февраля 2010

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

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;

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

Ответы [ 2 ]

32 голосов
/ 12 февраля 2010

Я думаю, что нашел такой механизм. Он называется labeleled_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 ) ) ;

По какой-то причине labeleled_graph не описан в документации BGL, но отображается в папке с примерами.

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

1 голос
/ 11 февраля 2010

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

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

...