[ library(hcc) | Reference Manual | Alphabetic Index ]

hcc(+Vars, ++Points, ++Options)

Hall Circuit Constraint

Vars: Collection of variables representing the successor of each node
Points: List of points p(Id,X,Y), one for each node/value
Options: List of options

Description

Enforces the Hall Circuit Constraint on a collection of variables (Vars). The intended use is for Hamiltonian-circuit style models where the variable at position Id denotes the successor of node Id. The constraint removes self loops and applies Hall-set filtering to the successor variables.

Points. Points is the list of geometric coordinates associated with the nodes. Each element must have the form p(Id,X,Y), where Id is the node/value numeric integer identifier and X, Y are numeric coordinates. When a valid points list is supplied, the constraint automatically enables convex-hull based pruning on top of the standard Hall-set filtering. This geometric pruning is used unless it is explicitly switched off with geometry(off) (see Options below).

Supported Options are:

path(on): Enable path-based pruning. When a Hall component has one entry and one exit, the exit is forbidden until the path has visited the other nodes in the component.
path(off): Disable path-based pruning (default).
geometry(on): Enable convex-hull based pruning. This is already the default whenever a valid Points list is provided, so it normally need not be stated explicitly. It requires a valid points list: passing geometry(on) without coordinates raises an error.
geometry(off): Disable convex-hull based pruning even when a Points list is provided. Only the Hall-set filtering is then applied.

How to use. The graph is described by the user-provided facts point/3 (one point(Id,X,Y) fact per node, giving its coordinates) and edge/2 (one edge(From,To) fact per directed arc). The model collects the points, builds one successor variable per node whose domain is the set of out-neighbours, posts the constraint together with circuit/1, and searches for a Hamiltonian circuit. Because a valid points list is passed, convex-hull pruning is active (add geometry(off) to the option list to turn it off):

        hcc_test(N, L, SN):-
            findall(p(Id,X,Y), point(Id,X,Y), Lnodes),
            (var(N) -> length(Lnodes, N) ; true),
            length(L, N),
            create_var_hcc(L, Lnodes),
            hcc(L, Lnodes, _),
            circuit(L),
            search(L, 0, first_fail, indomain, complete, [backtrack(SN)]).


        create_var_hcc([], []):- !.
        create_var_hcc([X|L], [p(N,_,_)|LN]):-
            concat_string(["Nex",N], Name),
            set_var_name(X, Name),
            findall(M, edge(N,M), Dom),
            X :: Dom,
            create_var_hcc(L, LN).

Examples

        % Basic HCC, no geometry, no path pruning
        hcc(Vars)
        % HCC with path pruning, no geometry
        hcc(Vars, [path(on)])
        % Points provided but convex-hull pruning explicitly disabled
        hcc(Vars, Points, [geometry(off)])
        % Convex-hull pruning (from the points) plus path pruning
        hcc(Vars, Points, [path(on)])