Skip to content

evanberkowitz/buckygen

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

20 Commits
.gitignore
.gitignore
 
 
BuckyGen.m
BuckyGen.m
 
 
LICENSE
LICENSE
 
 
README.md
README.md
 
 
buckygen-guide.txt
buckygen-guide.txt
 
 
buckygen.c
buckygen.c
 
 
makefile
makefile
 
 
splay.c
splay.c
 
 

Repository files navigation

buckygen

buckygen
Author Jan Goedgebeur
in collaboration with Gunnar Brinkmann and Brendan McKay
License GPLv3
Orignal source http://caagt.ugent.be/buckygen/

References:

TABLE OF CONTENTS

INTRODUCTION.

buckygen is a program for the efficient generation of all nonisomorphic fullerenes. These are triangulations where all vertices have degree 5 or 6. Or if the dual representation is used: cubic plane graphs where all faces are pentagons or hexagons. Euler's formula implies that a fullerene contains exactly 12 pentagonal faces.

The program can also be used to generate IPR fullerenes, these are fullerenes which have no adjacent degree 5 vertices.

buckygen has been tested on Linux and Mac OS X.

INSTALLING buckygen.

The latest version of buckygen can be obtained from http://caagt.ugent.be/buckygen/

After extracting the buckygen zipfile, compile buckygen using the command "make". Alternatively you can also compile it using:

cc -O4 buckygen.c -o buckygen

Important: splay.c must be in the same directory as buckygen.c

RUNNING buckygen.

An overview of all options can also be found by executing ./buckygen. Most parameters are the same as in plantri. More information about plantri can be found here at http://cs.anu.edu.au/~bdm/plantri/

