# graph_theory

graph_theory, a Fortran90 code which carries out operations on abstract graphs, such as a breadth-first-search, the computation of a minimum spanning tree, an Euler or Hamilton circuit, blocks, chromatic polynomial, or transitive closure. Objects include undirected and directed graphs, weighted graphs, and trees.

Some of the routine names begin with a prefix that indicates the type of object it is associated with:

• DIGRAPH_DIST is a directed graph described by a distance matrix;
• FACE is a collection of "faces" defined by circuits in a graph;
• GRAPH_ARC is an undirected graph described by an edge list;
• GRAPH_DIST is an undirected graph described by a distance matrix;

### Languages:

graph_theory is available in a Fortran90 version and a MATLAB version and an Octave version and a Python version.

### Related Data and Programs:

cities, a FORTRAN90 code which handles various problems associated with a set of "cities" on a map.

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

color_digraph_adj, a Fortran90 code which carries out operations on color digraphs, a directed graph in which each node has been assigned a color. That information is stored in an adjacency matrix in which the diagonal elements record colors. Operations include counting the colors, computing in- and out-degrees, computing the in- and out-degree sequences, counting the edges, printing the adjacency matrix, generating fixed and random examples.

color_graph_adj, a Fortran90 code which carries out operations on color graphs, an undirected graph in which each node has been assigned a color. That information is stored in an adjacency matrix in which the diagonal elements record colors. Operations include counting the colors, computing degrees, computing the degree sequences, counting the edges, printing the adjacency matrix, generating fixed and random examples.

digraph_adj, a Fortran90 code which carries out operations on digraphs, a directed graph. Information is stored in an adjacency matrix. Operations include computing in- and out-degrees, computing the in- and out-degree sequences, counting the edges, printing the adjacency matrix, generating fixed and random examples.

digraph_arc, a Fortran90 code which carries out operations on digraphs, a directed graph. Information is stored in an arc list, pairs of nodes forming edges. Operations include computing in- and out-degrees, computing the in- and out-degree sequences, counting the edges, printing the arc list, generating fixed and random examples.

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

graph_adj, a Fortran90 code which carries out operations on abstract graphs, with undirected edges, represented by an adjacency matrix. Operations include breadth-first search, the computation of a minimum spanning tree, an Euler or Hamilton circuit, blocks, chromatic polynomial, or transitive closure.

graph_arc, a Fortran90 code which carries out operations on graphs. Information is stored in an arc list, pairs of nodes forming edges. Operations include the chromatic polynomial, computing degrees, computing the degree sequence, counting the edges, determining edge and node connectivity, Euler circuits, spanning trees, shortest path, printing the arc list, generating fixed and random examples.

graph_dist, a Fortran90 code which carries out operations on abstract graphs, defined by undirected edges with an associated distance matrix.

grf, a data directory which contains a description of the GRF format and some examples.

grf_io, a FORTRAN90 code which reads and writes GRF files.

maze, a Fortran90 code which carries out operations on a maze, including the diameter, a random example, or a path that solves the maze.

toms097, a FORTRAN90 code which computes the distance between all pairs of nodes in a directed graph with weighted edges, using Floyd's algorithm.

treepack, a FORTRAN90 code 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,
ISBN: 0-12-519260-6,
LC: QA164.N54.
4. Robert Sedgewick,
Algorithms in C,
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:

Last revised on 01 March 2023.