Re: [igraph] Igraph calculating minimum spanning tree with weights C interface

[Szabolcs Horvát]

On 29 March 2016 at 15:59, <address@hidden> 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
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help