jburkardt

NEIGHBORS_TO_METIS_GRAPH\ Reformat Tet Mesh Neighbor File {#neighbors_to_metis_graph-reformat-tet-mesh-neighbor-file align=”center”} ===============================

NEIGHBORS_TO_METIS_GRAPH is a C++ 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: {#usage align=”center”}

neighbors_to_metis_graph neighbor_file: reads the data in neighbor_file, rearranges it to suit METIS, and writes out the modified data to metis_graph_file

Licensing: {#licensing align=”center”}

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

Languages: {#languages align=”center”}

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

GRAPHCHK, a C program, using the METIS library, which can 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 of 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, using the METIS library, which can 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 C++ 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 C++ program which reads data defining a triangulation, determines the neighboring triangles of each triangle, and writes that information to a file.

Reference: {#reference align=”center”}

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

Source Code: {#source-code align=”center”}

neighbors_to_metis_graph.cpp, the source code.

Examples and Tests: {#examples-and-tests align=”center”}

cube_tetra.neighbors, a sample tet mesh neighbor file that can be used as input to the program.
cube_tetra.metis_graph, the modified tet mesh neighbor file created by the program, suitable for input to METIS.

List of Routines: {#list-of-routines align=”center”}

MAIN is the main program for NEIGHBORS_TO_METIS_GRAPH.
CH_CAP capitalizes a single character.
CH_EQI is true if two characters are equal, disregarding case.
CH_TO_DIGIT returns the integer value of a base 10 digit.
FILE_COLUMN_COUNT counts the number of columns in the first line of a file.
FILE_NAME_EXT_GET determines the “extension” of a file name.
FILE_NAME_EXT_SWAP replaces the current “extension” of a file name.
FILE_ROW_COUNT counts the number of row records in a file.
I4_MAX returns the maximum of two I4’s.
I4_MIN returns the minimum of two I4’s.
I4COL_COMPARE compares columns I and J of an I4COL.
I4COL_SORT_A ascending sorts the columns of an I4COL.
I4COL_SWAP swaps two columns of an I4COL.
I4I4I4_SORT_A ascending sorts a triple of I4’s.
I4MAT_TRANSPOSE_PRINT prints an I4MAT, transposed.
I4MAT_TRANSPOSE_PRINT_SOME prints some of an I4MAT, transposed.
ITABLE_DATA_READ reads data from an ITABLE file.
ITABLE_HEADER_READ reads the header from an ITABLE file.
METIS_GRAPH_WRITE writes the METIS graph file.
S_INDEX_LAST_C points to the last occurrence of a given character.
S_LEN_TRIM returns the length of a string to the last nonblank.
S_TO_I4 reads an I4 from a string.
S_TO_I4VEC reads an I4VEC from a string.
S_WORD_COUNT counts the number of “words” in a string.
SORT_HEAP_EXTERNAL externally sorts a list of items into ascending order.
TIMESTAMP prints the current YMDHMS date as a time stamp.

You can go up one level to the C++ source codes.

Last revised on 22 October 2008.