BGL: "Supergraphs?"
Hi, I've been learning the BGL and porting some existing code over to it. First off, Kudos to Jeremy, Lie-Quan and all the BGL developers. This library is great! I find the filtered_graph potentially very useful for my application except for one case. In some (not rare) instances I need to be able to create a filtered_graph that spans two graphs. In other words, I have two separate graphs. Most of the time the information I need is entirely contained in one graph so a filtered_graph works perfectly. However, sometimes I need to create a filtered_graph from several separate graphs and link them together in a well-defined manner (i.e. I easily know where the edges should go). I need a "supergraph" that is the combination of the two filtered graphs. Right now the application handles this problem by creating a new graph from the existing graphs. But this takes time and memory. I'd like to get rid of this overhead if possible, especially since these are often short-lived graphs. The filtered_graph objects would not be induced subgraphs so a subgraph object wouldn't work (subgraph also doesn't support something that spans multiple graphs anyway). What I need is the opposite of subgraph -- a unified interface to multiple filtered_graphs. This seems very hard to do because each filtered_graph will have its own vertex and edge index mappings. An extra level of indirection would solve the problem but I'm not sure the overhead would be less than simply creating a new graph. Thoughts? Opinions? Thanks again for a great library! -Dave -- "Some little people have music in them, but Fats, he was all music, and you know how big he was." -- James P. Johnson
In reply to David A Green: A common implemtation of an edge list is an ordered list of edges. Ordering time is O(N long N), and lookup time is O(logN). If there is a priori knowledge about the sub-graphs (connected components), even before building the graph, then it would seem that overhead in terms of operation order count could be reduced by incorporating this information directly into the representation. Say that there are A subgraphs with N/A nodes each. Say the implementation has O(1) lookup time to get to sub-graph A. (Assuming no particular reason to oder the subgraphs, or assuming they are already pre-ordered). Then ordering time for edges becomes O(N * (log N - log A)) and lookup time becomes O(log N - log A). For your case, this seems to offer a potential savings in runtime overhead, not to mention avoiding the brute force rebuiling stage. Furthermore, if such a representation were available, it might be optimal to convert an existing graph to "super-graph" representation after having discovered the connected components. Doing so could reduce the edge lookup time as discussed above. Craig Hicks David A. Greene wrote:
Hi,
I've been learning the BGL and porting some existing code over to it. First off, Kudos to Jeremy, Lie-Quan and all the BGL developers. This library is great!
I find the filtered_graph potentially very useful for my application except for one case. In some (not rare) instances I need to be able to create a filtered_graph that spans two graphs. In other words, I have two separate graphs. Most of the time the information I need is entirely contained in one graph so a filtered_graph works perfectly. However, sometimes I need to create a filtered_graph from several separate graphs and link them together in a well-defined manner (i.e. I easily know where the edges should go). I need a "supergraph" that is the combination of the two filtered graphs.
Right now the application handles this problem by creating a new graph from the existing graphs. But this takes time and memory. I'd like to get rid of this overhead if possible, especially since these are often short-lived graphs.
The filtered_graph objects would not be induced subgraphs so a subgraph object wouldn't work (subgraph also doesn't support something that spans multiple graphs anyway). What I need is the opposite of subgraph -- a unified interface to multiple filtered_graphs.
This seems very hard to do because each filtered_graph will have its own vertex and edge index mappings. An extra level of indirection would solve the problem but I'm not sure the overhead would be less than simply creating a new graph.
Thoughts? Opinions?
Thanks again for a great library!
-Dave
Hi David, On Fri, 26 Apr 2002, David A. Greene wrote: greene> I've been learning the BGL and porting some existing code over greene> to it. First off, Kudos to Jeremy, Lie-Quan and all the BGL greene> developers. This library is great! You're welcome :) 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. In other words, I have two greene> separate graphs. Most of the time the information I need greene> is entirely contained in one graph so a filtered_graph greene> works perfectly. However, sometimes I need to create a greene> filtered_graph from several separate graphs and link them greene> together in a well-defined manner (i.e. I easily know where greene> the edges should go). I need a "supergraph" that is the greene> combination of the two filtered 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 :) greene> Right now the application handles this problem by creating greene> a new graph from the existing graphs. But this takes time greene> and memory. I'd like to get rid of this overhead if possible, greene> especially since these are often short-lived graphs. greene> greene> The filtered_graph objects would not be induced subgraphs greene> so a subgraph object wouldn't work (subgraph also doesn't greene> support something that spans multiple graphs anyway). What greene> I need is the opposite of subgraph -- a unified interface greene> to multiple filtered_graphs. greene> greene> This seems very hard to do because each filtered_graph will greene> have its own vertex and edge index mappings. An extra level greene> of indirection would solve the problem but I'm not sure the greene> overhead would be less than simply creating a new graph. greene> greene> Thoughts? Opinions? greene> greene> Thanks again for a great library! greene> greene> -Dave ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
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 -- "Some little people have music in them, but Fats, he was all music, and you know how big he was." -- James P. Johnson
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]
Hi Craig,
--On Sunday, April 28, 2002 11:55 AM +0900 hicks
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?
http://www.boost.org/libs/graph/doc/subgraph.html
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?
Sounds like an interesting approach. The challenge will be implementing an efficient out_edge_iterator for this kind of graph.
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.
Wow, thanks for the compliments! Cheers, Jeremy
hicks wrote:
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?
http://www.boost.org/libs/graph/doc/subgraph.html -Dave -- "Some little people have music in them, but Fats, he was all music, and you know how big he was." -- James P. Johnson
participants (3)
-
David A. Greene -
hicks -
Jeremy Siek