From: boost-users-bounces@lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Andrew Sutton
Sent: Sunday, February 08, 2009 7:06 PM
To: boost-users@lists.boost.org
Subject: Re: [Boost-users] [Graph] is it possible to define my ownedge_descriptor

I have a graph which corresponds to an n by m grid of vertices. Edges in this graph are only allowed to point from one vertex to an adjacent vertex. In this situation, it would be wonderful if I could define an edge, so that its target is not a vertex_descriptor but some other construct which would allow me to store the target in just one byte or less instead of the full unsigned int which I use to describe my vertices. That is, the edge could go from vertex 102 to a descriptor in the range [0,8] which would give you enough information to compute which vertex you're talking about.

The graph I'm working with is rather large. It could have millions of vertices and saving this kind of space would be fantastic.

If you're defining your own graph type, you can define your descriptors however you want. The CSR-graph does something similar, IIRC. That's probably not a very helpful comment. If you can post some code, I might be able to give a better answer.

Andrew Sutton
andrew.n.sutton@gmail.com

Actually, I wasn’t defining my own graph type. I’ve been using the CSR template class which was definitely an improvement over the adjacency list in terms of memory usage. I definitely have no use for adding and removing vertices on the fly. However, I am willing to look into defining my own graph. Do you think it’s not beyond someone who is only a mediocre C++ programmer? I’ve been reading the doc site, but I haven’t found any information about how to create my own graph. Could you please tell me where to look?

George Slavov