Buscar Boost BGL vertex con una clave

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 utilizar

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; 

¿Un listo para usar existe mecanismo?

Answer 1

Creo que he encontrado tal mecanismo. Se llama label_graph y es parte de BGL. En lugar de utilizar adjacency_list, se puede utilizar un predefinido envoltura 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 de este tipo, 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 de 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, etiquetado_nimizar no se describe en la documentación de BGL, pero aparece en la carpeta de ejemplos.

Gracias por la respuesta, 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 asigna el nombre de los datos al 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.