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:  sage6.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)
 600cell
 120cell
 200cell
 etc
See also ticket #9136.
Attachments (1)
Change History (40)
Changed 13 years ago by
comment:1 Changed 13 years ago by
Note  HoffmanSingleton 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 sage5.11 to sage5.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 600cell 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 600cell

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 600cell

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 600cell 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 120cell 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 120cell 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 120cell

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 followup: ↓ 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 200cell 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 200cell 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 sage6.1 to sage6.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 (nonfastforward updates were rejected)
I have made a more complicated algo for the 120cell 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 600cell

6067f18  trac #2686 good construction of the 600cell

0f5dccb  trac #2686: Two embeddings for the 600cell graph

007dde5  trac #2686 last details

299c340  trac #2686 adding the 120cell graph

237a53e  trac 2628: An embedding for the 120cell

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 120cell, 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 sage6.2 to sage6.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.