Opened 7 years ago

Closed 7 years ago

# Refactor min spanning tree

Reported by: Owned by: borassi major sage-6.8 graph theory Minimum spanning tree ncohen, dcoudert Michele Borassi David Coudert N/A 299bc40 299bc40fe3ad77bf4374e9f2e6c37dfd7ebf371e

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.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:1 Changed 7 years ago by ncohen

• Cc ncohen added

### comment:2 Changed 7 years ago by borassi

• Authors set to Michele Borassi
• 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 7 years ago by borassi

• Branch set to u/borassi/refactor_min_spanning_tree

### comment:4 Changed 7 years ago by borassi

• Commit set to 425eac73595d1472845a4c879dbbd1c474104316
• Status changed from new to needs_review

New commits:

 ​425eac7 `Corrected minimum spanning tree strange behaviors`

### comment:5 Changed 7 years ago by git

• Commit changed from 425eac73595d1472845a4c879dbbd1c474104316 to ace2f0d33337f08537a27b3b6cba8aff01b93576

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

 ​ace2f0d `Improved documentation`

### comment:6 Changed 7 years ago by dcoudert

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

### comment:7 Changed 7 years ago by git

• Commit changed from ace2f0d33337f08537a27b3b6cba8aff01b93576 to dd7e57592f99e76a1fc2768611a492b2ba3455a6

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

 ​dd7e575 `Sorted output`

### comment:8 Changed 7 years ago by dcoudert

• Reviewers set to David Coudert
• Status changed from needs_review to positive_review

Good to go.

### comment:9 Changed 7 years ago by borassi

• 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 7 years ago by git

• 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 7 years ago by borassi

• 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 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

### comment:12 Changed 7 years ago by git

• Commit changed from 78e97957d2259cca983a725f9f14c8b4de8072c8 to 268662fa493378a6b221f77e35153e756e12d216

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`

### comment:13 follow-up: ↓ 15 Changed 7 years ago by dcoudert

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 7 years ago by git

• 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 7 years ago by borassi

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

### comment:16 Changed 7 years ago by git

• Commit changed from c0a18032f71897554c59583314116c3c46c085dd to 299bc40fe3ad77bf4374e9f2e6c37dfd7ebf371e

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

 ​299bc40 `Small modification`

### comment:17 Changed 7 years ago by dcoudert

• 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 7 years ago by vbraun

• Branch changed from u/borassi/refactor_min_spanning_tree to 299bc40fe3ad77bf4374e9f2e6c37dfd7ebf371e
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.