thnx for your answers. I'm dealing with an undirectred graph. In the beginning I have a given number of vertices (53 in my case now) and a list or relations between them. All I do is adding a new edge (a <-> b) if a is in relatoin to be. My problem is, i dont know form the beginning if it's loopsless. but I need to have it without any loops.
greatz Johannes Am 05.02.2011 07:53, schrieb Nathann Cohen: > >> >> 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 > g -- 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
