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

[Pasquale D'Andreti]

Thank you Tamas for your advice,

I just write down a _very early_ and _very poorly written_ C code to 
find all paths in a noncyclic and nonlooped directed graph. It should be 
a matter of 2-3 more code lines to check for loops and cycles. It should 
be OK with multiple edges although I never tested so. I just checked 
code on only one graph and was OK.
I'm not sure that there are no memory leakages because I don't know 
exactly how igraph_ptr_destroy_all does its work and I didn't stressed 
enough my calloc/free related code.
Now it'll be easy to find the k-shortest paths but I suspect that there 
is a better/smarter way to do all I need.

Pasquale


...initial code here...

        igraph_t graph;
        igraph_integer_t s, t;
        igraph_adjlist_t adjlist;
        igraph_vector_ptr_t paths;

...graph building here... (noncyclic and nonlooped)

        igraph_adjlist_init(&graph, &adjlist, IGRAPH_OUT);
        igraph_vector_ptr_init(&paths, 0);

...s (from) and t (to) initialization here...

// compute all paths
        get_all_st_paths(&paths, &adjlist, s, t, NULL);

// print the paths found
        int i;
        for (i = 0; i < (int) igraph_vector_ptr_size(&paths); i++) {
                printf("path %3d:", i);
                igraph_vector_print(VECTOR(paths)[i]);
                printf("\n");
        }

        igraph_vector_ptr_destroy_all(&paths);
        igraph_adjlist_destroy(&adjlist);
        igraph_destroy(&graph);

...other code here...

Now the C function

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

        int i;
        igraph_vector_t *vadlist, *path1;
        igraph_real_t child;

        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++) {
                child = VECTOR(*vadlist)[i];
                path1 = (igraph_vector_t *) calloc(1, sizeof(igraph_vector_t));
                igraph_vector_copy(path1, path);
                get_all_st_paths(paths, al, child, to, path1);
        }
        igraph_vector_destroy(path);
        free(path);

}

On 09/01/2011 22:33, Tamás Nepusz wrote:
> Hi Pasquale,
>
> > I'm looking for a C function that help me to find the k-shortest paths between 
> > to vertices or, at least, to find (and enumerate) all paths between to 
> > vertices, preferably in form of edge sequence.
> > [...]
> > Are there any news since then?
> No, there aren't any -- you have to implement this yourself. The Python 
> solution you've seen on Stack Overflow is pretty self-explanatory once you 
> understand a bit of Python; if you have specific questions about it and need 
> some pointers to translate it to C, let me know.