On 29 March 2016 at 15:59, <dave.po...@pinan.co.uk> wrote:
> 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.
>
The edge betweenness does not need to be calculated. This simple example
program simply uses the edge betweenness as edge weights. You can use
whatever weights you want.
> 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);
>
>
It looks like nargs is the number of edges in your graph. You need to pass
the number of nodes to igraph_empty().
>
>
> 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.
>
You can use whatever values you want for edge weights. Here you copied the
example program, calculated the edge betweenness and used that as weights.
Do you want to use the edge betweenness (eb) or your original weights
(weights)? It all depends on what you want to do.
> One value per edge between a source and a target.
>
> regards
>
> Dave.
>
> _______________________________________________
> igraph-help mailing list
> igraph-help@nongnu.org
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
_______________________________________________
igraph-help mailing list
igraph-help@nongnu.org
https://lists.nongnu.org/mailman/listinfo/igraph-help
