Opened 6 years ago

Closed 6 years ago

#18906 closed defect (fixed)

Refactor min spanning tree

Reported by: borassi Owned by:
Priority: major Milestone: sage-6.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:

Status badges

Description (last modified by 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.

Change History (18)

comment:1 Changed 6 years ago by ncohen

  • Cc ncohen added

comment:2 Changed 6 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 6 years ago by borassi

  • Branch set to u/borassi/refactor_min_spanning_tree

comment:4 Changed 6 years ago by borassi

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

New commits:

425eac7Corrected minimum spanning tree strange behaviors

comment:5 Changed 6 years ago by git

  • Commit changed from 425eac73595d1472845a4c879dbbd1c474104316 to ace2f0d33337f08537a27b3b6cba8aff01b93576

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

ace2f0dImproved documentation

comment:6 Changed 6 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 6 years ago by git

  • Commit changed from ace2f0d33337f08537a27b3b6cba8aff01b93576 to dd7e57592f99e76a1fc2768611a492b2ba3455a6

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

dd7e575Sorted output

comment:8 Changed 6 years ago by dcoudert

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

Good to go.

comment:9 Changed 6 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 6 years ago by git

  • Commit changed from dd7e57592f99e76a1fc2768611a492b2ba3455a6 to 78e97957d2259cca983a725f9f14c8b4de8072c8

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

78e9795Corrected behavior with digraphs, created routine simplify

comment:11 Changed 6 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 6 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:

29346b2Corrected behavior with digraphs, created routine simplify
268662fRemoved some tests dealing with digraphs

comment:13 follow-up: Changed 6 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 6 years ago by git

  • Commit changed from 268662fa493378a6b221f77e35153e756e12d216 to c0a18032f71897554c59583314116c3c46c085dd

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

c0a1803Modified allow_multiple_edges, and removed simplify

comment:15 in reply to: ↑ 13 Changed 6 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 6 years ago by git

  • Commit changed from c0a18032f71897554c59583314116c3c46c085dd to 299bc40fe3ad77bf4374e9f2e6c37dfd7ebf371e

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

299bc40Small modification

comment:17 Changed 6 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 6 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.