Opened 10 years ago

Closed 6 years ago

#9136 closed enhancement (fixed)

more named graphs

Reported by: mvngu Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: graph theory Keywords:
Cc: brunellus Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

The database of common graphs currently implements lots of named graphs. Below is a list of named graphs to add to that database. See also ticket #2686:

  1. Bidiakis cube --- #10307
  2. Brinkmann graph --- #10310
  3. Butterfly graph --- #10313
  4. Friendship graph --- #10315
  5. Dürer graph --- #10316
  6. Errera graph --- #10321
  7. Franklin graph --- #10322
  8. Goldner–Harary graph --- #10329
  9. Grötzsch graph --- #10330
  10. Herschel graph --- #10337
  11. Moser spindle --- #10338
  12. Balaban 10-cage --- #12942
  13. Balaban 11-cage --- #12945
  14. Double-star snark --- #12952
  15. Ellingham–Horton graph --- #12989
  16. fullerene graphs --- #14618
  17. Harries graph--- #12952
  18. Harries–Wong graph --- #12980
  19. Hoffman graph --- #13038
  20. Holt graph --- #13411
  21. Horton graph --- #15049
  22. Kittell graph --- #15049
  23. Markström graph --- #15049
  24. McGee graph --- #12982
  25. Meredith graph -- #15044
  26. Sousselier graph --- #15049
  27. Poussin graph --- #15049
  28. Robertson graph --- #14911
  29. Tutte's fragment
  30. Tutte graph --- #15049
  31. Young–Fibonacci lattice
  32. Wagner graph --- #12982
  33. Wiener-Araya graph -- #15049
  34. Clebsch graph --- #13038
  35. Hall–Janko graph --- #13058
  36. Paley graph --- #13088
  37. Shrikhande graph --- #10781
  38. Möbius–Kantor graph (done)
  39. Nauru graph --- #13862
  40. Coxeter graph --- #13038
  41. Tutte–Coxeter graph --- #12982
  42. Dyck graph --- #10790
  43. Foster graph --- #12952
  44. Biggs–Smith graph --- #12971
  45. Rado graph
  46. Folkman graph --- #14904
  47. Gray graph --- #12952
  48. Ljubljana graph --- #12981
  49. Tutte 12-cage --- #12982
  50. Blanuša snarks -- #15054
  51. Szekeres snark -- #15054
  52. Tietze's graph -- #15054
  53. Watkins snark -- #15054

Change History (53)

comment:1 Changed 10 years ago by ncohen

My god O_O SO you are basically saying I'm not sending enough ? :-D

To be honest I have tried to implement some of them, but felt I should ask for the help of Sage's algebraists... This one, for example : is there any way to build it using Sage's tools ?

http://www.win.tue.nl/~aeb/graphs/Schlaefli.html

Nathann

comment:2 Changed 9 years ago by mvngu

  • Description modified (diff)
  • Milestone set to sage-wishlist

comment:3 Changed 9 years ago by mvngu

  • Description modified (diff)

comment:4 Changed 9 years ago by mvngu

  • Description modified (diff)

comment:5 Changed 9 years ago by mvngu

  • Description modified (diff)

comment:6 Changed 9 years ago by mvngu

  • Description modified (diff)

comment:7 follow-ups: Changed 9 years ago by dimpase

Many of these graphs can be trivially generated in GAP using its package Grape (a part of the optional gap_packages spkg) and a library of primitive groups (a part of optional databases_gap spkg). E.g. here is how to get Schlaefli graph:

