HP MLIB User's Guide Vol. 2 7th Ed.

964 HP MLIB User’s Guide
What you need to know to use these routines
http://www-users.cs.umn.edu/~karypis/metis/metis/index.html
What you need to know to use these routines
METIS provides stand-alone library interfaces that can be directly called from
C or Fortran programs. The next sections describe HP MLIB METIS subroutine
interfaces and the data structures used by these subroutines.
NOTE When and only when you use METIS internal routines like GKmalloc to
allocate memory, you must also use METIS internal routines like GKfree
to free the memory.
Graph Data Structure
Graph partitioning and sparse matrix ordering routines in METIS take as
input parameters the adjacency structure of a graph and eventually the
weights of the vertices and edges.
The adjacency structure of a graph with n vertices and m edges is represented
using the Compressed Storage Row format (CSR). Two arrays xadj and adjncy
are required for the CSR representation:
• adjncy(*)—Integer array of length 2m containing the adjacency lists of each
vertex of the graph. The array adjncy( ) has length 2m because both edges (i,
j) and (j, i) are represented when vertices i and j are connected.
• xadj(*)—Integer array of length n+1 such that xadj(i) points to the location
on adjncy( ) of the beginning of the adjacency list of vertex i.
Given a vertex i, its adjacency list is stored in consecutive locations in the array
adjncy( ), and the array xadj( ) is used to point to where it begins and where it
ends; adjncy(xadj(i)) through and including adjncy(xadj(i+1)-1) is the adjacency
list of vertex i.
Consider, for example, the adjacency-matrix representation of a graph with 5
vertices: