Chaco

Chaco is a software package for partitioning graphs and the meshes derived from them, developed by Bruce Hendrickson and Robert Leland at Sandia National Laboratories. Version 1.0 was released in 1993 and the substantially expanded version 2.0 in October 1995; the code is written in C and distributed under a GNU open-source license. Its primary purpose is domain decomposition for parallel scientific computing: given a finite-element or finite-difference mesh represented as an undirected graph, Chaco divides the vertices into balanced subsets while minimizing the number of cut edges, so that the workload of a numerical simulation can be spread across processors with little inter-processor communication.

The package implements a broad family of partitioning algorithms that can be applied recursively, bisecting, quadrisecting, or octasecting the graph at each level. These include simple linear and random schemes, geometric (inertial) methods that exploit the coordinates of the mesh, spectral methods based on eigenvectors of the graph Laplacian, the Kernighan-Lin local-refinement heuristic, and multilevel methods. Chaco is historically important as one of the first implementations of multilevel graph partitioning, which coarsens the graph, partitions the small coarse version, and progressively refines the result; this approach combines high partition quality with fast runtimes and was widely imitated, notably by METIS and Scotch, which occupy the same niche. Chaco also extended spectral partitioning to use two or three Laplacian eigenvectors at once.

Input is an undirected graph with optional vertex and edge weights, supplied in a plain-text adjacency-list format (Chaco) in which the first line gives the vertex and edge counts plus a format flag, and each following line lists a vertex's neighbors. This same layout is shared with METIS and was used in the 10th DIMACS Implementation Challenge, so Chaco, METIS, and DIMACS partitioning tools are largely file-compatible; geometric methods additionally read a coordinates file.

Within a format-conversion catalog Chaco is best understood as a partitioner rather than a converter: it consumes a simple weighted-graph text format and emits an assignment of vertices to partitions, not a translation between graph serializations. Its limitations reflect its age and focus. It targets undirected, static graphs for load balancing and offers no support for directed graphs, rich attributes, or the interchange formats used by general graph tools; it is a serial code (parallel repartitioning is handled by successors such as Zoltan), and it is essentially unmaintained, so modern users often prefer METIS or Scotch. It nonetheless remains a well-documented reference implementation of classic partitioning algorithms.