[igraph] shortest path edges disjoint with another path

[John Lapeyre]

Hi, I wonder if someone has a comment on the efficiency of
this procedure using the C interface. Given a path A, I want
to find the shortest path between two chosen vertices on A
that is edge disjoint with all edges on A. I iterate this
over several pairs of vertices on A. I also iterate over A,
which are geodesics themselves.

To find these shortest paths, I delete the edges of A and
then use a shortest path routine. igraph_get_all_paths
returns paths as vectors of vertices. I convert a vector of
vertices to an edge selector (which is then converted to an
iterator for deleting, I think). Then I call
igraph_delete_edges. To iterate over A, I have at least two
options: Add the edges again (this must be done with the
original list of vertices, I think, because the edges have
been renumbered) Or, I can use a saved copy of the original
graph. In some tests, the second method is a bit
faster. Maybe it is in most cases. I suppose this makes
sense if adding and deleting edges is O(|V|+|E|).

Anyway, the procedure seems quite expensive compared to
somehow marking the edges without actually deleting them. Of
course, each edge would then have to be checked for the mark
in shortest path routines. Does this seem reasonable ?

Thanks, John