CODEWITHSUNDEEP
cshortest-pathigraphedges
Stefan Pantea
Stefan Pantea

Reputation: 51

igraph how to get edge ids along the shortest paths

I have a graph with multiple shortest paths and want to retrieve the ids of the vertices and the ids of the edges:

igraph_get_all_shortest_paths(...) computes only the list of the vertices.

Isn't 

igraph_get_shortest_paths(&g, &vertices, &edges, from,igraph_vss_1(to), IGRAPH_ALL);

supposed to do that ?

When I run:

igraph_t g1;
igraph_vector_t v1;
int ret;

/* Create a graph */
igraph_vector_init(&v1, 0);

igraph_create(&g1, &v1, 0, 0);
igraph_add_vertices(&g1, 1, 0);
igraph_add_vertices(&g1, 1, 0);
igraph_add_vertices(&g1, 1, 0);
igraph_add_vertices(&g1, 1, 0);
igraph_add_vertices(&g1, 1, 0);

igraph_add_edge(&g1,0,1);
igraph_add_edge(&g1,0,2);
igraph_add_edge(&g1,2,3);
igraph_add_edge(&g1,1,3);
igraph_add_edge(&g1,0,4);
igraph_add_edge(&g1,4,3);
igraph_add_edge(&g1,4,3);
igraph_add_edge(&g1,4,3);

igraph_vector_ptr_t verts;
igraph_vector_ptr_init(&verts, 2);


igraph_vector_ptr_t eds;
igraph_vector_ptr_init(&eds, 2);

igraph_vector_t v2;
igraph_vector_init(&v2,2);
VECTOR(v2)[0] = 3;
VECTOR(v2)[1] = 3;

igraph_vs_t tovs = igraph_vss_vector(&v2);

igraph_get_shortest_paths(&g1, &verts, &eds, 0, tovs , IGRAPH_ALL);
igraph_destroy(&g1);

I get error: igraph_vector_clear: Assertion `v != ((void *)0)' failed

Upvotes: 1

Views: 1459

Answers (2)

Stefan Pantea
Stefan Pantea

Reputation: 51

The

igraph_get_shortest_paths(&g, &vecs, &evecs, 0, vs, IGRAPH_OUT)

doesn't seem to return multiple shortest paths to one vertex. To be more explicit in the case you have more than one shortest path to/from one vertex the method returns only ONE PATH (ignoring the rest)!!!! Not multiple paths to/from one vertex as mentioned in the docs.

Upvotes: 0

Gabor Csardi
Gabor Csardi

Reputation: 10825

Yes it is supposed to do that. From the docs at the igraph homepage:

[...]

vertices:

The result, the ids of the vertices along the paths. This is a pointer vector, each element points to a vector object. These should be initialized before passing them to the function, which will properly clear and/or resize them and fill the ids of the vertices along the geodesics from/to the vertices. Supply a null pointer here if you don't need these vectors. Normally, either this argument, or the edges should be non-null, but no error or warning is given if they are both null pointers.

edges:

The result, the ids of the edges along the paths. This is a pointer vector, each element points to a vector object. These should be initialized before passing them to the function, which will properly clear and/or resize them and fill the ids of the vertices along the geodesics from/to the vertices. Supply a null pointer here if you don't need these vectors. Normally, either this argument, or the vertices should be non-null, but no error or warning is given if they are both null pointers.

[...]

So the vertices along the paths are returned in vertices and the edges along the paths are returned in edges.

Edit

I see you added some source code. As the docs says, the vectors in the pointer vector(s) must be allocated and initialized before calling this function. This is somewhat strange, because it is different from other igraph functions, but still, this is why you get the error message.

Upvotes: 1

Related Questions