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