igraph-help
[Top][All Lists]

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

 From: Pasquale D'Andreti Subject: Re: [igraph] k-shortest paths between two vertices Date: Sun, 09 Jan 2011 23:30:00 +0100 User-agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.13) Gecko/20101208 Thunderbird/3.1.7

```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_vector_ptr_t paths;

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

igraph_vector_ptr_init(&paths, 0);

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

// compute all paths

// 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_destroy(&graph);

...other code here...

Now the C function

int get_all_st_paths(
igraph_vector_ptr_t *paths,     // paths vector
igraph_integer_t from,          // from node
igraph_integer_t to,            // to node
igraph_vector_t *path           // current path
) {

int i;
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;
}

for (i = 0; i < igraph_vector_size(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.

```
```

```