Opened 15 years ago
Closed 9 years ago
#2686 closed enhancement (fixed)
graph generators - new additions
Reported by: | rlm | Owned by: | rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-6.3 |
Component: | graph theory | Keywords: | graphs |
Cc: | Merged in: | ||
Authors: | Nathann Cohen | Reviewers: | Frédéric Chapoton |
Report Upstream: | N/A | Work issues: | |
Branch: | c88c3d1 (Commits, GitHub, GitLab) | Commit: | c88c3d163e169d5fdd2ce6e200f8b402ad8eda3a |
Dependencies: | Stopgaps: |
Description (last modified by )
Contains code for the following graphs
- Paley (done)
- Higman Sims (done)
- Johnson (done)
- Kneser (done)
- Coxeter (done)
- Schlaefli (done)
- Clebsch (done)
- Hoffman Singleton (done)
- 600-cell
- 120-cell
- 200-cell
- etc
See also ticket #9136.
Attachments (1)
Change History (40)
Changed 15 years ago by
comment:2 Changed 14 years ago by
Description: | modified (diff) |
---|
comment:3 Changed 12 years ago by
Description: | modified (diff) |
---|---|
Report Upstream: | → N/A |
comment:4 Changed 9 years ago by
Milestone: | sage-5.11 → sage-5.12 |
---|
comment:5 Changed 9 years ago by
Description: | modified (diff) |
---|---|
Keywords: | graphs added |
Status: | new → needs_info |
Is there still something useful here ?
comment:7 Changed 9 years ago by
This being said the code seems to be attached... Looks easy to transform into a real patch. I'll do that right now.
Nathann
comment:8 Changed 9 years ago by
Branch: | → public/2686 |
---|
Well, I just used the code above to build a 600 cell and the construction seems wrong for the number of edges should be 720 according to Wikipedia and is 3168 in Sage.
Sooooooo well, if somebody knows what is wrong ... (given that I don't get a line of what the code does :-P
)
Nathann
comment:9 Changed 9 years ago by
Commit: | → 13b7786b64a23990dc74fc810cbb71c03a84aaa1 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
13b7786 | Bad construction of the 600-cell
|
comment:10 Changed 9 years ago by
Commit: | 13b7786b64a23990dc74fc810cbb71c03a84aaa1 → 5859da4a18dc97e1f77b141a4a20810a8a635d5e |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
5859da4 | trac #2686 good construction of the 600-cell
|
comment:11 Changed 9 years ago by
Here is a working version, using exactly the description of vertices given by wikipedia.
comment:12 Changed 9 years ago by
Wow cool ! Thanks ! I will compute a nice embedding and finish the patch ;-)
Nathann
comment:14 Changed 9 years ago by
Commit: | 5859da4a18dc97e1f77b141a4a20810a8a635d5e → a25921694c5e688dba6a67f9dcaf3e4d7abb866a |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
a259216 | trac #2686: Two embeddings for the 600-cell graph
|
comment:15 Changed 9 years ago by
Commit: | a25921694c5e688dba6a67f9dcaf3e4d7abb866a → ba6fc3437bf5010c337d976465ceacd1ce64277d |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
ba6fc34 | trac #2686 last details
|
comment:16 Changed 9 years ago by
I have corrected two details. This looks goot to me.
What to do now ? Maybe also use this ticket for the 120-cell graph ?
comment:17 Changed 9 years ago by
Well, no problem with that... Do you feel like implementing it ? I will add a nice embedding :-)
Nathann
comment:18 Changed 9 years ago by
Commit: | ba6fc3437bf5010c337d976465ceacd1ce64277d → 6052742892e7765f6538c13d410f03a573f46144 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
6052742 | trac #2686 adding the 120-cell graph
|
comment:19 Changed 9 years ago by
Ok, here is a try. I am not very happy with the efficiency (I had to use Set)
Another question : Cell600 and Cell120 do not sound very good, find better names ?
comment:20 Changed 9 years ago by
Commit: | 6052742892e7765f6538c13d410f03a573f46144 → 46e590a91ffb1f2a32354b202738799cf8399b29 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
46e590a | trac 2628: An embedding for the 120-cell
|
comment:21 Changed 9 years ago by
Hmmmmmm... Well, I removed set and used frozenset instead but it does not change much. And I don't know what to do with the names either : it just can't begin with a number because of Python, so it looks like it is the best we can do :-/
Nathann
comment:22 follow-up: 23 Changed 9 years ago by
- with some more work, one can maybe avoid creating duplicate vertices. I will not have time to do that soon.
- for the name, one could maybe use SixHundredCell? and OneHundredTwentyCell? (like they do in some other very expensive stuff named
M*********a
)
- I have never heard of the 200-cell before. One should look for references.
- One still has to make sure that nothing else useful is still hidden there
comment:23 Changed 9 years ago by
Hellooooooo !
- with some more work, one can maybe avoid creating duplicate vertices. I will not have time to do that soon.
Well.. It's a bit slow but it isn't really the kind of function that is called very often in a code :-P
- for the name, one could maybe use SixHundredCell? and OneHundredTwentyCell? (like they do in some other very expensive stuff named
M*********a
)
Tastes... Honestly I think that Cell<n>
is still easier to find. Plus you cannot build Cell600
without learning that Cell120
is implemented too.
- I have never heard of the 200-cell before. One should look for references.
Well even the 600 was news to me :-P
- One still has to make sure that nothing else useful is still hidden there
In the code ? I just looked at the functions and it looks like we already have all that is contained there.
Nathann
comment:24 Changed 9 years ago by
Milestone: | sage-6.1 → sage-6.2 |
---|
comment:25 Changed 9 years ago by
Branch: | public/2686 → u/chapoton/2686 |
---|---|
Commit: | 46e590a91ffb1f2a32354b202738799cf8399b29 → 902976ee3c3fdba18d94a56c9b72d1dc2d4fbd67 |
Status: | needs_info → needs_review |
Hello,
I have replaced public/2686 by my branch because git was complaining (non-fast-forward updates were rejected)
I have made a more complicated algo for the 120-cell which is a bit less slow, but still rather slow.. I am not sure that was worth the time spent.
New commits:
828af0f | Bad construction of the 600-cell
|
6067f18 | trac #2686 good construction of the 600-cell
|
0f5dccb | trac #2686: Two embeddings for the 600-cell graph
|
007dde5 | trac #2686 last details
|
299c340 | trac #2686 adding the 120-cell graph
|
237a53e | trac 2628: An embedding for the 120-cell
|
902976e | trac #2686 just a bit less slow for the 120 cell (but more complicated)
|
comment:26 Changed 9 years ago by
Commit: | 902976ee3c3fdba18d94a56c9b72d1dc2d4fbd67 → efec54711a347e981030b4efcfdf556427899e1e |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
efec547 | trac #2686 fixing doctest
|
comment:27 Changed 9 years ago by
Commit: | efec54711a347e981030b4efcfdf556427899e1e → 9ee0824302c6777c005a5d0533a74708eb7f308f |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
9ee0824 | trac #2686 little changes in 120 cell
|
comment:28 Changed 9 years ago by
Yooooooooo !!
Well, I do not mind much for as long as the graph can be built, this is very unlikely to become the critical operation of any code in the future :-D
If you have problems when pushing a branch, use git push -f
. This will force the push operation, erasing what was on the othe side if necessary. Weird that you needed it here, though.
Oh. I see. You rebase the whole branch. You should not do that :-/
It is much cleaner to "merge" the latest develop release into the branch. This way you just add another commit in the branch which merges it with the latest release, and there is no rebasing going on, while you "copied" all commits on top of the latest release.
It's not a problem if you rewrote history here, however, as nobody based a branch on our earlier commits.
I just applied your branch, and I have to recompile Sage as a result as I was working on an earlier beta. Will check that tests pass, and then give this ticket a positive review.
Nathann
comment:29 Changed 9 years ago by
Argggggggg... Okay I had not looked closely at the code, but really it is more complicated... You added a lot of code ! :-/
Would you mind including the former version instead ? The speed really isn't a problem here :-/
Nathann
comment:30 Changed 9 years ago by
Oh, well, no problem, one can keep the long one. But it needs to be tagged with # long time
comment:31 Changed 9 years ago by
Okay, thanks ! Do you feel like playing with git a bit, creating new branches and moving your # long time
commit a bit lower in the history ? Or do I do that, and you will review it ? ;-)
Nathann
comment:32 Changed 9 years ago by
Branch: | u/chapoton/2686 → public/2686 |
---|---|
Commit: | 9ee0824302c6777c005a5d0533a74708eb7f308f → 5f313268137c89da3739a0c291a566175c2ea57a |
comment:33 Changed 9 years ago by
Hello,
it seems that you added long time
on the quickest one only (600 cell). The really bad guy is the 120-cell, which takes almost 10s on my computer (and 6s with my enhanced but abandoned code)
comment:34 Changed 9 years ago by
Commit: | 5f313268137c89da3739a0c291a566175c2ea57a → c88c3d163e169d5fdd2ce6e200f8b402ad8eda3a |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
c88c3d1 | trac #2686: missing # long time
|
comment:36 Changed 9 years ago by
Authors: | → Nathann Cohen |
---|---|
Reviewers: | → Frédéric Chapoton |
Status: | needs_review → positive_review |
ok, good enough for me.
comment:38 Changed 9 years ago by
Milestone: | sage-6.2 → sage-6.3 |
---|
comment:39 Changed 9 years ago by
Branch: | public/2686 → c88c3d163e169d5fdd2ce6e200f8b402ad8eda3a |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
Some constructions of Chris Godsil, to be transplanted.