Dataset for On the regular linear spaces up to order 16
收藏资源简介：
This dataset contains, up to isomorphism, all (15_4,20_3) and (15_5,25_3) configurations, all (16_6,32_3) configurations with nontrivial automorphisms, as well as all 4-regular graphs on 15 vertices, 6-regular graphs on 15 vertices, 3-regular graphs on 16 vertices, and 4-regular graphs on 17 vertices. The configurations uniquely give regular linear spaces with parameters (15|2^45,3^20), (15|2^30,3^25), and (16|2^24,3^32). All files are compressed with gzip. The dataset supplements the publication "On the Regular Linear Spaces up to Order 16" by Anton Betten, Dieter Betten, Daniel Heinlein, and Patric R. J. Östergård. In the files containing configurations, each line is a configuration with the syntax<br> <number of points> <number b of blocks> <B1> <B2> ... <Bb> A<number of automorphisms><br> where<br> Bi is a block for all i=1,...,b and represented as a hex-encoded<br> (with alphabet 0123456789abcdef) characteristic vector of points.<br> The least significant bit is the rightmost bit. Example:<br> Assuming a total of 15 points labeled with {0,...,14}, the characteristic vector of a block {1,3,14} is<br> (0)100|0000|0000|1010<br> The first bit is padding as each hexadecimal number encodes four bits. Vertical bars designate groups of four bits. Consequently, the block is encoded as<br> 400a The following example shows the first line of one of the files:<br> $ zcat conf_15_4_20_3.txt.gz | head -n1<br> 15 20 1081 4101 2201 0c01 0026 004a 0092 4402 008c 0054 0a04 0038 2108 1110 0160 0620 08c0 5200 3400 6800 A1 For the files containing graphs, we apply the graph6 file format but we extend each line by the corresponding number of automorphisms as described for configurations above, without the letter A. Programs for manipulating graphs in the graph6 format can be found in the gtools package that comes with the graph isomorphism program nauty (https://pallini.di.uniroma1.it/). Details regarding the graph6 format can be found in the documentation of nauty (https://pallini.di.uniroma1.it/Guide.html). For graphs with a most 62 vertices, which holds in all cases here, a line in graph6 format is the ASCII converted equivalent of<br> <number n of vertices + 63><ADJ><br> where ADJ is the upper triangle of the adjacency matrix read column-wise (that is, using the ordering 01, 02, 12, 03, 13, 23, ...) and of length n*(n-1)/2, encoded in the following way:<br> - pad on the right to make the length a multiple of 6<br> - split into groups of 6 and convert each group to a decimal number<br> - add 63 to each decimal number and convert to ASCII<br> We further extend any graph6 line by the nonstandard<br> <space><order of automorphism group> Example:<br> Assume a graph with 5 vertices and edges: 02, 04, 13, 34 (the path 2-0-4-3-1), which has the adjacency matrix<br> 00101<br> 00010<br> 10000<br> 01001<br> 10010<br> Hence, the upper triangle read column-wise is<br> 0100101001<br> After padding we get<br> 010010100100<br> and after grouping<br> 010010|100100<br> Converting to decimal and adding 63 gives<br> 63+16+2|63+32+4<br> that is<br> 81|99<br> The number of vertices is 5, so we prepend 5+63=68:<br> 68 81 99<br> The line in graph6 format is therefore<br> DQc<br> and our nonstandard appending of the order of the automorphism group gives<br> DQc 2 The first line of one of the files is as follows:<br> $ zcat graph_15_4.txt.gz | head -n1<br> Ns_???BAwjDoTOY_M_? 2 The orders of the automorphism groups and the numbers of isomorphism classes are as follows. The (up to isomorphism) 114711393113 (16_6,32_3) regular linear spaces with no nontrivial automorphisms are not stored. (15_4,20_3) (15_5,25_3) (16_6,32_3) 1 251712191 1442354689 114711393113 2 94229 180367 1125379 3 1129 2178 17287 4 915 936 3054 5 29 33 6 142 180 240 8 85 36 50 9 4 10 4 4 12 10 13 30 15 1 16 7 3 18 4 3 2 20 2 2 24 10 5 2 30 1 32 1 36 4 2 40 2 1 48 4 1 72 1 96 1 120 1 600 1 720 1 total 251808770 1442538454 114712539165 4-regular graphs with 15 vertices 6-regular graphs with 15 vertices 3-regular graphs with 16 vertices 4-regular graphs with 17 vertices 1 656794 1396131168 1547 76356249 2 119881 69928313 1261 8665624 3 17 630 2 127 4 21500 3848635 667 997704 5 14 6 409 55060 15 27213 8 4789 274294 330 131662 10 10 35 12 352 21334 11 12577 14 4 16 1020 23435 147 19786 18 1 10 2 20 7 12 24 210 5596 11 4344 28 18 30 4 7 32 243 2463 51 3320 34 3 36 1 128 53 48 106 1453 33 1500 56 1 15 60 2 2 64 54 285 16 639 68 1 72 6 165 2 96 96 41 309 24 504 112 7 120 5 692 128 10 48 4 132 140 1 144 10 74 3 82 168 1 1 192 14 77 20 193 216 2 3 224 2 6 240 18 1 2 497 256 1 6 1 24 280 1 288 5 36 9 53 320 4 384 6 26 11 58 432 9 3 2 448 1 480 15 191 512 1 2 5 576 6 12 8 22 672 1 1 720 2 7 768 4 7 4 18 864 3 5 2 7 896 1 960 7 83 1056 2 1152 1 4 10 1200 1 1296 1 1440 1 3 8 1536 1 3 1 5 1728 4 3 1920 6 2 32 2016 1 2304 1 1 1 6 2400 1 2592 1 1 2880 8 3072 2 3360 1 3456 1 1 1 3840 1 6 4480 1 4608 1 2 2 5760 1 10 6912 1 1 2 7680 1 6 8640 1 9216 3 10368 2 1 11520 1 2 13824 1 3 15360 3 16128 1 17280 1 2 18432 2 2 20736 1 2 28800 1 36864 1 38400 1 55296 1 1 77760 1 82944 1 92160 1 248832 1 403200 1 552960 1 1382400 1 1935360 1 7962624 1 10368000 1 total 805579 1470293676 4207 86223660
本数据集涵盖同构意义下全部(15_4,20_3)与(15_5,25_3)构型(configuration)、所有带有非平凡自同构群(automorphism group)的(16_6,32_3)构型，以及15顶点4正则图、15顶点6正则图、16顶点3正则图与17顶点4正则图。上述构型可唯一对应参数为(15|2^45,3^20)、(15|2^30,3^25)与(16|2^24,3^32)的正则线性空间(regular linear space)。所有文件均采用gzip压缩格式。本数据集为Anton Betten、Dieter Betten、Daniel Heinlein与Patric R. J. Östergård发表的论文《On the Regular Linear Spaces up to Order 16》的补充数据集。 在包含构型的文件中，每行对应一个构型，语法格式为：<点数> <块数b> <B1> <B2> … <Bb> A<自同构群阶数>。其中，Bi为第i个块（i=1,…,b），以十六进制（字符集为0123456789abcdef）编码的点特征向量表示，最低有效位(least significant bit)为最右侧比特。示例：假设共有15个标记为{0,…,14}的点，则块{1,3,14}的特征向量为(0)100|0000|0000|1010。由于每个十六进制数编码4比特，首比特为填充位；竖线用于分隔4比特组，因此该块的编码为`400a`。以下为其中一个配置文件的首行示例： $ zcat conf_15_4_20_3.txt.gz | head -n1 15 20 1081 4101 2201 0c01 0026 004a 0092 4402 008c 0054 0a04 0038 2108 1110 0160 0620 08c0 5200 3400 6800 A1 对于包含图的文件，我们采用graph6格式，但会按照前述构型的格式，在每行末尾追加对应的自同构群阶数（无需字母A）。可用于处理graph6格式图的程序可在与图同构程序nauty配套的gtools工具包中获取（https://pallini.di.uniroma1.it/）。有关graph6格式的详细说明可参考nauty的官方文档（https://pallini.di.uniroma1.it/Guide.html）。 对于本文集中所有顶点数不超过62的图，graph6格式的行等价于经ASCII转换后的`<顶点数n + 63> <ADJ>`，其中ADJ为邻接矩阵(adjacency matrix)的上三角部分，按列优先顺序读取（即采用顺序01, 02, 12, 03, 13, 23, …），长度为`n*(n-1)/2`，编码步骤如下： 1. 在右侧填充比特至长度为6的整数倍； 2. 将结果按6比特为一组拆分，并将每组转换为十进制数； 3. 对每个十进制数加63后转换为ASCII字符。 我们进一步将非标准格式的graph6行追加为：`<空格><自同构群阶数>`。示例：假设有一个5顶点的图，边为02、04、13、34（对应路径2-0-4-3-1），其邻接矩阵为： 00101 00010 10000 01001 10010 因此按列优先读取的上三角部分为`0100101001`。填充后得到`010010100100`，分组后为`010010|100100`。转换为十进制并加63后得到`63+16+2 | 63+32+4`，即`81|99`。顶点数为5，因此前缀为`5+63=68`，最终graph6格式的行为`DQc`，追加自同构群阶数后为`DQc 2`。以下为其中一个图文件的首行示例： $ zcat graph_15_4.txt.gz | head -n1 Ns_???BAwjDoTOY_M_? 2 下表列出了各自同构群阶数对应的同构类数量。未存储无任何非平凡自同构的(16_6,32_3)正则线性空间，其同构类总数为114711393113。总计数分别为251808770（15_4,20_3构型）、1442538454（15_5,25_3构型）与114712539165（16_6,32_3构型）。 四类正则图的同构类统计总计数分别为：805579（15顶点4正则图）、1470293676（15顶点6正则图）、4207（16顶点3正则图）与86223660（17顶点4正则图）。
