[Boost-users] Problem in calculating radius and girth of a graph

From: abhishek.v_at_[hidden]
Date: 2007-09-26 07:54:23

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_at_[hidden]
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