GRAFPACK - Graph Computations

GRAFPACK includes routines for performing common calculations involving graphs, such as a breadth-first-search, 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.

For a related set of routines that determine isomorphism using the idea of codes, see CODEPACK.

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;
• TREE_ARC is a tree described by an edge list;

Files you may copy include:

• grafpack.f90, the source code;
• grafpack_prb.f90, the calling program;
• grafpack_prb.out, the sample output.
• 57_city_distances.txt, a city distance table.
• knightstour.grf, a knight tour graph in GRF format.

The list of routines includes:

• 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.
• 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 computes the eigenvalues of a digraph from its adjacency matrix.
• DIGRAPH_ADJ_EXAMPLE_CYCLER sets up the 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 finds 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 finds the next path in a 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 from its adjacency ma
• DIGRAPH_ADJ_IS_STRONG_CONNECTED determines if a digraph is strongly connected.
• DIGRAPH_ADJ_IS_TOURNAMENT determines if a digraph is a tournament from its adjacency matrix.
• 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 a digraph from adjacency to arc list form.
• DIGRAPH_ADJ_TO_DIGRAPH_INC converts an adjacency digraph to an incidence digraph.
• DIGRAPH_ADJ_TOP_SORT finds a reverse topological sorting 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 finds candidates for the 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 up the arc list information for the cycler digraph.
• DIGRAPH_ARC_IS_EULERIAN determines if a digraph is Eulerian from its edge list.
• DIGRAPH_ARC_PRINT prints out a digraph from an edge list.
• DIGRAPH_ARC_TO_DIGRAPH_ADJ converts an arc list digraph to an adjacency digraph.
• DIGRAPH_ARC_TO_DIGRAPH_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_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 finds the blocks of an undirected graph from its adjacency list.
• GRAPH_ADJ_CLOSURE generates the transitive closure of a graph.
• GRAPH_ADJ_COLOR_CAND finds 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 returns 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 the 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 sets up the adjacency information 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 finds 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 determines if a graph is 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_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 finds 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 tries to complete the next face, given a few starting nod
• GRAPH_ARC_IS_EULERIAN determines if a graph is Eulerian from its edge list.
• 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 up the forward star representation of an undirected gr
• 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.
• I_MODP returns the nonnegative remainder of integer division.
• I_RANDOM returns a random integer in a given range.
• I_SWAP switches two integer values.
• ICOL_COMPARE compares columns I and J of a integer array.
• ICOL_SORT_A ascending sorts an integer array of columns.
• ICOL_SWAP swaps columns I and J of a integer array of column data.
• ICOL_UNIQ keeps the unique elements in a sorted integer array of columns.
• IMAT_PERM permutes the rows and columns of a square integer matrix.
• IMAT_PERM_RANDOM selects a random permutation of an integer matrix.
• IMAT_PRINT prints an integer matrix.
• IMAT_ROW_COMPARE compares two rows of an integer matrix.
• IMAT_ROW_SORT_D sorts the rows of an integer matrix into descending order.
• IMAT_ROW_SWAP swaps two rows of an integer matrix.
• ISET2_COMPARE compares two I2 sets.
• ISET2_INDEX_INSERT_UNIQUE inserts a unique I2 set value in an indexed sorted list.
• ISET2_INDEX_SEARCH searches for an I2 set value in an indexed sorted list.
• IVEC_BACKTRACK supervises a backtrack search for an integer vector.
• IVEC_COMPARE compares two integer vectors.
• IVEC_HEAP_A reorders an array of integers into an ascending heap.
• IVEC_HEAP_D reorders an array of integers into an descending heap.
• IVEC_NONZERO counts the nonzero entries in an integer vector
• IVEC_ORDER_TYPE determines if an integer array is (non)strictly ascending/descending.
• IVEC_PERM_RANDOM selects a random permutation of an integer vector.
• IVEC_PRINT prints an integer vector.
• IVEC_RANDOM returns a random integer vector in a given range.
• IVEC_REVERSE reverses the elements of an integer vector.
• IVEC_ROTATE rotates an object in place.
• IVEC_SORT_HEAP_A ascending sorts an integer array using heap sort.
• IVEC_SORT_HEAP_D descending sorts an integer array using heap sort.
• IVEC_SORT_HEAP_INDEX_D does an indexed heap descending sort of an integer vector.
• IVEC_UNIQ finds the number of unique elements in a sorted integer array.
• IVEC2_COMP compares pairs of integers stored in two vectors.
• IVEC2_PRINT prints a pair of integer vectors.
• IVEC2_SORT_A ascending sorts a vector of pairs of integers.
• IVEC2_SORT_D descending sorts a vector of pairs of integers.
• IVEC2_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.
• PRUEFER_TO_TREE_2 produces the edge list of a tree from its Pruefer code.
• PYTHAG computes SQRT ( A**2 + B**2 ) carefully.
• R_RANDOM returns a random real in a given range.
• R_SWAP swaps two real values.
• RCOL_FIND seeks a table column equal to a real vector.
• RMAT_PRINT prints out a portion of a dense matrix.
• RVEC_PRINT prints a real vector.
• RVEC_RANDOM returns a random real vector in a given range.
• RVEC2_PRINT prints a pair of real vectors.
• RVEC3_COMPARE compares two R3 vectors.
• RVEC3_INDEX_INSERT_UNIQUE inserts a unique R3 value in an indexed sorted list.
• RVEC3_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_I reads an integer value from a string.
• S_TO_R reads a real number from a string.
• SGE_CHECK checks the dimensions of a general matrix.
• SGE_DET computes the determinant of a matrix factored by SGE_FA or SGE_TRF.
• SGE_FA factors a general matrix.
• 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 linear 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 of a graph.
• SPAN_TREE_NEXT uses backtracking to find spanning forests of a graph.
• TQLRAT compute all eigenvalues of a real symmetric tridiagonal matrix.
• TRED1 transforms a real symmetric matrix to tridiagonal form.
• TREE_ARC_CENTER computes the center, eccentricity, and parity of a tree.
• TREE_ARC_DIAM computes the "diameter" of a tree.
• TREE_ARC_RANDOM selects a random labeled tree and its Pruefer code.
• TREE_ARC_TO_PRUEFER is given a labeled tree, and computes its Pruefer code.
• TREE_ENUM enumerates the labeled trees on NNODE nodes.
• TREE_PARENT_NEXT generates, one at a time, all labeled trees.
• TREE_PARENT_TO_ARC converts a tree from parent to arc representation.
• TREE_RB_ENUM returns the number of rooted binary trees with N nodes.
• TREE_RB_LEX_NEXT generates rooted binary trees in lexicographic order.
• TREE_RB_TO_PARENT converts a rooted binary tree to parent node representation.
• TREE_RB_YULE adds two nodes to a rooted binary tree using the Yule model.
• TREE_ROOTED_CODE returns the code of a rooted tree.
• TREE_ROOTED_CODE_COMPARE compares (a portion of) the codes for two rooted trees.
• TREE_ROOTED_DEPTH returns the depth of a rooted tree.
• TREE_ROOTED_ENUM counts the number of unlabeled rooted trees.
• TREE_ROOTED_RANDOM selects a random unlabeled rooted tree.
• 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.

Back to the FORTRAN software page.