Graphs#
- Release:
5.0.0
- Date:
Sep 18, 2026
How to add a new graph?#
Just create a PR (Pull Request) corresponding to the “Template for adding a new graph”.
File structure#
A graph is distributed as an archive <name>.tar.gz that unpacks to a
directory named after the graph:
README.md— the description of the graph and of its files;grammar/— the grammars for this graph in the cnf format (if any);graph/— one MatrixMarket file per edge label.
The pre-migration graphs on the Old graphs page use the old CSV format instead.
Each file graph/<label>.mtx is a Boolean pattern matrix that holds
exactly the edges with that label:
%%MatrixMarket matrix coordinate pattern general
%%GraphBLAS type bool
<num_nodes> <num_nodes> <num_edges>
<tail> <head>
...
Node ids are 0-based integers, and the matrix dimensions equal the number of
nodes. A whole directory is loaded by
graph_from_mtx_dir.
Indexed labels#
Some graphs have families of labels that differ only in a numeric suffix,
e.g. load_0, load_1, …, load_857. In the per-graph pages and
in grammars such a family is written once with a placeholder subscript
(load_f or load_i) and a note that lists the index set. Each stored
label has its own file named after the label itself (load_5.mtx holds
the edges labeled load_5).
Reversed edges#
For every edge label L there is a reversed label L_r (written
\(\overline{L}\) in the per-graph pages): an edge (u, v) labeled
L corresponds to an edge (v, u) labeled L_r. Reversed edges are
not stored in the archives; they are derived by
add_reverse_edges, and the
“Edges Statistics” tables of the per-graph pages list the stored labels
only.
Contents#
The per-category tables include one column per grammar language
applicable to that category. Each cell shows the number of vertex pairs
reachable with respect to the respective language (i.e. the number of
pairs (u, v) for which some string in the language labels a path from
\(u\) to \(v\)). The count depends on the language, not on a
particular grammar: several grammars may generate the same language and
yield the same count. A cell reading “not available” means the value has
not been computed yet; an empty cell means the grammar does not apply to
that graph.
Source area |
Number of graphs |
|---|---|
20 |
|
20 |
|
21 |
|
10 |
|
10 |
|
18 |
|
4 |
|
10 |