LAUPACK - Graph routines by H T Lau

LAUPACK is a set of graph routines by H T Lau.

Reference:

Hang Tong Lau,
Algorithms on Graphs,
Tab Books, 1989.

Files you may copy include:

• LAUPACK.F90, the source code.
• LAUPACK_PRB.F90, a sample problem.
• LAUPACK_PRB.OUT, sample problem output.

The list of routines includes:

• COLOR2 carries out a two-coloring for a planarity test.
• 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.
• I_SWAP swaps two integer values.
• IVEC_PRINT prints an integer vector.
• IVEC_REVERSE reverses the elements of an integer vector.
• R_SWAP swaps two real values.
• RMAT_PRINT prints out a portion of a dense matrix.
• RVEC_PRINT prints a real vector.

Return to the FORTRAN software page.