METIS

METIS (file extension .graph) is the plain-text adjacency format read and written by the METIS graph-partitioning and sparse-matrix-ordering library developed by George Karypis and Vipin Kumar at the University of Minnesota. Though defined as an input format for a specific tool rather than an interchange standard, it became a de facto lingua franca for the graph-partitioning community: the same layout is shared by the earlier Chaco partitioner (hence Chaco is essentially identical) and was adopted as the official input for the 10th DIMACS Implementation Challenge on graph clustering and partitioning.

The data model is a simple undirected, unweighted-or-weighted graph with no self-loops and no parallel edges. A graph with n vertices and m edges is stored in exactly n+1 lines of ASCII. The first line is a header holding two to four whitespace-separated integers: n m, optionally followed by fmt and ncon. The fmt field is a three-digit binary flag whose bits (right to left) signal the presence of edge weights, vertex weights, and vertex sizes respectively; for example 011 means both vertex and edge weights are supplied. ncon gives the number of weights carried per vertex, enabling METIS's multi-constraint partitioning. Lines beginning with % are comments and are skipped.

Each of the following n lines describes one vertex, using 1-based numbering. A line lists the vertex's neighbors as vertex indices; when edge weights are present, each neighbor index is immediately followed by its weight, and any per-vertex weights precede the neighbor list. Because the graph is undirected, every edge appears twice (once in each endpoint's line), so the total neighbor entries number 2m — mirroring the compressed-sparse-row (xadj/adjncy) arrays METIS uses internally.

The format's strength is its minimalism and density: it is trivial to parse, compact for very large meshes and matrices, and directly consumed by high-performance partitioners including METIS, ParMETIS, KaHIP and Scotch (via Scotch conversions). Its limitations are equally clear. There is no place for node labels, attributes, geometry, or directed edges; vertices are anonymous ordinals, so any external identifiers must be tracked separately. The double-listing of edges and strict "no self-loops, no parallel edges" rules make it a poor fit for richer property graphs, for which attribute-carrying formats such as GraphML, GML or DIMACS are more suitable. It is best understood as a numeric partitioning input rather than a general-purpose graph-exchange format.