[Top][All Lists]

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

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

From: cheng-chun Tu
Subject: Re: [igraph] k-shortest paths between two vertices
Date: Mon, 7 Feb 2011 22:20:06 -0500

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) {
            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, 
                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);

William Tu
Stony Brook University

reply via email to

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