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:

1. Hang Tong Lau,
   Algorithms on Graphs,
   Tab Books, 1989,
   LC: QA166 L38.

Source Code:

• laupack.f90, the source code.

Examples and Tests:

• laupack_test.f90, a sample problem.
• laupack_test.txt, the output file.

List of Routines:

• COLOR2 carries out a two-coloring 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 depth-first 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 K-th 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 edge-connectivity 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 K-connectivity.
• 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 node-colored 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.