In our project we need the ability to associate an object with a vertex, so naturally I add the object ptr as a vertex property. However, we also need to access the vertex according to the object (for example, for performing a shortest-path algorithm from the vertex representing the specific object). So, I also have a map mapping a vertex_descriptor for each object: typedef std::map<ObjectPtr, GraphTraits::vertex_descriptor> ObjVertexMap; Now, the problem is that when an object/vertex is removed from the graph, depending on the container holding vertices (vecS vs. listS), a renumbering of the vertex_descriptors may occur (or may not...) For example: (The typedefs are pretty large and not neccessarily needed to understand the code - so may want to skip them) // *** TYPEDEFS START HERE typedef std::map<ObjectPtr, GraphTraits::vertex_descriptor> ObjVertexMap; typedef Object * ObjectPtr; // Define new prperty struct vertex_obj_t { typedef boost::vertex_property_tag kind; }; // Define graph type typedef boost::adjacency_list< boost::vecS, boost::vecS, // If this is boost::listS then no renumbering on vertex delete??? boost::directedS, boost::property<vertex_tmfobj_t, ObjectPtr>,

GraphType;

// *** TYPEDEFS END HERE class GraphMgr { protected: GraphType m_graph; ObjVertexMap m_objects; public: bool addEntity(ObjectPtr a_obj) { if (m_objects.find(a_obj) != m_objects.end()) { return false; } GraphTraits::vertex_descriptor newVertex = boost::add_vertex(Graph::vertex_property_type(a_obj), m_graph); m_objects.insert(ObjVertexMap::value_type(a_obj, newVertex)); return true; } bool removeEntity(const ObjectPtr a_obj) { ObjVertexMap::iterator itr = m_objects.find(a_obj); if (itr == m_objects.end()) { return false; } boost::clear_vertex((*itr).second, m_graph); boost::remove_vertex((*itr).second, m_graph); // will this do a renumbering of the vertices? m_objects.erase(itr); // !!! If renumbering of the vertices was made I must update the ObjVertexMap! return true; } }; The problem is that if I use one type of container for vertices, the vecS, then renumbering on remove_vertex occurs and I need to update all indices in m_objects - this means I need to KNOW that vertex_descriptor is an index and how remove_vertex is implemented... Even worse: as far as I undertand if I use listS then vertex_desfcriptor is no longer an index an no renumbering occurs in remove_vertex! So, unless I want to commit to using vecS and to a specific implementation I need to somehow KNOW whether or not to perform renumbering. I coulld do this via a traits template with sepcialization for each vertices container type, but it seems to me that the library should have (and probably has) a better way of abstracting this, no? Perhaps the problem is that I'm storing vertex_descriptors in the ObjVertexMap, which may be defined as transient entities that (like iterators after an erase) might be invalidated after a remove_vertex - but then, how can I hold some persistent and efficient identifier into the graph that remains valid after remove_vertex? If anyone has any ideas, plz help. Yariv.