[boost] graph library questions

From: jeremy siek (jsiek_at_[hidden])
Date: 2000-09-29 10:31:38

Hi Krishna,

Krishna Padmasola writes:
 > Since you mentioned that the ggcl mailing will be discontinued, I am 
 > posting my questions here. I apologize if this is not the appropriate 
 > list for such questions.

You've come to the right place :)

 > I have some questions regarding the implementation and use of
 > property 
 > accessors and vertex/edge descriptors:
 > 
 > - How is a property stored and accessed (I mean the implementation)? 
 > Does this depend on the type of selector we use for vertex/edge? How 
 > much space does it take and what is the time complexity for accessing 
 > the property?

The following applies to internal properties. External property access
implementation is up to you (except for the random access iterator
property accessor, which does constant time access).

In adjacency_list, vertex properties are always stored "on the
vertex". Anotherwords, the backbone container's value type is a vertex
struct that contains the vertex properties, and the out-edge list.
Vertex descriptors are either an index into the backbone container (if
VertexList=vecS) or a pointer to a vertex struct (if
VertexList=listS). Either way, vertex property access is constant time
and there is no extra space overhead.

In adjacency_list, edge properties are stored in two ways
depending on the Directed parameter.

1. Directed=directedS
  Edge properties are stored in the out-edge lists. An edge
  descriptor will contain a pointer to the edge property, so
  property access is constant time and there is no extra
  space overhead.

2. Directed=bidirectionalS or undirectedS
  Edge properties are stored in a seperate linked list. The
  out-edge and in-edge lists contain pointers into the linked list.
  Again, the property access is constant time, however there
  is some space overhead, 4 extra pointers stored per edge.
  This extra overhead is required to get constant time
  edge insertion and removal, and constant time property lookup.

 > - Are internal properties stored with a vertex/edge? Does the 
 > vertex/edge descriptor have a way to access a property?

Yes, they basically have a pointer to the property for constant
time lookup.

 > - Is there a way to find a vertex/edge with a certain value for a 
 > given property? e.g., give me the 'red' vertex? What is the time 
 > complexity for this operation? (I was not able to find this).

The Standard Template Library has such a function: std::find_if.
You can use this function with iterators from the graph library:

typename graph_traits<Graph>::vertex_iterator vi, vi_end;
tie(vi, vi_end) = vertices(g);
find_if(vi, vi_end, color_is_red);

(you will need to constructor a functor class for color_is_red)

The time complexity is linear in the number of vertices.

 > - If my application stores the vertex descriptors (created during 
 > add_vertex) for future use, under what conditions do they remain
 > valid 
 > in future? Does adding new vertices using add_vertex invalidate any 
 > references to the earlier vertex descriptors ? Is this dependent on 
 > the kind of VertexList selector in use (listS/vecS)?

When VertexList=vecS, add_vertex() will invalidate earlier vertex
descriptors. When VertexList=listS, vertex descriptors are never
invalidated.

 > - Since any non trivial application will have properties associated 
 > with the vertices/edges, in your opinion, what is the most efficient 
 > way to go about doing this? In my application don't know the number
 > of 
 > vertices in advance, so currently I am using add_vertex, and adding 
 > the property to the resulting vertex descriptor.

That sounds like the right approach.

 > I tried to find some of the answers by going through the source code, 
 > but as I am just getting familiar with STL, it is a daunting task at 
 > the moment :-)

Some of these answers are in the new HTML documentation. I'll also
be filling in the docs more (especially with answers that I give
to email questions).

http://www.boost.org/libs/graph/docs/adjacency_list.html
and
http://www.boost.org/libs/graph/docs/using_adjacency_list.html

Cheers,

Jeremy