graph generators - new additions

[rlm]

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.

[rlm]

Some constructions of Chris Godsil, to be transplanted.

[rlm]

Note - Hoffman-Singleton is included in #2765

[chapoton]

Is there still something useful here ?

[ncohen]

Well, I don't even know what the 600-cell is :-D

Nathann

[ncohen]

This being said the code seems to be attached... Looks easy to transform into a real patch. I'll do that right now.

Nathann

[ncohen]

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

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​13b7786

Bad construction of the 600-cell

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​5859da4

trac #2686 good construction of the 600-cell

[chapoton]

Here is a working version, using exactly the description of vertices given by wikipedia.

[ncohen]

Wow cool ! Thanks ! I will compute a nice embedding and finish the patch ;-)

Nathann

[ncohen]

What do you think ? ;-)

Nathann

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​a259216

trac #2686: Two embeddings for the 600-cell graph

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​ba6fc34

trac #2686 last details

[chapoton]

I have corrected two details. This looks goot to me.

What to do now ? Maybe also use this ticket for the 120-cell graph ?

[ncohen]

Well, no problem with that... Do you feel like implementing it ? I will add a nice embedding :-)

Nathann

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​6052742

trac #2686 adding the 120-cell graph

[chapoton]

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 ?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​46e590a

trac 2628: An embedding for the 120-cell

[ncohen]

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

[chapoton]

• 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

[ncohen]

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

[chapoton]

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)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​efec547

trac #2686 fixing doctest

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9ee0824

trac #2686 little changes in 120 cell

[ncohen]

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

[ncohen]

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

[chapoton]

Oh, well, no problem, one can keep the long one. But it needs to be tagged with # long time

[ncohen]

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

[ncohen]

Just did it.

Nathann

---

New commits:

​5f31326

trac #2686: little changes in 120 cell

[chapoton]

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)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​c88c3d1

trac #2686: missing # long time

[ncohen]

Dead right ! It is now fixed.

Nathann

[chapoton]

ok, good enough for me.

[ncohen]

Thaaaaaaaaaanks !

Nathann