Boost logo

Boost Users :

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)
_______________________________________________


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net