Re: How to call a METIS subroutine from my FORTRAN code.

AM,

The following code works nicely with Intel Fortran 9.0 for Windows.
Hope this may help.

Edmund

------------------------------------------------------------------------------------

subroutine MND(n, m, node, link, perm, iperm)
implicit none
integer,intent(in) :: n, m
integer,intent(in),dimension(n+1) :: node
integer,intent(in),dimension(2*m) :: link
integer,intent(out),dimension(n) :: perm, iperm
integer :: numflag
integer,dimension(0:7) :: options
external METIS_NodeND
!DEC$ ATTRIBUTES C,REFERENCE, ALIAS:"_METIS_NodeND" :: METIS_NodeND
!
! METIS_NodeND (N, NODE, LINK, NUMFLAG, OPTIONS, PERM, IPERM)
!
! Description
!
! This function computes fill reducing orderings of sparse matrices
! using the multilevel nested dissection algorithm. It provides the
! functionality of the onmetis program.
!
! Parameters
!
! N The number of vertices in the graph.
!
! NODE, LINK
! The adjacency structure of the graph as described below.
!
! NUMFLAG Used to indicate which numbering scheme is used for the
! adjacency structure of the graph. NUMFLAG can take the following two
! values:
! 0 C-style numbering is assumed that starts from 0
! 1 Fortran-style numbering is assumed that starts from 1
!
! OPTIONS This is an array of 8 integers that is used to pass
! parameters for the various phases of the algorithm.
!
! If OPTIONS[0]=0 then default values are used. If OPTIONS[0]=1, then
! the remaining seven elements of options are interpreted as follows:
!
! OPTIONS[1] Determines the matching type. Possible values are:
! 1 Random Matching (RM)
! 2 Heavy-Edge Matching (HEM)
! 3 Sorted Heavy-Edge Matching (SHEM) (Default)
! Experiments have shown that all three matching schemes perform
quite
! well. In general SHEM is faster and RM is slower, but feel free to
! experiment with the other matching schemes.
!
! OPTIONS[2] Determines the algorithm used during initial
! partitioning. Possible values are:
! 1 Edge-based region growing (Default)
! 2 Node-based region growing
!
! OPTIONS[3] Determines the algorithm used for refinement. Possible
! values are:
! 1 Two-sided node FM refinement
! 2 One-sided node FM refinement (Default)
! One-sided FM refinement is faster than two-sided, but in some cases
! two-sided refinement may produce better orderings. Feel free to
! experiment with this option.
!
! OPTIONS[4] Used for debugging purposes. Always set it to 0
! (Default).
!
! OPTIONS[5] Used to select whether or not to compress the graph and
! to order connected components separately. The possible
! values and their meaning are as follows:
! 0 Do not try to compress the graph and do not order each connected
! component separately.
! 1 Try to compress the graph. (A compressed graph is actually formed
! if the size of the graph can be reduced by at least 15%)
! (Default).
! 2 Order each connected component of the graph separately. This
! option is particularly useful when after a few levels of nested
! dissection, the graph breaks up in many smaller disconnected
! subgraphs. This is true for certain types of LP matrices.
! 3 Try to compress the graph and also order each connected component
! separately.
!
! OPTIONS[6] Used to control whether or not the ordering algorithm
! should remove any vertices with high degree (i.e.,
dense
! columns). This is particularly helpful for certain
! classes of LP matrices, in which there a few vertices
! that are connected to many other vertices. By removing
! these vertices prior to ordering, the quality and the
! amount of time required to do the ordering improves.
The
! possible values are as follows:
! 0 Do not remove any vertices (Default)
! x Where x > 0, instructs the algorithm to remove any vertices
whose
! degree is greater than 0.1 * x * average degree). For example if
! x = 40, and the average degree is 5, then the algorithm will
! remove all vertices with degree greater than 20. The vertices
! that are removed are ordered last (i.e., they are automatically
! placed in the top-level separator). Good values are often in the
! range of 60 to 200 (i.e., 6 to 20 times more than the average).
!
! OPTIONS[7] Used to determine how many separators to find at each
! step of nested dissection. The larger the number of
! separators found at each step, the higher the runtime
! and better the quality is (in general). The default
! value is 1, unless the graph has been compressed by
more
! than a factor of 2, in which case it becomes 2.
! Reasonable values are in the range of 1 to 5. For most
! problems, a value of 5 increases the runtime by a
factor
! of 3.
!
! PERM, IPERM
! These are vectors, each of size n. Upon successful completion, they
! store the fill-reducing permutation and inverse-permutation. Let A be
! the original matrix and A' be the permuted matrix. The arrays PERM
and
! IPERM are defined as follows. Row (column) i of A' is the PERM[i] row
! (column) of A, and row (column) i of A is the IPERM[i] row (column)
of
! A'. The numbering of this vector starts from either 0 or 1, depending
! on the value of numflag.
!
!
======================================================================
!
! The adjacency structure of the graph is stored using the compressed
! storage format (CSR). The CSR format is a widely used scheme for
! storing sparse graphs. In this format the adjacency structure of a
! graph with n vertices and m edges is represented using two arrays
NODE
! and LINK. The NODE array is of size n+1 whereas the LINK array is of
! size 2m (this is because for each edge between vertices v and u we
! actually store both (v,u) and (u,v)).
!
! The adjacency structure of the graph is stored as follows. Assuming
! that vertex numbering starts from 1 (Fortran style), then the
! adjacency list of vertex i is stored in array LINK starting at index
! NODE[i] and ending at (but not including) index NODE[i+1] (i.e.,
! LINK[NODE[i]] through and including LINK[NODE[i+1]-1]). That is, for
! each vertex i , its adjacency list is stored in consecutive locations
! in the array LINK, and the array NODE is used to point to where it
! begins and where it ends. Figure 1(b) illustrates the CSR format for
! the 15-vertex graph shown in Figure 1(a).
!
!
! 1-- 2-- 3-- 4-- 5
! | | | | |
! 6-- 7-- 8-- 9--10
! | | | | |
! 11--12--13--14--15
!
! (a) A sample graph
!
!
! N = 15; M = 22
!
! NODE(N+1) 1 3 6 9 12 14 17 21 25 29 32 34 37 40 43 45
!
! LINK(2*M) 2 6 1 3 7 2 4 8 3 5 9 4 10 1 7 11 2 6
! 8 12 3 7 9 13 4 8 10 14 5 9 15 6 12 7 11 13
! 8 12 14 9 13 15 10 14
!
! (b) CSR format
!
! Figure 1: An example of the CSR format for storing sparse graphs.
!
!
numflag = 1
options(0) = 0
call METIS_NodeND(n, node, link, numflag, options, perm, iperm)
return
end subroutine MND

