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