Opened 12 years ago

Last modified 9 years ago

#9136 closed enhancement

more named graphs — at Version 33

Reported by: Minh Van Nguyen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: graph theory Keywords:
Cc: Lukáš Lánský Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Change History (33)

comment:1 Changed 12 years ago by Nathann Cohen

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 12 years ago by Minh Van Nguyen

Description: modified (diff)
Milestone: sage-wishlist

comment:3 Changed 12 years ago by Minh Van Nguyen

Description: modified (diff)

comment:4 Changed 12 years ago by Minh Van Nguyen

Description: modified (diff)

comment:5 Changed 12 years ago by Minh Van Nguyen

Description: modified (diff)

comment:6 Changed 12 years ago by Minh Van Nguyen

Description: modified (diff)

comment:7 Changed 12 years ago by Dima Pasechnik

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 12 years ago by Dima Pasechnik

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 12 years ago by Minh Van Nguyen

Description: modified (diff)

comment:10 Changed 12 years ago by Minh Van Nguyen

Description: modified (diff)

comment:11 Changed 12 years ago by Minh Van Nguyen

Description: modified (diff)

comment:12 Changed 12 years ago by Minh Van Nguyen

Description: modified (diff)

comment:13 Changed 12 years ago by Minh Van Nguyen

Description: modified (diff)

comment:14 Changed 12 years ago by Dima Pasechnik

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 Changed 12 years ago by Nathann Cohen

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 12 years ago by Dima Pasechnik

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 ; Changed 12 years ago by Robert Miller

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 ; Changed 12 years ago by Dima Pasechnik

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 12 years ago by Robert Miller

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 12 years ago by Minh Van Nguyen

Description: modified (diff)

comment:21 Changed 12 years ago by Keshav Kini

Description: modified (diff)

comment:22 Changed 12 years ago by Keshav Kini

Description: modified (diff)

comment:23 Changed 11 years ago by Lukáš Lánský

Cc: Lukáš Lánský added

comment:24 Changed 11 years ago by David Joyner

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 11 years ago by Keshav 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 11 years ago by Nathann Cohen

Description: modified (diff)

comment:27 Changed 11 years ago by Nathann Cohen

Description: modified (diff)

comment:28 Changed 11 years ago by Nathann Cohen

Description: modified (diff)

comment:29 Changed 11 years ago by Nathann Cohen

Description: modified (diff)

comment:30 Changed 11 years ago by Nathann Cohen

Description: modified (diff)

comment:31 Changed 11 years ago by Nathann Cohen

Description: modified (diff)

comment:32 Changed 11 years ago by Nathann Cohen

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 11 years ago by Nathann Cohen

Description: modified (diff)
Note: See TracTickets for help on using tickets.