Logic Programming with Graph Automorphism: Integrating nauty with Prolog (Tool Description)*. Issue 5 (14th October 2016)

• Record Type: Journal Article
• Authors: FRANK, MICHAEL; CODISH, MICHAEL
• Editors: Carro, Manuel; King, Andy
• Is Part Of: Theory and practice of logic programming. Volume 16:Issue 5/6(2016)
• Page Start: 688
• Page End: 702
• Publication Date: 2016-10-14
• Subjects: Logic programming -- Periodicals; Artificial intelligence -- Computer programs -- Periodicals; Constraint programming (Computer science) -- Periodicals; 005.115
• DOI: 10.1017/S1471068416000223
• Languages: English
• ISSNs: 1471-0684

Abstract

Abstract: This paper presents thepl-nauty library, a Prolog interface to thenauty graph-automorphism tool. Adding the capabilities ofnauty to Prolog combines the strength of the "generate and prune" approach that is commonly used in logic programming and constraint solving, with the ability to reduce symmetries while reasoning over graph objects. Moreover, it enables the integration ofnauty in existing tool-chains, such as SAT-solvers or finite domain constraints compilers which exist for Prolog. The implementation consists of two components:pl-nauty, an interface connectingnauty 's C library with Prolog, andpl-gtools, a Prolog framework integrating the software component ofpl-nauty, calledgtools, with Prolog. The complete tool is available as a SWI-Prolog module. We provide a series of usage examples including two that apply to generate Ramsey graphs.