Contrainte d'accessibilité dans SWI/CLP(FD)

Question

J'essaie de déterminer cette forme d'un graphe orienté en résolvant les contraintes de présence de nœuds et d'arcs, par exemple une variable binaire V1V2 est 1 s'il y a un arc à partir du nœud V1 à V2.Je voudrais exprimer la contrainte d'accessibilité (ou, alternativement, trouver une fermeture transitive), par exemple, exiger que le graphe soit connecté ou qu'il existe un chemin d'un nœud donné à un autre nœud donné.

J'ai vu que SICStus Prolog a fd_closure à cet effet, mais je n'ai rien trouvé de similaire dans SWI Prolog.Dois-je utiliser CHR?J'ai regardé les exemples de cohérence arc/chemin mais je ne sais pas si je regarde dans la bonne direction.

Answer 1

SICStus' fd_closure/2 est très similaire à celui de SWI-Prolog term_attvars/2.Il vous donne toutes les variables qui peuvent être atteintes de manière transitive via des attributs (et le CLP(FD) de SWI utilise des attributs pour stocker les contraintes).

Notez que vous faites généralement pas besoin de ces prédicats.Ils sont utilisés par exemple au niveau supérieur pour obtenir des objectifs résiduels.

Vous pouvez exprimer un graphe avec des contraintes de domaine fini sans utiliser aucun de ces prédicats.Par exemple, utilisez une variable de domaine fini B_i_j qui vaut 1 si et si il y a un arc depuis le nœud je au nœud j.

Si vous avez besoin de propriétés plus solides, vous aurez probablement besoin de propriétés plus fortes. contraintes.Par exemple, circuit/1 est disponible dans SICStus et SWI et décrit un circuit hamiltonien.Pour d'autres propriétés, vous pouvez implémenter des algorithmes de filtrage dédiés.

Answer 2

Avec copy_term/3 et term_variables/2 vous devriez pouvoir obtenir (modifier :presque) le même effet que fd_closure/2.

Veuillez noter que fd_closure dans SICStus ne fonctionne que pour les contraintes FD.Les autres connexions entre variables ne sont pas prises en compte.

Modifier:De cette façon, vous n'obtiendrez que des copies des variables internes - cela devrait être suffisant pour déterminer la forme.Cependant, vous souhaiterez peut-être faire référence à ces variables plus tard, auquel cas la solution de @mat est la bonne.