CMU Artificial Intelligence Repository
Home INFO Search FAQs Repository Root

Prolog graph-handling routines

This package contains two programs: one for decomposing a non-weighted directed graph into strongly connected components; and the other for finding simple and elementary cycles in a strongly connected component.
Origin: (
   as graph.tar.Z

Version: 12-JAN-91 Ports: Runs in SICStus Prolog, which is Quintus compatible and hence uses the `standard' Edinburgh syntax. Some of the I/O is non-portable. CD-ROM: Prime Time Freeware for AI, Issue 1-1 Author(s): Paul Freedman Laboratoire d'automatique et d'analyse des systemes Groupe Robotique et Intelligence Artificielle 7 Avenue du colonel Roche 31 077 Toulouse Cedex Keywords: Authors!Freedman, Graph Theory, Math, Prolog!Code, Prolog!Math References: The programs are commented, but a basic knowledge of graph theory would be useful. The following are the most important references for the algorithms behind the programs. A. Aho and J. Hopcroft and J. Ullman, "The Design and Analysis of Computer Algorithms", Addison-Wesley, 1974. R. Read and R. Tarjan, "Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees", Networks 5:237-252, 1975. R. Tarjan, "Depth First Search and Linear Graph Algorithms", SIAM Journal of Computing 1(2):146-160, June 1972.
Last Web update on Mon Feb 13 10:33:49 1995