Boost logo

Boost Users :

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



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