Hi Graham, On Mon, Dec 6, 2010 at 4:57 AM, Graham Enos <[email protected]> wrote: > Hi all, > > I wasn't sure if I should submit a ticket on this or not, since it > seems to fall under "unexpected behavior" rather than "software bug."
I think it's a case of both. > I've been working through some small graph theory problems and was > computing minimum spanning trees on graphs with weighted edges (where > edges were assigned a weight as their label). I was getting completely > unexpected behavior; after some digging, I found that > G.min_spanning_tree() defaults to setting all edge weights to 1, even > if the edges have weights assigned. This shouldn't happen and as you said above it's an unexpected behaviour. What the code for min_spanning_tree() fails to take into account is that an undirected graph G might be weighted. The default implementation uses a weight function. But if we don't have a weight function and we really want to use the weights already in G, then the current implementation gives you the unexpected behaviour. > Perhaps it's just me, but I would expect that if an edge is created > with a number label that Sage recognize it as a weight and act > accordingly. This may be a difference of philosophy (better to have > predefined, easy to understand, works-every-time default behavior than > several exceptions and subcases) I think min_spanning_tree() should also do as you described: detect that G is weighted and use the already assigned weights. This is not currently implemented. See ticket #10433 [1] where this enhancement is tracked. Note that the current implementation only takes care of Kruskal's and Prim's algorithms. I would like to also implement Boruvka's algorithm for ticket #10433. > or of course be due to my ignorance > of how Sage portrays graphs more than anything. On the other hand, I > think the behavior expected by those with a level of ignorance similar > to my own might be similar. Perhaps in G.min_spanning_tree() we could > have the default weight_function be something like > > def weight(edge): > try: > return RR(edge[2]) > except: > return 1 > > Any thoughts? This is equivalent to the current implementation. Here's how I would clean up min_spanning_tree(): * Leave the current parameters alone. * If a weight function is supplied, then use that weight function. * If the graph G is weighted, then use the already assigned weights. * If G is weighted and a weight function is also supplied, then use the already assigned weights of G, not the weight function. If you really want to use a weight function for G even if G is weighted, then first convert G to be unweighted and pass in the weight function. * If the weights of G are all distinct, then use Boruvka's algorithm. The advantage here is that Boruvka's algorithm is embarrassingly parallelizable (that's a technical term :-). * If G is unweighted, then default to using unit weight for each edge of G. * The default behaviour is to use the already assigned weights of G provided that G is weighted. * Similar comments apply for digraphs, multigraphs, and multidigraphs. [1] http://trac.sagemath.org/sage_trac/ticket/10433 -- Regards Minh Van Nguyen -- To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
