START Conference Manager    

Write it Recursively: A Generic Framework for Optimal Path Queries

Akimasa Morihata, Kiminori Matsuzaki and Masato Takeichi

The 13th ACM SIGPLAN International Conference on Functional Programming (ICFP 2008)
Victoria, British Columbia, Canada, September 22-24, 2008


Abstract

Optimal path queries are queries to obtain an optimal path specified by a given criterion of optimality. Optimal path queries are important from both theoretical and practical aspects. While there exist many researches on this topic, most of them are problem-specific and algorithmic works, and it is difficult for non-specialists to utilize them. In this paper, we propose a generic and linguistic framework for optimal path queries. We design a small functional language to describe optimal path queries, which forms a functional interface between algorithmic works and non-specialists. Then, we describe an algorithm to find an optimal path specified in our language and report on our implementation of an optimal path querying system. The most distinct feature of our framework is the use of recursive functions in specifying queries. Recursive functions not only provide high expressiveness to our language but also lead to an efficient optimal path querying algorithm. Our framework is expressive in the sense that it can describe many known problems and their combinations. Our algorithm is efficient in the sense that it is a generalization of some known efficient algorithms. Our system is neat in the sense that it can answer queries on graphs of practical size despite its small code size.


START Conference Manager (V2.54.6)