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: George Slavov (gslavov_at_[hidden])
Date: 2009-02-09 00:52:46

From: boost-users-bounces_at_[hidden]
[mailto:boost-users-bounces_at_[hidden]] On Behalf Of Andrew Sutton
Sent: Sunday, February 08, 2009 7:06 PM
To: boost-users_at_[hidden]
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_at_[hidden]

 

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