Re: [Boost-users] Problem in cal diameter and girth using BGL

From: tonyaim83 (abhishek.v_at_[hidden])
Date: 2007-09-26 07:55:48

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 in advance

Douglas Gregor-2 wrote:
> 
> 
> On Sep 20, 2007, at 6:59 AM, tonyaim83 wrote:
>> I want to calculate diameter and girth of a graph using BGL so i m  
>> taking
>>
>> http://www.cs.ualberta.ca/~ghali/courses/texts/BGL/html/ 
>> girth.cpp.html#pred_t.54
>> as a reference.
>> I have already created graph  using adjacency_list
>>
>> Now i m not able to understand how to use :-
>>
>> typedef boost::v_property<long> dist_t;
>> boost::property_map<Graph*, dist_t>::type d_map;
>>
>> typedef boost::u_property<vertex_descriptor> pred_t;
>> boost::property_map<Graph*, pred_t>::type p_map;
> 
> Those are Stanford GraphBase-specific property maps. You can create  
> your own property maps from the adjacency_list; see http:// 
> www.boost.org/libs/graph/doc/using_property_maps.html
> 
>> Is there any alternative to calculate diameter and girth
> 
> We don't have these functions in the BGL at this time.
> 
> 	- Doug
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
> 
> 

-- 
View this message in context: http://www.nabble.com/Problem-in-cal-diameter-and-girth-using-BGL-tf4486815.html#a12899346
Sent from the Boost - Users mailing list archive at Nabble.com.