Sorry, I didn't get the beginning of the thread, but if you need the graph without loops, it is a tree. So, you can compute a maximal spanning tree of the graph, and see if you get the whole graph together. This will also tell you what edges to remove, if the graph is not a tree. Of course, the maximal spanning tree is not unique, so the set of edges to be removed will not be uniquely determined.
Sorry if this was already mentioned, or if it is actually unrelated to what you need. On Sat, Feb 5, 2011 at 7:37 AM, Johannes <dajo.m...@web.de> wrote: > 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<sage-support%2bunsubscr...@googlegroups.com> > For more options, visit this group at > http://groups.google.com/group/sage-support > URL: http://www.sagemath.org > -- 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
