Minimum Spanning Trees

[Graham Enos]

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'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. [Note: I was working in 4.4.4; now
updating to 4.6]

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) 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?

Best,
Graham

[Graham Enos]

Thanks Minh! I must say, it's rather exciting having open source
software
that fits my needs so well and is both well and speedily maintained. I
hope
to get more involved in the future with this incredible software and
community.

Graham

On Dec 10, 2:07 am, Minh Nguyen <nguyenmi...@gmail.com> wrote:
> Hi Graham,

>
> On Mon, Dec 6, 2010 at 4:57 AM, Graham Enos <graham.e...@gmail.com> wrote:
> > 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'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.
>

> The patch at ticket #10433
>
> http://trac.sagemath.org/sage_trac/ticket/10433
>
> should fix the problem you were experiencing, at least for the case
> where you use Kruskal's algorithm to find a minimum spanning tree.
>
> --
> Regards
> Minh Van Nguyen