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

From: hicks (hicks_at_[hidden])
Date: 2002-04-26 20:17:50

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
>