[Boost-users] A problem in using "prim_minimum_spanning_tree.hpp"

Subject: [Boost-users] A problem in using "prim_minimum_spanning_tree.hpp"
From: Íõΰ (wangwei7451_at_[hidden])
Date: 2010-08-19 11:52:48

Hi,
I'm studying MST algorithms in GPU recently.I need BGL implementation as coparison,But I have a problem in using  prim_minimum_spanning_tree.hpp.The problem is:when I use large input(e.g. >1M),the result is wrong,all the parent of vertices is "no parent".But when the input(e.g. 1K) is small,the result is noproblem. I haven't found know the reason yet.My complier is gcc 4.1.2,OS is RHEL5.
Help would be appreciated. Thanks in advance.
Wang wei
The complete code is:
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
#include <fstream>
#include <string.h>
using namespace std;

int main()
{
using namespace boost;
typedef adjacency_list < vecS, vecS, undirectedS,
    property<vertex_distance_t, long>, property < edge_weight_t, int > > Graph;
typedef std::pair < long, long >E;

//read graph data from file
long num_nodes,num_edges,u,v;
int w;
ifstream infile;
infile.open("convertResult.txt");
if(!infile)
{
cerr<<"error:unable to open file."<<endl;
return -1;
}
infile>>num_nodes>>num_edges;
E edges[num_edges];
int weights[num_edges];
for(long i=0;i<num_edges;i++)
{
infile>>u>>v>>w;
edges[i] = make_pair(u,v);
weights[i] = w;
}
  
//construct input parameters
Graph g(edges, edges + sizeof(edges) / sizeof(E), weights, num_nodes);
property_map<Graph, edge_weight_t>::type weightmap = get(edge_weight, g);
std::vector < graph_traits < Graph >::vertex_descriptor >
    p(num_vertices(g));

//call the BGL PRIM
prim_minimum_spanning_tree(g, &p[0]);

//output the result
ofstream outfile;
outfile.open("primResult.txt");
for (std::size_t i = 0; i != p.size(); ++i)
if (p[i] != i)
outfile<< "parent[" << i << "] = " << p[i] << std::endl;
else
outfile<< "parent[" << i << "] = no parent" << std::endl;

return EXIT_SUCCESS;
}