CMU Artificial Intelligence Repository
Prolog graph-handling routines
lang/prolog/code/math/graph/
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:
src.doc.ic.ac.uk:packages/prolog-pd-software/ (146.169.2.1)
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
AI.Repository@cs.cmu.edu