Opened 12 years ago

Closed 6 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) Commit: c88c3d163e169d5fdd2ce6e200f8b402ad8eda3a
Dependencies: Stopgaps:

Description (last modified by chapoton)

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)

grfs.sage​ (10.2 KB) - added by rlm 12 years ago.
Some constructions of Chris Godsil, to be transplanted.

Download all attachments as: .zip

Change History (40)

Changed 12 years ago by rlm

Some constructions of Chris Godsil, to be transplanted.

comment:1 Changed 12 years ago by rlm

Note - Hoffman-Singleton is included in #2765

comment:2 Changed 12 years ago by rlm

  • Description modified (diff)

comment:3 Changed 9 years ago by mvngu

  • Description modified (diff)
  • Report Upstream set to N/A

comment:4 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:5 Changed 6 years ago by chapoton

  • Description modified (diff)
  • Keywords graphs added
  • Status changed from new to needs_info

Is there still something useful here ?

comment:6 Changed 6 years ago by ncohen

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

Nathann

comment:7 Changed 6 years ago by 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

comment:8 Changed 6 years ago by ncohen

  • 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 6 years ago by git

  • Commit set to 13b7786b64a23990dc74fc810cbb71c03a84aaa1

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

​13b7786Bad construction of the 600-cell

comment:10 Changed 6 years ago by git

  • Commit changed from 13b7786b64a23990dc74fc810cbb71c03a84aaa1 to 5859da4a18dc97e1f77b141a4a20810a8a635d5e

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

​5859da4trac #2686 good construction of the 600-cell

comment:11 Changed 6 years ago by chapoton

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

comment:12 Changed 6 years ago by ncohen

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

Nathann

comment:13 Changed 6 years ago by ncohen

What do you think ? ;-)

Nathann

comment:14 Changed 6 years ago by git

  • Commit changed from 5859da4a18dc97e1f77b141a4a20810a8a635d5e to a25921694c5e688dba6a67f9dcaf3e4d7abb866a

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

​a259216trac #2686: Two embeddings for the 600-cell graph

comment:15 Changed 6 years ago by git

  • Commit changed from a25921694c5e688dba6a67f9dcaf3e4d7abb866a to ba6fc3437bf5010c337d976465ceacd1ce64277d

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

​ba6fc34trac #2686 last details

comment:16 Changed 6 years ago by 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 ?

comment:17 Changed 6 years ago by ncohen

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

Nathann

comment:18 Changed 6 years ago by git

  • Commit changed from ba6fc3437bf5010c337d976465ceacd1ce64277d to 6052742892e7765f6538c13d410f03a573f46144

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

​6052742trac #2686 adding the 120-cell graph

comment:19 Changed 6 years ago by 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 ?

comment:20 Changed 6 years ago by git

  • Commit changed from 6052742892e7765f6538c13d410f03a573f46144 to 46e590a91ffb1f2a32354b202738799cf8399b29

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

​46e590atrac 2628: An embedding for the 120-cell

comment:21 Changed 6 years ago by 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

Last edited 6 years ago by ncohen (previous) (diff)

comment:22 follow-up: Changed 6 years ago by chapoton

  • with some more work, one can maybe avoid creating duplicate vertices. I will not have time to do that soon.
  • 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 6 years ago by 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

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 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:25 Changed 6 years ago by chapoton

  • 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:

​828af0fBad construction of the 600-cell
​6067f18trac #2686 good construction of the 600-cell
​0f5dccbtrac #2686: Two embeddings for the 600-cell graph
​007dde5trac #2686 last details
​299c340trac #2686 adding the 120-cell graph
​237a53etrac 2628: An embedding for the 120-cell
​902976etrac #2686 just a bit less slow for the 120 cell (but more complicated)

comment:26 Changed 6 years ago by git

  • Commit changed from 902976ee3c3fdba18d94a56c9b72d1dc2d4fbd67 to efec54711a347e981030b4efcfdf556427899e1e

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

​efec547trac #2686 fixing doctest

comment:27 Changed 6 years ago by git

  • Commit changed from efec54711a347e981030b4efcfdf556427899e1e to 9ee0824302c6777c005a5d0533a74708eb7f308f

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

​9ee0824trac #2686 little changes in 120 cell

comment:28 Changed 6 years ago by 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

comment:29 Changed 6 years ago by 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

comment:30 Changed 6 years ago by chapoton

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

comment:31 Changed 6 years ago by 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

comment:32 Changed 6 years ago by ncohen

  • Branch changed from u/chapoton/2686 to public/2686
  • Commit changed from 9ee0824302c6777c005a5d0533a74708eb7f308f to 5f313268137c89da3739a0c291a566175c2ea57a

Just did it.

Nathann

New commits:

​5f31326trac #2686: little changes in 120 cell

comment:33 Changed 6 years ago by 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)

comment:34 Changed 6 years ago by git

  • Commit changed from 5f313268137c89da3739a0c291a566175c2ea57a to c88c3d163e169d5fdd2ce6e200f8b402ad8eda3a

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

​c88c3d1trac #2686: missing # long time

comment:35 Changed 6 years ago by ncohen

Dead right ! It is now fixed.

Nathann

Last edited 6 years ago by ncohen (previous) (diff)

comment:36 Changed 6 years ago by chapoton

  • Authors set to Nathann Cohen
  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok, good enough for me.

comment:37 Changed 6 years ago by ncohen

Thaaaaaaaaaanks !

Nathann

comment:38 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:39 Changed 6 years ago by vbraun

  • Branch changed from public/2686 to c88c3d163e169d5fdd2ce6e200f8b402ad8eda3a
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.