This technical synthesis explores the methodologies for representing and reasoning about graphs within the Prolog environment. It contrasts spatial representations (graphs as single terms) with temporal representations (graphs enumerated via backtracking) and analyzes the performance trade-offs inherent in various data structures. The discussion covers tree-to-term mapping, adjacency lists in library(ugraphs), logarithmic lookup via AVL trees (library(assoc)), and constant-time access methods including argument indexing, the arg/3 predicate for adjacency matrices, and attributed variables for heap-based pointer structures. Practical applications are demonstrated through implementations of transitive closures, Eulerian path detection for the Seven Bridges of Königsberg, and Hamiltonian cycles using Constraint Logic Programming (CLP).
Representing Graphs in Prolog: Technical Summary & Analysis
0:01 Graph and Tree Fundamentals: A graph is defined as an ordered pair of vertices ($V$) and edges ($E$). In computer science, rooted trees are a critical subset where every node except the root has a unique parent.
1:22 Trees as Prolog Terms: Ordered rooted trees (plain trees) map directly to Prolog terms.
Takeaway: Using functors as nodes (e.g., d(b(a,c), e(h,g,f))) is memory-efficient, requiring exactly one Warren Abstract Machine (WAM) cell per node. However, this is non-uniform and complicates the attachment of node/edge metadata.
4:20 Uniform Spatial Representations: Representing nodes as node_children(Node, ChildrenList) offers a uniform shape for recursive processing.
Detail: This format is highly compatible with Definite Clause Grammars (DCGs) for sequence description but consumes more memory due to additional list constructors and wrappers.
9:23 Binary Tree Optimization: Binary trees can be represented more compactly than general trees by replacing lists with pairs or specialized node(Value, Left, Right) structures. The nil atom typically denotes an empty leaf.
12:09 Library(assoc) and AVL Trees: Many Prolog systems use AVL trees to implement associations.
Takeaway: This provides logarithmic $O(\log n)$ overhead for lookup, insertion, and deletion, which is generally acceptable for most graph-related applications.
13:50 Adjacency Lists and Library(ugraphs): General graphs are frequently represented as adjacency lists (pairs of Vertex-Neighbors).
Detail:library(ugraphs) provides two formats: P-representation (list of directed edges) and S-representation (sorted vertex-neighbor pairs). The latter allows for efficient computation of transitive closures using Warshall’s algorithm.
Argument Indexing (20:08): Storing a graph as a set of facts in the clause database allows the Prolog engine to use automatic indexing for constant-time lookup. However, database modifications are slow and non-backtrackable (side effects).
The arg/3 Predicate (24:40): Using a compound term as an adjacency matrix allows arg/3 to access any "cell" in constant time.
Optimization: To mitigate the quadratic $O(V^2)$ space complexity, bits can be packed into integers (bit-packing) to reduce memory usage by approximately a factor of 60.
32:54 Attributed Variables and Constraint Graphs: Attributed variables allow the attachment of metadata directly to variables on the heap, effectively creating a graph where edges are pointers.
Application: This is the underlying mechanism for constraint solvers. Jean-Charles Régin’s filtering algorithm for the all_distinct constraint uses this to reason about the "value graph" (a bipartite graph of variables and domain elements).
46:04 Case Study: Seven Bridges of Königsberg: This multigraph problem is implemented in Prolog using a list of undirected edges and a DCG to find an Eulerian path.
Takeaway: Generalizing the program to track "remaining edges" (multiset difference) makes the code more testable and verifiable, confirming Euler’s proof that no such path exists for the specific Königsberg configuration.
56:43 Hamiltonian Circuits and CLP(B/FD): Specialized constraints like circuit/1 in CLP(FD) represent graphs where the $k$-th element of a list denotes the successor of node $k$.
Takeaway: This representation leverages filtering to prune the search space before and during labeling, significantly improving search efficiency for NP-complete problems.