Re: [igraph] shortest path edges disjoint with another path

[Gábor Csárdi]

On Fri, May 20, 2011 at 5:02 PM, John Lapeyre <address@hidden> wrote:
> 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 ?

Yes, I think you could take the igraph shortest path code, and extend
it with the possibility of forbidding some edges. You can then just
use a vector for marking the edges, and don't need to modify the graph
at all.

Gabor

> Thanks, John
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>



-- 
Gabor Csardi <address@hidden>     MTA KFKI RMKI