> > how can i add a new edge (a->b) to a given graph G (n.n. connected), > just in the case that there is no path (a -> ... -> b) before?
>From your question, I can not infer whether you are dealing with directed or undirected graphs. So just in case : - If your graph is undirected and there are no paths between two vertices a and b, it means that a and b lie in different connected components. Given a graph g, you can obtain the list of connected components with g.connected_components(). It is a list of list (a partition of the vertices). Two vertices are joined by a path if and only if they are in the same connected component (in a Graph, "being linked by a path" is an equivalence relation). As soon as you add an edge between two connected components, you "merge" them :-) http://en.wikipedia.org/wiki/Connected_component_(graph_theory) - If your graph is directed, there is no equivalence relation anymore, because it is not even reflexive. You may have a path from a to b, but no path from b to a. We are then talking about strongly connected components (g.strongly_connected_components()), g.is_strongly_connected()). If you have two strongly conected components A and B in your graph, [ (adding one arc from any vertex of A to any vertex of B) AND (adding one arc from any vertex of B to any vertex of A) ] will ensure that for any pair of vertices in A U B there exist paths in both directions. Pretty often you just need to add ONE arc instead of two. You can get this information with the method strongly_components_digraph Strongly connected components : http://en.wikipedia.org/wiki/Strongly_connected_component In any case, you will often have a HUGE number of paths in your graphs, while checking whether there exists a path from a to b is almost instantaneous. You can do it manually with g.distance(a,b) <= g.order() or len(g.shortest_path(u,v)) > 0. The methods connected_components() or strongly_connected_components() actually test all the pairs at the same time, which is faster than actually computing shortest paths or distances between all pair. These methods are the most efficient you will find in Sage : they are very simple and implemented in Cython, as they appear very, very often in graph algorithms. (if I missed your point, please also tell me whether you are dealing with graphs/digraphs) :-) Nathann -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
