[Boost-users] [BGL] Question on prim_minimum_spanning_tree

From: Wang Johny (workmorehard2005_at_[hidden])
Date: 2005-05-28 16:14:26

Hi, there
 
I am a new user of boost (in particular BGL). For my project, I am using the function of "prim_minimum_spanning_tree" to construct the minimum spanning tree. But I found a strange problem and hope to get your help. 
 
Specifically, I am following the sample code "prim-example.cpp" (using MSVC), with one modification to the weight property. That is, I am defining the weight property as 
 
property < edge_weight_t, float >
 
not the original one 
 
property < edge_weight_t, int >
 
And I found by doing so, the function of "prim_minimum_spanning_tree" return wrong results (no edge is returned at all). But the original version using "property < edge_weight_t, int >" definition works well. So I am wondering if I missed something to make user-defined weitgh property work for this function.
 
Any suggestion is welcome. Thank you very much.
 
Best regards,
 
Shenai 
 
 
Problematic code:
///////////////////////////////////////////////////////////////////////////////////////////////////
 
typedef adjacency_list < vecS, vecS, undirectedS, property<vertex_distance_t, int>, property < edge_weight_t, float > > Graph;
  typedef std::pair < int, int >E;
  const int num_nodes = 5;
  E edges[] = { E(0, 2), E(1, 1), E(1, 3), E(1, 4), E(2, 1), E(2, 3),
    E(3, 4), E(4, 0)
  };
  float weights[] = { 1.0f, 2.0f, 1.0f, 2.0f, 7.0f, 3.0f, 1.0f, 1.0f };
  Graph g(num_nodes);
  property_map<Graph, edge_weight_t>::type weightmap = get(edge_weight, g); 
  
  for (std::size_t j = 0; j < sizeof(edges) / sizeof(E); ++j) {
    graph_traits<Graph>::edge_descriptor e; bool inserted;
    tie(e, inserted) = add_edge(edges[j].first, edges[j].second, g);
    weightmap[e] = weights[j];
  }
 std::vector < graph_traits < Graph >::vertex_descriptor >   p(num_vertices(g));
  property_map<Graph, vertex_distance_t>::type distance = get(vertex_distance, g);
  property_map<Graph, vertex_index_t>::type indexmap = get(vertex_index, g);
  prim_minimum_spanning_tree(g, *vertices(g).first, &p[0], distance, weightmap, indexmap,  default_dijkstra_visitor());
  for (std::size_t i = 0; i != p.size(); ++i){
  
  if (p[i] != i){
  TRACE("I am here");
  }
  }
 
///////////////////////////////////////////////////////////////////////////////////////////////////

---------------------------------
Do You Yahoo!?
150万曲MP3疯狂搜，带您闯入音乐殿堂
美女明星应有尽有，搜遍美图、艳图和酷图
1G就是1000兆，雅虎电邮自助扩容！