Symptom: Breadth first graph visitor misses visiting vertexes when debugging statements removed during graph construction. OS: Fedora Core Linux BOOST: 1.33.1-11.fc6 GCC: 4.1.1-51.fc6 Problem: I am suspecting that there is a timing issue or something else that I am missing that causes the boost breath first visitor to miss two nodes in a graph. The reason why U suspect something is that when I add three debugging statements to determine what is happening with graph construction that the visitor is able to visit all vertexes. The following commented out lines are the ones that I add. void Component_Graph::add_Component ( Component::ptr_t obj_ptr ) { bool no_duplicate; IdVertexMap_t::iterator pos; Vertex_t node; /* std::cout << boost::format("Component_Graph::add_Component for id %d") % obj_ptr->get_ID() << std::endl; */ if ( obj_ptr.get() == 0 ) { std::cerr << boost::format("Exception throw in %s at line %d") % __FILE__ % __LINE__ << std::endl; throw errors::Component_Exception ( errors::Component_Exception::NULL_POINTER ); } boost::tie (pos, no_duplicate) = m_index.insert (std::make_pair(obj_ptr->get_ID(), node)); if ( no_duplicate ) { /* std::cout << boost::format("Component_Graph::add_Component - no duplicate with id = %d") % obj_ptr->get_ID() << std::endl; */ // Insertion was successful // Make a new vertex and return handle to 'node' node = add_vertex(m_graph); // Get list of Components boost::property_map<Graph_Base::Graph_t, vertex_name_t>::type clist = get(vertex_name, m_graph); // Assign component to vertex position clist[node] = obj_ptr; // Add vertex handle to map position pos->second = node; // Get list of indexes boost::property_map<Graph_Base::Graph_t, vertex_index_t>::type ilist = get(vertex_index, m_graph); ilist[node] = obj_ptr->get_ID(); // Grab list of parent ids std::list<boost::uint32_t> source_list = obj_ptr->get_Source_List (); for ( std::list<boost::uint32_t>::const_iterator cpos = source_list.begin(); cpos != source_list.end(); ++cpos ) { /* std::cout << boost::format("Component_Graph::add_Component parent(id=%d) for child(id=%d)") % (*cpos) % obj_ptr->get_ID() << std::endl; */ // Call add_child. This adds a edge from the parent Component to the child Component this->add_Child ( (*cpos), obj_ptr ); } } else { std::cerr << "ERROR: Duplicate source found. Skipping Component" << std::endl; return; } } The graph is a simple adjacency list that I keep in a class called Component_Graph. When it comes time to visit the boost graph is returned from the Component_Graph. Here is my definition: 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; As you can see a standard adjacency list graph with a component as the property. The graph visitor going to each vertex is inherited from the default breadth first search visitor. Each Component performs its task via 'run()' and the results are collected for storage in the Data_Map_t for use by children Component. Order of operation is important. All parents to a Component must be executed before a child works. This was the reason why I choose a breadth first search visitor. class Graph_Visitor : public boost::default_bfs_visitor { public: // Constructor explicit 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; // This will execute the Component to perform its task src_obj_ptr->run ( m_data_map ); typename Graph::degree_size_type num_children = out_degree (v, g); // Print out the id of the vertex being visited std::cout << boost::format(" Node(%d) - children: %d") % src_obj_ptr->get_ID() % num_children << std::endl; // Save results for children Components infrastructure::Graph_Base::Result_Data_t result_data = std::make_pair ( src_obj_ptr->results(), num_children ); m_data_map->insert ( std::make_pair ( src_obj_ptr->get_ID(), result_data ) ); typename Graph::out_edge_iterator pos; typename Graph::out_edge_iterator end; typename Graph::vertex_descriptor node; boost::shared_ptr<infrastructure::Component> target_obj_ptr; // Notify children Components that the parent Component data is available for ( boost::tie(pos,end) = out_edges(v, g); pos != end; ++pos ) { node = target (*pos, g); target_obj_ptr = m_graph_ref.get_Component ( node ); target_obj_ptr->received_Input_Source_Data ( src_obj_ptr->get_ID() ); } } private: infrastructure::Component_Graph const& m_graph_ref; infrastructure::Graph_Base::Data_Map_t* m_data_map; }; So a resulting graph, which I output via a separate visitor, shows one arrange of components as it should be and how the vertexes are being visited at present ----------------------------- EXPECTED ----------------------------- digraph analysis { 1 [label="File_Type_Detector(1)"]; // Visitor starts here 1 -> 20; // All children components are initialized with Component #1 data 1 -> 30; 1 -> 40; 1 -> 5; 20 [label="Arch_Type_Detector(20)"]; // Component #20 executes 20 -> 5; // Component #5 initialized with Component #20 data 30 [label="Data_Section_Detector(30)"]; // Component #30 executes 30 -> 5; // Component #5 initialized with Component #30 data 40 [label="Code_Section_Detector(40)"]; // Component #40 executes 40 -> 5; // Component #5 initialized with Component #40 data 5 [label="Meta_Writer(5)"]; // Component #5 executes } ----------------------------- PRESENT RESULTS ----------------------------- digraph analysis { 1 [label="File_Type_Detector(1)"]; // Visitor starts here 1 -> 20; // All children components are initialized with Component #1 data 1 -> 30; 1 -> 40; 1 -> 5; 20 [label="Arch_Type_Detector(20)"]; // Component #20 executes 20 -> 5; // Component #5 initialized with Component #20 data 5 [label="Meta_Writer(5)"]; // Component #5 fails to execute. Missing data from Component #30 and #40 } STEPS TAKEN: 1. I went through the code and reviewed its design a. Redesign Component so its a pure virtual class b. Added new classes to add the old functionality via composition 2. Added the debug print statements to see what was happening with the visitors. NOTE: This is where I noticed that it work with them but fails without them. 3. Checked to see if making the copy constructors for the objects that compose the Component functionality as 'explicit' was the problem. They were not. Are there any reasons which would make a breadth first search visitor skip visiting a vertex? Stephen