Opened 6 years ago
Closed 6 years ago
#18906 closed defect (fixed)
Refactor min spanning tree
Reported by:  borassi  Owned by:  

Priority:  major  Milestone:  sage6.8 
Component:  graph theory  Keywords:  Minimum spanning tree 
Cc:  ncohen, dcoudert  Merged in:  
Authors:  Michele Borassi  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  299bc40 (Commits, GitHub, GitLab)  Commit:  299bc40fe3ad77bf4374e9f2e6c37dfd7ebf371e 
Dependencies:  Stopgaps: 
Description (last modified by )
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) <ipythoninput27b461ae20ba97> in <module>() > 1 g.min_spanning_tree(algorithm='NetworkX') /home/michele/Programmi/sage/local/lib/python2.7/sitepackages/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 selfloops 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.
Change History (18)
comment:1 Changed 6 years ago by
 Cc ncohen added
comment:2 Changed 6 years ago by
 Cc dcoudert added
 Component changed from PLEASE CHANGE to graph theory
 Description modified (diff)
 Keywords Minimum spanning tree added
 Type changed from PLEASE CHANGE to defect
comment:3 Changed 6 years ago by
 Branch set to u/borassi/refactor_min_spanning_tree
comment:4 Changed 6 years ago by
 Commit set to 425eac73595d1472845a4c879dbbd1c474104316
 Status changed from new to needs_review
comment:5 Changed 6 years ago by
 Commit changed from 425eac73595d1472845a4c879dbbd1c474104316 to ace2f0d33337f08537a27b3b6cba8aff01b93576
Branch pushed to git repo; I updated commit sha1. New commits:
ace2f0d  Improved documentation

comment:6 Changed 6 years ago by
I like this patch, and I didn't know that it had bugs.
Wouldn't it be nicer if edges were sorted (including endvertices) ? You could use e.g. sorted( (u,v,l) if u<v else (v,u,l) for u,v,l in edges )
. It adds some computation time, but that would give an additional value (i.e., we can assume that...). In fact, I assume that some algorithms are already doing it. For others, it might be sufficient to add a test before inserting in list edges
.
comment:7 Changed 6 years ago by
 Commit changed from ace2f0d33337f08537a27b3b6cba8aff01b93576 to dd7e57592f99e76a1fc2768611a492b2ba3455a6
Branch pushed to git repo; I updated commit sha1. New commits:
dd7e575  Sorted output

comment:8 Changed 6 years ago by
 Reviewers set to David Coudert
 Status changed from needs_review to positive_review
Good to go.
comment:9 Changed 6 years ago by
 Status changed from positive_review to needs_work
Hello!
I just realized I need some more modifications on the code to deal with multiple edges, before implementing the Boost version. I will submit the new version as soon as possible!
See you,
Michele
comment:10 Changed 6 years ago by
 Commit changed from dd7e57592f99e76a1fc2768611a492b2ba3455a6 to 78e97957d2259cca983a725f9f14c8b4de8072c8
Branch pushed to git repo; I updated commit sha1. New commits:
78e9795  Corrected behavior with digraphs, created routine simplify

comment:11 Changed 6 years ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
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 selfloops 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
comment:12 Changed 6 years ago by
 Commit changed from 78e97957d2259cca983a725f9f14c8b4de8072c8 to 268662fa493378a6b221f77e35153e756e12d216
comment:13 followup: ↓ 15 Changed 6 years ago by
There is no need for a new method simplify
since we already have method to_simple
in generic_graph.py
.
I however fully agree that the to_simple
method is incorrect since it starts with g=self.to_undirected()
... O_o
The best is to improve to_simple
, and possibly also allow_loops
, allow_multiple_edges
, remove_loops
, multiple_edges
, etc. but first to_simple
.
comment:14 Changed 6 years ago by
 Commit changed from 268662fa493378a6b221f77e35153e756e12d216 to c0a18032f71897554c59583314116c3c46c085dd
Branch pushed to git repo; I updated commit sha1. New commits:
c0a1803  Modified allow_multiple_edges, and removed simplify

comment:15 in reply to: ↑ 13 Changed 6 years ago by
There is no need for a new method
simplify
since we already have methodto_simple
ingeneric_graph.py
.
You are right: I removed the method, and I call the to_simple
routine.
I however fully agree that the
to_simple
method is incorrect since it starts withg=self.to_undirected()
... O_oThe best is to improve
to_simple
, and possibly alsoallow_loops
,allow_multiple_edges
,remove_loops
,multiple_edges
, etc. but firstto_simple
.
I have improved to_simple
and allow_multiple_edges
: the user can choose if the graph is converted to an undirected graph, and which label should be kept (the minimum, the maximum, or any label).
comment:16 Changed 6 years ago by
 Commit changed from c0a18032f71897554c59583314116c3c46c085dd to 299bc40fe3ad77bf4374e9f2e6c37dfd7ebf371e
Branch pushed to git repo; I updated commit sha1. New commits:
299bc40  Small modification

comment:17 Changed 6 years ago by
 Status changed from needs_review to positive_review
It's much better now.
I ran successfully sage t l src/sage/graphs/
(except for the error solved in #18911)
The doc builds properly and looks good.
Thanks.
comment:18 Changed 6 years ago by
 Branch changed from u/borassi/refactor_min_spanning_tree to 299bc40fe3ad77bf4374e9f2e6c37dfd7ebf371e
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Corrected minimum spanning tree strange behaviors