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@netscape.com ] 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]