METIS GRAPH Files

These are some examples of "graph" files used by the METIS program. METIS can read a graph file, and partition the nodes in a balanced way so that each partition has about the same number of nodes, and the number of cut edges is minimized. This process is designed with the idea that the graph represents a computation that is to be divided up among various processors, with the stipulation that the amount of interprocessor communication must be limited.

METIS GRAPH File Characteristics:

• ASCII
• a graph of N nodes is stored in a file of N+1 lines;
• the first line lists the number of nodes and the number of edges;
• If the first line contains more than two values, the extra values indicate the weights;
• each subsequent line lists the "neighbors" of a node;
• comment lines begin with a "%" sign;

Reference:

1. metis.pdf,
   George Karypis and Vipin Kumar,
   METIS, a Software Package for Partitioning Unstructured Graphs and Computing Fill-Reduced Orderings of Sparse Matrices;
2. George Karypis, Vipin Kumar,
   A fast and high quality multilevel scheme for partitioning irregular graphs,
   SIAM Journal on Scientific Computing,
   Volume 20, Number 1, 1998, pages 359-392;
3. http://www.cs.umn.edu/~metis,
   The METIS home page;

Programs and routines to read a METIS GRAPH file:

• io.c contains the routines needed to read a METIS graph file.

Programs to process a METIS GRAPH file:

• graphchk can read a METIS GRAPH file and report whether it has the correct format.
• kmetis can partition the nodes of a graph defined by a METIS GRAPH file.
• OEMETIS reads the adjacency graph of a sparse matrix, stored in METIS GRAPH format, and produces a reordering of the nodes to minimize fill.
• ONMETIS reads the adjacency graph of a sparse matrix, stored in METIS GRAPH format, and produces a reordering of the nodes to minimize fill.
• pmetis can partition the nodes of a graph defined by a METIS GRAPH file.

Programs to convert a file to a METIS GRAPH file:

• MESH2DUAL is an executable C program which reads a METIS MESH file and writes out a METIS GRAPH file of the dual graph.
• MESH2NODAL is an executable C program which reads a METIS MESH file and writes out a METIS GRAPH file of the nodal graph.
• NEIGHBORS_TO_METIS_GRAPH reads information describing the adjacency relations in a tet mesh, and writes out essentially the same information, but in a format that METIS will accept.

Sample METIS GRAPH Files:

• 4elt.graph, a "small" graph representing a 2D finite element mesh (15,606 nodes and 45,878 edges);
• test.mgraph, a "very small" graph that includes two vertex weights (766 nodes and 1,314 edges);
• tiny_01.graph, a "tiny" graph that includes no weights (7 nodes and 11 edges);
• tiny_02.graph, a "tiny" graph that includes edge weights (7 nodes and 11 edges);
• tiny_03.graph, a "tiny" graph that includes vertex and edge weights (7 nodes and 11 edges);
• tiny_04.graph, a "tiny" graph that includes three sets of vertex weights (7 nodes and 11 edges);

You can go up one level to the DATA page.