#7492 closed enhancement (fixed)
Decomposition of a doubly stochastic matrix as a convex sum of permutations (Birkhoff–von Neumann Theorem)
Reported by: | ncohen | Owned by: | mhansen |
---|---|---|---|
Priority: | major | Milestone: | sage-4.4.4 |
Component: | combinatorics | Keywords: | |
Cc: | Merged in: | sage-4.4.4.alpha0 | |
Authors: | Nathann Cohen | Reviewers: | Mike Hansen, David Loeffler |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
As the title says, the Birkhoff–von Neumann Theorem (http://en.wikipedia.org/wiki/Birkhoff%E2%80%93von_Neumann_Theorem) says that any doubly stochastic matrix ( http://en.wikipedia.org/wiki/Doubly_stochastic_matrix ) can be written as a convex sum of permutations.
This patch requires several other patches to be applied first ( or merged into Sage ) :
Nathann
Attachments (2)
Change History (19)
comment:1 Changed 10 years ago by
- Description modified (diff)
- Summary changed from Decomposition of a doubly stochastic matrix as a convex sum of permutations to Decomposition of a doubly stochastic matrix as a convex sum of permutations (Birkhoff–von Neumann Theorem)
comment:2 Changed 10 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:3 Changed 9 years ago by
- Description modified (diff)
- Report Upstream set to N/A
comment:4 Changed 9 years ago by
- Description modified (diff)
comment:5 Changed 9 years ago by
- Reviewers set to Mike Hansen
- Status changed from needs_review to needs_work
comment:6 Changed 9 years ago by
- Status changed from needs_work to needs_review
comment:7 follow-up: ↓ 8 Changed 9 years ago by
- Status changed from needs_review to needs_work
Needs work, I'm afraid.
- Firstly, there are no checks on the input type. It will happily accept non-doubly-stochastic matrices, and return garbage; and it seems to silently replace real numbers with rational approximations to them, which is frankly rather weird. The docstring should state clearly what base rings are allowed (integers? rationals? reals?) and there should be a check to make sure that the input matrix really is a doubly stochastic matrix over one of these base rings.
- The doctests won't work without an optional spkg, so they should be flagged as such.
- Non-ASCII character in the docstring (it reads as "Birkhoff[a-with-circumflex][empty-square-box][empty-square-box]von Neumann" on my system)
- There's not a lot of point in adding functions when there's no obvious way of calling them from the command line. Either this should be imported in an all.py somewhere, or (much preferably) there should be a method of one of the matrix classes that calls it.
comment:8 in reply to: ↑ 7 Changed 9 years ago by
Replying to davidloeffler:
and it seems to silently replace real numbers with rational approximations to them, which is frankly rather weird.
Sorry, that was a mistake in my test script, not in your code. But I still think that the code should do some sanity checks on its input.
comment:9 Changed 9 years ago by
- Description modified (diff)
comment:10 Changed 9 years ago by
- Status changed from needs_work to needs_info
Hello !!
This patch needed to be updated anyway, as it was veeeeery old and many things changed since. I will gladly add a chechking that the matrix is indeed bistochastic if you think it necessary (though I like to think of functions doing just what they are meant to, and not spend too much time checking the user is not doing anything wrong). It is not very long anyway :-)
- Considering how the algorithm works, it does not really care about the base ring. Anyone will work (well, as long as it is completely ordered !), so Reals, Integers, Rationals are all ok. How would you like this to be mentionned ? I never use these types, and I do not know at all how it is usually done.
- The doctests *needed* an optional package. With #8166, they don't anymore, and I will update the patch in consequence :-)
- Sorry about the non-ASCII character !!
- Another place where I wouldn't know how to do otherwise. There are some graph functions which are not method of the Graph object, just because they are too specific to be, and the users can find out about them by reading the reference manual, or the correct module. If it is not the custom in this part of Sage, where would you like to see it ? I have to admit I have no clue... :-)
Thank you for your help !!
Nathann
comment:11 Changed 9 years ago by
I think the standard practice is to have an optional argument "check", which defaults to True but can be set to False if you know your input is valid and you don't want to waste time checking.
Rather than having an explicit list of allowable base rings, I suggest checking that the base ring has a canonical coercion map to RR.
Maybe you could put in a method under (perhaps) sage.matrix.matrix2 that calls this, and cross-reference between the two docstrings.
David
comment:12 Changed 9 years ago by
- Status changed from needs_info to needs_review
Well, it took me some time but.... Would this patch suit your taste ? :-)
Nathann
Changed 9 years ago by
comment:13 Changed 9 years ago by
- Reviewers changed from Mike Hansen to Mike Hansen, David Loeffler
Excellent! I only have one minor suggestion: I think it's also worth checking that the matrix has nonnegative entries. I've added a reviewer patch that makes this change, and also adds a couple more doctests. I'm happy with the code now, modulo these changes; so if you (or anyone else who happens to be reading this) could double-check my second patch, then we can call this a positive review.
comment:14 Changed 9 years ago by
- Status changed from needs_review to positive_review
comment:15 Changed 9 years ago by
(if you have a few seconds for them, by the way ^{}; ... they are very simple and require absolutely no knowledge of graph theory -- #8364 just adds arguments to graph functions that are immediately forwarded to a sub-function, and #8166 merges two functions which were doing the same thing in different ways ) :-)
Nathann
comment:16 Changed 9 years ago by
- Merged in set to sage-4.4.4.alpha0
- Resolution set to fixed
- Status changed from positive_review to closed
Some of doctests had to be marked as optional as they required a linear programming solver.
comment:17 Changed 9 years ago by
I somehow missed the dependence on #8166. I've removed the optional markings from the doctests in this patch.
This patch needs to be updated as there is no max_matching method for graphs.