<ConsistencyModule:> ham_path(?Start,?End,+Succ,++CostMatrix,?Cost)

Start

An integer or )domain) variable (array notation accepted)

End

An integer or (domain) variable (array notation accepted)

Succ

A collection of N different (domain) variables or integers

CostMatrix

A NxN matrix collection of integers.

Cost

A (domain) variable or integer (array notation accepted).

Description

Succ is a collection of N elements presenting a digraph of N nodes, where the i'th element of Succ represents the successor to node i. The constraint enforces Succ to form a Hamiltonian path, a path through every node in the graph, visiting each node once, with Start giving the first node of the path, and End giving the last node of the path. Note that the Succ of the last node will be N+1, i.e. a dummy node not in the graph. Additionally, CostMatrix specifies the cost for traversing between each pair of nodes: CostMatrix[i,j] represents the cost of travelling from node i to j, and Cost is constrained to the total cost for the path.

Note that the Gecode implementation of this constraint has index (node id) starting from 0, rather than 1. This constraint is actually posted as ham_path_offset_g/4 with an offset of 1. A version of this constraint with native Gecode indexing is available as ham_path_g/3.

This constraint can be embedded in a constraint expression in its functional form (without the last argument).

ConsistencyModule is the optional module specification to give the consistency level for the propagation for this constraint: gfd_gac for generalised arc consistency (domain consistency), and gfd_vc for value consistency.

This constraint is implemented by Gecode's path() constraint (variant with cost), using an offset of 1.

Examples

[eclipse 2]: CostM = []([](0,3,5,7),[](4,0,9,6),[](2,1,0,5),[](-7,8,-2,0)),
        ham_path(4,3,[2,3,5,1], CostM, C).

CostM = []([](0, 3, 5, 7), [](4, 0, 9, 6), [](2, 1, 0, 5), [](-7, 8, -2, 0))
C = 5

See Also