sage: gap.load_package('grape')
sage: gap.eval('G:=NullGraph(PrimitiveGroup(27,12),27);')
'rec( isGraph := true, order := 27, group := PSp(4, 3), \n  schreierVector := [ -1, 1, 2, 1, 2, 2, 2, 2, 1, 2, 1, 2, 2, 2, 2, 1, 2, 1, \n      2, 1, 1, 2, 2, 1, 1, 1, 2 ], adjacencies := [ [  ] ], \n  representatives := [ 1 ], isSimple := true )'
sage: gap.eval('AddEdgeOrbit(G,[1,2]);')
''
sage: gap.eval('VertexDegrees(G);')
'[ 10 ]'
sage: edges=gap('Orbit(G.group,[1,2],OnSets)')
sage: len(edges)
135
sage: schlaefli=Graph([[int(x[1])-1,int(x[2])-1] for x in edges])
sage: schlaefli.degree()
[10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
sage: schlaefli.diameter()
2

IMHO there is a more fundamental issue here: Sage should handle such graphs in an efficient way --- just keeping all the edges is pretty much a waste, in particular for bigger examples with hundreds of vertices...

comment:8 in reply to: ↑ 7 Changed 9 years ago by dimpase

Replying to dimpase:

Many of these graphs can be trivially generated in GAP using its package Grape (a part of the optional gap_packages spkg) and a library of primitive groups (a part of optional databases_gap spkg).

actually, Grape isn't even needed (I mentioned it for illustrative purposes): to construct the Sage graph, all you need is the following:

sage: edges=gap('Orbit(PrimitiveGroup(27,12),[1,2],OnSets)')
sage: schlaefli=Graph([[int(x[1])-1,int(x[2])-1] for x in edges])

PS. To get e.g. Hall-Janko graph, use PrimitiveGroup(100,1)...

comment:9 Changed 9 years ago by mvngu

  • Description modified (diff)

comment:10 Changed 9 years ago by mvngu

  • Description modified (diff)

comment:11 Changed 9 years ago by mvngu

  • Description modified (diff)

comment:12 Changed 9 years ago by mvngu

  • Description modified (diff)

comment:13 Changed 9 years ago by mvngu

  • Description modified (diff)

comment:14 follow-up: Changed 9 years ago by dimpase

Fullerens are in fact a family, that can be generated. G.Brinkmann wrote a program called fullgen http://cs.anu.edu.au/~bdm/plantri/ that does just this, generating all non-isomorphic fullerens with given number of hexagonal faces. Unfortunately it has a weird license, so it cannot be just hooked up to Sage, at least not in a standard package.

comment:15 follow-up: Changed 9 years ago by ncohen

I have been sighing at plantri for a while.... I *need* to generate random planar graphs :-p

Nathann

comment:16 in reply to: ↑ 15 Changed 9 years ago by dimpase

Replying to ncohen:

I have been sighing at plantri for a while.... I *need* to generate random planar graphs :-p

Sage way: throw random points on the sphere, generate the facets of their convex closuse (using e.g. cdd), then take the skeleton of the polytope (again, using cdd). Slow, but trivial to code :-)

comment:17 in reply to: ↑ 7 ; follow-up: Changed 9 years ago by rlm

Replying to dimpase:

IMHO there is a more fundamental issue here: Sage should handle such graphs in an efficient way --- just keeping all the edges is pretty much a waste, in particular for bigger examples with hundreds of vertices...

The underlying architecture is already in place; one needs only to implement a GraphBackend? which represents the graph in question. Implementing simple methods such as has_edge, has_vertex, etc. one can then get the rest of the methods automatically. Check out the source!

comment:18 in reply to: ↑ 17 ; follow-up: Changed 9 years ago by dimpase

Replying to rlm:

Replying to dimpase:

IMHO there is a more fundamental issue here: Sage should handle such graphs in an efficient way --- just keeping all the edges is pretty much a waste, in particular for bigger examples with hundreds of vertices...

The underlying architecture is already in place; one needs only to implement a GraphBackend? which represents the graph in question. Implementing simple methods such as has_edge, has_vertex, etc. one can then get the rest of the methods automatically. Check out the source!

I am not sure I understand how to implement things like add_vertex() and add_edge() - as we would start with a permutation group G, the set of vertices is the domain of the group, and edges cannot be added one by one, but only as whole G-orbits. (Alternatively, not all orbits of G are used as the vertex set, and then adding a vertex would mean adding its G-orbit.)

comment:19 in reply to: ↑ 18 Changed 9 years ago by rlm

Replying to dimpase:

I am not sure I understand how to implement things like add_vertex() and add_edge() - as we would start with a permutation group G, the set of vertices is the domain of the group, and edges cannot be added one by one, but only as whole G-orbits. (Alternatively, not all orbits of G are used as the vertex set, and then adding a vertex would mean adding its G-orbit.)

Well, you can always raise an error in the add_vertex function:

RuntimeError?: You can't add vertices to this kind of graph.

Or something similar. Then whenever you called a function which tried to add a vertex you would get that error, but the rest of the graph library would work just fine.

comment:20 Changed 9 years ago by mvngu

  • Description modified (diff)

comment:21 Changed 9 years ago by kini

  • Description modified (diff)

comment:22 Changed 9 years ago by kini

  • Description modified (diff)

comment:23 Changed 8 years ago by brunellus

  • Cc brunellus added

comment:24 Changed 8 years ago by wdj

