
Boost Users : 
From: hicks (hicks_at_[hidden])
Date: 20020426 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 subgraphs (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 subgraph A.
(Assuming no particular reason to oder the subgraphs, or assuming
they are already preordered).
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 "supergraph" 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, LieQuan 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 welldefined 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 shortlived 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
>
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net