Re: [Boost-users] a question about the vertices in boost graph libary (BGL)

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2005-04-05 09:42:25

Hi Vivid,

On Apr 5, 2005, at 9:09 AM, Vivid Yang wrote:
> Hi,
>
> I saw all the BGL examples begin with enumeration:
>     // Make convenient labels for the vertices
>     enum { Amherst, Boston, City, Denver, Egypt, Niagara };
> So it is convenient to access properties, for example:
>     distance(Boston) = 50; //distance is a property of vertices
>
> The problem is that I have to build my graph incrementally and might 
> have to
> remove some vertices later. So enumeration does not work for me.
> When I want to set distance(Boston) = 50, I have to find the 
> descriptor for
> "Boston" first, (It takes O(n) to traverse all the vertices). It is too
> expensive for a large graph.
>
> Is there anyway I can skip this step?  I am thinking add a hash table, 
> which
> maps each city to a descriptor. I have to update the hash table 
> whenever I
> remove vertices. It is inconvenient neither.
>
> Do I think it in the right way? Any suggestions?

If you are using adjacency_list, make sure to use VertexList=listS,
otherwise when you remove a vertex all the vertex descriptors in your
hash table will be invalidated.

-Jeremy

_______________________________________________
Jeremy Siek <jsiek_at_[hidden]>
http://www.osl.iu.edu/~jsiek
Ph.D. Student, Indiana University Bloomington
C++ Booster (http://www.boost.org)
_______________________________________________