Graph Computations

GRAFPACK is a FORTRAN90 library which performs common calculations involving (abstract mathematical) graphs.

This includes such tasks as a breadth-first-search, the computation of a minimum spanning tree, an Euler or Hamilton circuit, blocks, chromatic polynomial, or transitive closure. Some algorithms are general, while others apply only to directed graphs or trees.

Some of the routine names begin with a prefix that indicates the type of object it is associated with:


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


GRAFPACK is available in a FORTRAN90 version.

Related Data and Programs:

CITIES, a FORTRAN90 library which handles various problems associated with a set of "cities" on a map.

CITIES, a dataset directory which contains a number of city distance datasets.

CODEPACK, a FORTRAN90 library which computes "codes" that can determine if two graphs are isomorphic.

FLOYD, a FORTRAN90 library which implements Floyd's algorithm for finding the shortest distance between pairs of nodes on a directed graph.

GRAPH_REPRESENTATION, a data directory which contains examples of ways of representing abstract mathematical graphs

GRF, a data directory which contains a description of the GRF format and some examples.

GRF_IO, a FORTRAN90 library which reads and writes GRF files.

GRF_TO_EPS, a FORTRAN90 library which can make an Encapsulated PostScript (EPS) image of a GRF file.

SUBSET, a FORTRAN90 library which generates, ranks and unranks various combinatorial objects.

TABLE_GRAPH_CODE, a FORTRAN90 program which reads a TABLE file describing a graph, and computes its graph code.

TOMS097, a FORTRAN90 library which computes the distance between all pairs of nodes in a directed graph with weighted edges, using Floyd's algorithm.

TREEPACK, a FORTRAN90 library which carries out computations on trees, a simple kind of graph that is minimally connected.


  1. Alan Gibbons,
    Algorithmic Graph Theory,
    Cambridge University Press, 1985,
    ISBN: 0-5212-8881-9,
    LC: QA166.G53.
  2. Hang Tong Lau,
    Combinatorial Heuristic Algorithms with FORTRAN,
    Springer, 1986,
    ISBN: 3540171614,
    LC: QA402.5.L37.
  3. Albert Nijenhuis, Herbert Wilf,
    Combinatorial Algorithms for Computers and Calculators,
    Second Edition,
    Academic Press, 1978,
    ISBN: 0-12-519260-6,
    LC: QA164.N54.
  4. Robert Sedgewick,
    Algorithms in C,
    Addison-Wesley, 1990,
    ISBN: 0-201-51425-7,
    LC: QA76.73.C15S43.
  5. Dennis Stanton, Dennis White,
    Constructive Combinatorics,
    Springer, 1986,
    ISBN: 0387963472,
    LC: QA164.S79.
  6. Krishnaiyan Thulasiraman, M Swamy,
    Graphs: Theory and Algorithms,
    John Wiley, 1992,
    ISBN: 0471513563,
    LC: QA166.T58.

Source Code:

Examples and Tests:

KNIGHTSTOUR is a GRF file created to illustrate a Knight's tour of the chess board.

FISH is a set of data defining a 3D model of fish. Various routines manipulate this data.

List of Routines:

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

Last revised on 24 June 2013.