GRAFPACK
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:

• COLOR_DIGRAPH_ADJ is a directed graph whose nodes are colored;
• COLOR_GRAPH_ADJ is an undirected graph whose nodes are colored;
• DIGRAPH_ADJ is a directed graph described by an adjacency matrix;
• DIGRAPH_ARC is a directed graph described by an edge list;
• FACE is a collection of "faces" defined by circuits in a graph;
• GRAPH_ADJ is an undirected graph described by an adjacency matrix;
• GRAPH_ARC is an undirected graph described by an edge list;
• GRAPH_DIST is an undirected graph described by a distance matrix;
• MAZE is a maze;

Licensing:

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

Languages:

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.

Reference:

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:

• grafpack.f90, the source code;

Examples and Tests:

• grafpack_test.f90, the calling program;
• grafpack_test.txt, the output file.
• 57_city_distances.txt, a city distance table.

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

• knightstour.grf, a knight's tour graph in GRF format.
• knightstour.png, a PNG image of the knight's tour graph.

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

• fish_faces.iv, an Inventor file that contains the "faces" of the fish, that is, the polygonal surfaces.
• fish_faces.png, a PNG image of a "snapshot" of the fish face model.
• fish_lines.vla, a VLA file that records the edges of the polygonal surfaces of the fish model.
• fish_nodes.png, a PNG file that displays a "snapshot" of the nodes of the fish model.

List of Routines:

