Documentation Index
Fetch the complete documentation index at: https://mintlify.com/KarypisLab/METIS/llms.txt
Use this file to discover all available pages before exploring further.
The METIS graph file format is a plain-text, line-oriented format used by the gpmetis, ndmetis, and graphchk command-line programs, as well as by any application that calls ReadGraph from programs/io.c. Each file describes an undirected graph using a header line followed by one adjacency-list line per vertex. All integers in the file use 1-based vertex numbering by default (the C API works in 0-based internally and converts automatically when METIS_OPTION_NUMBERING is set to 1).
The first non-comment line of the file contains two to four space-separated integers:
nvtxs nedges [fmt [ncon]]
| Field | Meaning |
|---|
nvtxs | Number of vertices in the graph |
nedges | Number of edges, counting each undirected edge once |
fmt | Optional format code (default 0). Controls what extra data appears on each vertex line |
ncon | Optional number of vertex-weight constraints. Required when fmt indicates vertex weights |
% are treated as comments and are skipped by the parser.
The fmt field
fmt is read as a three-digit decimal number (fmtstr = "%03d" % fmt) where each digit controls one type of optional data:
fmt = [vsize_flag][vwgt_flag][ewgt_flag]
| Digit position (left to right) | Controls |
|---|
Hundreds digit (1xx) | Vertex sizes (vsize) for the min-volume objective |
Tens digit (x1x) | Vertex weights (vwgt) for load balancing |
Units digit (xx1) | Edge weights (adjwgt) |
fmt values:
fmt value | Meaning |
|---|
0 | Unweighted graph (default) |
1 | Edge weights only |
10 | Vertex weights only, single constraint |
11 | Both vertex and edge weights |
100 | Vertex sizes only |
110 | Vertex sizes and vertex weights |
111 | All three: vertex sizes, vertex weights, and edge weights |
fmt tens digit is 1), ncon specifies how many weight values appear per vertex. If ncon is omitted it defaults to 1.
Adjacency list lines
After the header, there is exactly one line per vertex, in order from vertex 1 to vertex nvtxs. Each line lists the optional per-vertex data followed by the adjacency list:
[vsize] [vwgt_1 ... vwgt_ncon] neighbor_1 [ewgt_1] neighbor_2 [ewgt_2] ...
- All neighbors are listed with 1-based IDs.
- For edge-weighted graphs, each neighbor ID is immediately followed by its edge weight.
- Both directions of every undirected edge must appear: if vertex
u lists v as a neighbor, vertex v must also list u.
nedges in the header counts each edge once (not twice).
Unweighted graph example
A simple 5-vertex path graph 1—2—3—4—5 with a cross-edge 2—4:
Header: 5 vertices, 5 edges, no weights. Vertex 2 connects to vertices 1, 3, and 4; vertex 3 connects to 2 and 4; and so on.
Weighted graph example
The file graphs/test.mgraph demonstrates a graph with two vertex-weight constraints (fmt=010, ncon=2):
%% graph file %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% 1st line: n, m
%% ff lines: vwgt1, vwgt2, adjacencies
766 1314 010 2
1 1 479 389 571 2
2 2 395 1 534 4
4 4 148 207 409 498
4 4 2 729 6 695
- Header: 766 vertices, 1314 edges, vertex weights only (
010), 2 constraints.
- Each vertex line starts with two weight values (one per constraint), followed by the neighbor list.
- Vertex 1 has weights
(1, 1) and connects to vertices 479, 389, 571, and 2.
- Vertex 2 has weights
(2, 2) and connects to vertices 395, 1, 534, and 4.
In-memory CSR representation
The graph file format maps directly to the CSR (compressed sparse row) arrays used by the METIS C API:
| File concept | C API array | Size |
|---|
| Adjacency list start offsets | xadj | nvtxs + 1 |
| All neighbor IDs (0-based) | adjncy | 2 * nedges |
| Vertex weights (interleaved by constraint) | vwgt | nvtxs * ncon |
| Edge weights | adjwgt | 2 * nedges |
| Vertex sizes | vsize | nvtxs |
xadj[i] is the index into adjncy where the adjacency list of vertex i begins (0-based). The adjacency list of vertex i runs from adjncy[xadj[i]] to adjncy[xadj[i+1] - 1]. This is the standard CSR format also used by sparse linear algebra libraries.
The multi-constraint vertex weight for vertex i and constraint j is stored at vwgt[i * ncon + j]. When ncon == 1, vwgt is simply a flat array of per-vertex weights.
The ReadGraph function in programs/io.c performs the translation from file to API arrays. The key steps are:
- Parse the header to determine
nvtxs, nedges, the format bits, and ncon.
- Allocate
xadj[nvtxs+1], adjncy[2*nedges], vwgt[ncon*nvtxs], adjwgt[2*nedges], vsize[nvtxs].
- For each vertex line, read optional
vsize, ncon weight values, then neighbor/weight pairs.
- Convert neighbor IDs from 1-based (file) to 0-based (API) by subtracting 1.
- Set
xadj[i+1] after processing all edges of vertex i.
When calling the API directly (bypassing file I/O), you supply these arrays yourself. You may pass NULL for vwgt, adjwgt, or vsize to indicate uniform weights of 1.
Validating a graph file
Use graphchk to check that a graph file is well-formed before passing it to gpmetis or ndmetis:
graphchk graphs/4elt.graph
graphchk graphs/test.mgraph
graphchk verifies that:
- The edge count in the header matches the actual number of edges in the file.
- Every edge
(u, v) has a corresponding reverse edge (v, u).
- All neighbor IDs are within the valid range
[1, nvtxs].
- All weights are positive (edge weights must be strictly positive; vertex weights must be non-negative).
If you see an error like “I detected that you specified twice the number of edges”, you are counting each undirected edge twice in the header. The nedges field must count each undirected edge only once, even though each edge appears twice in the adjacency lists.
