CME342 / AA220 / CS238 Assignment 3

File formats

The following is a short description of the formats of the files that have been provided to you with this homework for each of the graphs that are to be partitioned.  This should help you read information into your own graph partitioner and into Metis (mesh file is provided in a format that is directly readable by the partnmesh and partdmesh programs supplied with Metis).

In addition, we suggest an output format (identical to the one created by the partdmesh and partnmesh programs in Metis) so that you can use a small visualization program supplied by us that can help you debug your graph partitioning algorithm.

You can find examples of all of the file formats by clicking here.
 
 

Graph Input File Formats

For each of the graphs to be partitioned in this homework assignment, you will be supplied three input files that entirely describe the graph.  In the following, assume that the name of the case to be partitioned is "graph".
 

graph.xyz

This file contains the information about the physical location of all the nodes in the mesh/graph.  The first line contains an integer value, nnode, equal to the total number of nodes in the graph.  Each of the remaining nnode lines contains the (x,y,z) coordinates for all the nodes in the mesh/graph. Note: you can perform the inertial partitioning of each of the three meshes/graphs provided by looking at this file only.

graph.conn

This file is a Metis-compatible, element-node description of a tetrahedral mesh.  The first line in the file contains two integers.  The first integer, ncell, is the number of tetrahedral elements in the mesh/graph.  The second integer is 2, to convey the fact that all elements in the mesh/graph are tetrahedra (this number is a Metis convention).   The remaining ncell lines provide the indexes of the nodes that make up the four vertices of each of the tetrahedra in the mesh/graph.  Note that all nodes are numbered from 1 to nnode.
 

graph.surf

This file is provided for purposes of visualization only.  It contains the connectivity of the surface of the airplane configuration that has been meshed up in each of the three meshes/graphs.  You do not need to do anything with this file.  It will be read by a program supplied to you, in order to create "pretty pictures" of the partitioned mesh.
 

Graph Output File Format


 

graph.part

This file contains the output of the partitioning process.   It is quite simple.  It contains nnode lines and each line has a single integer that denotes the partition that that specific node belongs to.  Note that if you are partitioning a graph into Npart partitions, the integers in this file should be between 0 and Npart-1.  When you use Metis to partition these graphs, this file will be produced with the name graph.conn.npart.Npart if you run the Metis partitioning with the command:
  
metis-4.0/partnmesh graph.conn Npart
 

You can safely ignore the graph.conn.epart.Npart file.

Visualization program

A small OpenInventor program that reads the following files:

can be found on the course Web page by clicking here.   You must run this program on one of the following three platforms: If you run on a Silicon Graphics computer, the OpenInventor runtime libraries are installed by default in the default locations so you do not have to worry about them. If you are running on Linux, you must have the OpenInventor libraries and the Xm library on your machine. Alternatively, you can tell the loader to look for the libraries in the course directory (they have been placed there for your convenience) by typing
  
setenv LD_LIBRARY_PATH /usr/class/cs238/Inventor
  if you are using the csh or tcsh, or
  
export LD_LIBRARY_PATH=/usr/class/cs238/Inventor
  if you are using the ksh or bash. If you are using Windows 2000, all you have to do is place the executable and the shared libraries (*.dll) in the same directory; all the files will unzip properly. OpenInventor is available here in source and compiled-binary forms. In order to see the outcome of your partitioning, make sure the three files above are present, and execute the following command:
  
metis_viewer graph npart
You will get a screen with the surface geometry colored by the partition that each portion of the domain belongs to.  Only npart partitions will be displayed.  If npart is larger than the actual number of partitions, the additional partitions will be disregarded.  Note that the files, graph.part, graph.xyz, and graph.surf need to be present in the directory where you execute the program metis_viewer.

Good luck,

JJA
5/16/05