.

Relevant Pages

  • Re: Chart Performance Problem with Large Data Set
    ... How does this affect the execution time? ... The next thing I saw in your code is that you are using a Workbook to ... supply your graph with data. ... Since your data is in an array already, why don't you just use the array ...
    (microsoft.public.office.developer.web.components)
  • Re: named array range- having a brain meltdown
    ... > So I need to create a named range, within which is an array formula ... > without ever putting them in worksheet cells. ... > then be added to an existing graph as a new series. ...
    (microsoft.public.excel.misc)
  • Re: Absolute beginner vs. fuzzy logic
    ... into B) is readily available in MatLab. ... new +1-dimensional array. ... The graph showed how a certain mechanical system ... > each iteration. ...
    (comp.soft-sys.matlab)
  • Re: How to plot Double values graph with MSChART
    ... "The MSChart control provides a ChartData property for loading data ... directly from an array into the data grid. ... 'Set the column labels. ... Code for Drawing Graph ...
    (microsoft.public.vb.general.discussion)
  • Re: Pathfinding in community
    ... > Each member is able to add his own contacts at the community. ... Dijkstra's algorithm is simply a refined breadth first search. ... In your case all the edges on the graph have the same weight, ... I would suggest loading this data into an array of arrays. ...
    (comp.lang.php)