I have been trying to calculate a minimum spanning tree using prim method, but I have got a little bit confused about the weights are used in this context. The suggest example program in the source documents does not seem to be correct, I don't understand why the edge betweenness needs to be calculated. Please see the following program, its designed to make a simple undirected graph. #include <igraph.h>
int main()
{
igraph_vector_t eb, edges;
igraph_vector_t weights;
long int i;
igraph_t theGraph, tree;
struct arg {
int index;
int source;
int target;
float weight;
};
struct arg data[] = {
{0, 0, 1, 2.0},
{1, 1, 2, 3.0},
{2, 2, 3, 44.0},
{3, 3, 4, 3.0},
{4, 4, 1, 2.0},
{5, 4, 5, 9.0},
{6, 4, 6, 3.0},
{6, 6, 5, 7.0}
};
int nargs = sizeof(data) / sizeof(struct arg);
igraph_empty(&theGraph, nargs, IGRAPH_UNDIRECTED);
igraph_vector_init(&weights, nargs);
// create graph
for (i = 0; i < nargs; i++) {
igraph_add_edge(&theGraph, data[i].source, data[i].target);
// Add an weight per entry
igraph_vector_set(&weights, i, data[i].weight);
}
igraph_vector_init(&eb, igraph_ecount(&theGraph));
igraph_edge_betweenness(&theGraph, &eb, IGRAPH_UNDIRECTED, &weights);
for (i = 0; i < igraph_vector_size(&eb); i++) {
VECTOR(eb)[i] = -VECTOR(eb)[i];
}
igraph_minimum_spanning_tree_prim(&theGraph, &tree, &eb);
igraph_write_graph_edgelist(&tree, stdout);
igraph_vector_init(&edges, 0);
igraph_minimum_spanning_tree(&theGraph, &edges, &eb);
igraph_vector_print(&edges);
igraph_vector_destroy(&edges);
igraph_destroy(&tree);
igraph_destroy(&theGraph);
igraph_vector_destroy(&eb);
return 0;
}
Can anybody see anything that is wrong with this program its designed to build a simple graph with what I hope is the correct way to use a weight argument. One value per edge between a source and a target.
regards
Dave.