• BALANC balances a real matrix before eigenvalue calculations.
• CH_CAP capitalizes a single character.
• CH_EQI is a case insensitive comparison of two characters for equality.
• CH_TO_DIGIT returns the integer value of a base 10 digit.
• CATALAN computes the Catalan numbers, from C(0) to C(N).
• COLOR_DIGRAPH_ADJ_DEGREE computes the indegree and outdegree of each node.
• COLOR_DIGRAPH_ADJ_DEGREE_SEQ computes the degree sequence of a color digraph.
• COLOR_DIGRAPH_ADJ_EDGE_COUNT counts the number of edges in a color digraph.
• COLOR_DIGRAPH_ADJ_EXAMPLE_CUBE sets up the cube color digraph.
• COLOR_DIGRAPH_ADJ_EXAMPLE_OCTO sets up an 8 node example color digraph.
• COLOR_DIGRAPH_ADJ_PRINT prints out the adjacency matrix of a color digraph.
• COLOR_DIGRAPH_ADJ_RANDOM generates a random color graph.
• COLOR_GRAPH_ADJ_COLOR_COUNT counts the number of colors in a color graph.
• COLOR_GRAPH_ADJ_COLOR_SEQUENCE computes the color sequence of a color graph.
• COLOR_GRAPH_ADJ_CONNECT_RANDOM generates a random connected color graph.
• COLOR_GRAPH_ADJ_DEGREE computes the degree of each node.
• COLOR_GRAPH_ADJ_DEGREE_SEQ computes the degree sequence of a color graph.
• COLOR_GRAPH_ADJ_EDGE_COUNT counts the number of edges in a color graph.
• COLOR_GRAPH_ADJ_EXAMPLE_BUSH sets up the bush color graph.
• COLOR_GRAPH_ADJ_EXAMPLE_CUBE sets up the cube color graph.
• COLOR_GRAPH_ADJ_EXAMPLE_OCTO sets up an 8 node example color graph.
• COLOR_GRAPH_ADJ_EXAMPLE_TWIG sets up the twig color graph.
• COLOR_GRAPH_ADJ_PRINT prints out the adjacency matrix of a color graph.
• COLOR_GRAPH_ADJ_RANDOM generates a random color graph.
• DEGREE_SEQ_IS_GRAPHIC reports whether a degree sequence represents a graph.
• DEGREE_SEQ_TO_GRAPH_ADJ computes a graph with the given degree sequence.
• DGE_CHECK checks the dimensions of a general matrix.
• DGE_DET computes the determinant of a matrix factored by DGE_FA or DGE_TRF.
• DGE_FA factors a general matrix.
• DIGRAPH_ADJ_CLOSURE generates the transitive closure of a digraph.
• DIGRAPH_ADJ_COMPONENTS finds the strongly connected components of a digraph.
• DIGRAPH_ADJ_CYCLE searches for cycles in a digraph.
• DIGRAPH_ADJ_DEGREE computes the indegree and outdegree of each node.
• DIGRAPH_ADJ_DEGREE_MAX computes the maximum degrees of a digraph.
• DIGRAPH_ADJ_DEGREE_SEQ computes the directed degree sequence.
• DIGRAPH_ADJ_EDGE_COUNT counts the number of edges in a digraph.
• DIGRAPH_ADJ_EIGEN: eigenvalues of a digraph from its adjacency matrix.
• DIGRAPH_ADJ_EXAMPLE_CYCLER sets adjacency information for the cycler digraph.
• DIGRAPH_ADJ_EXAMPLE_OCTO sets up an 8 node example digraph.
• DIGRAPH_ADJ_EXAMPLE_SIXTY sets the adjacency matrix for the sixty digraph.
• DIGRAPH_ADJ_HAM_CAND: candidates for the next node in a Hamiltonian circuit.
• DIGRAPH_ADJ_HAM_NEXT returns the next Hamilton circuit for a digraph.
• DIGRAPH_ADJ_HAM_NEXT_BRUTE finds the next Hamiltonian circuit in a digraph.
• DIGRAPH_ADJ_HAM_PATH_NEXT_BRUTE: next path in digraph that visits all nodes.
• DIGRAPH_ADJ_IS_EDGE_CONNECTED determines if a digraph is edgewise connected.
• DIGRAPH_ADJ_IS_EULERIAN determines if a digraph is Eulerian.
• DIGRAPH_ADJ_IS_STRONG_CONNECTED: is a digraph strongly connected?
• DIGRAPH_ADJ_IS_TOURNAMENT determines if a digraph is a tournament.
• DIGRAPH_ADJ_IS_TRANSITIVE determines if a digraph is transitive.
• DIGRAPH_ADJ_IS_WEAK_CONNECTED determines if a digraph is weakly connected.
• DIGRAPH_ADJ_PRINT prints out an adjacency matrix for a digraph.
• DIGRAPH_ADJ_RANDOM generates a random digraph.
• DIGRAPH_ADJ_REDUCE generates a transitive reduction of a digraph.
• DIGRAPH_ADJ_TO_DIGRAPH_ARC converts digraph from adjacency to arc list form.
• DIGRAPH_ADJ_TO_DIGRAPH_INC converts adjacency digraph to incidence digraph.
• DIGRAPH_ADJ_TOP_SORT: reverse topological sort of a directed acyclic graph.
• DIGRAPH_ADJ_TOURNAMENT_RANDOM generates a random tournament digraph.
• DIGRAPH_ARC_DEGREE determines the degree of the nodes of a digraph.
• DIGRAPH_ARC_EDGE_SORT sorts the edge array of a graph.
• DIGRAPH_ARC_EULER_CIRC_CAND: candidates for K-th edge of an Euler circuit.
• DIGRAPH_ARC_EULER_CIRC_NEXT returns the next Euler circuit for a digraph.
• DIGRAPH_ARC_EXAMPLE_CYCLER sets arc list information for the cycler digraph.
• DIGRAPH_ARC_IS_EULERIAN determines if a digraph is Eulerian.
• DIGRAPH_ARC_PRINT prints out a digraph from an edge list.
• DIGRAPH_ARC_TO_DIGRAPH_ADJ converts arc list digraph to an adjacency digraph.
• DIGRAPH_ARC_TO_DIGRAPH_STAR sets forward star representation of a digraph.
• DIGRAPH_ARC_WEIGHT_PRINT prints out a weighted digraph from an edge list.
• DIGRAPH_DIST_PRINT prints the distance matrix defining a digraph.
• DIGRAPH_INC_PRINT prints the incidence matrix of a digraph.
• EDGE_ADD_NODES adds the edge defined by two nodes to the edge list.
• EDGE_BOUND reports the edges which are part of the boundary.
• EDGE_MATCH_FACE seeks an edge common to a face and the edge list.
• EDGE_MATCH_NODES seeks an edge of the form (N1,N2) or (N2,N1) in EDGE.
• EDGES_TO_PS writes subplot edges to a PostScript file.
• ELMHES transforms a real general matrix to upper Hessenberg form.
• FACE_CHECK checks and analyzes a set of faces.
• FACE_EXAMPLE_BOX returns the faces of a simple box.
• FACE_EXAMPLE_PIECES returns the faces of a set of three objects.
• FACE_FLIP flips faces to achieve a consistent orientation.
• FACE_TO_IV writes some simple graphics data to an Inventor file.
• FACE_SORT renumbers the faces in order of object and tier.
• FACE_TO_EDGE converts face data to edge data.
• FACE_TOUCH reports whether two polygonal faces touch.
• GET_UNIT returns a free FORTRAN unit number.
• GRAPH_ADJ_BFS carries out a breadth-first traversal of a graph.
• GRAPH_ADJ_BIPARTITE_RANDOM generates a random bipartite graph.
• GRAPH_ADJ_BLOCK: blocks of an undirected graph from its adjacency list.
• GRAPH_ADJ_CLOSURE generates the transitive closure of a graph.
• GRAPH_ADJ_COLOR_CAND: possible colors for a node during a graph coloring.
• GRAPH_ADJ_COLOR_NEXT returns possible colorings of a graph, one at a time.
• GRAPH_ADJ_COMPLEMENT: the adjacency matrix of the complement of a graph.
• GRAPH_ADJ_CONNECT_RANDOM generates a random connected graph.
• GRAPH_ADJ_CYCLE searches for cycles in a graph.
• GRAPH_ADJ_DEGREE computes the degree of each node.
• GRAPH_ADJ_DEGREE_MAX computes the maximum node degree.
• GRAPH_ADJ_DEGREE_SEQ computes the degree sequence of a graph.
• GRAPH_ADJ_DFS does a depth first search of a graph.
• GRAPH_ADJ_DFS_2 does a depth-first search of a graph.
• GRAPH_ADJ_EDGE_COUNT counts the number of edges in a graph.
• GRAPH_ADJ_EIGEN computes eigenvalues of a graph from its adjacency matrix.
• GRAPH_ADJ_EXAMPLE_BUSH sets up the adjacency information for the bush graph.
• GRAPH_ADJ_EXAMPLE_CUBE sets up the adjacency information for the cube graph.
• GRAPH_ADJ_EXAMPLE_DODECAHEDRON: adjacency info for the dodecahedron graph.
• GRAPH_ADJ_EXAMPLE_OCTO sets up an 8 node example graph.
• GRAPH_ADJ_EXAMPLE_TWIG sets up the adjacency information for the twig graph.
• GRAPH_ADJ_HAM_CAND: candidates for the next node in a Hamiltonian circuit.
• GRAPH_ADJ_HAM_NEXT returns the next Hamilton circuit for a graph.
• GRAPH_ADJ_HAM_NEXT_BRUTE finds the next Hamiltonian circuit in a graph.
• GRAPH_ADJ_IS_BIPARTITE determines if a graph is bipartite.
• GRAPH_ADJ_IS_EDGE_CONNECTED determines if a graph is edgewise connected.
• GRAPH_ADJ_IS_EULERIAN: is a graph Eulerian from its adjacency matrix?
• GRAPH_ADJ_IS_NODE_CONNECTED determines if a graph is nodewise connected.
• GRAPH_ADJ_IS_TREE determines whether a graph is a tree.
• GRAPH_ADJ_PRINT prints out an adjacency matrix for a graph.
• GRAPH_ADJ_RANDOM generates a random graph on NNODE nodes with NEDGE edges.
• GRAPH_ADJ_RANDOM2 generates a random graph on NNODE nodes with NEDGE edges.
• GRAPH_ADJ_REDUCE generates a transitive reduction of a graph.
• GRAPH_ADJ_SPAN_TREE finds a spanning tree of a graph.
• GRAPH_ADJ_SPAN_TREE_ENUM enumerates the spanning trees of a graph.
• GRAPH_ADJ_SYMMETRIZE symmetrizes an adjacency matrix.
• GRAPH_ADJ_TO_GRAPH_ARC converts an adjacency graph to an arc list graph.
• GRAPH_ARC_COMPLEMENT returns the edge list of the complement of a graph.
• GRAPH_ARC_DEGREE determines the degree of the nodes of a graph.
• GRAPH_ARC_EDGE_CON2 finds the edge-connectivity of a connected graph.
• GRAPH_ARC_EDGE_SORT sorts the edge array of a graph.
• GRAPH_ARC_EULER_CIRC finds an Euler circuit in an Eulerian graph.
• GRAPH_ARC_EULER_CIRC_CAND: candidates for the K-th edge of an Euler circuit.
• GRAPH_ARC_EULER_CIRC_NEXT returns the next Euler circuit for a graph.
• GRAPH_ARC_EXAMPLE_DIAMOND returns the graph of a "diamond" 3D shape.
• GRAPH_ARC_FACE constructs a set of faces for a plane graph.
• GRAPH_ARC_FACE_NEXT completes the next face, given a few starting nodes.
• GRAPH_ARC_IS_EULERIAN determines if a graph is Eulerian from its edge list.
• GRAPH_ADJ_IS_TREE determines whether a graph is a tree.
• GRAPH_ARC_MATCH finds a maximum matching in a bipartite graph.
• GRAPH_ARC_MIN_PATH finds the shortest path between two nodes.
• GRAPH_ARC_MIN_SPAN_TREE finds a minimum spanning tree of a graph.
• GRAPH_ARC_NCOLOR_PRINT prints out a node-colored graph from an edge list.
• GRAPH_ARC_NODE_COUNT counts the number of nodes in a graph.
• GRAPH_ARC_PRINT prints out a graph from an edge list.
• GRAPH_ARC_TO_PS writes graph information to a PostScript file.
• GRAPH_ARC_SPAN_FOREST determines a graph's connectivity and spanning forest.
• GRAPH_ARC_SPAN_TREE constructs the spanning tree of a graph.
• GRAPH_ARC_TO_DIGRAPH_ARC converts an undirected to a directed graph.
• GRAPH_ARC_TO_GRAPH_ADJ converts an arc list graph to an adjacency graph.
• GRAPH_ARC_TO_GRAPH_STAR sets the forward star form of an undirected graph.
• GRAPH_ARC_WEIGHT_PRINT prints out a weighted graph from an edge list.
• GRAPH_CHRO calculates the chromatic polynomial of a connected graph.
• GRAPH_DIST_ALL finds the distance from every node to every other node.
• GRAPH_DIST_CHECK checks a distance matrix for consistency.
• GRAPH_DIST_MIN_SPAN_TREE computes a spanning tree of minimal length.
• GRAPH_DIST_MIN_SPAN_TREE2 computes a spanning tree of minimal length.
• GRAPH_DIST_MIN_SPAN_TREE3 finds a minimum spanning tree.
• GRAPH_DIST_ONE computes the distance from one node to all others in a graph.
• GRAPH_DIST_PRINT prints a distance matrix.
• GREEDY pairs two sets of nodes using the least total distance.
• GRF_READ reads a GRF file containing a 2D representation of a graph.
• HQR computes all eigenvalues of a real upper Hessenberg matrix.
• I4_MODP returns the nonnegative remainder of integer division.
• I4_SWAP switches two integer values.
• I4_UNIFORM returns a scaled pseudorandom I4.
• I4VEC_UNIFORM_AB returns a scaled pseudorandom I4VEC.
• I4COL_COMPARE compares columns I and J of a integer array.
• I4COL_SORT_A ascending sorts an I4COL.
• I4COL_SWAP swaps columns I and J of an I4COL.
• I4COL_UNIQ keeps the unique elements in a sorted I4COL.
• I4MAT_PERM permutes the rows and columns of a square I4MAT.
• I4MAT_PERM_RANDOM selects a random permutation of an I4MAT.
• I4MAT_PRINT prints an I4MAT.
• I4MAT_ROW_COMPARE compares two rows of an I4MAT.
• I4MAT_ROW_SORT_D sorts the rows of an I4MAT into descending order.
• I4MAT_ROW_SWAP swaps two rows of an I4MAT.
• I4ROW_COMPARE compares two rows of an I4ROW.
• I4ROW_SORT_D descending sorts the rows of an I4ROW.
• I4ROW_SWAP swaps two rows of an I4ROW.
• ISET2_COMPARE compares two I2 sets.
• ISET2_INDEX_INSERT_UNIQUE inserts unique I2 set value in indexed sorted list.
• ISET2_INDEX_SEARCH searches for an I2 set value in an indexed sorted list.
• I4VEC_BACKTRACK supervises a backtrack search for an integer vector.
• I4VEC_COMPARE compares two integer vectors.
• I4VEC_HEAP_A reorders an array of integers into an ascending heap.
• I4VEC_HEAP_D reorders an array of integers into an descending heap.
• I4VEC_INDICATOR sets an integer vector to the indicator vector.
• I4VEC_NONZERO counts the nonzero entries in an integer vector
• I4VEC_ORDER_TYPE determines if I4VEC is (non)strictly ascending/descending.
• I4VEC_PERM_RANDOM selects a random permutation of an I4VEC.
• I4VEC_PRINT prints an integer vector.
• I4VEC_REVERSE reverses the elements of an integer vector.
• I4VEC_ROTATE rotates an object in place.
• I4VEC_SORT_HEAP_A ascending sorts an integer array using heap sort.
• I4VEC_SORT_HEAP_D descending sorts an integer array using heap sort.
• I4VEC_SORT_HEAP_INDEX_D: indexed heap descending sort of an I4VEC.
• I4VEC_UNIQ finds the number of unique elements in a sorted integer array.
• I4VEC2_COMP compares pairs of integers stored in two vectors.
• I4VEC2_PRINT prints a pair of integer vectors.
• I4VEC2_SORT_A ascending sorts a vector of pairs of integers.
• I4VEC2_SORT_D descending sorts a vector of pairs of integers.
• I4VEC2_UNIQ keeps the unique elements in a array of pairs of integers.
• KSUB_RANDOM selects a random subset of size K from a set of size N.
• M_GRAPH_ADJ_EDGE_SEQ computes the edge sequence of a multigraph.
• MAZE_DIAM computes the "diameter" of a maze that has no circuits.
• MAZE_PATH finds a path through a maze.
• MAZE_PRINT prints out a maze and a path.
• MAZE_RANDOM generates a random maze in a rectangular region.
• NETWORK_FLOW_MAX finds the maximal flow and a minimal cut in a network.
• NODE_ORDER_PRINT prints out a node ordering.
• NODE_RELAX smooths a shape by an averaging operation on the node positions.
• NODES_TO_PS writes subplot nodes to a PostScript file.
• OBJECT_BUILD builds edge-connected "objects" out of polygonal faces.
• PERM_CYCLE analyzes a permutation.
• PERM_FREE reports the number of unused items in a partial permutation.
• PERM_INC "increments" a permutation to get the "next" one.
• PERM_INV inverts a permutation.
• PERM_NEXT computes all of the permutations on N objects, one at a time.
• PERM_RANDOM selects a random permutation of N objects.
• POLY performs operations on polynomials in power or factorial form.
• POLY_TO_TRI converts a collection of polygons into a collection of triangles.
• PRUEFER_TO_TREE_ARC is given a Pruefer code, and computes the tree.
• PYTHAG computes SQRT ( A^2 + B^2 ) carefully.
• R4_UNIFORM_01 returns a unit pseudorandom R4.
• R8_SWAP swaps two double precision values.
• R8_UNIFORM_01 returns a unit pseudorandom R8.
• R8COL_FIND seeks a table column equal to a real vector.
• R8MAT_PRINT prints out a portion of a dense matrix.
• R8VEC_PRINT prints an R8VEC.
• R8VEC_UNIFORM returns a scaled pseudorandom R8VEC.
• R8VEC_UNIFORM_01 returns a unit pseudorandom R8VEC.
• R8VEC2_PRINT prints a pair of R8VEC's.
• R8VEC3_COMPARE compares two R8VEC's.
• R8VEC3_INDEX_INSERT_UNIQUE inserts unique value in an indexed sorted list.
• R8VEC3_INDEX_SEARCH searches for an R3 value in an indexed sorted list.
• S_BLANKS_DELETE replaces consecutive blanks by one blank.
• S_CAT concatenates two strings to make a third string.
• S_EQI is a case insensitive comparison of two strings for equality.
• S_TO_I4 reads an I4 from a string.
• S_TO_R8 reads an R8 from a string.
• SHAPE_2D_EDGES_TO_PS writes 2D shape edges to a PostScript file.
• SHAPE_2D_FACES_TO_PS writes 2D shape faces to a PostScript file.
• SHAPE_2D_NODES_TO_PS writes 2D shape nodes to a PostScript file.
• SHAPE_3D_EDGES_TO_PS writes 3D shape edges to a PostScript file.
• SHAPE_3D_FACES_TO_PS writes 3D shape faces to a PostScript file.
• SHAPE_3D_NODES_TO_PS writes 3D shape nodes to a PostScript file.
• SORT_HEAP_EXTERNAL externally sorts a list of items into ascending order.
• SPAN_FOREST determines a graph's connectivity and spanning forest.
• SPAN_TREE_CAND finds candidates for the K-th edge of a spanning tree.
• SPAN_TREE_NEXT uses backtracking to find spanning forests of a graph.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TQLRAT compute all eigenvalues of a real symmetric tridiagonal matrix.
• TRED1 transforms a real symmetric matrix to tridiagonal form.
• TREE_ARC_RANDOM selects a random labeled tree and its Pruefer code.
• VEC_NEXT generates all N-vectors of integers modulo a given base.
• VEC_RANDOM selects a random N-vector of integers modulo a given base.
• VLA_TO_GRAPH_ARC reads graphics information from a VLA file.
• WORD_NEXT_READ "reads" words from a string, one at a time.

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