RE: BGL question

From: Lie-Quan Lee (llee1_at_[hidden])
Date: 2001-09-27 11:22:48

> -----Original Message-----
> From: Craig Hicks [mailto:hicks_at_[hidden]]
> Sent: Thursday, September 27, 2001 8:08 AM
> To: llee1_at_[hidden]
> Subject: BGL question
>
>
> Hi
>
> I have a question about the BGL.
>
> Does the visitor pattern concept always incurr an iteration through all
> vertices first to initialize them?
>
> I have a large graph with many vertices, divided into many disjoint
> subgraphs.  Most of which
> are single cycles.
> I have already called connected_components() to group the subgraphs.
> Now I want to iterate each cycle once, and I had thought of using DFS, but
> if each seperate call to DFS,
> one for each subgraph, invokes an iteration through all vertices first to
> initialize them,
> that's a lot of overhead.
>
> What do you advise?

BGL has a function template, depth_first_visit, which is what you want. It
assumes that initialization is done.
Basically, you can initialize properties once for all vertices. Then you
call depth_first_visit for each components.

The initialization code is like:

    template <class VertexListGraph, class DFSVisitor, class ColorMap>
    void
    dfs_init(const VertexListGraph& g, DFSVisitor vis, ColorMap color)
    {
      function_requires<DFSVisitorConcept<DFSVisitor, VertexListGraph> >();
      typedef typename property_traits<ColorMap>::value_type ColorValue;
      typedef color_traits<ColorValue> Color;

      typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;
      for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
        put(color, *ui, Color::white());
        vis.initialize_vertex(*ui, g);
      }
   }

BTW, boost_at_[hidden] is the best place to ask BGL questions.

--
Lie-Quan Lee
Research Associate at IU Bloomington
>
> Yours
>
> Craig Hicks
> Engineer, KGK Tokyo, Japan
>
>
>