Perform connected_components avec adjacency_list Boost où vertexList =

Question

I LISTES DE utilisent Boost Graph Library dans un projet et il est déclaré que:

typedef adjacency_list <listS, listS, undirectedS, TrackInformation, LinkInformation> TracksConnectionGraph; 

Les choses vont bien jusqu'à ce que je dois appeler connected_components sur mon graphique.

typedef std::map<TracksConnectionGraph::vertex_descriptor, TracksConnectionGraph::vertices_size_type> component_type; 
component_type component; 
boost::associative_property_map<component_type> component_map(component); 

int num_components = connected_components(tracks_connection_graph_, component_map); 

Le problème semble être que si les vertexList = Les lists, je n'ai pas vertex_index comme propriété de mon sommet. Cela rend connected_components me donnent des erreurs comme thèses:

/usr/local/include/boost-1_39/boost/property_map.hpp: En fonction membre « R boost :: iterator_property_map :: operator [] (typename boost :: property_traits :: key_type) const [avec RandomAccessIterator = __gnu_cxx :: __ normal_iterator , indexmap = boost :: adj_list_vertex_property_map, boost :: détail :: error_property_not_found, const boost :: détail :: error_property_not_found &, boost :: vertex_index_t>, T = boost :: default_color_type, R = boost :: default_color_type &] ':

La question est donc: comment puis-je ajouter vertex_index comme une propriété de mes sommets? Si je l'ajoute, cela signifie-t-il que chaque fois que j'appelle add_vertex, remove_vertex et autres, je dois mettre à jour cette information pour chaque sommet?

Answer 1

Vous pouvez ajouter une propriété vertex_index à la définition de votre type de graphique (dans l'argument modèle de propriété sommet à adjacency_list, changer TrackInformation-property<vertex_index_t, size_t, TrackInformation>). Avant d'appeler l'algorithme, vous devez remplir la carte des propriétés en utilisant une boucle telle que:

size_t index = 0; 
BGL_FORALL_VERTICES(v, tracks_connection_graph_, TracksConnectionGraph) { 
    put(vertex_index, g, v, index++); 
}