DIMACS

DIMACS is a family of plain-text, line-oriented file formats for describing graphs and network problems, named after the Center for Discrete Mathematics and Theoretical Computer Science at Rutgers University. It originated with the DIMACS Implementation Challenges launched in the early 1990s, a series of workshops that benchmarked algorithms on shared problem instances. To make instances portable between competing implementations, the organizers standardized simple ASCII encodings. The name is now used loosely for several related dialects rather than a single specification, and the exact grammar depends on which challenge a file belongs to.

The best-known dialect is the clique/coloring format (file extensions .clq and .col), introduced for the Second Challenge on maximum clique, graph coloring, and satisfiability. A file is a sequence of one-character-prefixed lines: c lines are free-text comments, a single p line declares the problem type and the vertex and edge counts (for example, p edge 5 6), and each e line names one undirected edge by two 1-based integer vertex indices. There are no explicit vertex declarations, no attributes, and each edge is listed once rather than in both directions. Sibling dialects reuse the same skeleton for other problems: the shortest-path format from the Ninth Challenge uses p sp with directed, weighted a (arc) lines plus a companion .co coordinate file (v lines with longitude/latitude), and the max-flow format uses p max with n lines marking source and sink nodes.

Within the graph-data ecosystem DIMACS occupies the niche of a minimal, fast-to-parse benchmark exchange format, much like METIS, Chaco, or Edge List, and unlike attribute-rich formats such as GraphML or GML. It remains a de facto standard for combinatorial-optimization and SAT-adjacent research datasets. Many toolkits read and write it, including NetworkX, igraph, JGraphT, LEMON, and Boost Graph Lib, and general converters such as GraphInOut can bridge it to richer formats.

Its strengths are simplicity, compactness, and near-universal support for classic benchmark instances. Its limitations follow directly from that minimalism: node identifiers must be contiguous integers, there is no native support for labels, typed attributes, or multiple graphs per file, and the declared header counts can drift out of sync with the body. Because "DIMACS format" spans incompatible clique, shortest-path, and max-flow dialects sharing only a common line syntax, tools must know which variant they are parsing, so files are not reliably interchangeable across problem domains.