more named graphs

[mvngu]

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
13. ​Balaban 11-cage
14. ​Double-star snark
15. ​Ellingham–Horton graph
16. ​fullerene graphs
17. ​Harries–Wong graph
18. ​Hoffman graph
19. ​Holt graph
20. ​Horton graph
21. ​Kittell graph
22. ​Markström graph
23. ​McGee graph
24. ​Meredith graph
25. ​Sousselier graph
26. ​Poussin graph
27. ​Robertson graph
28. ​Tutte's fragment
29. ​Tutte graph
30. ​Young–Fibonacci lattice
31. ​Wagner graph
32. ​Wiener-Araya graph
33. ​Clebsch graph
34. ​Hall–Janko graph
35. ​Paley graph
36. ​Shrikhande graph
37. ​Möbius–Kantor graph
38. ​Nauru graph
39. ​Coxeter graph
40. ​Tutte–Coxeter graph
41. ​Dyck graph
42. ​Foster graph
43. ​Biggs–Smith graph
44. ​Rado graph
45. ​Folkman graph
46. ​Gray graph
47. ​Ljubljana graph
48. ​Tutte 12-cage
49. ​Blanuša snarks
50. ​Szekeres snark
51. ​Tietze's graph
52. ​Watkins snark

[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

[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...

[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)...

[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.

[ncohen]

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

Nathann

[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 :-)

[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!

[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.)

[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.