Reachability constraint in SWI/CLP(FD)

Question

I'm trying to determine that shape of a directed graph by solving constraints on presence of nodes and arcs, e.g., binary variable V1V2 is 1 if there is an arc from node V1 to V2. I would like to express the reachability constraint (or, alternatively, find a transitive closure), e.g., to require that the graph is connected, or that there is a path from one given node to another given node.

I've seen that SICStus Prolog has fd_closure for this purpose, but I could not find anything similar in SWI Prolog. Should I use CHR? I've been looking at the arc/path consistency examples but I'm not sure whether I'm looking in the right direction.

Answer 1

SICStus' fd_closure/2 is very similar to SWI-Prolog's term_attvars/2. It gives you all variables that can be transitively reached via attributes (and SWI's CLP(FD) uses attributes to store constraints).

Note that you typically do not need these predicates. They are used for example on the toplevel to obtain residual goals.

You can express a graph with finite domain constraints without using any of these predicates. For example, use a finite domain variable B_i_j which is 1 iff there is an arc from node i to node j.

If you require stronger properties, you will likely need stronger constraints. For example, circuit/1 is available in SICStus and SWI and describes a Hamiltonian circuit. For other properties, you can implement dedicated filtering algorithms.

Answer 2

With copy_term/3 and term_variables/2 you should be able to get (edit: almost) the same effect as fd_closure/2.

Please note that fd_closure in SICStus only works for FD-constraints. Other connections between variables are not taken into account.

Edit: This way you will get only copies of internal variables - this should be good enough to determine the shape. However, you might want to refer to those variables later on in which case @mat's solution is it.