Re: [Boost-users] question about subgraphs

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-10-19 16:11:58

On Oct 19, 2005, at 8:49 AM, Jeffrey Holle wrote:

> I am using boost 1.33.0.
>
> I want to use a subgraph to represent a spanning tree of a graph.
>
> This application requires adding and deleteing edges to just the  
> tree and not
> the underlining graph though.
>
> Note that this wouldn't violate the requirements of a subgraph, a  
> spanning tree
> contains all the vertices, and a subset of the edges of the  
> underlining graph.

That depends on which definition you use for "subgraph." The subgraph  
adaptor in the BGL is for an induced subgraph, which means that you  
only specify the vertices in the subgraph and then all of the edges  
in the underlying graph that connect vertices in the subgraph are  
automatically included. Unfortunately, an induced subgraph is not  
what you want.

> Is it possible to do this, maybe through inheritance?

Aggregation is probably the easiest way to handle things. Even though  
it doesn't do exactly what you want, you should check out the  
subgraph adaptor in the BGL. It wraps up a reference to another graph  
and gives a view of a subgraph of the graph. You could do the same,  
but keep your own vertex/edge lists in your adaptor so that you get  
the kind of subgraph that you need to represent a spanning tree.

     Doug