Refactor min spanning tree

[sagetrac-borassi]

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.

CC: @nathanncohen @dcoudert

Component: graph theory

Keywords: Minimum spanning tree

Author: Michele Borassi

Branch/Commit: 299bc40

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/18906

[sagetrac-borassi]

Changed keywords from none to Minimum spanning tree

[sagetrac-borassi]

Author: Michele Borassi

[sagetrac-borassi]

Branch: u/borassi/refactor_min_spanning_tree

[sagetrac-borassi]

Commit: 425eac7

[sagetrac-borassi]

New commits:

425eac7

Corrected minimum spanning tree strange behaviors

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ace2f0d

Improved documentation

[sagetrac-git]

Changed commit from 425eac7 to ace2f0d

[dcoudert]

comment:6

I like this patch, and I didn't know that it had bugs.

Wouldn't it be nicer if edges were sorted (including end-vertices) ? 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.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

dd7e575

Sorted output

[sagetrac-git]

Changed commit from ace2f0d to dd7e575

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:8

Good to go.

[sagetrac-borassi]

comment:9

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

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

78e9795

Corrected behavior with digraphs, created routine simplify

[sagetrac-git]

Changed commit from dd7e575 to 78e9795

[sagetrac-borassi]

comment:11

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

[sagetrac-git]

Changed commit from 78e9795 to 268662f

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

29346b2	Corrected behavior with digraphs, created routine simplify
268662f	Removed some tests dealing with digraphs

[dcoudert]

comment:13

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.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

c0a1803

Modified allow_multiple_edges, and removed simplify

[sagetrac-git]

Changed commit from 268662f to c0a1803

[sagetrac-borassi]

comment:15

There is no need for a new method simplify since we already have method to_simple in generic_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 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.

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

[sagetrac-git]

Changed commit from c0a1803 to 299bc40

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

299bc40

Small modification

[dcoudert]

comment:17

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.

[vbraun]

Changed branch from u/borassi/refactor_min_spanning_tree to 299bc40