[Boost-users] [boost graph] adjusting vertex_descriptors when performing a remove_vertex

From: Yariv Tal (yariv_tal2003_at_[hidden])
Date: 2005-03-15 06:44:22

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.