NEIGHBORS_TO_METIS_GRAPH
Reformat Tet Mesh Neighbor File


NEIGHBORS_TO_METIS_GRAPH is a MATLAB program which reads a file describing the graph-theoretic adjacency structure of the elements in a mesh of triangles or tetrahedrons and writes out a similar file that is suitable for input to the mesh partitioning program METIS.

Since we know we are dealing with a triangle or tet mesh, each "node" of the adjacency graph has 3 or 4 potential edges. If a potential edge is not used (in other words, if a face is a boundary face), then by convention we write out a "-1" for the neighbor value. Otherwise, the adjacency information lists the index of the element that is a neighbor on that face of the element

Converting to a METIS GRAPH format is trivial. We include an initial line that lists the number of "nodes" (elements) and "edges" (interfaces between pairs of elements), followed by, for each node (element), a list of the adjacent nodes (a list of the adjacent elements, omitting the "-1" values). A cross-eyed schoolboy sitting on a tack would be able to carry out this task!

Usage:

neighbors_to_metis_graph ( 'neighbor_file' )
where reads the data in 'neighbor_file', rearranges it to suit METIS, and writes out the modified data to 'metis_graph_file'.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

NEIGHBORS_TO_METIS_GRAPH is available in a C++ version and a FORTRAN90 version and a MATLAB version.

Related Programs:

GRAPHCHK, a C program which uses the METIS library to check that a METIS graph file has the proper format;

KMETIS, a C program which uses the METIS library to partition the nodes of a graph in a balanced way, useful for parallel processing;

METIS, a C library which partitions the nodes of a graph or the elements of a mesh, for division among a number of parallel processes, or to reorder the variables in a sparse matrix to minimize fillin;

METIS_GRAPH, a data directory which contains examples of METIS GRAPH files, the format for graphs to be read by METIS, which can partition a graph;

OEMETIS, a C program which uses the METIS library to reorder the variables in a sparse matrix.

ONMETIS, a C program which uses the METIS library to reorder the variables in a sparse matrix.

PMETIS, a C program which uses the METIS library to partition the nodes of a graph in a balanced way, useful for parallel processing;

TET_MESH_TET_NEIGHBORS, a MATLAB program which reads information about a tet mesh and writes out a list of the tetrahedrons that are adjacent to a given tetrahedron;

TRIANGULATION_TRIANGLE_NEIGHBORS, a MATLAB program which reads data defining a triangulation, determines the neighboring triangles of each triangle, and writes that information to a file.

Reference:

  1. George Karypis, Vipin Kumar,
    METIS, a Software Package for Partitioning Unstructured Graphs and Computing Fill-Reduced Orderings of Sparse Matrices;

Source Code:

Examples and Tests:

You can go up one level to the MATLAB source codes.


Last revised on 15 October 2008.