Re: [igraph] k-shortest paths between two vertices

[cheng-chun Tu]

Hi igraph users:

I've modified the get_all_sd_paths from Pasquale. I added some checks now it 
works on undirected graph. Also there is a max hop limit value. In case of a 
very large graph, this can save some time and eliminate the too long path.

int get_all_st_paths(
    igraph_vector_ptr_t *paths,     // paths vector
    igraph_adjlist_t *al,           // adjacency list
    igraph_integer_t from,          // from node
    igraph_integer_t to,            // to node
    igraph_vector_t *path,           // current path
    igraph_integer_t maxhop         // maximum number of hops
) {
        int i;
        igraph_vector_t *vadlist, *path1;
        igraph_real_t adjnode;
        if (path != NULL && igraph_vector_size(path) > maxhop) {
            free(path);
            return 0;
        }
        if (path == NULL) {
                path = (igraph_vector_t *) calloc(1, sizeof(igraph_vector_t));
                igraph_vector_init(path, 0);
        }
        igraph_vector_push_back(path, from);
        if (to == from) {
                // append last found path to paths ptr vector
                igraph_vector_ptr_push_back(paths, path);
                return 0;
        }
        vadlist = igraph_adjlist_get(al, from);
        for (i = 0; i < igraph_vector_size(vadlist); i++) {
                adjnode = VECTOR(*vadlist)[i];
                if (!igraph_vector_empty(path) && igraph_vector_contains(path, 
adjnode))
                    continue;
                path1 = (igraph_vector_t *) calloc(1, sizeof(igraph_vector_t));
                igraph_vector_copy(path1, path);
                get_all_st_paths(paths, al, adjnode, to, path1, maxhop);
        }
        igraph_vector_destroy(path);
        free(path);
}

---
William Tu
Stony Brook University