The gt file format

The gt file format#

The gt file format is a simple binary format designed to store graph-tool Graph instances in a compact and fast manner, including all types of property maps supported by the library. It serves as an alternative to the text-based graphml format for very large graphs where I/O may become very time and space consuming.

Here we describe the encoding in detail, using as an example the lesmis network from the graph_tool.collection module.

The header begins with the magic string gt in utf-8 encoding, totaling 6 bytes, followed by the version number (currently 0x01) in a single byte, and a Boolean (also a single byte) determining the endianness (0x00: little-endian, 0x01: big-endian):

00000000  e2 9b be 20 67 74 01 00                           |... gt..|
00000008

This is followed by a comment string. Strings are stored by a length (8 bytes, uint64_t) and the corresponding sequence of bytes, not null-terminated. The comment may be empty, but graph-tool outputs a human readable summary of the file, which can be inspected with tools like hexdump:

00000000  e2 9b be 20 67 74 01 00  dd 00 00 00 00 00 00 00  |... gt..........|
00000010  67 72 61 70 68 2d 74 6f  6f 6c 20 62 69 6e 61 72  |graph-tool binar|
00000020  79 20 66 69 6c 65 20 28  68 74 74 70 3a 3a 2f 2f  |y file (http:://|
00000030  67 72 61 70 68 2d 74 6f  6f 6c 2e 73 6b 65 77 65  |graph-tool.skewe|
00000040  64 2e 64 65 29 20 67 65  6e 65 72 61 74 65 64 20  |d.de) generated |
00000050  62 79 20 76 65 72 73 69  6f 6e 20 32 2e 32 2e 33  |by version 2.2.3|
00000060  32 64 65 76 20 28 63 6f  6d 6d 69 74 20 64 34 66  |2dev (commit d4f|
00000070  31 66 31 62 66 2c 20 4d  6f 6e 20 41 75 67 20 31  |1f1bf, Mon Aug 1|
00000080  31 20 31 36 3a 32 36 3a  35 34 20 32 30 31 34 20  |1 16:26:54 2014 |
00000090  2b 30 32 30 30 29 20 73  74 61 74 73 3a 20 37 37  |+0200) stats: 77|
000000a0  20 76 65 72 74 69 63 65  73 2c 20 32 35 34 20 65  | vertices, 254 e|
000000b0  64 67 65 73 2c 20 75 6e  64 69 72 65 63 74 65 64  |dges, undirected|
000000c0  2c 20 32 20 67 72 61 70  68 20 70 72 6f 70 73 2c  |, 2 graph props,|
000000d0  20 32 20 76 65 72 74 65  78 20 70 72 6f 70 73 2c  | 2 vertex props,|
000000e0  20 31 20 65 64 67 65 20  70 72 6f 70 73           | 1 edge props|
000000ed

The adjacency list now follows, beginning with a Boolean byte specifying whether or not the graph is directed (0x00: undirected, 0x01: directed), and 8 bytes (uint64_t) containing the number of nodes, N. It is followed by the list of out-neighbors of all N nodes in sequence. The sequence itself determines implicitly the index of the nodes, in the range from 0 to N-1. The list of out-neighbors of a given node is composed of a length (8 bytes, uint64_t) and a sequence of node indices with this length. The number of bytes d used to encode the node indices in this list is determined by the value of N, and will be the smallest value of the set {1, 2, 4, 8} (i.e. {uint8_t, uint16_t, uint32_t, uint64_t}, respectively) which is sufficient to accommodate all N nodes. For undirected graphs, here it is important that each edge appears only once, i.e. if node u appears in the list of neighbors of v, then v should not appear in the list of u again, otherwise it will be considered as a different (parallel) edge. In this way, the total number of bytes used for the adjacency is 1 + 8 + N * 8 + E * d with E being the number of edges:

00000000  e2 9b be 20 67 74 01 00  dd 00 00 00 00 00 00 00  |... gt..........|
00000010  67 72 61 70 68 2d 74 6f  6f 6c 20 62 69 6e 61 72  |graph-tool binar|
00000020  79 20 66 69 6c 65 20 28  68 74 74 70 3a 3a 2f 2f  |y file (http:://|
00000030  67 72 61 70 68 2d 74 6f  6f 6c 2e 73 6b 65 77 65  |graph-tool.skewe|
00000040  64 2e 64 65 29 20 67 65  6e 65 72 61 74 65 64 20  |d.de) generated |
00000050  62 79 20 76 65 72 73 69  6f 6e 20 32 2e 32 2e 33  |by version 2.2.3|
00000060  32 64 65 76 20 28 63 6f  6d 6d 69 74 20 64 34 66  |2dev (commit d4f|
00000070  31 66 31 62 66 2c 20 4d  6f 6e 20 41 75 67 20 31  |1f1bf, Mon Aug 1|
00000080  31 20 31 36 3a 32 36 3a  35 34 20 32 30 31 34 20  |1 16:26:54 2014 |
00000090  2b 30 32 30 30 29 20 73  74 61 74 73 3a 20 37 37  |+0200) stats: 77|
000000a0  20 76 65 72 74 69 63 65  73 2c 20 32 35 34 20 65  | vertices, 254 e|
000000b0  64 67 65 73 2c 20 75 6e  64 69 72 65 63 74 65 64  |dges, undirected|
000000c0  2c 20 32 20 67 72 61 70  68 20 70 72 6f 70 73 2c  |, 2 graph props,|
000000d0  20 32 20 76 65 72 74 65  78 20 70 72 6f 70 73 2c  | 2 vertex props,|
000000e0  20 31 20 65 64 67 65 20  70 72 6f 70 73 00 4d 00  | 1 edge props.M.|
000000f0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 01 00  |................|
00000100  00 00 00 00 00 00 00 01  00 00 00 00 00 00 00 00  |................|
00000110  02 00 00 00 00 00 00 00  00 02 01 00 00 00 00 00  |................|
00000120  00 00 00 01 00 00 00 00  00 00 00 00 01 00 00 00  |................|
00000130  00 00 00 00 00 01 00 00  00 00 00 00 00 00 01 00  |................|
00000140  00 00 00 00 00 00 00 01  00 00 00 00 00 00 00 00  |................|
00000150  00 00 00 00 00 00 00 00  04 00 00 00 00 00 00 00  |................|
00000160  0a 03 02 00 01 00 00 00  00 00 00 00 0b 01 00 00  |................|
00000170  00 00 00 00 00 0b 01 00  00 00 00 00 00 00 0b 01  |................|
00000180  00 00 00 00 00 00 00 0b  00 00 00 00 00 00 00 00  |................|
00000190  01 00 00 00 00 00 00 00  10 02 00 00 00 00 00 00  |................|
000001a0  00 10 11 03 00 00 00 00  00 00 00 10 11 12 04 00  |................|
000001b0  00 00 00 00 00 00 10 11  12 13 05 00 00 00 00 00  |................|
000001c0  00 00 10 11 12 13 14 06  00 00 00 00 00 00 00 10  |................|
000001d0  11 12 13 14 15 09 00 00  00 00 00 00 00 10 11 12  |................|
000001e0  13 14 15 16 0c 0b 02 00  00 00 00 00 00 00 17 0b  |................|
000001f0  03 00 00 00 00 00 00 00  18 17 0b 04 00 00 00 00  |................|
00000200  00 00 00 18 0b 10 19 05  00 00 00 00 00 00 00 0b  |................|
00000210  17 19 18 1a 02 00 00 00  00 00 00 00 0b 1b 03 00  |................|
00000220  00 00 00 00 00 00 17 1b  0b 01 00 00 00 00 00 00  |................|
00000230  00 17 04 00 00 00 00 00  00 00 1e 0b 17 1b 01 00  |................|
00000240  00 00 00 00 00 00 0b 02  00 00 00 00 00 00 00 0b  |................|
00000250  1b 02 00 00 00 00 00 00  00 0b 1d 03 00 00 00 00  |................|
00000260  00 00 00 0b 22 1d 04 00  00 00 00 00 00 00 22 23  |...."........."#|
00000270  0b 1d 05 00 00 00 00 00  00 00 22 23 24 0b 1d 06  |.........."#$...|
00000280  00 00 00 00 00 00 00 22  23 24 25 0b 1d 01 00 00  |......."#$%.....|
00000290  00 00 00 00 00 19 01 00  00 00 00 00 00 00 19 02  |................|
000002a0  00 00 00 00 00 00 00 18  19 03 00 00 00 00 00 00  |................|
000002b0  00 29 19 18 03 00 00 00  00 00 00 00 0b 1a 1b 02  |.)..............|
000002c0  00 00 00 00 00 00 00 1c  0b 01 00 00 00 00 00 00  |................|
000002d0  00 1c 00 00 00 00 00 00  00 00 01 00 00 00 00 00  |................|
000002e0  00 00 2e 04 00 00 00 00  00 00 00 2f 19 1b 0b 02  |.........../....|
000002f0  00 00 00 00 00 00 00 1a  0b 02 00 00 00 00 00 00  |................|
00000300  00 31 18 03 00 00 00 00  00 00 00 31 1a 0b 02 00  |.1.........1....|
00000310  00 00 00 00 00 00 33 27  01 00 00 00 00 00 00 00  |......3'........|
00000320  33 03 00 00 00 00 00 00  00 33 31 1a 0a 00 00 00  |3........31.....|
00000330  00 00 00 00 33 31 27 36  1a 0b 10 19 29 30 02 00  |....31'6....)0..|
00000340  00 00 00 00 00 00 31 37  03 00 00 00 00 00 00 00  |......17........|
00000350  37 29 30 05 00 00 00 00  00 00 00 37 30 1b 39 0b  |7)0........70.9.|
00000360  04 00 00 00 00 00 00 00  3a 37 30 39 03 00 00 00  |........:709....|
00000370  00 00 00 00 30 3a 3b 06  00 00 00 00 00 00 00 30  |....0:;........0|
00000380  3a 3c 3b 39 37 08 00 00  00 00 00 00 00 37 3a 3b  |:<;97........7:;|
00000390  30 39 29 3d 3c 08 00 00  00 00 00 00 00 3b 30 3e  |09)=<........;0>|
000003a0  39 3a 3d 3c 37 0a 00 00  00 00 00 00 00 37 3e 30  |9:=<7........7>0|
000003b0  3f 3a 3d 3c 3b 39 0b 0a  00 00 00 00 00 00 00 3f  |?:=<;9.........?|
000003c0  40 30 3e 3a 3d 3c 3b 39  37 09 00 00 00 00 00 00  |@0>:=<;97.......|
000003d0  00 40 3a 3b 3e 41 30 3f  3d 3c 01 00 00 00 00 00  |.@:;>A0?=<......|
000003e0  00 00 39 06 00 00 00 00  00 00 00 19 0b 18 1b 30  |..9............0|
000003f0  29 07 00 00 00 00 00 00  00 19 44 0b 18 1b 30 29  |).........D...0)|
00000400  08 00 00 00 00 00 00 00  19 45 44 0b 18 1b 29 3a  |.........ED...):|
00000410  08 00 00 00 00 00 00 00  1b 45 44 46 0b 30 29 19  |.........EDF.0).|
00000420  03 00 00 00 00 00 00 00  1a 1b 0b 01 00 00 00 00  |................|
00000430  00 00 00 30 02 00 00 00  00 00 00 00 30 49 07 00  |...0........0I..|
00000440  00 00 00 00 00 00 45 44  19 30 29 46 47 07 00 00  |......ED.0)FG...|
00000450  00 00 00 00 00 40 41 42  3f 3e 30 3a              |.....@AB?>0:|
0000045c

