Re: [Boost-Users] BGL: "Supergraphs?"

From: hicks (hicks_at_[hidden])
Date: 2002-04-27 21:55:09

To Mr. Greene
1. I could not find any reference to the subgraphs in the BGL 
documentation accompanying the boost library.
Can you explain what you mean or where you found it?

To Mr. Siek
2.  Concerning Jeremey Siek's comments about virtually combining 
graph's, I included an excerpt from the BGL documentation
at the bottom of this mail, which states that in order to "wrap" an 
existing graph (or suitable class) you need to overload
all the free functions required by the interface which you will be using 
for that graph, an approach called "external interface".

I suppose in a virtual combination of graphs, the graph object would be 
a container of sub-graphs, and
that indices would be a pair, subgraph number + index. (for either 
vertices or edges).
Its easy to imagine how the free functions could be overloaded easily 
using such an indexing system.
So why should memory be consumed?

I find the BGL one of the most profoundly inspirational pieces of 
software I have ever seen.
The flexibility offered by the use of property maps and the external 
interface approach
are in and of themselves something to be admired.  
Thanks to the creators for their efforts.

Craig Hicks

David A. Greene wrote:

>Jeremy Siek wrote:
>
>>greene> I find the filtered_graph potentially very useful for my
>>greene> application except for one case.  In some (not rare)
>>greene> instances I need to be able to create a filtered_graph
>>greene> that spans two graphs.  
>>
>>It seems that the right approach would be to first have something that
>>"virtually" combines the two graphs, and then simply apply filtered_graph
>>to the result. However, off the top of my head I don't know of a good way
>>to "virtually" combine two graphs without lots of memory overhead. I'm
>>open to ideas :)
>>
>
>Well, no one said this would be easy.  :)  Can you comment on the
>applicability of the subgraph class to this problem?  Originally I
>skimmed the document and I thought that subgraph required a
>consistent indexing across graphs, therefore eliminating the
>possibility of using it to combine independent graphs.  However,
>going over it again I read about "local" and "global" indices.
>I don't think there's an interface for combining two existing graphs
>into a subgraph tree (BTW the graphs in my case are truly independent
>-- they do not share any nodes or vertices), but I wonder if the
>subgraph _structure_ might be appropriate.  I need to look into how
>that all works a little more.
>
>                              -Dave
>

          

  How to Convert Existing Graphs to BGL

Though the main goal of BGL is to aid the development of new 
applications and graph algorithms, there are quit a few existing codes 
that could benefit from using BGL algorithms. One way to use the BGL 
algorithms with existing graph data structures is to copy data from the 
older graph format into a BGL graph which could then be used in the BGL 
algorithms. The problem with this approach is that it can be expensive 
to make this copy. Another approach is to wrap the existing graph data 
structure with a BGL interface.

The Adaptor pattern [ 12 <cid:part1.01050909.07060201_at_[hidden]> ] 
typically requires that the adaptee object be contained inside a new 
class that provides the desired interface. This containment is not 
required when wrapping a graph for BGL because the BGL graph interface 
consists solely of free (global) functions. Instead of creating a new 
graph class, you need to overload all the free functions required by the 
interface. We call this free function wrapper approach external adaptation.

[Non-text portions of this message have been removed]