#18906: Refactor min spanning tree
-------------------------------------+-------------------------------------
Reporter: borassi | Owner:
Type: defect | Status: needs_review
Priority: major | Milestone: sage-6.8
Component: graph theory | Resolution:
Keywords: Minimum spanning | Merged in:
tree | Reviewers: David Coudert
Authors: Michele Borassi | Work issues:
Report Upstream: N/A | Commit:
Branch: | 78e97957d2259cca983a725f9f14c8b4de8072c8
u/borassi/refactor_min_spanning_tree| Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by borassi):
* status: needs_work => needs_review
Old 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.
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.
Finally, it will modify Kruskal algorithm as follows:
* now, the input can only be an undirected graph, so that the behavior is
much more clear, and the documentation becomes much smaller;
* we moved the code to remove self-loops and multiple edges in a separate
routine, because it will be used by Boost.
This is a first step before the inclusion of Boost minimum spanning tree
algorithms.
--
Comment:
Hello!
I have made two more changes to the Kruskal algorithm, specified in the
description:
* now, the input can only be an undirected graph, so that the behavior
is much more clear, and the documentation becomes much smaller;
* we moved the code to remove self-loops and multiple edges in a separate
routine, because it will be used by Boost.
Sorry for the "late" decision, but I realized this was better only after I
submitted the previous code.
Michele
--
Ticket URL: <http://trac.sagemath.org/ticket/18906#comment:11>
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.
