igraph-help
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[igraph] Igraph calculating minimum spanning tree with weights C interfa


From: dave . potts
Subject: [igraph] Igraph calculating minimum spanning tree with weights C interface
Date: Tue, 29 Mar 2016 13:59:08 +0000

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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]