Opened 13 years ago
Closed 7 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 13 years ago by
comment:1 Changed 13 years ago by
Note - Hoffman-Singleton is included in #2765
comment:2 Changed 13 years ago by
- Description modified (diff)
comment:3 Changed 10 years ago by
- Description modified (diff)
- Report Upstream set to N/A
comment:4 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:5 Changed 7 years ago by
- Description modified (diff)
- Keywords graphs added
- Status changed from new to needs_info
Is there still something useful here ?
comment:6 Changed 7 years ago by
Well, I don't even know what the 600-cell is :-D
Nathann
comment:7 Changed 7 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 7 years ago by
- Branch set to 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 7 years ago by
- Commit set to 13b7786b64a23990dc74fc810cbb71c03a84aaa1
Branch pushed to git repo; I updated commit sha1. New commits:
13b7786 | Bad construction of the 600-cell
|
comment:10 Changed 7 years ago by
- Commit changed from 13b7786b64a23990dc74fc810cbb71c03a84aaa1 to 5859da4a18dc97e1f77b141a4a20810a8a635d5e
Branch pushed to git repo; I updated commit sha1. New commits:
5859da4 | trac #2686 good construction of the 600-cell
|
comment:11 Changed 7 years ago by
Here is a working version, using exactly the description of vertices given by wikipedia.
comment:12 Changed 7 years ago by
Wow cool ! Thanks ! I will compute a nice embedding and finish the patch ;-)
Nathann
comment:13 Changed 7 years ago by
What do you think ? ;-)
Nathann
comment:14 Changed 7 years ago by
- Commit changed from 5859da4a18dc97e1f77b141a4a20810a8a635d5e to 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 7 years ago by
- Commit changed from a25921694c5e688dba6a67f9dcaf3e4d7abb866a to ba6fc3437bf5010c337d976465ceacd1ce64277d
Branch pushed to git repo; I updated commit sha1. New commits:
ba6fc34 | trac #2686 last details
|
comment:16 Changed 7 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 7 years ago by
Well, no problem with that... Do you feel like implementing it ? I will add a nice embedding :-)
Nathann
comment:18 Changed 7 years ago by
- Commit changed from ba6fc3437bf5010c337d976465ceacd1ce64277d to 6052742892e7765f6538c13d410f03a573f46144
Branch pushed to git repo; I updated commit sha1. New commits:
6052742 | trac #2686 adding the 120-cell graph
|
comment:19 Changed 7 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 7 years ago by
- Commit changed from 6052742892e7765f6538c13d410f03a573f46144 to 46e590a91ffb1f2a32354b202738799cf8399b29
Branch pushed to git repo; I updated commit sha1. New commits:
46e590a | trac 2628: An embedding for the 120-cell
|
comment:21 Changed 7 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 7 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 in reply to: ↑ 22 Changed 7 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 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:25 Changed 7 years ago by
- Branch changed from public/2686 to u/chapoton/2686
- Commit changed from 46e590a91ffb1f2a32354b202738799cf8399b29 to 902976ee3c3fdba18d94a56c9b72d1dc2d4fbd67
- Status changed from needs_info to 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 7 years ago by
- Commit changed from 902976ee3c3fdba18d94a56c9b72d1dc2d4fbd67 to efec54711a347e981030b4efcfdf556427899e1e
Branch pushed to git repo; I updated commit sha1. New commits:
efec547 | trac #2686 fixing doctest
|
comment:27 Changed 7 years ago by
- Commit changed from efec54711a347e981030b4efcfdf556427899e1e to 9ee0824302c6777c005a5d0533a74708eb7f308f
Branch pushed to git repo; I updated commit sha1. New commits:
9ee0824 | trac #2686 little changes in 120 cell
|
comment:28 Changed 7 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 7 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 7 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 7 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 7 years ago by
- Branch changed from u/chapoton/2686 to public/2686
- Commit changed from 9ee0824302c6777c005a5d0533a74708eb7f308f to 5f313268137c89da3739a0c291a566175c2ea57a
comment:33 Changed 7 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 7 years ago by
- Commit changed from 5f313268137c89da3739a0c291a566175c2ea57a to c88c3d163e169d5fdd2ce6e200f8b402ad8eda3a
Branch pushed to git repo; I updated commit sha1. New commits:
c88c3d1 | trac #2686: missing # long time
|
comment:35 Changed 7 years ago by
Dead right ! It is now fixed.
Nathann
comment:36 Changed 7 years ago by
- Reviewers set to Frédéric Chapoton
- Status changed from needs_review to positive_review
ok, good enough for me.
comment:37 Changed 7 years ago by
Thaaaaaaaaaanks !
Nathann
comment:38 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:39 Changed 7 years ago by
- Branch changed from public/2686 to c88c3d163e169d5fdd2ce6e200f8b402ad8eda3a
- Resolution set to fixed
- Status changed from positive_review to closed
Some constructions of Chris Godsil, to be transplanted.