Re: [sage-support] Re: edges in graphs
Yea, sure. but my problem is a tree like this: 1 / \ 23 45 and so on. but i don't need it in that order I have a few crossing edes in it and I'd like to have one like 1 / \ 35 24 or 1 / \ 25 34 or someting like that, such that i have just a minimal number of crosssings. even more, it would be nice, if every vertex is placed under his parent and not from left to right: 1 / \ 4 5 / \ \ 6 7 _ 9 where '_' denotes a free space for a left child node of 5. greatz Am 07.02.2011 19:09, schrieb Nathann Cohen: > Hello !!! > > Among the wealth of tricky options one can use in plot/show, you will find : > > g.plot(layout='tree') > > :-) > > 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
Re: [sage-support] Re: edges in graphs
Hello !!! Among the wealth of tricky options one can use in plot/show, you will find : g.plot(layout='tree') :-) 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
Re: [sage-support] Re: edges in graphs
yea. it's connected. i tried the spanning trees too, but I had to look ob how the trees differ, depending on how they are build. I've just one small (opticial) problem remaining. if I plot the tree all vertices are ordert on each level but beacause of this many lines are crossing. I dont need to have them sorted, but it would be nice to have as less as possible edges crossing. greatz Johannes Am 05.02.2011 16:02, schrieb Luiz Felipe Martins: > 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 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 >>> 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
Re: [sage-support] Re: edges in graphs
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 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 >> 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
Re: [sage-support] Re: edges in graphs
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 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 > 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
Re: [sage-support] Re: edges in graphs
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
[sage-support] Re: edges in graphs
> > 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
