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<size_type> 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_limits<std::size_t>::max();
  for (i = 0; i < num_vertices(g); ++i)
  {
      calc_distance_visitor<size_type*> 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 <class Edge, class Graph>
    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