[Boost-users] Advice on how to make a custom graph visitor

From: Stephen Torri (storri_at_[hidden])
Date: 2007-03-24 18:15:10

I have a graph that I am having difficulty making a graph visitor. I
thought a breadth first visitor would do but there is a issue of order.
I cannot guarantee what the order of visits to all the vertices will be
on a graph. My graph that I am testing against is a directed graph of
Component objects. Each Component requires input from the parent
Component objects in the graph. For example,

              (Graph)
                  C1
                 |
             ------------------
             |     |     |    |
             C20   C30   C40  |
             |     |     |    |
            -------------------
                   |
                  C5
        
        
           (Table of inputs)
             C1  C20  C30  C40  C5
        C1
        C20  x
        C30  x
        C40  x
        C5   x     x    x    x   x
        
I thought a breadth first search visitor would work. The behavior I was
expecting was visits in the following order: C1, C20, C30, C40, Cc5.
What I found was that I had C1, C40 and then C5. My program will abort
at that point that c5 is visited since it is missing inputs from C20 and
C30. When I take away calls to my code in the visitor and include just a
simple "Hey I am at Component X" message I get the order I suspect.

My graph is defined as:

        typedef property< vertex_index_t,
                          uint32_t,
                          property< vertex_name_t,
                                    boost::shared_ptr<Component> > >
        VertexProperty_t;

        typedef adjacency_list<setS, // OutEdgeList
                               setS, // VertexList
                               directedS, // Directed
                               VertexProperty_t> // VertexProperties
        Graph_t;

The visitor is defined as:

    class Graph_Visitor : public boost::default_bfs_visitor
    {
    public:

        // Constructor
        Graph_Visitor
        ( infrastructure::Component_Graph const& graph_ref,
          infrastructure::Graph_Base::Data_Map_t* dmap );

        // Visitor functions
        template <class Vertex, class Graph> void
        discover_vertex(Vertex v, Graph const& g)
        {
            boost::shared_ptr<infrastructure::Component> src_obj_ptr =
                m_graph_ref.get_Component(v);

            std::cout << "Visiting node: " << src_obj_ptr->get_ID() <<
std::endl;

          .... verify inputs ....
            .... if all inputs present then do work ....
         }
     };

Is there a problem with my choice of design for the graph or how I am
using the breadth first visitor?

Stephen