c++ - Encuentre el vértice BGL de Boost con una tecla

graph boost-graph

Question

Estoy buscando una forma de acceder a las propiedades de los vértices utilizando una clave en lugar de la referencia de los vértices. Por ejemplo, si tengo

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;

En lugar de usar

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

me gustaría tener

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

¿Existe un mecanismo listo para usar?

Answer 1

Creo que he encontrado tal mecanismo. Se llama label_graph y es parte de BGL. En lugar de usar adjacency_list , se puede usar un contenedor predefinido labeled_graph :

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

Después de definir un gráfico como este, es posible acceder a los vértices de la siguiente manera:

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 );

El efecto secundario de esto es que uno necesita usar la función miembro graph () para hacer que algunos algoritmos funcionen:

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

Por algún motivo, labeled_graph no se describe en la documentación de BGL, pero aparece en la carpeta de ejemplos.

Gracias por responder, Serge

Answer 2

No existe un mecanismo listo para usar, ya que el concepto adjacency_list no puede saber que desea acceder a su propiedad de vértice por un campo en una estructura.

Preferiría la forma de tener un mapa adicional que mapee el nombre de los datos en el vértice correspondiente. Además, puede encapsular su algoritmo en una clase o función, de modo que al agregar un nuevo vértice, el mapa se llene automáticamente.