#18906: Refactor min spanning tree
-----------------------------------------+------------------------
Reporter: borassi | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-6.8
Component: graph theory | Resolution:
Keywords: Minimum spanning tree | Merged in:
Authors: Michele Borassi | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
-----------------------------------------+------------------------
Changes (by {'newvalue': u'Michele Borassi', 'oldvalue': ''}):
* author: => Michele Borassi
* cc: dcoudert (added)
* component: PLEASE CHANGE => graph theory
* keywords: => Minimum spanning tree
* type: PLEASE CHANGE => defect
Old description:
New description:
Solve some strange behaviors / bugs in minimum spanning tree routines.
Usually, if the graph is weighted, the weight is ignored, and the
`weight_function` argument is used. If this argument is not provided, the
(rather counterintuitive) behavior is to set all weights to 1 (so that any
spanning tree can be outputted). However, if Kruskal algorithm is used,
and `check` is set to `True`, then edge weights are used, instead.
{{{
sage: g = Graph(weighted=True)
sage: g.add_edges([[0,1,1],[1,2,1],[2,0,10]])
sage: g.min_spanning_tree(algorithm='Kruskal')
[(0, 1, 1), (0, 2, 10)]
sage: g.min_spanning_tree(algorithm='Prim_fringe')
[(0, 1), (0, 2)]
sage: g.min_spanning_tree(algorithm='Prim_edge')
[(0, 1, 1), (0, 2, 10)]
sage: sage: g.min_spanning_tree(algorithm='Kruskal', check=True)
[(0, 1, 1), (1, 2, 1)]
}}}
This example also shows that the outputs are different.
Moreover, NetworkX algorithm does not work:
{{{
sage: g.min_spanning_tree(algorithm='NetworkX')
---------------------------------------------------------------------------
TypeError Traceback (most recent call
last)
<ipython-input-27-b461ae20ba97> in <module>()
----> 1 g.min_spanning_tree(algorithm='NetworkX')
/home/michele/Programmi/sage/local/lib/python2.7/site-
packages/sage/graphs/generic_graph.pyc in min_spanning_tree(self,
weight_function, algorithm, starting_vertex, check)
3433 import networkx
3434 G = networkx.Graph([(u, v,
dict(weight=weight_function((u, v)))) for u, v, l in
self.edge_iterator()])
-> 3435 return list(networkx.mst(G))
3436 else:
3437 raise NotImplementedError("Minimum Spanning Tree
algorithm '%s' is not implemented." % algorithm)
TypeError: 'module' object is not callable
}}}
This ticket will change this behavior, by defining a specific order in the
choice of weights:
* if the function weight_function is provided, it is used as default;
* if the function weight_function is None (default) and the graph is
weighted, the edge weights are used;
* otherwise, all weights are set to 1.
Moreover, it will fix NetworkX problems, and it will standardize the
output. This is a first step before the inclusion of Boost minimum
spanning tree algorithms.
--
--
Ticket URL: <http://trac.sagemath.org/ticket/18906#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