Usage: ./buckygen [-uagsh -IS#rq -odV -v] n [res/mod] [outfile]

The only compulsory parameter is the number of vertices n. By default the generated fullerenes encoded in planar_code and written to stdout. The output formats are described below.

An example of a buckygen run is:

./buckygen 32 fuller_32

which generates all triangulations with 32 vertices where all vertices have degree 5 or 6 and writes them to a file with name fuller_32. The number of vertices "32" can also be given as "60d" (the suffix 'd' means 'dual') in which case it is converted by adding 4 then dividing by 2: (60+4)/2 = 32. This calculation yields the number of faces of the triangulation, which is the number of vertices in the dual cubic graph. More examples will be given below.

Apart from the one compulsory parameter, there are three types of optional parameters:

  • SWITCHES are introduced by a - character. If there are more than one they can be arbitrarily concatenated or separated. They can also appear anywhere. For example, these command lines are all equivalent:

    buckygen 32 -S12 -d -u buckygen 32 -S12du buckygen 32 -udS12 buckygen -ud 32 -S12

    The meanings of the switches are explained in the next sections.

  • An OUTPUT FILE outfile can be given, if you want the graphs to be sent somewhere other than standard output. Information other than graphs (such as statistics) is written to the standard error stream.

  • A RES/MOD pair res/mod can be given to split the generation in MOD (more or less equally big) parts. This pair comprises two integers with '/' between, such as 13/100. The first integer can be from 0 to one less than the second number. In this example part 13 will be executed. Splitting the generation causes a small overhead, so the sum of the timings for the small parts will be slightly more than the time needed to run the same case without modulo. But this overhead is usually negligible compared to the total execution time. The normal rules for modulo calculation apply. So '0/2' will give the same result as '0/4' and '2/4' combined.

Parameters and switches may appear in any order with one exception: the compulsory parameter (number of vertices) must precede any output file or res/mod parameters.

SWITCHES.

  • -S# Output all fullerenes with 'i' vertices (# <= i <= n) instead of only the fullerenes with 'n' vertices. Since buckygen recursively constructs all fullerenes from smaller fullerenes, using switch -S only gives a minor overhead.

  • -I Only generate and output the IPR fullerenes. In this case a specialized generator for IPR fullerenes is used, so this is done quite efficiently.

  • -d Causes the dual graph to be written instead of the original graph. The dual graph of a triangulation where all vertices have degree 5 or 6 is a cubic plane graph where all faces are pentagons or hexagons. Note that it is applied only at the output stage. All other switches refer to the original graph before the dual is taken. For example, -S12 (start output from 12 vertices) refers to the original graph (so to a triangulation) and not to the dual.

  • -r Tests if the generated fullerenes have spirals starting at a degree 5 or a degree 6 vertex. Fullerenes which do not have a spiral starting at a degree 5 vertex are written to a file named "No_pentagon_spiral_x". And fullerenes which do not have a spiral starting at any vertex of the fullerene are written to a file named "No_spiral_x".

  • -o Normally, one member of each isomorphism class is written. If this switch is given, one member of each orientation preserving (O-P) isomorphism class is written. Since graph6 and sparse6 formats don't encode the imbedding anyway, this switch is ignored for output purposes if you use -g or -s.

  • -V Only output graphs with non-trivial group. If -o is given, the O-P group is used.

  • -v buckygen will always tell you (by a message to standard error) the number of graphs that were produced. If you specify -v, it might tell you some additional statistical information. For example, if you use -o, -v will cause it to also inform you of the number of isomorphism classes as well as the number of isomorphism classes which are O-P isomorphic to their mirror images.

-q Work in 'quiet' mode: does not output any information to the standard error stream.

OUTPUT FORMATS.

buckygen can write graphs in a variety of different formats.

  • PLANAR CODE is the default format. It is the preferred format if you plan to feed the graph into a program that needs the imbedding, and also convenient if you don't need the imbedding. However, it uses characters which are not printable so it is not suitable for looking at by eye.

  • ASCII CODE is a human-readable version of planar code. The vertices of the graph are named by ASCII characters starting with 'a'. Example: 7 bcdefg,agfdc,abd,acbfe,adf,aedbg,afb This is a graph with 7 vertices a,b,c,d,e,f,g. The neighbours of 'a' in clockwise order are b,c,d,e,f,g; and so on. Each graph occupies one line of output. Ascii code is convenient if you just want to draw a few graphs by hand. To select ascii code use -a.

  • GRAPH6 is a compact code for the abstract structure of a graph. The imbedding is not represented, so this is not a suitable code to use if you want the imbedding. It is also restricted to simple graphs. graph6 is one of the formats supported by Brendan McKay's 'gtools' package. Each graph occupies one line. To select graph6 code use -g.

  • SPARSE6 is a compact code for the abstract structure of a graph which is optimized for sparse graphs. If you don't want the imbedding and are dealing with cubic graphs of 20 or more vertices, sparse6 is a good choice. sparse6 is one of the formats supported by Brendan McKay's gtools package. Each graph occupies one line. To select sparse6 code use -s.

Each of those formats except for ascii code also has a standard header, which is written to the output at the beginning:

format header written by default?
planar code >>planar_code<< yes
graph6 >>graph6<< no
sparse6 >>sparse6<< no

In each case the header is written with no end-of-line characters after it (for portability reasons). To write a header when the default is not to, or vice-versa, use -h.

If you only want to count the graphs and not write them, use -u to select no output.

Details of these formats is given in Appendices A and B.

EXAMPLES.

Below are some examples of possible execution parameters.

./buckygen 65 -S32 -I

Generates and outputs all IPR fullerenes with at most 65 and at least 32 vertices and writes them to the standard output stream in planar code.

./buckygen 55 -S20d fuller_55_20

Generates all fullerenes with at most 55 and at least 20 vertices and writes their dual graph (i.e. a cubic graph) to a file with name "fuller_55_20".

./buckygen 52 -ru

Generates all fullerenes with 52 vertices, but does not output them. Also checks if the fullerenes have a spiral starting at a pentagon or a hexagon.

./buckygen 132 -Ig 10/200

Splits the generation of all IPR fullerenes with 132 vertices in 200 parts and executes part 10 and outputs the fullerenes in graph6 format to the standard output stream.

MATHEMATICA PACKAGE

BuckyGen.m provides the BuckyGen package for Mathematica. It implements one function, buckygen, which calls the buckygen executable. It assumes that that the buckygen executable is in Environment["PATH"] in Mathematica.

You can simply copy BuckyGen.m to your preferred location where Mathematica can find it, FileNameJoin[{$UserBaseDirectory, "Applications"}] for example.

The usage is described in the package:

buckygen::usage = "buckygen[n_Integer, options]
    n is the degree of the fullerenes you wish to generate.
    
    Options largely correspond to the command-line options available for the buckygen executable.
    They correspond as follows:
    
    Flag Option       ->   Default|Otherwise
         "Verbose"    ->   False|True                 if False, simply return the list; if True print the stdout of running the buckygen executable.
         
    -S   "Start"      ->   False|s_Integer            if not False, produce fullerenes of degree s through n inclusive.
    -d   "Dual"       ->   False|True                 if False, faces are triangles; if True vertices are degree 3.
    -I   "IPR"        ->   False|True                 if False, ignore the isolated pentagon rule; if True, follow it.
    -r   "SpiralTest" ->   False|True                 Completely ignored, totally unsupported.
    -o   "PreserveOrientation" -> False|True          if False, ignore orientation information; otherwise consider it.
                                                          As imbeddings are ignored, only affects results if "RequireNonTrivialGroup" -> True.
    -V   "RequireNontrivialGroup" -> False|Trure,     if False, generate all fullerenes; if True only generate those with a nontrivial group.

After it is installed, the package may be loaded via Needs["BuckyGen`"].

APPENDIX A. Definition of PLANAR CODE.

PLANAR CODE is the default output format for buckygen. The vertices of the graph are numbered starting at 1. PLANAR CODE represents the graph by a series of bytes, whose unsigned numerical values (0..255) are significant. The first byte gives the number of vertices n. Then there are n sections, where section v contains the neighbours of vertex v in clockwise order followed by a zero byte. There is no end-of-line character appended.

In addition to the encodings of graphs, a PLANAR CODE file by default begins with the 15 characters >>planar_code<< without end-of-line characters.

APPENDIX B. Definition of GRAPH6 and SPARSE6.

All numbers in this description are in decimal unless obviously in binary. GRAPH6 and SPARSE6 are text formats, and a file containing them is a text file.

Apart from the header, there is one object per line. Apart from the header and the end-of-line characters, all bytes have a value in the range 63-126 (which are all printable ASCII characters).

BIT VECTORS:

A bit vector x of length k can be represented as follows.
Example: 1000101100011100

(1) Pad on the right with 0 to make the length a multiple of 6. Example: 100010110001110000

(2) Split into groups of 6 bits each. Example: 100010 110001 110000

(3) Add 63 to each group, considering them as bigendian binary numbers. Example: 97 112 111

These values are then stored one per byte.
So, the number of bytes required is ceiling(k/6).

Let R(x) denote this representation of x as a string of bytes.

SMALL NONNEGATIVE INTEGERS:

Let n be an integer in the range 0-262143 (262143 = 2^18-1).

If 0 <= n <= 62, define N(n) to be the single byte n+63. If n >= 63, define N(n) to be the four bytes 126 R(x), where x is the bigendian 18-bit binary form of n.

Examples: N(30) = 93 N(12345) = N(000011 000000 111001) = 126 69 63 120

GRAPH6 format:

Suppose G has n vertices. Write the upper triangle of the adjacency matrix of G as a bit vector x of length n(n-1)/2, using the ordering (0,1),(0,2),(1,2),(0,3),(1,3),(2,3),...,(n-1,n).

Then the graph is represented as N(n) R(x).

Example: Suppose n=5 and G has edges 0-2, 0-4, 1-3 and 3-4.

   x = 0 10 010 1001

   Then N(n) = 68 and R(x) = R(010010 100100) = 81 99.
   So, the graph is  68 81 99.

Note that GRAPH6 format cannot represent loops or parallel edges.

SPARSE6 format:

The encoded graph consists of: (1) The character ':'. (This is present to distinguish the code from GRAPH6 format.) (2) The number of vertices. (3) A list of edges. (4) end-of-line

Loops and multiple edges are supported, but not directed edges.

Number of vertices n: Represented as N(n) like in GRAPH6 format.

List of edges:

Let k be the number of bits needed to represent n-1 in binary.
The remaining bytes encode a sequence R(z) where
  z = b[0] x[0] b[1] x[1] b[2] x[2] ... b[m] x[m] 111...

Each b[i] occupies 1 bit, and each x[i] occupies k bits, and the number
of 1's at the end is the least needed to make the total length a 
multiple of 6.

The vertices of the graph are 0..n-1.
The edges encoded by this sequence are determined thus:

   v = 0
   for i from 0 to m do
      if b[i] = 1 then v = v+1 endif;
      if x[i] > v then v = x[i] else output {x[i],v} endif
   endfor

Example:    :Fa@x^
':' indicates sparse6 format.
Subtract 63 from the other bytes and write them in binary, six bits each.
     000111 100010 000001 111001 011111
The first byte is not 63, so it is n.  n=7
n-1 needs 3 bits (k=3).  Write the other bits in groups of 1 and k:
  1 000  1 000  0 001  1 110   0 101  1 111
This is the b/x sequence  1,0 1,0 0,1 1,6 0,5 1,7.
The 1,7 at the end is just padding.
The remaining pairs give the edges 0-1 1-2 5-6.

APPENDIX C. Fullerene Counts.

In this section we tabulate the counts of the fullerenes which were generated with buckygen. For the dual graphs, switch the number of vertices and faces.

# Vertices # Faces # fullerenes IPR fullerenes
20 12 1 0
22 13 0 0
24 14 1 0
26 15 1 0
28 16 2 0
30 17 3 0
32 18 6 0
34 19 6 0
36 20 15 0
38 21 17 0
40 22 40 0
42 23 45 0
44 24 89 0
46 25 116 0
48 26 199 0
50 27 271 0
52 28 437 0
54 29 580 0
56 30 924 0
58 31 1205 0
60 32 1812 1
62 33 2385 0
64 34 3465 0
66 35 4478 0
68 36 6332 0
70 37 8149 1
72 38 11190 1
74 39 14246 1
76 40 19151 2
78 41 24109 5
80 42 31924 7
82 43 39718 9
84 44 51592 24
86 45 63761 19
88 46 81738 35
90 47 99918 46
92 48 126409 86
94 49 153493 134
96 50 191839 187
98 51 231017 259
100 52 285914 450
102 53 341658 616
104 54 419013 823
106 55 497529 1233
108 56 604217 1799
110 57 713319 2355
112 58 860161 3342
114 59 1008444 4468
116 60 1207119 6063
118 61 1408553 8148
120 62 1674171 10774
122 63 1942929 13977
124 64 2295721 18769
126 65 2650866 23589
128 66 3114236 30683
130 67 3580637 39393
132 68 4182071 49878
134 69 4787715 62372
136 70 5566949 79362
138 71 6344698 98541
140 72 7341204 121354
142 73 8339033 151201
144 74 9604411 186611
146 75 10867631 225245
148 76 12469092 277930
150 77 14059174 335569
152 78 16066025 404667
154 79 18060979 489646
156 80 20558767 586264
158 81 23037594 697720
160 82 26142839 836497
162 83 29202543 989495
164 84 33022573 1170157
166 85 36798433 1382953
168 86 41478344 1628029
170 87 46088157 1902265
172 88 51809031 2234133
174 89 57417264 2601868
176 90 64353269 3024383
178 91 71163452 3516365
180 92 79538751 4071832
182 93 87738311 4690880
184 94 97841183 5424777
186 95 107679717 6229550
188 96 119761075 7144091
190 97 131561744 8187581
192 98 145976674 9364975
194 99 159999462 10659863
196 100 177175687 12163298
198 101 193814658 13809901
200 102 214127742 15655672
202 103 233846463 17749388
204 104 257815889 20070486
206 105 281006325 22606939
208 106 309273526 25536557
210 107 336500830 28700677
212 108 369580714 32230861
214 109 401535955 36173081
216 110 440216206 40536922
218 111 477420176 45278722
220 112 522599564 50651799
222 113 565900181 56463948
224 114 618309598 62887775
226 115 668662698 69995887
228 116 729414880 77831323
230 117 787556069 86238206
232 118 857934016 95758929
234 119 925042498 105965373
236 120 1006016526 117166528
238 121 1083451816 129476607
240 122 1176632247 142960479
242 123 1265323971 157402781
244 124 1372440782 173577766
246 125 1474111053 190809628
248 126 1596482232 209715141
250 127 1712934069 230272559
252 128 1852762875 252745513
254 129 1985250572 276599787
256 130 2144943655 303235792
258 131 2295793276 331516984
260 132 2477017558 362302637
262 133 2648697036 395600325
264 134 2854536850 431894257
266 135 3048609900 470256444
268 136 3282202941 512858451
270 137 3501931260 557745670
272 138 3765465341 606668511
274 139 4014007928 659140287
276 140 4311652376 716217922
278 141 4591045471 776165188
280 142 4926987377 842498881
282 143 5241548270 912274540
284 144 5618445787 987874095
286 145 5972426835 1068507788
288 146 6395981131 1156161307
290 147 6791769082 1247686189
292 148 7267283603 1348832364
294 149 7710782991 1454359806
296 150 8241719706 1568768524
298 151 8738236515 1690214836
300 152 9332065811 1821766896
302 153 9884604767 1958581588
304 154 10548218751 2109271290
306 155 11164542762 2266138871
308 156 11902015724 2435848971
310 157 12588998862 2614544391
312 158 13410330482 2808510141
314 159 14171344797 3009120113
316 160 15085164571 3229731630
318 161 15930619304 3458148016
320 162 16942010457 3704939275
322 163 17880232383 3964153268
324 164 19002055537 4244706701
326 165 20037346408 4533465777
328 166 21280571390 4850870260
330 167 22426253115 5178120469
332 168 23796620378 5531727283
334 169 25063227406 5900369830
336 170 26577912084 6299880577
338 171 27970034826 6709574675
340 172 29642262229 7158963073
342 173 31177474996 7620446934
344 174 33014225318 8118481242
346 175 34705254287 8636262789
348 176 36728266430 9196920285
350 177 38580626759 9768511147
352 178 40806395661 10396040696
354 179 42842199753 11037658075
356 180 45278616586 11730538496
358 181 47513679057 12446446419
360 182 50189039868 13221751502
362 183 52628839448 14010515381
364 184 55562506886 14874753568
366 185 58236270451 15754940959
368 186 61437700788 16705334454
370 187 64363670678 17683643273
372 188 67868149215 18744292915
374 189 71052718441 19816289281
376 190 74884539987 20992425825
378 191 78364039771 22186413139
380 192 82532990559 23475079272
382 193 86329680991 24795898388
384 194 90881152117 26227197453
386 195 95001297565 27670862550
388 196 99963147805 29254036711
390 197 104453597992 30852950986
392 198 109837310021 32581366295
394 199 114722988623 34345173894
396 200 120585261143 36259212641
398 201 125873325588 38179777473
400 202 132247999328 40286153024

APPENDIX D. Version History

Version Date Commit
1.0 May 31, 2012 0ccdeab5bc22544216c31e413362608f84ee5366

About

Generate fullerenes

Resources

Readme

License

GPL-3.0 license
Activity

Stars

3 stars

Watchers

2 watching

Forks

5 forks
Report repository

Releases

1 tags

Packages

No packages published

Languages