Oh, I was imprecise. If it has no loops, it is a forest. So you have to get a spanning tree for each component.
On Sat, Feb 5, 2011 at 10:01 AM, Luiz Felipe Martins < luizfelipe.mart...@gmail.com> wrote: > 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
