Hi
I m able to calculate the diameter of a graph using BFS visitor. I got all
the distances and then i m finding out the maximum using the following to
get the diameter ..
template <class Distance>class calc_distance_visitor : public
boost::bfs_visitor<>
{
public:
calc_distance_visitor(Distance d,std::size_t& girth) :
distance(d),Girth(girth)
{
}
template <class Graph>
void tree_edge(typename boost::graph_traits<Graph>::edge_descriptor
e,Graph& g)
{
Vertex u, v;
u = boost::source(e, g);
v = boost::target(e, g);
distance[v] = distance[u] + 1;
}
};
and then
typedef std::vector IntVector;
/// Create N x N matrix for storing the shortest distances
//// between each vertex. Initialize all distances to zero.
std::vector<IntVector> d_matrix(num_vertices(g),IntVector(num_vertices(g),
0));
size_type i;
std::size_t girth = std::numeric_limitsstd::size_t::max();
for (i = 0; i < num_vertices(g); ++i)
{
calc_distance_visitor vis(&d_matrix[i][0],girth);
Vertex src = vertices(g).first[i];
breadth_first_search(g, src, boost::visitor(vis));
}
for (i = 0; i < num_vertices(g); ++i)
{
diameter = std::max(diameter, *std::max_element(d_matrix[i].begin(),
d_matrix[i].end()));
}
Now what is required is the radius which means minimum distance so i used
the following code :-
for (i = 0; i < num_vertices(g); ++i)
{
radius = std::min(radius, *std::min_element(d_matrix[i].begin(),
d_matrix[i].end()));
}
What is wrong with the above code . As i m getting incorrect values in
case of radius and i cross checked all values are correct...
Secondly i m facing problem in calculating girth of a graph :- For this
what is needed is to first identify if cycle exist and then find the
maximum distance for calculating circumfrence and minimum distance for
calculating girth of a graph..
For identifying the cycles i used the following code. :-
struct cycle_detector : public dfs_visitor<>
{
cycle_detector( bool& has_cycle):_has_cycle(has_cycle)
{ }
template
void back_edge(Edge, Graph&)
{
file_op<<"It's inside back_edge ";
Vertex u, v;
u = boost::source(e, g); // I m not able to understand what vertex
values it is giving in this case..
v = boost::target(e, g);
_has_cycle = true;
}
protected:
bool& _has_cycle;
};
bool has_cycle = false;
typedef Traits::vertices_size_type size_type;
cycle_detector vis(has_cycle);
boost::depth_first_search(g, visitor(vis));
The above code is same as given on
http://www.boost.org/libs/graph/doc/file_dependency_example.html
Now what i want is to record the vertex on which cycle is present and then
calculate the distance. So how should i record the vertex name/Index.
Kindly help
Thanks
Abhishek Vyas
Tata Consultancy Services
Mailto: abhishek.v@tcs.com
Website: http://www.tcs.com
____________________________________________
Experience certainty. IT Services
Business Solutions
Outsourcing
____________________________________________
=====-----=====-----=====
Notice: The information contained in this e-mail
message and/or attachments to it may contain
confidential or privileged information. If you are
not the intended recipient, any dissemination, use,
review, distribution, printing or copying of the
information contained in this e-mail message
and/or attachments to it are strictly prohibited. If
you have received this communication in error,
please notify us by reply e-mail or telephone and
immediately and permanently delete the message
and any attachments. Thank you