The adjacency is followed by a list of property maps. The list begins with a total number of property maps (8 bytes, uint64_t), and then the individual records. Each property map begins with a key type (1 byte, uint8_t) specifying whether it is a graph (0x00), a vertex (0x01) or an edge (0x02) property map, followed by a string (8 byte length + length bytes) containing the name of the property map. This is then followed by a byte (uint8_t) specifying the value type index, from the following table:

Type name

Bytes

Index

bool

1

0x00

int16_t

2

0x01

int32_t

4

0x02

int64_t

8

0x03

double

8

0x04

long double

16

0x05

string

8 + length

0x06

vector<bool>

8 + length

0x07

vector<int16_t>

8 + 2 * length

0x08

vector<int32_t>

8 + 4 * length

0x09

vector<int64_t>

8 + 8 * length

0x0a

vector<double>

8 + 8 * length

0x0b

vector<long double>

8 + 16 * length

0x0c

vector<string>

8 + <variable>

0x0d

python::object

8 + length

0x0e

The values of the property map follow in the order of the vertex indices (for vertex properties) or in the same order in which the edges appear in the preceding adjacency list (for edge properties). For graph properties only one value follows. Strings and vectors are encoded with a length prefix of 8 bytes (uint64_t) followed by a sequence of that size with the appropriate element size. The elements of vector<string> are encoded as pairs of (8 byte length, bytes) as usual. Values of type python::object are encoded just as strings, with the string content encoded or decoded via pickle.