The following at 3-regular Hamiltonian graphs, hence covered by the LCF construction (http://en.wikipedia.org/wiki/LCF_notation):

Balaban 10-cage
L = [-9, -25, -19, 29, 13, 35, -13, -29, 19, 25, 9, -29, 29, 17, 33, 21, 9,-13, -31, -9, 25, 17, 9, -31, 27, -9, 17, -19, -29, 27, -17, -9, -29, 33, -25,25, -21, 17, -17, 29, 35, -29, 17, -17, 21, -25, 25, -33, 29, 9, 17, -27, 29, 19, -17, 9, -27, 31, -9, -17, -25, 9, 31, 13, -9, -21, -33, -17, -29, 29]
G = graphs.LCFGraph(70, L, 1)

Balaban 11-cage
L = [44, 26, -47, -15, 35, -39, 11, -27, 38, -37, 43, 14, 28, 51, -29, -16, 41, -11, -26, 15, 22, -51, -35, 36, 52, -14, -33, -26, -46, 52, 26, 16, 43, 33, -15, 17, -53, 23, -42, -35, -28, 30, -22, 45, -44, 16, -38, -16, 50, -55, 20, 28, -17, -43, 47, 34, -26, -41, 11, -36, -23, -16, 41, 17, -51, 26, -33, 47, 17, -11, -20, -30, 21, 29, 36, -43, -52, 10, 39, -28, -17, -52, 51, 26, 37, -17, 10, -10, -45, -34, 17, -26, 27, -21, 46, 53, -10, 29, -50, 35, 15, -47, -29, -41, 26, 33, 55, -17, 42, -26, -36, 16]
G = graphs.LCFGraph(112, L, 1)


Bidiakis cube 
G = graphs.LCFGraph(12, [6,4,-4], 4) 

Biggs-Smith graph
L = [16, 24, -38, 17, 34, 48, -19, 41, -35, 47, -20, 34, -36, 21, 14, 48, -16, -36, -43, 28, -17, 21, 29, -43, 46, -24, 28, -38, -14, -50, -45, 21, 8, 27, -21, 20, -37, 39, -34, -44, -8, 38, -21, 25, 15, -34, 18, -28, -41, 36, 8, -29, -21, -48, -28, -20, -47, 14, -8, -15, -27, 38, 24, -48, -18, 25, 38, 31, -25, 24, -46, -14, 28, 11, 21, 35, -39, 43, 36, -38, 14, 50, 43, 36, -11, -36, -24, 45, 8, 19, -25, 38, 20, -24, -14, -21, -8, 44, -31, -38, -28, 37]
G = graphs.LCFGraph(102, L, 1)


Dyck graph
G = graphs.LCFGraph(32, [5,-5,13,-13], 8) 


Foster graph
G = graphs.LCFGraph(90, [17,-9,37,-37,9,-17], 15)  

Franklin graph
G = graphs.LCFGraph(12, [5,-5], 6) 


Gray graph
G = graphs.LCFGraph(54, [-25,7,-7,13,-13,25], 9)

Harries graph
G = graphs.LCFGraph(70, [-29,-19,-13,13,21,-27,27,33,-13,13,19,-21,-33,29], 5)

Harries-Wong graph
L = [9, 25, 31, -17, 17, 33, 9, -29, -15, -9, 9, 25, -25, 29, 17, -9, 9, -27, 35, -9, 9, -17, 21, 27, -29, -9, -25, 13, 19, -9, -33, -17, 19, -31, 27, 11, -25, 29, -33, 13, -13, 21, -29, -21, 25, 9, -11, -19, 29, 9, -27, -19, -13, -35, -9, 9, 17, 25, -9, 9, 27, -27, -21, 15, -9, 29, -29, 33, -9, -25]
G = graphs.LCFGraph(70, L, 1)


Ljubljana graph
L = [47, -23, -31, 39, 25, -21, -31, -41, 25, 15, 29, -41, -19, 15, -49, 33, 39, -35, -21, 17, -33, 49, 41, 31, -15, -29, 41, 31, -15, -25, 21, 31, -51, -25, 23, 9, -17, 51, 35, -29, 21, -51, -39, 33, -9, -51, 51, -47, -33, 19, 51, -21, 29, 21, -31, -39] 
G = graphs.LCFGraph(112, L, 2)

McGee graph
G = graphs.LCFGraph(24, [12,7,-7], 8) 

Möbius–Kantor graph
G = graphs.LCFGraph(16, [5,-5], 8) 


Nauru graph
G = graphs.LCFGraph(24, [5,-9,7,-7,9,-5], 4)

Tutte 12-cage
G = graphs.LCFGraph(126, [17, 27, -13, -59, -35, 35, -11, 13, -53, 53, -27, 21, 57, 11, -21, -57, 59, -17], 7)

Tutte–Coxeter graph
G = graphs.LCFGraph(30, [-13,-9,7,-7,9,13], 5) 

Wagner graph
G = graphs.LCFGraph(8, [4], 8)

Some of the Fullerene graphs can be expressed in LCF notation as well.

comment:25 Changed 8 years ago by kini

It's nice to have them explicitly constructed so you get a nice picture in a plot, though. I have a really old patch lying around for the Balaban 11-cage, I'll see if I can rebase it...

comment:26 Changed 8 years ago by ncohen

  • Description modified (diff)

comment:27 Changed 8 years ago by ncohen

  • Description modified (diff)

comment:28 Changed 8 years ago by ncohen

  • Description modified (diff)

comment:29 Changed 8 years ago by ncohen

  • Description modified (diff)

comment:30 Changed 8 years ago by ncohen

  • Description modified (diff)

comment:31 Changed 8 years ago by ncohen

  • Description modified (diff)

comment:32 Changed 8 years ago by ncohen

Well David, all of your graphs are now Sage patches or are included already. My only regret is that I found not nice embedding for Tutte's 12 cage :-/

Nathann

comment:33 Changed 8 years ago by ncohen

  • Description modified (diff)

comment:34 Changed 8 years ago by ncohen

  • Description modified (diff)

comment:35 Changed 8 years ago by ncohen

  • Description modified (diff)

comment:36 Changed 8 years ago by chapoton

  • Description modified (diff)

comment:37 Changed 7 years ago by chapoton

  • Description modified (diff)

comment:38 Changed 7 years ago by chapoton

  • Description modified (diff)

comment:39 Changed 7 years ago by chapoton

  • Description modified (diff)

comment:40 in reply to: ↑ 14 ; follow-up: Changed 7 years ago by nvcleemp

Replying to dimpase:

Fullerens are in fact a family, that can be generated. G.Brinkmann wrote a program called fullgen http://cs.anu.edu.au/~bdm/plantri/ that does just this, generating all non-isomorphic fullerens with given number of hexagonal faces. Unfortunately it has a weird license, so it cannot be just hooked up to Sage, at least not in a standard package.

Brinkmann's student J. Goedgebeur implemented a new version using a different algorithm which is faster for the `small' cases: http://caagt.ugent.be/buckygen/ This program is available under the GPL, so I assume it can be integrated in Sage. I'm willing to work on this. I have some familiarity with the program, since I integrated it into CaGe (http://caagt.ugent.be/CaGe).

comment:41 in reply to: ↑ 40 Changed 7 years ago by ncohen

Brinkmann's student J. Goedgebeur implemented a new version using a different algorithm which is faster for the `small' cases: http://caagt.ugent.be/buckygen/ This program is available under the GPL, so I assume it can be integrated in Sage. I'm willing to work on this. I have some familiarity with the program, since I integrated it into CaGe (http://caagt.ugent.be/CaGe).

Wow ! Coooooooooool ! When you will create this ticket, could you please add in Cc : "azi, Slani, Stefan, ncohen" ? :-)

THaaaaaaaaaaanks !!

Nathann

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

comment:42 Changed 7 years ago by nvcleemp

  • Description modified (diff)

comment:43 Changed 7 years ago by chapoton

  • Description modified (diff)

comment:44 Changed 7 years ago by chapoton

  • Description modified (diff)

comment:45 Changed 6 years ago by ncohen

  • Description modified (diff)

comment:46 Changed 6 years ago by ncohen

  • Description modified (diff)

comment:47 Changed 6 years ago by ncohen

  • Description modified (diff)

comment:48 Changed 6 years ago by ncohen

  • Description modified (diff)

comment:49 Changed 6 years ago by ncohen

  • Description modified (diff)

comment:50 Changed 6 years ago by chapoton

Maybe we can close that one ?

comment:51 Changed 6 years ago by ncohen

  • Status changed from new to needs_review

I think that we can !

Funny.. It seemed unreachable when Minh created it... ;-)

Nathann

comment:52 Changed 6 years ago by ncohen

  • Milestone changed from sage-wishlist to sage-duplicate/invalid/wontfix
  • Status changed from needs_review to positive_review

Everything has been implemented.

comment:53 Changed 6 years ago by vbraun

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