SDA SE Wiki

Fast and reliable Prolog implementations of several essential graph algorithms will be an indispensable basis for the entire lab.

This talk will start with an introduction of the basic graph theory concepts that we want to implement:

• Strongly connected components
• Shortest / longest paths
• Projection of cyclic graph onto an acyclic graph in which each node represents an SCC¹⁾ in the cyclic graph²⁾
• Diameter of a cycle (1/2 of the length of the cycle)
• Minimal flow / graph connectivity
• Minimal number of edges to remove in order to break cycles

It will then discuss techniques to implement these concepts efficiently in Prolog focusing on the relation of connectivity to linear programming and the “Constraint Logic Programming for Finite Domains” library of SWI-Prolog.

Ideally, the you will have already turned the existing “max_flow” predicate of the clpfd library into a min_flow predicate. In that case this part of the talk will focus on the USE of the library and predicate, explaining only the very basics of CLPFD (not the entire implementation of min_flow).

If there is time, the presentation will also explain the USE of the available Prolog implementation of Tarski's linear-time algorithm for finding strongly connected components. Here it will focus in particular on the object-oriented structure of the implementation, as a template for how we want to write reusable / extensible Prolog code during the lab.

What remains to be done in the lab phase could be discussed in a concluding slide: Making suggestions for which (not just how many) edges to remove to break a cycle.

A good entry point to the graph theory basics is the wikipedia article on

• Graph Connectivity

The relation of the connectivity problem to linear programming is described in the article on the

• Max-flow min-cut theorem

An introduction to linear programming and the original simplex algorithm is given here:

• Linear_programming

An implementation of the Simplex algorithm (and others) in Prolog is provided as part of the “Constraint Logic Programming for Finite Domains” (CLPFD) library of SWI-Prolog (contribution of Markus Triska), which is contained in the file “/libraries/clp/clpfd.pl” of your SWI-Prolog installation. This file also contains, the predicate maximum_flow/2, which may be useful to you with small modifications to compute the min_flow value. Among all saturated arcs, you could then search for the cuts themselves. See also the implementation of maximum_matching/2. Markus Triska markus.triska@gmx.at (the author of the CLPD library) offered to help if you have any questions about the code.

The basics of using CLPFD are described in the SWI-Prolog manual:

• SWI-Prolog manual, Appendix 7

The first complete version of the presentation will be presented to GK on Thursday, Sept 30, 2010 at 9:00.