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

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 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::type d_map;

typedef boost::u_property pred_t; boost::property_map::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@lists.boost.org 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.... Sent from the Boost - Users mailing list archive at Nabble.com.