[boost] Re: Hupergraphs and the BGL

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-04-28 21:50:35

--On Sunday, April 28, 2002 12:01 PM -0500 boost-request_at_[hidden] 
wrote:

>> Your description of what you want is what I would consider
>> hierarchical graph structure: graphs can be subgraphs of other
>> graphs.  What are the key problems with using BGL's 'subgraph'
>> support?
>
> Well, for one thing the subgraphs are already created.  Some time
> later I need to combine them into the "supergraph."  From the
> BGL page, it looks as though the normal mode of operation is to
> create the root graph first and then create subgraphs and add
> vertices and edges to them.  Doing this is no less expensive
> than creating a new graph out of the original separate graphs.
> I don't see any interface for taking two graphs and making
> a subgraph tree out of them.

Also, the subgraph class is not a very space-efficient design. The
graph structure of each subgraph is stored explicitly. This is because
the design goal for subgraph was time-efficiency.

>
>> You may have already done this, but I would suggest
>> examining what you could currently do with subgraphs and edge_lists
>> and such operations such as unions and intersections, and decide if
>> there is some limited addition to these capabilities that would
>> support what you need efficiently.  I can guess it would have to
>> do with on-the-fly, efficient union/intersection of
>> graphs/edge_lists/vertices.
>
> Right.
>
>                           -Dave
>