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

On Mon, 9 Feb 2009, Andrew Sutton wrote:

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?

I think your best bet may be to modify the CSR graph types to use something other than size_t. Copy it, rename the type, and change it to suit your needs. That's close enough to creating your own graph type :)

I'm not entirely convinced that the benefits will outweigh the cost here. Maybe you'll save a couple MB, but you might do so at the expense of performance.

If your graph is purely a grid, you can also just create an implicit graph that takes no space (at least for the graph structure). In this case, your vertex_descriptor would just be the grid coordinates, and the edge_descriptor would be a source vertex and an output index. You could save a large amount of memory for large graphs that way, since the structure of the graph would not be stored at all, and you could trivially convert between vertex_descriptors and positions in the grid. Your properties would still take memory if you have some, of course. There is an example of how to create a graph like you want in chapter 9 of the BGL book (your grid is very similar to the knight's tour problem in that chapter). -- Jeremiah Willcock