On Thu, Dec 15, 2011 at 8:34 AM, Albert Heinle <albert.hei...@googlemail.com> wrote: > Hello Sage-Team, > > a friend of mine and I have found a bug today in sage in the algorithm for > computing the minimum spanning tree. > > We are using Sage Version 4.7, Release Date: 2011-05-23 on a mac with OS X > Snow Leopard. > > Here is the short example, where the algorithms do fail: > > g = Graph(weighted = True) > g.add_vertices(range(1,5)) > for v in g.vertices(): > for u in g.vertices(): > if (u == 1 and v == 3) or (u == 3 and v == 1): > g.add_edge(u,v,100) > continue > if not u == v: > g.add_edge((u,v,1)) > > which is a simple example. The graph looks like this. The edges have all > weight 1, except from the one between 3 and 1, which has 100. > > > > Now, the call of > g.min_spanning_tree() > results in > [(1, 2, 1), (1, 3, 100), (1, 4, 1)] > which is clearly not the minimum spanning tree. We also tried another > algorithm (Prim Edge) and got the same results. >
I got this: sage: from sage.graphs.spanning_tree import kruskal sage: kruskal(g, check=True) [(1, 2, 1), (1, 4, 1), (2, 3, 1)] The docs say "By default, we turn off the sanity checks for performance reasons." Do you think this could explain it? > > For further questions on this report, feel free to respond to this mail. > > Thanks in advance for fixing it. > > Albert Heinle > -- > 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
