Re: [Boost-users] Creating custom depth first search visitor for Boost graph

From: Stephen Torri (storri_at_[hidden])
Date: 2005-03-14 19:45:31

On Mon, 2005-03-14 at 16:09 -0500, Douglas Gregor wrote:
> Alternatively, you can use a topological ordering of the vertices 
> computed on the reversed graph. Check out the file dependency example 
> in the BGL docs:
> 
> 	http://www.boost.org/libs/graph/doc/file_dependency_example.html
> 

Thanks for the suggestion. It greatly simplified my algorithm. :)

Here is the extent of the algorithm as implemented:

  Filter_Search::Filter_Search
  (call_traits<infrastructure::Component_Graph::ptr>::param_type g)
    :
      m_graph (g)
  {
    // Create execution order and store in 'm_exec_order'
    boost::topological_sort (g->get_Graph(),
                             std::front_inserter (m_exec_order));
  }

  // Execute node order using simple default dfs visitor.
  void Filter_Search::operator()
    (call_traits<Kurt_Filter_Visitor>::reference vis)
  {
    for (ExecOrder::iterator node = m_exec_order.begin();
         node != m_exec_order.end();
         ++node)
      {
        infrastructure::Component::ptr comp_obj =
          m_graph->get_Component (*node);

        vis.discover_vertex (*node, m_graph->get_Graph());
      }
  }

Isn't elegance nice! :)

Stephen