00000000  e2 9b be 20 67 74 01 00  dd 00 00 00 00 00 00 00  |... gt..........|
00000010  67 72 61 70 68 2d 74 6f  6f 6c 20 62 69 6e 61 72  |graph-tool binar|
00000020  79 20 66 69 6c 65 20 28  68 74 74 70 3a 3a 2f 2f  |y file (http:://|
00000030  67 72 61 70 68 2d 74 6f  6f 6c 2e 73 6b 65 77 65  |graph-tool.skewe|
00000040  64 2e 64 65 29 20 67 65  6e 65 72 61 74 65 64 20  |d.de) generated |
00000050  62 79 20 76 65 72 73 69  6f 6e 20 32 2e 32 2e 33  |by version 2.2.3|
00000060  32 64 65 76 20 28 63 6f  6d 6d 69 74 20 64 34 66  |2dev (commit d4f|
00000070  31 66 31 62 66 2c 20 4d  6f 6e 20 41 75 67 20 31  |1f1bf, Mon Aug 1|
00000080  31 20 31 36 3a 32 36 3a  35 34 20 32 30 31 34 20  |1 16:26:54 2014 |
00000090  2b 30 32 30 30 29 20 73  74 61 74 73 3a 20 37 37  |+0200) stats: 77|
000000a0  20 76 65 72 74 69 63 65  73 2c 20 32 35 34 20 65  | vertices, 254 e|
000000b0  64 67 65 73 2c 20 75 6e  64 69 72 65 63 74 65 64  |dges, undirected|
000000c0  2c 20 32 20 67 72 61 70  68 20 70 72 6f 70 73 2c  |, 2 graph props,|
000000d0  20 32 20 76 65 72 74 65  78 20 70 72 6f 70 73 2c  | 2 vertex props,|
000000e0  20 31 20 65 64 67 65 20  70 72 6f 70 73 00 4d 00  | 1 edge props.M.|
000000f0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 01 00  |................|
00000100  00 00 00 00 00 00 00 01  00 00 00 00 00 00 00 00  |................|
00000110  02 00 00 00 00 00 00 00  00 02 01 00 00 00 00 00  |................|
00000120  00 00 00 01 00 00 00 00  00 00 00 00 01 00 00 00  |................|
00000130  00 00 00 00 00 01 00 00  00 00 00 00 00 00 01 00  |................|
00000140  00 00 00 00 00 00 00 01  00 00 00 00 00 00 00 00  |................|
00000150  00 00 00 00 00 00 00 00  04 00 00 00 00 00 00 00  |................|
00000160  0a 03 02 00 01 00 00 00  00 00 00 00 0b 01 00 00  |................|
00000170  00 00 00 00 00 0b 01 00  00 00 00 00 00 00 0b 01  |................|
00000180  00 00 00 00 00 00 00 0b  00 00 00 00 00 00 00 00  |................|
00000190  01 00 00 00 00 00 00 00  10 02 00 00 00 00 00 00  |................|
000001a0  00 10 11 03 00 00 00 00  00 00 00 10 11 12 04 00  |................|
000001b0  00 00 00 00 00 00 10 11  12 13 05 00 00 00 00 00  |................|
000001c0  00 00 10 11 12 13 14 06  00 00 00 00 00 00 00 10  |................|
000001d0  11 12 13 14 15 09 00 00  00 00 00 00 00 10 11 12  |................|
000001e0  13 14 15 16 0c 0b 02 00  00 00 00 00 00 00 17 0b  |................|
000001f0  03 00 00 00 00 00 00 00  18 17 0b 04 00 00 00 00  |................|
00000200  00 00 00 18 0b 10 19 05  00 00 00 00 00 00 00 0b  |................|
00000210  17 19 18 1a 02 00 00 00  00 00 00 00 0b 1b 03 00  |................|
00000220  00 00 00 00 00 00 17 1b  0b 01 00 00 00 00 00 00  |................|
00000230  00 17 04 00 00 00 00 00  00 00 1e 0b 17 1b 01 00  |................|
00000240  00 00 00 00 00 00 0b 02  00 00 00 00 00 00 00 0b  |................|
00000250  1b 02 00 00 00 00 00 00  00 0b 1d 03 00 00 00 00  |................|
00000260  00 00 00 0b 22 1d 04 00  00 00 00 00 00 00 22 23  |...."........."#|
00000270  0b 1d 05 00 00 00 00 00  00 00 22 23 24 0b 1d 06  |.........."#$...|
00000280  00 00 00 00 00 00 00 22  23 24 25 0b 1d 01 00 00  |......."#$%.....|
00000290  00 00 00 00 00 19 01 00  00 00 00 00 00 00 19 02  |................|
000002a0  00 00 00 00 00 00 00 18  19 03 00 00 00 00 00 00  |................|
000002b0  00 29 19 18 03 00 00 00  00 00 00 00 0b 1a 1b 02  |.)..............|
000002c0  00 00 00 00 00 00 00 1c  0b 01 00 00 00 00 00 00  |................|
000002d0  00 1c 00 00 00 00 00 00  00 00 01 00 00 00 00 00  |................|
000002e0  00 00 2e 04 00 00 00 00  00 00 00 2f 19 1b 0b 02  |.........../....|
000002f0  00 00 00 00 00 00 00 1a  0b 02 00 00 00 00 00 00  |................|
00000300  00 31 18 03 00 00 00 00  00 00 00 31 1a 0b 02 00  |.1.........1....|
00000310  00 00 00 00 00 00 33 27  01 00 00 00 00 00 00 00  |......3'........|
00000320  33 03 00 00 00 00 00 00  00 33 31 1a 0a 00 00 00  |3........31.....|
00000330  00 00 00 00 33 31 27 36  1a 0b 10 19 29 30 02 00  |....31'6....)0..|
00000340  00 00 00 00 00 00 31 37  03 00 00 00 00 00 00 00  |......17........|
00000350  37 29 30 05 00 00 00 00  00 00 00 37 30 1b 39 0b  |7)0........70.9.|
00000360  04 00 00 00 00 00 00 00  3a 37 30 39 03 00 00 00  |........:709....|
00000370  00 00 00 00 30 3a 3b 06  00 00 00 00 00 00 00 30  |....0:;........0|
00000380  3a 3c 3b 39 37 08 00 00  00 00 00 00 00 37 3a 3b  |:<;97........7:;|
00000390  30 39 29 3d 3c 08 00 00  00 00 00 00 00 3b 30 3e  |09)=<........;0>|
000003a0  39 3a 3d 3c 37 0a 00 00  00 00 00 00 00 37 3e 30  |9:=<7........7>0|
000003b0  3f 3a 3d 3c 3b 39 0b 0a  00 00 00 00 00 00 00 3f  |?:=<;9.........?|
000003c0  40 30 3e 3a 3d 3c 3b 39  37 09 00 00 00 00 00 00  |@0>:=<;97.......|
000003d0  00 40 3a 3b 3e 41 30 3f  3d 3c 01 00 00 00 00 00  |.@:;>A0?=<......|
000003e0  00 00 39 06 00 00 00 00  00 00 00 19 0b 18 1b 30  |..9............0|
000003f0  29 07 00 00 00 00 00 00  00 19 44 0b 18 1b 30 29  |).........D...0)|
00000400  08 00 00 00 00 00 00 00  19 45 44 0b 18 1b 29 3a  |.........ED...):|
00000410  08 00 00 00 00 00 00 00  1b 45 44 46 0b 30 29 19  |.........EDF.0).|
00000420  03 00 00 00 00 00 00 00  1a 1b 0b 01 00 00 00 00  |................|
00000430  00 00 00 30 02 00 00 00  00 00 00 00 30 49 07 00  |...0........0I..|
00000440  00 00 00 00 00 00 45 44  19 30 29 46 47 07 00 00  |......ED.0)FG...|
00000450  00 00 00 00 00 40 41 42  3f 3e 30 3a 05 00 00 00  |.....@AB?>0:....|
00000460  00 00 00 00 00 0b 00 00  00 00 00 00 00 64 65 73  |.............des|
00000470  63 72 69 70 74 69 6f 6e  06 24 01 00 00 00 00 00  |cription.$......|
00000480  00 4c 65 73 20 4d 69 73  65 72 61 62 6c 65 73 3a  |.Les Miserables:|
00000490  20 63 6f 61 70 70 65 61  72 61 6e 63 65 20 6e 65  | coappearance ne|
000004a0  74 77 6f 72 6b 20 6f 66  20 63 68 61 72 61 63 74  |twork of charact|
000004b0  65 72 73 20 69 6e 20 74  68 65 20 6e 6f 76 65 6c  |ers in the novel|
000004c0  20 4c 65 73 20 4d 69 73  65 72 61 62 6c 65 73 2e  | Les Miserables.|
000004d0  20 50 6c 65 61 73 65 20  63 69 74 65 20 44 2e 20  | Please cite D. |
000004e0  45 2e 20 4b 6e 75 74 68  2c 20 54 68 65 20 53 74  |E. Knuth, The St|
000004f0  61 6e 66 6f 72 64 20 47  72 61 70 68 42 61 73 65  |anford GraphBase|
00000500  3a 20 41 20 50 6c 61 74  66 6f 72 6d 20 66 6f 72  |: A Platform for|
00000510  20 43 6f 6d 62 69 6e 61  74 6f 72 69 61 6c 20 43  | Combinatorial C|
00000520  6f 6d 70 75 74 69 6e 67  2c 20 41 64 64 69 73 6f  |omputing, Addiso|
00000530  6e 2d 57 65 73 6c 65 79  2c 20 52 65 61 64 69 6e  |n-Wesley, Readin|
00000540  67 2c 20 4d 41 20 28 31  39 39 33 29 2e 20 52 65  |g, MA (1993). Re|
00000550  74 72 69 65 76 65 64 20  66 72 6f 6d 20 60 4d 61  |trieved from `Ma|
00000560  72 6b 20 4e 65 77 6d 61  6e 27 73 20 77 65 62 73  |rk Newman's webs|
00000570  69 74 65 20 3c 68 74 74  70 3a 2f 2f 77 77 77 2d  |ite <http://www-|
00000580  70 65 72 73 6f 6e 61 6c  2e 75 6d 69 63 68 2e 65  |personal.umich.e|
00000590  64 75 2f 7e 6d 65 6a 6e  2f 6e 65 74 64 61 74 61  |du/~mejn/netdata|
000005a0  2f 3e 60 5f 2e 00 06 00  00 00 00 00 00 00 72 65  |/>`_..........re|
000005b0  61 64 6d 65 06 e2 01 00  00 00 00 00 00 54 68 65  |adme.........The|
000005c0  20 66 69 6c 65 20 6c 65  73 6d 69 73 2e 67 6d 6c  | file lesmis.gml|
000005d0  20 63 6f 6e 74 61 69 6e  73 20 74 68 65 20 77 65  | contains the we|
000005e0  69 67 68 74 65 64 20 6e  65 74 77 6f 72 6b 20 6f  |ighted network o|
000005f0  66 20 63 6f 61 70 70 65  61 72 61 6e 63 65 73 20  |f coappearances |
00000600  6f 66 0a 63 68 61 72 61  63 74 65 72 73 20 69 6e  |of.characters in|
00000610  20 56 69 63 74 6f 72 20  48 75 67 6f 27 73 20 6e  | Victor Hugo's n|
00000620  6f 76 65 6c 20 22 4c 65  73 20 4d 69 73 65 72 61  |ovel "Les Misera|
00000630  62 6c 65 73 22 2e 20 20  4e 6f 64 65 73 20 72 65  |bles".  Nodes re|
00000640  70 72 65 73 65 6e 74 0a  63 68 61 72 61 63 74 65  |present.characte|
00000650  72 73 20 61 73 20 69 6e  64 69 63 61 74 65 64 20  |rs as indicated |
00000660  62 79 20 74 68 65 20 6c  61 62 65 6c 73 20 61 6e  |by the labels an|
00000670  64 20 65 64 67 65 73 20  63 6f 6e 6e 65 63 74 20  |d edges connect |
00000680  61 6e 79 20 70 61 69 72  20 6f 66 0a 63 68 61 72  |any pair of.char|
00000690  61 63 74 65 72 73 20 74  68 61 74 20 61 70 70 65  |acters that appe|
000006a0  61 72 20 69 6e 20 74 68  65 20 73 61 6d 65 20 63  |ar in the same c|
000006b0  68 61 70 74 65 72 20 6f  66 20 74 68 65 20 62 6f  |hapter of the bo|
000006c0  6f 6b 2e 20 20 54 68 65  20 76 61 6c 75 65 73 20  |ok.  The values |
000006d0  6f 6e 20 74 68 65 0a 65  64 67 65 73 20 61 72 65  |on the.edges are|
000006e0  20 74 68 65 20 6e 75 6d  62 65 72 20 6f 66 20 73  | the number of s|
000006f0  75 63 68 20 63 6f 61 70  70 65 61 72 61 6e 63 65  |uch coappearance|
00000700  73 2e 20 20 54 68 65 20  64 61 74 61 20 6f 6e 20  |s.  The data on |
00000710  63 6f 61 70 70 65 61 72  61 6e 63 65 73 20 77 65  |coappearances we|
00000720  72 65 0a 74 61 6b 65 6e  20 66 72 6f 6d 20 44 2e  |re.taken from D.|
00000730  20 45 2e 20 4b 6e 75 74  68 2c 20 54 68 65 20 53  | E. Knuth, The S|
00000740  74 61 6e 66 6f 72 64 20  47 72 61 70 68 42 61 73  |tanford GraphBas|
00000750  65 3a 20 41 20 50 6c 61  74 66 6f 72 6d 20 66 6f  |e: A Platform fo|
00000760  72 0a 43 6f 6d 62 69 6e  61 74 6f 72 69 61 6c 20  |r.Combinatorial |
00000770  43 6f 6d 70 75 74 69 6e  67 2c 20 41 64 64 69 73  |Computing, Addis|
00000780  6f 6e 2d 57 65 73 6c 65  79 2c 20 52 65 61 64 69  |on-Wesley, Readi|
00000790  6e 67 2c 20 4d 41 20 28  31 39 39 33 29 2e 0a 01  |ng, MA (1993)...|
000007a0  05 00 00 00 00 00 00 00  6c 61 62 65 6c 06 06 00  |........label...|
000007b0  00 00 00 00 00 00 4d 79  72 69 65 6c 08 00 00 00  |......Myriel....|
000007c0  00 00 00 00 4e 61 70 6f  6c 65 6f 6e 0e 00 00 00  |....Napoleon....|
000007d0  00 00 00 00 4d 6c 6c 65  42 61 70 74 69 73 74 69  |....MlleBaptisti|
000007e0  6e 65 0b 00 00 00 00 00  00 00 4d 6d 65 4d 61 67  |ne........MmeMag|
000007f0  6c 6f 69 72 65 0c 00 00  00 00 00 00 00 43 6f 75  |loire........Cou|
00000800  6e 74 65 73 73 44 65 4c  6f 08 00 00 00 00 00 00  |ntessDeLo.......|
00000810  00 47 65 62 6f 72 61 6e  64 0c 00 00 00 00 00 00  |.Geborand.......|
00000820  00 43 68 61 6d 70 74 65  72 63 69 65 72 08 00 00  |.Champtercier...|
00000830  00 00 00 00 00 43 72 61  76 61 74 74 65 05 00 00  |.....Cravatte...|
00000840  00 00 00 00 00 43 6f 75  6e 74 06 00 00 00 00 00  |.....Count......|
00000850  00 00 4f 6c 64 4d 61 6e  07 00 00 00 00 00 00 00  |..OldMan........|
00000860  4c 61 62 61 72 72 65 07  00 00 00 00 00 00 00 56  |Labarre........V|
00000870  61 6c 6a 65 61 6e 0a 00  00 00 00 00 00 00 4d 61  |aljean........Ma|
00000880  72 67 75 65 72 69 74 65  06 00 00 00 00 00 00 00  |rguerite........|
00000890  4d 6d 65 44 65 52 07 00  00 00 00 00 00 00 49 73  |MmeDeR........Is|
000008a0  61 62 65 61 75 07 00 00  00 00 00 00 00 47 65 72  |abeau........Ger|
000008b0  76 61 69 73 09 00 00 00  00 00 00 00 54 68 6f 6c  |vais........Thol|
000008c0  6f 6d 79 65 73 09 00 00  00 00 00 00 00 4c 69 73  |omyes........Lis|
000008d0  74 6f 6c 69 65 72 07 00  00 00 00 00 00 00 46 61  |tolier........Fa|
000008e0  6d 65 75 69 6c 0b 00 00  00 00 00 00 00 42 6c 61  |meuil........Bla|
000008f0  63 68 65 76 69 6c 6c 65  09 00 00 00 00 00 00 00  |cheville........|
00000900  46 61 76 6f 75 72 69 74  65 06 00 00 00 00 00 00  |Favourite.......|
00000910  00 44 61 68 6c 69 61 07  00 00 00 00 00 00 00 5a  |.Dahlia........Z|
00000920  65 70 68 69 6e 65 07 00  00 00 00 00 00 00 46 61  |ephine........Fa|
00000930  6e 74 69 6e 65 0d 00 00  00 00 00 00 00 4d 6d 65  |ntine........Mme|
00000940  54 68 65 6e 61 72 64 69  65 72 0a 00 00 00 00 00  |Thenardier......|
00000950  00 00 54 68 65 6e 61 72  64 69 65 72 07 00 00 00  |..Thenardier....|
00000960  00 00 00 00 43 6f 73 65  74 74 65 06 00 00 00 00  |....Cosette.....|
00000970  00 00 00 4a 61 76 65 72  74 0c 00 00 00 00 00 00  |...Javert.......|
00000980  00 46 61 75 63 68 65 6c  65 76 65 6e 74 0a 00 00  |.Fauchelevent...|
00000990  00 00 00 00 00 42 61 6d  61 74 61 62 6f 69 73 08  |.....Bamatabois.|
000009a0  00 00 00 00 00 00 00 50  65 72 70 65 74 75 65 08  |.......Perpetue.|
000009b0  00 00 00 00 00 00 00 53  69 6d 70 6c 69 63 65 0b  |.......Simplice.|
000009c0  00 00 00 00 00 00 00 53  63 61 75 66 66 6c 61 69  |.......Scaufflai|
000009d0  72 65 06 00 00 00 00 00  00 00 57 6f 6d 61 6e 31  |re........Woman1|
000009e0  05 00 00 00 00 00 00 00  4a 75 64 67 65 0c 00 00  |........Judge...|
000009f0  00 00 00 00 00 43 68 61  6d 70 6d 61 74 68 69 65  |.....Champmathie|
00000a00  75 06 00 00 00 00 00 00  00 42 72 65 76 65 74 0a  |u........Brevet.|
00000a10  00 00 00 00 00 00 00 43  68 65 6e 69 6c 64 69 65  |.......Chenildie|
00000a20  75 0b 00 00 00 00 00 00  00 43 6f 63 68 65 70 61  |u........Cochepa|
00000a30  69 6c 6c 65 09 00 00 00  00 00 00 00 50 6f 6e 74  |ille........Pont|
00000a40  6d 65 72 63 79 0c 00 00  00 00 00 00 00 42 6f 75  |mercy........Bou|
00000a50  6c 61 74 72 75 65 6c 6c  65 07 00 00 00 00 00 00  |latruelle.......|
00000a60  00 45 70 6f 6e 69 6e 65  07 00 00 00 00 00 00 00  |.Eponine........|
00000a70  41 6e 7a 65 6c 6d 61 06  00 00 00 00 00 00 00 57  |Anzelma........W|
00000a80  6f 6d 61 6e 32 0e 00 00  00 00 00 00 00 4d 6f 74  |oman2........Mot|
00000a90  68 65 72 49 6e 6e 6f 63  65 6e 74 07 00 00 00 00  |herInnocent.....|
00000aa0  00 00 00 47 72 69 62 69  65 72 09 00 00 00 00 00  |...Gribier......|
00000ab0  00 00 4a 6f 6e 64 72 65  74 74 65 09 00 00 00 00  |..Jondrette.....|
00000ac0  00 00 00 4d 6d 65 42 75  72 67 6f 6e 08 00 00 00  |...MmeBurgon....|
00000ad0  00 00 00 00 47 61 76 72  6f 63 68 65 0c 00 00 00  |....Gavroche....|
00000ae0  00 00 00 00 47 69 6c 6c  65 6e 6f 72 6d 61 6e 64  |....Gillenormand|
00000af0  06 00 00 00 00 00 00 00  4d 61 67 6e 6f 6e 10 00  |........Magnon..|
00000b00  00 00 00 00 00 00 4d 6c  6c 65 47 69 6c 6c 65 6e  |......MlleGillen|
00000b10  6f 72 6d 61 6e 64 0c 00  00 00 00 00 00 00 4d 6d  |ormand........Mm|
00000b20  65 50 6f 6e 74 6d 65 72  63 79 0b 00 00 00 00 00  |ePontmercy......|
00000b30  00 00 4d 6c 6c 65 56 61  75 62 6f 69 73 0e 00 00  |..MlleVaubois...|
00000b40  00 00 00 00 00 4c 74 47  69 6c 6c 65 6e 6f 72 6d  |.....LtGillenorm|
00000b50  61 6e 64 06 00 00 00 00  00 00 00 4d 61 72 69 75  |and........Mariu|
00000b60  73 09 00 00 00 00 00 00  00 42 61 72 6f 6e 65 73  |s........Barones|
00000b70  73 54 06 00 00 00 00 00  00 00 4d 61 62 65 75 66  |sT........Mabeuf|
00000b80  08 00 00 00 00 00 00 00  45 6e 6a 6f 6c 72 61 73  |........Enjolras|
00000b90  0a 00 00 00 00 00 00 00  43 6f 6d 62 65 66 65 72  |........Combefer|
00000ba0  72 65 09 00 00 00 00 00  00 00 50 72 6f 75 76 61  |re........Prouva|
00000bb0  69 72 65 07 00 00 00 00  00 00 00 46 65 75 69 6c  |ire........Feuil|
00000bc0  6c 79 0a 00 00 00 00 00  00 00 43 6f 75 72 66 65  |ly........Courfe|
00000bd0  79 72 61 63 07 00 00 00  00 00 00 00 42 61 68 6f  |yrac........Baho|
00000be0  72 65 6c 07 00 00 00 00  00 00 00 42 6f 73 73 75  |rel........Bossu|
00000bf0  65 74 04 00 00 00 00 00  00 00 4a 6f 6c 79 09 00  |et........Joly..|
00000c00  00 00 00 00 00 00 47 72  61 6e 74 61 69 72 65 0e  |......Grantaire.|
00000c10  00 00 00 00 00 00 00 4d  6f 74 68 65 72 50 6c 75  |.......MotherPlu|
00000c20  74 61 72 63 68 09 00 00  00 00 00 00 00 47 75 65  |tarch........Gue|
00000c30  75 6c 65 6d 65 72 05 00  00 00 00 00 00 00 42 61  |ulemer........Ba|
00000c40  62 65 74 0a 00 00 00 00  00 00 00 43 6c 61 71 75  |bet........Claqu|
00000c50  65 73 6f 75 73 0c 00 00  00 00 00 00 00 4d 6f 6e  |esous........Mon|
00000c60  74 70 61 72 6e 61 73 73  65 09 00 00 00 00 00 00  |tparnasse.......|
00000c70  00 54 6f 75 73 73 61 69  6e 74 06 00 00 00 00 00  |.Toussaint......|
00000c80  00 00 43 68 69 6c 64 31  06 00 00 00 00 00 00 00  |..Child1........|
00000c90  43 68 69 6c 64 32 06 00  00 00 00 00 00 00 42 72  |Child2........Br|
00000ca0  75 6a 6f 6e 0c 00 00 00  00 00 00 00 4d 6d 65 48  |ujon........MmeH|
00000cb0  75 63 68 65 6c 6f 75 70  01 03 00 00 00 00 00 00  |ucheloup........|
00000cc0  00 70 6f 73 0b 02 00 00  00 00 00 00 00 6e c8 82  |.pos.........n..|
00000cd0  10 aa 06 a1 c0 92 2c ff  95 d9 9d 6c c0 02 00 00  |......,....l....|
00000ce0  00 00 00 00 00 63 e4 06  e4 7b fc a0 c0 1b 96 8c  |.....c...{......|
00000cf0  84 16 45 6c c0 02 00 00  00 00 00 00 00 01 9e b0  |..El............|
00000d00  80 fe 0e a1 c0 53 f1 82  9b 28 a0 6c c0 02 00 00  |.....S...(.l....|
00000d10  00 00 00 00 00 2a 22 05  0b db 0d a1 c0 42 fb 82  |.....*"......B..|
00000d20  44 e2 58 6c c0 02 00 00  00 00 00 00 00 85 c9 58  |D.Xl...........X|
00000d30  e8 95 fb a0 c0 be eb ce  9b 1c fa 6c c0 02 00 00  |...........l....|
00000d40  00 00 00 00 00 73 4d d1  51 dc ff a0 c0 bb 17 30  |.....sM.Q......0|
00000d50  1e 9e 37 6d c0 02 00 00  00 00 00 00 00 19 a9 01  |..7m............|
00000d60  fb 3e fa a0 c0 1e 6f 5c  53 7e 99 6c c0 02 00 00  |.>....o\S~.l....|
00000d70  00 00 00 00 00 85 76 a4  9b 68 05 a1 c0 4e f1 63  |......v..h...N.c|
00000d80  ed 00 39 6d c0 02 00 00  00 00 00 00 00 0e 3b 97  |..9m..........;.|
00000d90  bb 07 00 a1 c0 1c 4e 73  a5 01 b9 6c c0 02 00 00  |......Ns...l....|
00000da0  00 00 00 00 00 e2 76 a4  90 6c 01 a1 c0 02 f4 76  |......v..l.....v|
00000db0  f6 8c 1b 6c c0 02 00 00  00 00 00 00 00 18 d7 fe  |...l............|
00000dc0  98 da 0f a1 c0 74 e0 45  c8 15 df 6b c0 02 00 00  |.....t.E...k....|
00000dd0  00 00 00 00 00 4b d8 fb  ec a9 1d a1 c0 b2 1c b8  |.....K..........|
00000de0  1a 4d 47 6c c0 02 00 00  00 00 00 00 00 05 b6 eb  |.MGl............|
00000df0  85 23 25 a1 c0 35 18 91  b5 40 11 6d c0 02 00 00  |.#%..5...@.m....|
00000e00  00 00 00 00 00 6f 83 35  3d 7e 15 a1 c0 07 56 03  |.....o.5=~....V.|
00000e10  7c 6e e6 6b c0 02 00 00  00 00 00 00 00 45 d8 ae  ||n.k.........E..|
00000e20  23 55 12 a1 c0 34 6e b5  11 41 2a 6c c0 02 00 00  |#U...4n..A*l....|
00000e30  00 00 00 00 00 6a 3b 47  7b 1c 14 a1 c0 26 23 12  |.....j;G{....&#.|
00000e40  7b e3 99 6b c0 02 00 00  00 00 00 00 00 83 62 cf  |{..k..........b.|
00000e50  40 3c 31 a1 c0 2f 1b 86  7f 10 a3 6c c0 02 00 00  |@<1../.....l....|
00000e60  00 00 00 00 00 cd f8 37  78 66 35 a1 c0 ed 4e 5b  |.......7xf5...N[|
00000e70  77 b8 3a 6d c0 02 00 00  00 00 00 00 00 c2 d4 1d  |w.:m............|
00000e80  7b 23 36 a1 c0 90 0a be  da 30 d4 6c c0 02 00 00  |{#6......0.l....|
00000e90  00 00 00 00 00 e5 19 cc  64 8f 37 a1 c0 24 ad 21  |........d.7..$.!|
00000ea0  9e bf 0b 6d c0 02 00 00  00 00 00 00 00 db b2 d0  |...m............|
00000eb0  f8 2e 30 a1 c0 ad ae f8  8e 3e 13 6d c0 02 00 00  |..0......>.m....|
00000ec0  00 00 00 00 00 73 a6 1c  b1 e3 31 a1 c0 92 5b 84  |.....s....1...[.|
00000ed0  d8 81 47 6d c0 02 00 00  00 00 00 00 00 09 78 b8  |..Gm..........x.|
00000ee0  9f 5a 33 a1 c0 de e8 fd  a1 46 fa 6c c0 02 00 00  |.Z3......F.l....|
00000ef0  00 00 00 00 00 01 60 9f  ee 86 2b a1 c0 63 bc d3  |......`...+..c..|
00000f00  3a eb be 6c c0 02 00 00  00 00 00 00 00 76 28 90  |:..l.........v(.|
00000f10  6c 93 27 a1 c0 42 b4 67  40 57 16 6c c0 02 00 00  |l.'..B.g@W.l....|
00000f20  00 00 00 00 00 e7 c4 c6  49 45 27 a1 c0 41 ec 50  |........IE'..A.P|
00000f30  f7 9f d3 6b c0 02 00 00  00 00 00 00 00 c4 10 23  |...k...........#|
00000f40  90 3e 2a a1 c0 c4 1e 7b  f8 30 3d 6c c0 02 00 00  |.>*....{.0=l....|
00000f50  00 00 00 00 00 01 0b d5  bc 11 22 a1 c0 4d e3 54  |.........."..M.T|
00000f60  77 94 2d 6c c0 02 00 00  00 00 00 00 00 7c 0c 07  |w.-l.........|..|
00000f70  af 9d 17 a1 c0 54 a1 6d  7c f7 ad 6c c0 02 00 00  |.....T.m|..l....|
00000f80  00 00 00 00 00 87 31 73  12 93 20 a1 c0 df 42 7d  |......1s.. ...B}|
00000f90  0f a4 cf 6c c0 02 00 00  00 00 00 00 00 9b c4 dd  |...l............|
00000fa0  85 da 29 a1 c0 9d eb b9  8e 8d 60 6d c0 02 00 00  |..).......`m....|
00000fb0  00 00 00 00 00 c6 b3 95  bb 0c 26 a1 c0 cb 9f ed  |..........&.....|
00000fc0  1a cf cb 6c c0 02 00 00  00 00 00 00 00 4e d1 b2  |...l.........N..|
00000fd0  93 28 13 a1 c0 48 e1 09  d7 59 e7 6c c0 02 00 00  |.(...H...Y.l....|
00000fe0  00 00 00 00 00 5a a6 11  73 ed 18 a1 c0 a7 42 2a  |.....Z..s.....B*|
00000ff0  af a7 37 6c c0 02 00 00  00 00 00 00 00 2e 16 53  |..7l...........S|
00001000  fc ef 18 a1 c0 66 ab 8e  60 82 02 6d c0 02 00 00  |.....f..`..m....|
00001010  00 00 00 00 00 1a 08 f5  3c 52 1f a1 c0 0f f0 df  |........<R......|
00001020  33 ae 2f 6d c0 02 00 00  00 00 00 00 00 07 c5 c2  |3./m............|
00001030  6b 79 1d a1 c0 ba 6f f6  a3 75 ff 6c c0 02 00 00  |ky....o..u.l....|
00001040  00 00 00 00 00 a6 e4 8e  87 16 1b a1 c0 13 e2 61  |...............a|
00001050  c4 60 35 6d c0 02 00 00  00 00 00 00 00 ba ab 48  |.`5m...........H|
00001060  24 a7 1b a1 c0 2c a0 10  86 5e cd 6c c0 02 00 00  |$....,...^.l....|
00001070  00 00 00 00 00 05 d7 d0  79 43 33 a1 c0 11 58 ab  |........yC3...X.|
00001080  67 b6 9f 6b c0 02 00 00  00 00 00 00 00 ae 66 73  |g..k..........fs|
00001090  4c ad 31 a1 c0 4e b6 ee  92 9f 2e 6b c0 02 00 00  |L.1..N.....k....|
000010a0  00 00 00 00 00 79 7b 28  6f 8c 25 a1 c0 9b c9 11  |.....y{(o.%.....|
000010b0  17 d3 92 6b c0 02 00 00  00 00 00 00 00 70 77 9e  |...k.........pw.|
000010c0  f0 e7 2d a1 c0 88 aa 1f  d8 8d a1 6b c0 02 00 00  |..-........k....|
000010d0  00 00 00 00 00 9e c2 b2  ad 2e 22 a1 c0 2d 1c c1  |.........."..-..|
000010e0  b5 d8 7e 6c c0 02 00 00  00 00 00 00 00 06 1c 6a  |..~l...........j|
000010f0  5b 31 14 a1 c0 81 03 92  e2 5e 7c 6c c0 02 00 00  |[1.......^|l....|
00001100  00 00 00 00 00 ac b2 ee  6d 98 11 a1 c0 3b 0d 0b  |........m....;..|
00001110  f6 5f 65 6d c0 02 00 00  00 00 00 00 00 45 34 48  |._em.........E4H|
00001120  30 0d 19 a1 c0 ee 62 f0  aa 97 af 69 c0 02 00 00  |0.....b....i....|
00001130  00 00 00 00 00 98 c1 e0  81 d1 1b a1 c0 8e 13 ce  |................|
00001140  53 e0 47 6a c0 02 00 00  00 00 00 00 00 40 30 1d  |S.Gj.........@0.|
00001150  3f 25 20 a1 c0 cd 0b 6b  51 23 40 6b c0 02 00 00  |?% ....kQ#@k....|
00001160  00 00 00 00 00 17 8d 0a  6b 35 2d a1 c0 71 f8 96  |........k5-..q..|
00001170  09 82 f2 6b c0 02 00 00  00 00 00 00 00 9d 4e 8c  |...k..........N.|
00001180  97 3e 34 a1 c0 fd 0a 77  1e 0d 3e 6c c0 02 00 00  |.>4....w..>l....|
00001190  00 00 00 00 00 d7 2d 7a  62 e8 2f a1 c0 25 5c d9  |......-zb./..%\.|
000011a0  23 32 23 6c c0 02 00 00  00 00 00 00 00 79 cb c2  |#2#l.........y..|
000011b0  11 c4 3a a1 c0 60 76 f7  8f cc d1 6b c0 02 00 00  |..:..`v....k....|
000011c0  00 00 00 00 00 f0 3d 0b  cd e3 3c a1 c0 8c 0c c7  |......=...<.....|
000011d0  ff a7 44 6c c0 02 00 00  00 00 00 00 00 a2 db 70  |..Dl...........p|
000011e0  bd c4 32 a1 c0 a7 de 35  e7 76 e9 6b c0 02 00 00  |..2....5.v.k....|
000011f0  00 00 00 00 00 a8 b7 ef  ec 15 2a a1 c0 97 b5 1c  |..........*.....|
00001200  a3 c1 91 6b c0 02 00 00  00 00 00 00 00 76 87 8e  |...k.........v..|
00001210  c7 ae 35 a1 c0 de 42 53  fd c5 68 6b c0 02 00 00  |..5...BS..hk....|
00001220  00 00 00 00 00 d7 bc 63  27 2a 2b a1 c0 4e 92 d3  |.......c'*+..N..|
00001230  12 bd 09 6b c0 02 00 00  00 00 00 00 00 ef fb 08  |...k............|
00001240  9b 12 23 a1 c0 3f c3 a8  ce 25 5a 6b c0 02 00 00  |..#..?...%Zk....|
00001250  00 00 00 00 00 db 4d 43  56 dd 28 a1 c0 72 0a 2e  |......MCV.(..r..|
00001260  07 c9 d5 6a c0 02 00 00  00 00 00 00 00 a1 15 b9  |...j............|
00001270  73 54 25 a1 c0 53 61 b7  d6 fe aa 6a c0 02 00 00  |sT%..Sa....j....|
00001280  00 00 00 00 00 ad 26 a7  bd 2e 28 a1 c0 29 8b f0  |......&...(..)..|
00001290  8e eb 1b 6b c0 02 00 00  00 00 00 00 00 94 fc 04  |...k............|
000012a0  61 42 23 a1 c0 d3 4b 1e  23 74 11 6b c0 02 00 00  |aB#...K.#t.k....|
000012b0  00 00 00 00 00 ab cc 32  05 ca 23 a1 c0 0d ce 64  |.......2..#....d|
000012c0  0a 44 e2 6a c0 02 00 00  00 00 00 00 00 cd ad 5d  |.D.j...........]|
000012d0  b3 3b 25 a1 c0 bf 02 c5  ba c4 3d 6b c0 02 00 00  |.;%.......=k....|
000012e0  00 00 00 00 00 27 e5 2c  80 67 26 a1 c0 b0 0f af  |.....'.,.g&.....|
000012f0  ad bb f2 6a c0 02 00 00  00 00 00 00 00 e8 eb d5  |...j............|
00001300  a0 59 21 a1 c0 64 50 e1  cc 96 be 6a c0 02 00 00  |.Y!..dP....j....|
00001310  00 00 00 00 00 ee 97 70  82 82 32 a1 c0 53 ac 89  |.......p..2..S..|
00001320  ab 23 6e 6a c0 02 00 00  00 00 00 00 00 9a a1 f9  |.#nj............|
00001330  0c e5 22 a1 c0 78 16 51  4b 83 e1 6b c0 02 00 00  |.."..x.QK..k....|
00001340  00 00 00 00 00 c6 26 6b  94 83 1f a1 c0 87 54 87  |......&k......T.|
00001350  53 7e e9 6b c0 02 00 00  00 00 00 00 00 c2 7b 25  |S~.k..........{%|
00001360  71 52 21 a1 c0 a5 8e 3c  2f 21 b7 6b c0 02 00 00  |qR!....</!.k....|
00001370  00 00 00 00 00 d0 35 be  fb 29 1d a1 c0 e6 10 a2  |......5..)......|
00001380  20 44 c2 6b c0 02 00 00  00 00 00 00 00 c5 c7 b3  | D.k............|
00001390  0c 78 26 a1 c0 91 34 b2  fd a2 79 6c c0 02 00 00  |.x&...4...yl....|
000013a0  00 00 00 00 00 38 05 6a  12 be 14 a1 c0 52 0b b2  |.....8.j.....R..|
000013b0  3e 37 e9 6a c0 02 00 00  00 00 00 00 00 87 5e 2b  |>7.j..........^+|
000013c0  e4 59 17 a1 c0 c0 8e 49  75 56 a5 6a c0 02 00 00  |.Y.....IuV.j....|
000013d0  00 00 00 00 00 a7 c0 28  f7 e4 1d a1 c0 d1 04 99  |.......(........|
000013e0  65 31 85 6b c0 02 00 00  00 00 00 00 00 e7 5b 2e  |e1.k..........[.|
000013f0  a9 24 1e a1 c0 98 70 5a  c4 12 ec 6a c0 02 05 00  |.$....pZ...j....|
00001400  00 00 00 00 00 00 76 61  6c 75 65 04 00 00 00 00  |......value.....|
00001410  00 00 f0 3f 00 00 00 00  00 00 20 40 00 00 00 00  |...?...... @....|
00001420  00 00 24 40 00 00 00 00  00 00 18 40 00 00 00 00  |..$@.......@....|
00001430  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001440  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001450  00 00 00 40 00 00 00 00  00 00 f0 3f 00 00 00 00  |...@.......?....|
00001460  00 00 f0 3f 00 00 00 00  00 00 08 40 00 00 00 00  |...?.......@....|
00001470  00 00 08 40 00 00 00 00  00 00 14 40 00 00 00 00  |...@.......@....|
00001480  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001490  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
000014a0  00 00 10 40 00 00 00 00  00 00 10 40 00 00 00 00  |...@.......@....|
000014b0  00 00 10 40 00 00 00 00  00 00 10 40 00 00 00 00  |...@.......@....|
000014c0  00 00 10 40 00 00 00 00  00 00 10 40 00 00 00 00  |...@.......@....|
000014d0  00 00 08 40 00 00 00 00  00 00 08 40 00 00 00 00  |...@.......@....|
000014e0  00 00 08 40 00 00 00 00  00 00 10 40 00 00 00 00  |...@.......@....|
000014f0  00 00 08 40 00 00 00 00  00 00 08 40 00 00 00 00  |...@.......@....|
00001500  00 00 08 40 00 00 00 00  00 00 08 40 00 00 00 00  |...@.......@....|
00001510  00 00 14 40 00 00 00 00  00 00 08 40 00 00 00 00  |...@.......@....|
00001520  00 00 08 40 00 00 00 00  00 00 08 40 00 00 00 00  |...@.......@....|
00001530  00 00 08 40 00 00 00 00  00 00 10 40 00 00 00 00  |...@.......@....|
00001540  00 00 10 40 00 00 00 00  00 00 08 40 00 00 00 00  |...@.......@....|
00001550  00 00 08 40 00 00 00 00  00 00 08 40 00 00 00 00  |...@.......@....|
00001560  00 00 08 40 00 00 00 00  00 00 10 40 00 00 00 00  |...@.......@....|
00001570  00 00 10 40 00 00 00 00  00 00 10 40 00 00 00 00  |...@.......@....|
00001580  00 00 00 40 00 00 00 00  00 00 22 40 00 00 00 00  |...@......"@....|
00001590  00 00 00 40 00 00 00 00  00 00 1c 40 00 00 00 00  |...@.......@....|
000015a0  00 00 2a 40 00 00 00 00  00 00 f0 3f 00 00 00 00  |..*@.......?....|
000015b0  00 00 28 40 00 00 00 00  00 00 10 40 00 00 00 00  |..(@.......@....|
000015c0  00 00 3f 40 00 00 00 00  00 00 f0 3f 00 00 00 00  |..?@.......?....|
000015d0  00 00 f0 3f 00 00 00 00  00 00 31 40 00 00 00 00  |...?......1@....|
000015e0  00 00 14 40 00 00 00 00  00 00 14 40 00 00 00 00  |...@.......@....|
000015f0  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001600  00 00 20 40 00 00 00 00  00 00 f0 3f 00 00 00 00  |.. @.......?....|
00001610  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001620  00 00 00 40 00 00 00 00  00 00 f0 3f 00 00 00 00  |...@.......?....|
00001630  00 00 00 40 00 00 00 00  00 00 08 40 00 00 00 00  |...@.......@....|
00001640  00 00 00 40 00 00 00 00  00 00 f0 3f 00 00 00 00  |...@.......?....|
00001650  00 00 f0 3f 00 00 00 00  00 00 00 40 00 00 00 00  |...?.......@....|
00001660  00 00 f0 3f 00 00 00 00  00 00 08 40 00 00 00 00  |...?.......@....|
00001670  00 00 00 40 00 00 00 00  00 00 08 40 00 00 00 00  |...@.......@....|
00001680  00 00 08 40 00 00 00 00  00 00 00 40 00 00 00 00  |...@.......@....|
00001690  00 00 00 40 00 00 00 00  00 00 00 40 00 00 00 00  |...@.......@....|
000016a0  00 00 00 40 00 00 00 00  00 00 f0 3f 00 00 00 00  |...@.......?....|
000016b0  00 00 00 40 00 00 00 00  00 00 00 40 00 00 00 00  |...@.......@....|
000016c0  00 00 00 40 00 00 00 00  00 00 00 40 00 00 00 00  |...@.......@....|
000016d0  00 00 f0 3f 00 00 00 00  00 00 00 40 00 00 00 00  |...?.......@....|
000016e0  00 00 00 40 00 00 00 00  00 00 00 40 00 00 00 00  |...@.......@....|
000016f0  00 00 00 40 00 00 00 00  00 00 00 40 00 00 00 00  |...@.......@....|
00001700  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001710  00 00 f0 3f 00 00 00 00  00 00 00 40 00 00 00 00  |...?.......@....|
00001720  00 00 08 40 00 00 00 00  00 00 00 40 00 00 00 00  |...@.......@....|
00001730  00 00 00 40 00 00 00 00  00 00 f0 3f 00 00 00 00  |...@.......?....|
00001740  00 00 08 40 00 00 00 00  00 00 f0 3f 00 00 00 00  |...@.......?....|
00001750  00 00 f0 3f 00 00 00 00  00 00 08 40 00 00 00 00  |...?.......@....|
00001760  00 00 f0 3f 00 00 00 00  00 00 00 40 00 00 00 00  |...?.......@....|
00001770  00 00 f0 3f 00 00 00 00  00 00 00 40 00 00 00 00  |...?.......@....|
00001780  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001790  00 00 f0 3f 00 00 00 00  00 00 08 40 00 00 00 00  |...?.......@....|
000017a0  00 00 00 40 00 00 00 00  00 00 f0 3f 00 00 00 00  |...@.......?....|
000017b0  00 00 f0 3f 00 00 00 00  00 00 22 40 00 00 00 00  |...?......"@....|
000017c0  00 00 00 40 00 00 00 00  00 00 00 40 00 00 00 00  |...@.......@....|
000017d0  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
000017e0  00 00 f0 3f 00 00 00 00  00 00 00 40 00 00 00 00  |...?.......@....|
000017f0  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001800  00 00 18 40 00 00 00 00  00 00 28 40 00 00 00 00  |...@......(@....|
00001810  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001820  00 00 35 40 00 00 00 00  00 00 33 40 00 00 00 00  |..5@......3@....|
00001830  00 00 f0 3f 00 00 00 00  00 00 00 40 00 00 00 00  |...?.......@....|
00001840  00 00 14 40 00 00 00 00  00 00 10 40 00 00 00 00  |...@.......@....|
00001850  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001860  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001870  00 00 f0 3f 00 00 00 00  00 00 1c 40 00 00 00 00  |...?.......@....|
00001880  00 00 1c 40 00 00 00 00  00 00 18 40 00 00 00 00  |...@.......@....|
00001890  00 00 f0 3f 00 00 00 00  00 00 10 40 00 00 00 00  |...?.......@....|
000018a0  00 00 2e 40 00 00 00 00  00 00 14 40 00 00 00 00  |...@.......@....|
000018b0  00 00 18 40 00 00 00 00  00 00 00 40 00 00 00 00  |...@.......@....|
000018c0  00 00 f0 3f 00 00 00 00  00 00 10 40 00 00 00 00  |...?.......@....|
000018d0  00 00 00 40 00 00 00 00  00 00 00 40 00 00 00 00  |...@.......@....|
000018e0  00 00 18 40 00 00 00 00  00 00 00 40 00 00 00 00  |...@.......@....|
000018f0  00 00 14 40 00 00 00 00  00 00 f0 3f 00 00 00 00  |...@.......?....|
00001900  00 00 f0 3f 00 00 00 00  00 00 22 40 00 00 00 00  |...?......"@....|
00001910  00 00 31 40 00 00 00 00  00 00 2a 40 00 00 00 00  |..1@......*@....|
00001920  00 00 1c 40 00 00 00 00  00 00 00 40 00 00 00 00  |...@.......@....|
00001930  00 00 f0 3f 00 00 00 00  00 00 18 40 00 00 00 00  |...?.......@....|
00001940  00 00 08 40 00 00 00 00  00 00 14 40 00 00 00 00  |...@.......@....|
00001950  00 00 14 40 00 00 00 00  00 00 18 40 00 00 00 00  |...@.......@....|
00001960  00 00 00 40 00 00 00 00  00 00 10 40 00 00 00 00  |...@.......@....|
00001970  00 00 08 40 00 00 00 00  00 00 00 40 00 00 00 00  |...@.......@....|
00001980  00 00 f0 3f 00 00 00 00  00 00 14 40 00 00 00 00  |...?.......@....|
00001990  00 00 28 40 00 00 00 00  00 00 14 40 00 00 00 00  |..(@.......@....|
000019a0  00 00 10 40 00 00 00 00  00 00 24 40 00 00 00 00  |...@......$@....|
000019b0  00 00 18 40 00 00 00 00  00 00 00 40 00 00 00 00  |...@.......@....|
000019c0  00 00 22 40 00 00 00 00  00 00 f0 3f 00 00 00 00  |.."@.......?....|
000019d0  00 00 f0 3f 00 00 00 00  00 00 14 40 00 00 00 00  |...?.......@....|
000019e0  00 00 1c 40 00 00 00 00  00 00 08 40 00 00 00 00  |...@.......@....|
000019f0  00 00 14 40 00 00 00 00  00 00 14 40 00 00 00 00  |...@.......@....|
00001a00  00 00 14 40 00 00 00 00  00 00 00 40 00 00 00 00  |...@.......@....|
00001a10  00 00 14 40 00 00 00 00  00 00 f0 3f 00 00 00 00  |...@.......?....|
00001a20  00 00 00 40 00 00 00 00  00 00 08 40 00 00 00 00  |...@.......@....|
00001a30  00 00 08 40 00 00 00 00  00 00 f0 3f 00 00 00 00  |...@.......?....|
00001a40  00 00 00 40 00 00 00 00  00 00 00 40 00 00 00 00  |...@.......@....|
00001a50  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001a60  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001a70  00 00 08 40 00 00 00 00  00 00 14 40 00 00 00 00  |...@.......@....|
00001a80  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001a90  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001aa0  00 00 f0 3f 00 00 00 00  00 00 18 40 00 00 00 00  |...?.......@....|
00001ab0  00 00 18 40 00 00 00 00  00 00 f0 3f 00 00 00 00  |...@.......?....|
00001ac0  00 00 f0 3f 00 00 00 00  00 00 00 40 00 00 00 00  |...?.......@....|
00001ad0  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001ae0  00 00 10 40 00 00 00 00  00 00 10 40 00 00 00 00  |...@.......@....|
00001af0  00 00 10 40 00 00 00 00  00 00 f0 3f 00 00 00 00  |...@.......?....|
00001b00  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001b10  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001b20  00 00 f0 3f 00 00 00 00  00 00 00 40 00 00 00 00  |...?.......@....|
00001b30  00 00 00 40 00 00 00 00  00 00 00 40 00 00 00 00  |...@.......@....|
00001b40  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001b50  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001b60  00 00 00 40 00 00 00 00  00 00 f0 3f 00 00 00 00  |...@.......?....|
00001b70  00 00 f0 3f 00 00 00 00  00 00 00 40 00 00 00 00  |...?.......@....|
00001b80  00 00 00 40 00 00 00 00  00 00 08 40 00 00 00 00  |...@.......@....|
00001b90  00 00 08 40 00 00 00 00  00 00 08 40 00 00 00 00  |...@.......@....|
00001ba0  00 00 08 40 00 00 00 00  00 00 f0 3f 00 00 00 00  |...@.......?....|
00001bb0  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001bc0  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001bd0  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001be0  00 00 f0 3f 00 00 00 00  00 00 f0 3f 00 00 00 00  |...?.......?....|
00001bf0  00 00 f0 3f 00 00 00 00  00 00 f0 3f              |...?.......?|
00001bfc

This file has an overall length of 0x00001bfc == 7164 bytes. In comparison, a graphml encoding results in 37506 bytes. Compressing both files with LZMA results in 2800 and 4192 bytes, respectively. However, this difference (even when compressed) tends to increase, often considerably, for larger graphs. Furthermore the reading and writing in the gt format tends to be about an order of magnitude faster than graphml, and largely I/O-bound, instead of the latter, which is often CPU-bound. Here is an example for a somewhat larger graph:

>>> import timeit
>>> g = gt.collection.data["pgp-strong-2009"]
>>> g.properties.clear()   # Use only topology for benchmark
>>> timeit.Timer(lambda: g.save("/tmp/pgp_graph.xml")).timeit(number=1)  
0.08416466903872788
>>> timeit.Timer(lambda: g.save("/tmp/pgp_graph.xml.xz")).timeit(number=1)  
14.706654848065227
>>> timeit.Timer(lambda: g.save("/tmp/pgp_graph.gt")).timeit(number=1)  
0.005980597110465169
>>> timeit.Timer(lambda: g.save("/tmp/pgp_graph.gt.xz")).timeit(number=1)  
0.43757575505878776
>>> timeit.Timer(lambda: gt.load_graph("/tmp/pgp_graph.xml")).timeit(number=1)  
0.9056955680716783
>>> timeit.Timer(lambda: gt.load_graph("/tmp/pgp_graph.xml.xz")).timeit(number=1)  
1.0840389159275219
>>> timeit.Timer(lambda: gt.load_graph("/tmp/pgp_graph.gt")).timeit(number=1)  
0.0512137800687924
>>> timeit.Timer(lambda: gt.load_graph("/tmp/pgp_graph.gt.xz")).timeit(number=1)  
0.07995201298035681
>>> import subprocess
>>> print(subprocess.check_output("du -b /tmp/pgp_graph* | sort -n", shell=True).decode("utf-8")) 
395148       /tmp/pgp_graph.gt.xz
921619       /tmp/pgp_graph.gt
1010208      /tmp/pgp_graph.xml.xz
21324583     /tmp/pgp_graph.xml