RE: [Boost-Users] Graphs: vertex_index vs. edge_index

From: Siegel, Matthew (matthew.siegel_at_[hidden])
Date: 2002-05-20 11:45:45

Hi Jeremy,

Thanks for the quick response.

As you may or may not recall from last week, I am having the issue with
MSVC++, where I can not put more than one property per edge or vertex when
defining the graph, that limits the size of the template expansion.  Because
of this, I have to use external property maps that I create myself.
Therefore I need an edge index map internal to the graph.

Currently my workaround is to keep an unsigned integer in my class, that
gets incremented until there's a free "slot" for the edge to go into.  This
is to allow the increment of the unsigned int to roll at maximum value.

Here's the way I think it should work.  I understand the space issues that
most people would be concerned about, however if a property_map of
edge_index_t is explicitly given in the list of edge properties when the
graph is defined, then the map should be created automatically for me, and
if an index is not provided on the add_edge() function, the index is
incremented in the same fashion.  If I'm explicitly adding the edge_index
map to my graph, then the space is of no concern to me.

Just a thought . . .thanks again,

Matt

-----Original Message-----
From: Jeremy Siek [mailto:jsiek_at_[hidden]]
Sent: Monday, May 20, 2002 12:01 PM
To: 'Boost-Users_at_[hidden]'
Subject: Re: [Boost-Users] Graphs: vertex_index vs. edge_index

Hi Matt,

On Mon, 20 May 2002, Siegel, Matthew wrote:
> Please correct me if I'm wrong.  It seems as if a vertex_index gets
> assigned to a vertex as it's added to the graph automatically.
> However, this doesn't seem to be the case for the edge_index.
>
> Is this correct??

That is mostly correct. The vertex_index gets assigned automatically
for adjacency_list with VertexList=vecS but not with VertexList=listS.
You are right about edge_index.

> I forsee the following problem.  With the graph implemented using a
> std::vector for both the vertex list and the edge list, if a vertex is
> removed from the graph the index is corrected for the
> vertex_descriptor to the new, appropriate index.  However, if an edge

Right. All vertices are re-indexed, so that after the removal the
remaining indices go from 0 to num_vertices-1

> is removed, the index for the edge_descriptor will not be corrected
> with the removal of an element in the vector.  Also, this causes
> headaches when using an external property map.  The edge index is
> linked directly to a location in my map.
>
> Any solutions for these problems??

The reason edge_index is not provided automatically is because it takes up
space (whereas the vertex_index is does not), and some users are concerned
about space issues.

Anyways, one possible solution is to somehow make it possible for you to
specify some code to be executed when an edge is added or removed from the
graph, and this code would adjust the edge indices, and perhaps the
external storage too. But before I get ahead of myself, could you describe
how you currently work around this problem, and perhaps how you'd like to
see it work?

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                          http://www.osl.iu.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------

Info: <http://www.boost.org>
Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl>
Unsubscribe: <mailto:boost-users-unsubscribe_at_[hidden]>
 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/