[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: [igraph] shortest path edges disjoint with another path

**From**: |
Gábor Csárdi |

**Subject**: |
Re: [igraph] shortest path edges disjoint with another path |

**Date**: |
Fri, 20 May 2011 19:12:02 -0400 |

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