|
|
Boost Users : |
From: Stephen Torri (storri_at_[hidden])
Date: 2007-04-10 13:56:21
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
Boost-users 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