laupack

laupack, a FORTRAN90 code which computes properties of mathematical graphs, including Euler circuits, Hamiltonian circuits, cliques, strongly connected components, minimal spanning tree, chromatic number, shortest paths, maximal flow, and planarity.

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;

Licensing:

The computer code and data files made available on this web page are distributed under the MIT license

Languages:

laupack is available in a FORTRAN90 version.

Related Data and Programs

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

DIJKSTRA, a FORTRAN90 code which runs a simple example of Dijkstra's minimum distance algorithm for graphs.

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

GRAFPACK, a FORTRAN90 code which carries out operations on abstract graphs.

laupack_test

SUBSET, a FORTRAN90 code 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.
• laupack.sh, compiles the source code.