Shortest paths weights in C

Usage
1

I am trying to get the shortest path from one node to another in a weighted graph. Using the function igraph_get_shortest_path_dijkstra I need to get the edges weight as one of the arguments, but I dont understand how to get them. I am using a graph initialized with igraph_adjacency using a weighted matrix, shouldnt weights be already present in the graph? Is there a way to get the weights that match exactly the edges? I have tried using the macro EANV to query for the attribute of all edges but I get segmentation fault.

So far this it my code

#include <igraph.h>

int main()
{
    igraph_matrix_t connectome;
    igraph_vector_t vertices, weights;
    const char *att = "weight";
    igraph_t graph;

    igraph_matrix_init(&connectome, 82, 82);
    igraph_matrix_set(&connectome, 0, 1, 5);
    igraph_matrix_set(&connectome, 0, 2, 1);
    igraph_matrix_set(&connectome, 1, 2, 1);
    igraph_weighted_adjacency(&graph, &connectome, IGRAPH_ADJ_UNDIRECTED, att, 1);
    igraph_vector_init(&vertices, 0);
    igraph_vector_init(&weights, 82 * 81 / 2);
    EANV(&graph, att, &weights);
    igraph_get_shortest_path_dijkstra(&graph, &vertices, NULL, 0, 1, 0, IGRAPH_ALL);

    printf("Shortest path between 1 and 0 is");
    for (int i = 0; i < igraph_vector_size(&vertices); i++)
    {
        printf(" %g ", (double)igraph_vector_e(&vertices, i));
    }
    printf("\n");

    igraph_matrix_destroy(&connectome);
    igraph_vector_destroy(&vertices);
    igraph_destroy(&graph);

    return 0;
}

Its just a silly test to try the weighted shortest path. I get segmentation fault when the program runs EANV. If someone could help me I would appreciate it.

Thanks in advance

2

Add this line to the beginning of the program:

igraph_set_attribute_table(&igraph_cattribute_table);

This will enable the C attribute handler, which is necessary to be able to work with attributes. Using attributes is not usually necessary when programming igraph in C. igraph_weighted_adjacency is a bit of a special case.

See here for more details:

https://igraph.org/c/doc/igraph-Attributes.html#accessing-attributes-from-c

1 Like
3

Some more tips:

Instead of igraph_matrix_set(&connectome, 0, 1, 5), use MATRIX(connectome, 0, 1) = 5.

Instead of igraph_vector_e(&vertices, i), use VECTOR(vertices)[i].

There is a cost to the igraph_vector_size call (as to any non-inlinable function call), so in performance-critical tight loops, first get and save the vector size, then you can use it repeatedly in the loop.

It’s okay to initialize the weight vector to size 0.

1 Like
4

Thanks for your fast answer, it solved the problem and helped me a lot.