LAUPACK
Graph routines by Hang Tong Lau
LAUPACK
is a FORTRAN90 library which
carries out a variety of operations on mathematical graphs.
Routines are included to:

find an Euler circuit (use every edge once);

find a Hamilton circuit (visit every node once);

find cliques (nodes that are all connected to each other);

find the strongly connected components of a directed graph;

find a minimum spanning tree (the shortest collection of edges
that leave the graph connected);

find the chromatic number (the number of colors necessary to
paint each node, with no adjacent nodes the same color);

find the K shortest paths in a graph whose edge lengths are given;

find the maximal flow in a graph with source and sink nodes,
and edge capacities;

determine if a graph is planar;
Languages:
LAUPACK is available in
a FORTRAN90 version.
Related Data and Programs
CODEPACK,
a FORTRAN90 library which
computes "codes" that can determine if two graphs are isomorphic.
DIJKSTRA,
a FORTRAN90 program which
runs a simple example of Dijkstra's minimum distance algorithm for graphs.
FLOYD,
a FORTRAN90 library which
implements Floyd's algorithm for finding the shortest distance between pairs of
nodes on a directed graph.
GRAFPACK,
a FORTRAN90 library which
carries out operations on abstract graphs.
GRAPH_REPRESENTATION,
a data directory which
contains examples of ways of representing abstract
mathematical graphs
GRF,
a data directory which
contains a description and examples of the GRF file format for storing graphs.
SUBSET,
a FORTRAN90 library which
enumerates combinations, partitions, subsets, index sets,
and other combinatorial objects.
Author:
Hang Tong Lau
Reference:

Hang Tong Lau,
Algorithms on Graphs,
Tab Books, 1989,
LC: QA166 L38.
Source Code:
Examples and Tests:
List of Routines:

COLOR2 carries out a twocoloring for a planarity test.

R8_SWAP swaps two R8's.

DECOMP does path decomposition for a planarity test.

DFS1 carries out the first depth first search for a planarity test.

DFS2 carries out the second depthfirst search for a planarity test.

DIGRAPH_ARC_EULER returns an Euler circuit in a digraph.

DIGRAPH_ARC_FIND_PATH determines if a path exists from 11 to J1.

DIGRAPH_ARC_GET_PATH retrieves the edges of the Kth shortest path.

DIGRAPH_ARC_HAMCYC finds a Hamiltonian circuit in a digraph.

DIGRAPH_ARC_KSHORT1 finds the K shortest paths in a digraph.

DIGRAPH_ARC_KSHORT2 finds the KPATHS shortest distinct path lengths without repeat nodes.

DIGRAPH_ARC_MINEQV finds a minimal equivalent of a strongly connected digraph.

DIGRAPH_ARC_NFLOW implements Karzanov's network flow algorithm.

DIGRAPH_ARC_PRINT prints out a digraph from an edge list.

DIGRAPH_ARC_PRT_PATH outputs at most MAXPTH number of K shortest paths between two nodes.

DIGRAPH_ARC_SHTREE finds the shortest paths from IROOT to all other nodes.

DIGRAPH_ARC_STCOMP finds the strongly connected components of a digraph.

DIGRAPH_ARC_TO_STAR sets up the forward star representation of a digraph.

DIGRAPH_ARC_WEIGHT_PRINT prints out a weighted digraph from an edge list.

DIGRAPH_DIST_ALLPATH finds the shortest paths for all pairs of nodes in a digraph.

DIGRAPH_DIST_FMIN stores values of K such that DISTAB(K) = LITTLE and DISTAB(J) = KEY.

DIGRAPH_DIST_PRINT prints a distance matrix.

DIGRAPH_DIST_SHORT_LN finds the shortest paths from one node to all others.

DIGRAPH_DIST_SHORTP finds the shortest path from ISORCE to ISINK in a digraph.

GRAPH_ARC_CLIQUE finds all the cliques of a graph.

GRAPH_ARC_COLOR_NUMBER finds the chromatic number of a graph.

GRAPH_ARC_COLOR_POLY computes the chromatic polynomial of a graph.

GRAPH_ARC_CONECT finds the bridges, blocks and cut nodes of an undirected graph.

GRAPH_ARC_DEGREE finds the degree of the nodes of an undirected graph.

GRAPH_ARC_EDGE_CON finds the edgeconnectivity of a connected graph.

GRAPH_ARC_EULER returns an Euler circuit in an undirected graph.

GRAPH_ARC_FCYCLE finds a fundamental set of cycles in an undirected graph.

GRAPH_ARC_HAMCYC finds a Hamiltonian circuit in a graph.

GRAPH_ARC_MAKEG constructs a graph with NNODE nodes and Kconnectivity.

GRAPH_ARC_MATCH finds a maximum cardinality matching in a graph.

GRAPH_ARC_MINTR2 finds the minimum spanning tree of a graph, using an edge array.

GRAPH_ARC_NCOLOR_PRINT prints out a nodecolored graph from an edge list.

GRAPH_ARC_PLANAR determines if a graph is planar.

GRAPH_ARC_PRINT prints out a graph from an edge list.

GRAPH_ARC_TO_STAR sets up the forward star representation of an undirected graph.

GRAPH_ARC_WEIGHT_PRINT prints out a weighted graph from an edge list.

GRAPH_DIST_MINTR1 finds a minimum spanning tree for a graph using a distance matrix.

GRAPH_DIST_PRINT prints a distance matrix.

I4_SWAP swaps two I4's.

I4VEC_INDICATOR sets an I4VEC to the indicator vector.

I4VEC_PRINT prints an I4VEC.

I4VEC_REVERSE reverses the elements of an I4VEC.

R8MAT_PRINT prints out a portion of an R8MAT.

R8VEC_PRINT prints an R8VEC.

TIMESTAMP prints the current YMDHMS date as a time stamp.
You can go up one level to
the FORTRAN90 source codes.
Last revised on 27 November 2006.