Boost logo

Boost Users :

From: Renaud Detry (renaudjdetry_at_[hidden])
Date: 2008-06-17 04:06:11


Hi,

I have a question related to Boost.Graph bundle properties when there
are two distinct vertex/edge types.

I would like to implement a network structure using Boost.Graph. In
this structure, edges and vertices can be of two types. A vertex can
be either of type VA or of type VB, and and edge can be of type EA or
EB. The data element to which a vertex/edge is associated differs
depending on the vertex/edge type. I will be using the adjacency_list
and bundle properties

adjacency_list<OutEdgeList, VertexList, Directed,
                VertexProperties, EdgeProperties,
                GraphProperties, EdgeList>

I'm trying to figure what to use for VertexProperties and
EdgesProperties, focusing on maintainability and flexibility. Also, I
would like the whole structure to be serializable.

This seems like a rather generic problem, yet I wasn't able to find an
easy and elegant solution.

Here are some ideas for VertexProperties (the same scheme can directly
be used for EdgeProperties).

1a.- VertexProperties is set to boost::shared_ptr<VirtualVertexProp>,
      where VirtualVertexProp is a polymorphic class from which classes
      specific to types VA or VB can inherit. This approach has some
      issues though: for example, graph copies have to explicitly
      handle property clonage.

1b.- Instead of boost::shared_ptr,
      boost::ptr_array<VirtualVertexProp,1> could be used. The property
      instances are cloned when the ptr_array is copied.

2.- VertexProperties is a simple class that contains a type enum (VA
     or VB), and an index that identifies a data element in an external
     container. There would be two external containers, one containing
     VA data, the other for VB data.

The advantage of (1b) is automatic memory management -- when a vertex
is deleted, its properties also die. With (2), properties have to be
manually deleted when an vertex is removed. On the other hand, (2) is
a bit more simple to serialize, since there's no dynamic allocation
(i.e. not on the user side) and no polymorphism (no
BOOST_CLASS_EXPORT_GUID...).

My questions are:

- In (1b), will boost::ptr_array<VirtualVertexProp,1> provide the
   expected behavior, i.e. that of a clone_ptr?

- Am I missing something? Is there a more natural way to solve
   this problem?

Thanks a lot,
Renaud.


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net