Re: [Boost-users] [Graph] is it possible to define my ownedge_descriptor

Subject: Re: [Boost-users] [Graph] is it possible to define my ownedge_descriptor
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-02-09 10:43:48

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