Closed drvinceknight closed 9 years ago
(being curious)
Changed author from Vince Knight to none
Putting to no listed component because truly non fits. Also, author is really for actual author of any changes (which may well be vinceknight! but isn't yet).
Commit: e83553e
Last 10 new commits:
a5b0bd5 | gets large game working |
ca6a1e8 | creates repr function |
a589553 | creates a dictionary function |
d19af1b | fix some pep8 errors |
be8487f | creates latex function |
25f76c8 | Added matching games |
5516fed | Started to write the docs |
8ff811f | HAve first draft of docs built |
2c35bcd | Merge branch '16331' of https://github.com/theref/sage-game-theory into 16331 |
e83553e | Merge branch '16331' into t/16331/game_theory__build_capacity_to_solve_matching_games_in_to_sage_ |
Does this depend on #16466? I'm not sure why it's showing a red branch (doesn't apply cleanly).
Replying to @kcrisman:
Does this depend on #16466? I'm not sure why it's showing a red branch (doesn't apply cleanly).
Hi Karl, this ticket does not at all depend on #16466, the code in here is just a basic implementation of the Gale-Shapley algorithm. #16466 is for #16333, although in fact it's only for a specific optional algorithm in #16333 Not to sure what the red branch means?
This branch (#16331) is self contained (unless we messed up with something).
(Freaky that you got back in touch today as I've just written a blog post trying to encourage reviewers for this particular ticket :)).
Please let me know if there's anything I can help with.
I see the problem - this really seems to depend on #16333. The code probably doesn't, but in your work process I see lots of merging of that branch in. So it's hard to view this and probably the branch for this stuff needs to be redone - in other words,
This branch (#16331) is self contained (unless we messed up with something).
you messed up with something.
Other random comments:
_is_sovled
- really?numer
? I see other little typos like this around (matchin
, bi-partitie
, reviewes
, etc.)_Player
class, for instance). Just because it's 'hidden' doesn't mean it isn't at least minimally tested. Ideally, it's tested with lots of dumb-but-necessary corner cases like empty sets of players and such, but that is more work...That said, the concept is nice - not too much, but enough to be useful, allows strings and integers.
Replying to @kcrisman:
I see the problem - this really seems to depend on #16333. The code probably doesn't, but in your work process I see lots of merging of that branch in. So it's hard to view this and probably the branch for this stuff needs to be redone - in other words,
This branch (#16331) is self contained (unless we messed up with something).
you messed up with something.
Other random comments:
_is_sovled
- really?- What is a
numer
? I see other little typos like this around (matchin
,bi-partitie
,reviewes
, etc.)- Less trivially, there are a lot of methods with no doctests, and some even without documentation (I'm looking at the mysterious
_Player
class, for instance). Just because it's 'hidden' doesn't mean it isn't at least minimally tested. Ideally, it's tested with lots of dumb-but-necessary corner cases like empty sets of players and such, but that is more work...- What happens if you add a suitor but not a reviewer? Maybe those methods should be hidden or even in a different scope.
Eeeesh some of those are embarrassing... As soon as I have a working machine I'll get going on them (probably next week). Not too sure what to do about the git branch issue, will figure it out though. I seem to remember asking someone what was the best way to handle this but we obviously didn't quite get it right...
Thanks again!
Hi Karl,
I've added a lot more docstrings (and incidentally more tests).
Re issue about the branch, I haven't changed anything. Here's the discussion we had on the sage-devel user group when we started working on #16333 after working on #16332 and we weren't too sure about the best way forward when working on a 'family' of tickets:
Would the simplest way forward to be to remove the code relevant to #16333 (but not the git history?)?
Not too sure what the best alternative is... Very happy to be told what to do.
Last 10 new commits:
ad2c738 | More spelling fixes |
ca967f4 | Adding tests |
1028360 | Have tests for bi_partite |
f90f7ce | Have added a test for is_complete |
ec1ed79 | More tests for incomplete |
8d85ce1 | Have written more doctests up until point _sol_dict |
30f7bbb | Test for _sol dict |
afcbe38 | Have added tests and docstrings |
f3f7186 | Have written all docs |
24e80df | Merge branch '16331' of github.com:theref/sage-game-theory into 16331 |
Would the simplest way forward to be to remove the code relevant to #16333 (but not the git history?)?
I'm no git expert either, unfortunately. With the patch-based system that would be very easy to deal with. But right now I can't even view the branch on Trac!
Replying to @drvinceknight:
Re issue about the branch, I haven't changed anything. Here's the discussion we had on the sage-devel user group when we started working on #16333 after working on #16332 and we weren't too sure about the best way forward when working on a 'family' of tickets:
Would the simplest way forward to be to remove the code relevant to #16333 (but not the git history?)?
The easiest way to delete the code would be to delete the code (and commit the change). The log is there to show your workflow (because maybe you need some of that code for this ticket without #16333 [it's a hypothetical FYI]).
Also the branch field might be red even when the branch merges cleanly because the trac plugin can be more strict than git's merge (and there might be something related with #16332 being merged into develop
shrugs).
Branch pushed to git repo; I updated commit sha1. New commits:
40d4cfa | Deleting files from other tickets |
Replying to @tscrim:
Replying to @drvinceknight:
Re issue about the branch, I haven't changed anything. Here's the discussion we had on the sage-devel user group when we started working on #16333 after working on #16332 and we weren't too sure about the best way forward when working on a 'family' of tickets:
Would the simplest way forward to be to remove the code relevant to #16333 (but not the git history?)?
The easiest way to delete the code would be to delete the code (and commit the change). The log is there to show your workflow (because maybe you need some of that code for this ticket without #16333 [it's a hypothetical FYI]).
I've just deleted the code not relevant to this branch and committed. Not sure if this fixes the issue?
I've just deleted the code not relevant to this branch and committed. Not sure if this fixes the issue?
Sadly not.
Replying to @kcrisman:
I've just deleted the code not relevant to this branch and committed. Not sure if this fixes the issue?
Sadly not.
I'm not too sure I understand, if you pull this branch can you not see the code?
Please, have a look at http://git-scm.com/book/en/Git-Tools-Rewriting-History
It does not makes sense to cancel commits by adding another commit!!
EDIT: and you should not merge a beta release if there is no need to. There is a need only if there is a non-trivial conflict. Now there are 10+ commits in this ticket and there are completely screwed up by several merge of beta releases...
Vincent
I don't think I was trying to cancel a commit. I didn't want to lose/rewrite any of the history as I'm not entirely sure what is wrong and have no idea what is required to fix it.
Replying to @drvinceknight:
I don't think I was trying to cancel a commit. I didn't want to lose/rewrite any of the history as I'm not entirely sure what is wrong and have no idea what is required to fix it.
Start a new branch whose ends correspond to what you want. The reviewer does not care about your workflow. He only needs a clean view on what has changed! This is ideally done with one commit.
Then during the review process, you might have some remarks from the reviewer (maybe even a commit) and you might integrate it to the branch. You provide additional changes in that commit. And you go on until both the reviewer(s) and you agreed.
Vincent
Replying to @videlec:
Please, have a look at http://git-scm.com/book/en/Git-Tools-Rewriting-History
It does not makes sense to cancel commits by adding another commit!!
EDIT: and you should not merge a beta release if there is no need to. There is a need only if there is a non-trivial conflict. Now there are 10+ commits in this ticket and there are completely screwed up by several merge of beta releases...
I have no idea how we did that. We very aware that this mess could happen and tried our best to ask around before starting this as to how to avoid it... Is the best way forward to just push the code from the HEAD of this branch on to a new branch? Would this require a new ticket on trac?
Very eager to follow whatever advice/guidance. Is it worth throwing this discussion on the discussion group?
Vincent
Replying to @videlec:
Replying to @drvinceknight:
I don't think I was trying to cancel a commit. I didn't want to lose/rewrite any of the history as I'm not entirely sure what is wrong and have no idea what is required to fix it.
Start a new branch whose ends correspond to what you want. The reviewer does not care about your workflow. He only needs a clean view on what has changed! This is ideally done with one commit.
Then during the review process, you might have some remarks from the reviewer (maybe even a commit) and you might integrate it to the branch. You provide additional changes in that commit. And you go on until both the reviewer(s) and you agreed.
Ok. To fix the situation now, do I need to create a new ticket to in effect overwrite this ticket or would a git push from a newly created branch do the trick?
Vincent
Replying to @drvinceknight:
Replying to @videlec:
Replying to @drvinceknight:
I don't think I was trying to cancel a commit. I didn't want to lose/rewrite any of the history as I'm not entirely sure what is wrong and have no idea what is required to fix it.
Start a new branch whose ends correspond to what you want. The reviewer does not care about your workflow. He only needs a clean view on what has changed! This is ideally done with one commit.
Then during the review process, you might have some remarks from the reviewer (maybe even a commit) and you might integrate it to the branch. You provide additional changes in that commit. And you go on until both the reviewer(s) and you agreed.
Ok. To fix the situation now, do I need to create a new ticket to in effect overwrite this ticket or would a git push from a newly created branch do the trick?
No, no, no. Please, do not create any additional tickets. There is no need.
Git (where branch live) and trac (where tickets live) are two different things. You can create as many branches as you like, this is your space. But on trac it is one task for one ticket and it is public.
You should start a new git branch that would be a clean version of the one you proposed for that ticket. Then you should link the branch to this ticket (in the field "branch"). How do you use git? Through the "sage -devel" scripts? The "git trac" command? git and only git?
EDIT: a git push is fine if you provide the option "-f" (i.e. the remote git will forget about the previous position of the branch)
Vincent
Replying to @videlec:
Replying to @drvinceknight:
Replying to @videlec:
Replying to @drvinceknight:
I don't think I was trying to cancel a commit. I didn't want to lose/rewrite any of the history as I'm not entirely sure what is wrong and have no idea what is required to fix it.
Start a new branch whose ends correspond to what you want. The reviewer does not care about your workflow. He only needs a clean view on what has changed! This is ideally done with one commit.
Then during the review process, you might have some remarks from the reviewer (maybe even a commit) and you might integrate it to the branch. You provide additional changes in that commit. And you go on until both the reviewer(s) and you agreed.
Ok. To fix the situation now, do I need to create a new ticket to in effect overwrite this ticket or would a git push from a newly created branch do the trick?
No, no, no. Please, do not create any additional tickets. There is no need.
Cool, I didn't think so.
Git (where branch live) and trac (where tickets live) are two different things. You can create as many branches as you like, this is your space. But on trac it is one task for one ticket and it is public.
You should start a new git branch that would be a clean version of the one you proposed for that ticket. Then you should link the branch to this ticket (in the field "branch"). How do you use git? Through the "sage -devel" scripts? The "git trac" command? git and only git?
I use git trac.
So to summarise what I will/need to do:
Is that right?
Thanks for the help, I think the main problem came from working on multiple (related) tickets in quick succession and branching from completed tickets instead of the master branch.
Vincent
Replying to @drvinceknight:
So to summarise what I will/need to do:
- checkout a 'clean' version from the Sage master branch
Nope. The best would be the last "develop" branch (which is sage.6.4.beta2)
- add in one commit the code relevant to this ticket (in effect a single python file)
yes
- push to this ticket
yes
Thanks for the help, I think the main problem came from working on multiple (related) tickets in quick succession and branching from completed tickets instead of the master branch.
I agree this is always a mess. What I do is that I create a complete order on my tickets, i.e. ticket1 comes before ticket2, which comes before ticket3... Then I base ticket2 at the end of ticket1 and ticket3 and the end of ticket2. With the link I provided to rewrite history, it helps you to keep everything clean even if you have to do some rebase because of the reviews and/or some new beta release. Note that it might be helpful to the reviewer to add commit lines that looks like "ticket #XXX: change a doctest".
Vincent
Thanks, I'll do that later this evening!
Replying to @videlec:
Please, have a look at http://git-scm.com/book/en/Git-Tools-Rewriting-History
It does not makes sense to cancel commits by adding another commit!!
Yes it does; it is good git workflow in order to see what has done. I strongly encourage it. It is bad to rewrite history in released branches that people might have pulled. This includes forced pushes (the -f
option).
Again, the proper way to use git is to make more commits which revert changes!!
EDIT: and you should not merge a beta release if there is no need to. There is a need only if there is a non-trivial conflict. Now there are 10+ commits in this ticket and there are completely screwed up by several merge of beta releases...
There is, it's a PITA to rebuild sage when switching branches and the merge commits do not hurt anything. Look at the differences between the beta versions using git diff
. There are also easy options to see the commits which are not in develop
by
git log --no-merges ^develop <branch>
Quit thinking commits are like patches, they are not. Git workflow actually recommends lots of little logical commits (I'm actually somewhat bad about this).
In conclusion, this branch is fine (up to merge conflicts).
In conclusion, this branch is fine (up to merge conflicts).
So what should I do? (Happy to do anything)
Replying to @tscrim:
Replying to @videlec:
Please, have a look at http://git-scm.com/book/en/Git-Tools-Rewriting-History
It does not makes sense to cancel commits by adding another commit!!
Yes it does; it is good git workflow in order to see what has done. I strongly encourage it. It is bad to rewrite history in released branches that people might have pulled. This includes forced pushes (the
-f
option).
If somebody pulled it, he might have noticed that the history is dirty! My claim was about how people should write commits before submission to trac. You have the right to make a mistake and to change it. Nevertheless the branch has not disappeared from git so people are free to use it. If anybody has based his work on the last commit of a development branch without acknowledging the author it was just a stupid idea.
I mostly agree with http://www.mail-archive.com/dri-devel@lists.sourceforge.net/msg39091.html about clean history.
Again, the proper way to use git is to make more commits which revert changes!!
No. The timeline of a ticket is most of the time the timeline of a commit (except very exceptional cases). Reverting changes can be done at home (and it is good to do it) but not on trac.
If I pull I really do not want to see
commit 1: make a change in toto.py
commit 2: make a change in foo.py
commit 3: cancel a change from commit 1
commit 4: cancel a change from commit 2
commit 5: redo some changes introduced from commit 3
...
perhaps you do, but personally I will not review a ticket with 10+ commits.
EDIT: and you should not merge a beta release if there is no need to. There is a need only if there is a non-trivial conflict. Now there are 10+ commits in this ticket and there are completely screwed up by several merge of beta releases...
There is, it's a PITA to rebuild sage when switching branches and the merge commits do not hurt anything. Look at the differences between the beta versions using
git diff
. There are also easy options to see the commits which are not indevelop
bygit log --no-merges ^develop
I agree that it is a PITA. But, it is not because of git but because of the build system. There is nothing wrong during the review process to merge locally the branch you are reviewing into the develop branch.
Quit thinking commits are like patches, they are not. Git workflow actually recommends lots of little logical commits (I'm actually somewhat bad about this).
I agree but they should reflect the logic of the code implemented and not the author workflow.
Vincent
I want to say that in this case it does make sense to have a lot of commits for two reasons:
Replying to @kcrisman:
I want to say that in this case it does make sense to have a lot of commits for two reasons:
I should not have complained by the number of commits but rather about the number of useless commits.
- Implementing from scratch this functionality, like for sage-matroid
Sage-matroids was about 10K lines of code!
- Two different authors, and ideally one wants to keep their contributions clear
+1. To each commit is associated an author and we really do not want to fusion commits from different authors.
But again, my main concern is just that I am not git wizard enough to view the appropriate changes. It sounds like one will want to start from (say) the latest beta release and add the relevant code here. (That's good, because the original directory src/sage/game_theory/all.py is already in, I believe.)
At least we end up to the same conclusion: the branch linked to a simple ticket should be simple enough to have a clear view on what have changed.
Vincent
I want to say that in this case it does make sense to have a lot of commits for two reasons:
- Implementing from scratch this functionality, like for sage-matroid
- Two different authors, and ideally one wants to keep their contributions clear
If I understand correctly what Vincent says, he means that the history of a git branch should be made to ease the reviewer's job.
The reviewer wants to check that everything does its job and is implemented correctly. It does not help if what is done in one commit is undone in the next. What can help him is when each commit has a clearly defined task and does it well. That way the branch is easier to review.
What you do on your own computer is your own affair, but when you push to a public branch linked to a ticket you are already 'sharing' code, and it is better if the code you share is meant to be read.
Again: apologies for making this ticket so hard to review. I'm still unsure as to what I should do from here if anyone has any suggestions?
I know this will sound snarky/condescending, but I do honestly mean it. You should probably learn more git in order to be a better reviewer.
There is a good reason to merge the latest develop version, you never know what exactly has changed. Unless you're relying only on python (which I highly doubt is the case), you can get into subtle changes which can break your program (for example, output format was changed from a list into a tuple; I've been bitten by this).
For the most part I don't look at the commit history when reviewing a ticket, instead I look at the overall diff from develop/dependencies. Afterwards if additional changes are made, then it's commits, but I'd rather see the forest than tree by tree.
IMO, useless commits are ones which merge in individual unrelated tickets (for example, one on elliptic curves), or merge in commits from a dependency 1 by 1 which don't impact the current ticket.
From Vincent's example of undoing all changes immediately and pushed to trac, then you can consider starting a new branch in those cases as there is nothing inbetween (and changing the branch field on the ticket). However if there are additional commits, you either might want to cherry-pick them in or just continue on. Sometimes you realize things are unneeded and having that in the history is a good note. Nevertheless partial commit revisions deserve their own commits. As Nathann said, it's the code you want the reviewer to read, not the history. (Although when it comes to design decisions, especially if the author is not around, having the workflow in the history can give some insight.)
Again, commits are not the patches of Hg.
I'm happy to review of this ticket since I have no qualms about the current branch (although if Vince can merge in develop and push, I'd appreciate that).
Replying to @tscrim:
I know this will sound snarky/condescending, but I do honestly mean it. You should probably learn more git in order to be a better reviewer.
You should also learn git to become a better contributor! The reviewer is doing a kind of sacrifice, so there is no way to discuss that the effort should be done from the contributor side (of course ignore that for first contributions).
There is a good reason to merge the latest develop version, you never know what exactly has changed. Unless you're relying only on python (which I highly doubt is the case), you can get into subtle changes which can break your program (for example, output format was changed from a list into a tuple; I've been bitten by this).
Right. For me a doctest issue is also a merge conflict but not in the git sense. There are also a good reason to not do it: keep the history clean.
For the most part I don't look at the commit history when reviewing a ticket, instead I look at the overall diff from develop/dependencies. Afterwards if additional changes are made, then it's commits, but I'd rather see the forest than tree by tree.
The history is good to help the reviewer understands what the modifications provided by a branch does. You are of course allowed to ignore that. I really think that I am a git person and you are the hg person if you work that way. A global diff can be really ugly even if the commits are very nice (just have a look at #16884).
Again, commits are not the patches of Hg.
Hum, each commit is a diff and a patch is a diff. So technically speaking they are. Now, if you want to argue about the philosophy of what a commit should be and what a patch should be it has nothing to do with the softwares but how you use them... and you are free to use them the way you want!
By the way, I would like to stop that discussion on the ticket as it spoils the Game theory purpose of it!
Best, Vincent
I know this will sound snarky/condescending, but I do honestly mean it. You should probably learn more git in order to be a better reviewer.
You should also learn git to become a better contributor! The reviewer is doing a kind of sacrifice, so there is no way to discuss that the effort should be done from the contributor side (of course ignore that for first contributions).
Naturally both are true, but there is also the point that, in this case, both reviewer and contributor have other duties than learning lots of git.
By the way, I would like to stop that discussion on the ticket as it spoils the Game theory purpose of it!
Yes, probably true. Anyway, Vince K., it looks like I will probably have to wait until next week to figure out how to do this without breaking something, sorry :( because I do want to look at it carefully.
I'm happy to review of this ticket since I have no qualms about the current branch (although if Vince can merge in develop and push, I'd appreciate that).
Thanks tscrim. I have just pushed a merged version.
Apologies all again for the confusion/mess. I'm going away for 4 days (no internet access) so won't be able to address anything directly but will do so on Monday.
Thank you all for your time looking at this.
Green! Still depends on #16333 I guess. Have a great trip!
I just typed in a truly jumbo list of detailed comments, and then Trac logged me out and I lost them all. I'm not going to try again now. Short version is that there are lots of small questions I have, three typos, and then the big one is whether all this infrastructure (like _Player
) is really necessary to keep track of the info in question.
Aargh.
Ok, take two. I will remember to Ctrl-C first this time.
Typos:
extended Gale Shapley algorithm
should have a hyphenof in a population
has an extra wordrank their preference
should be preferences
?a stable matchin
should have a g
.Further comment: all the below is more Python, and not mathematics. I have not checked the actual G-S algorithm is correct, though I doubt that will take long to do. But it won't happen this time.
Comments I could reconstruct:
sage: m.solve()
{'A': ['J'],
'C': ['K'],
'B': ['M'],
'D': ['L'],
'K': ['C'],
'J': ['A'],
'M': ['B'],
'L': ['D']}
maybe instead
sage: m.solve()
{'A': ['J'],
'C': ['K'],
'B': ['M'],
'D': ['L'],
and then it will be easy to tell if it's inverted...
_repr_
really shouldn't have it possible to have something other than $2n$. I'm not asking to check the _is_complete
at that point, but at least they should be same number can be checked.latex
- I'm not sure this is standard notation. 4=\{(1, 0)\}
equals sign?game_to_dict
I just don't know whether one should have "undicted" the game in the first place. It seems like a lot of trouble to redictify the game. Maybe the data should be stored differently in any event. Constructing a whole _Player
for each player seems like a lot of overhead. They have no external existence._is_solved
? It just seems odd that those things might be directly accessible.{3: (0, 2, 1)
was changed to {3: (0, 2)
it would still raise the error but seem "complete" in some sense...3, 'Fred'
and now want to automatically add a third one.) I don't know the right answer here.sol_dict
should be an attribute and not a method. Especially since you're not really supposed to access it publicly._Player
class, needs doctests :)Replying to @kcrisman:
Comments I could reconstruct:
- Should it be a game of 2n players or size n? Is there a standard terminology?
- Since the matching $M$ is bijective and the algorithm is not symmetric, should the solution really have each match twice?
sage: m.solve() {'A': ['J'], 'C': ['K'], 'B': ['M'], 'D': ['L'], 'K': ['C'], 'J': ['A'], 'M': ['B'], 'L': ['D']}
maybe instead
sage: m.solve() {'A': ['J'], 'C': ['K'], 'B': ['M'], 'D': ['L'],
and then it will be easy to tell if it's inverted...
_repr_
really shouldn't have it possible to have something other than $2n$. I'm not asking to check the_is_complete
at that point, but at least they should be same number can be checked.latex
- I'm not sure this is standard notation.4=\{(1, 0)\}
equals sign?- in
game_to_dict
I just don't know whether one should have "undicted" the game in the first place. It seems like a lot of trouble to redictify the game. Maybe the data should be stored differently in any event. Constructing a whole_Player
for each player seems like a lot of overhead. They have no external existence.- Is it possible for someone to access all the partners and pref and such in such a way as to mess with
_is_solved
? It just seems odd that those things might be directly accessible.- I think another word than 'complete' is needed in checking completeness, because if
{3: (0, 2, 1)
was changed to{3: (0, 2)
it would still raise the error but seem "complete" in some sense...- What if the automatically added suitor name is already in use? (Say, we already have names
3, 'Fred'
and now want to automatically add a third one.) I don't know the right answer here.- Any rationale for the autoprefs?
- I wonder if
sol_dict
should be an attribute and not a method. Especially since you're not really supposed to access it publicly.- And of course, if you REALLY want to use the
_Player
class, needs doctests :)
Thanks Karl, will read through these carefully and work on them sometime this week.
Branch pushed to git repo; I updated commit sha1. New commits:
0a8aea0 | trying to introduce some game theory stuff |
6f508ce | Changed `_repr_` method to clarify size of game |
27ba15d | Fixed LaTeX method to have arrow instead of equals sign |
bf22249 | Merge branch '16331' into dev |
31734a4 | Solve method now returns only reviewers as key |
00a1975 | Solve method now returns only reviewers as key |
a1d2bf9 | sol_dict is now an attribute and not a method |
cdcdea0 | reviewer and suitor dicts are now stored attributes on initialisation, also have error if trying to add reviewer or suitor with name that is already used |
e9edce6 | Removed typos |
Include class for matching games as well as implementations of the Gale-Shapley algorithm.
Should be efficient to code in pure python/cython. Various methods to include possibility to give suitor/reviewer optimal matchings. Also, make use of graph plotting to represent game.
Possible extensions could include variations of matching games (indifference etc...).
Component: game theory
Keywords: Matching Games
Author: Vince Knight, James Campbell
Branch/Commit:
f9388c7
Reviewer: Karl-Dieter Crisman, Travis Scrimshaw
Issue created by migration from https://trac.sagemath.org/ticket/16331