No CrossRef data available.
Article contents
An in-situ algorithm for expanding a graph
Published online by Cambridge University Press: 07 January 2013
Extract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.
This pearl is devoted to a problem posed by Don Knuth about how to justify a certain array-based algorithm for changing the way an undirected graph is represented. In order to set the scene, we delay describing the precise problem until Section 4. Knuth (2011) recorded three different solutions, though no proofs of correctness were provided, nor even much explanation of why they worked. Recently, he asked various computer scientists interested in formal program development whether any of the proposed solutions “could have been discovered in a disciplined manner.” In what follows we respond by developing a purely functional solution. The solution makes heavy use of the operations in the Haskell library Data.Array, and the whole exercise turns out to be a fascinating study of the arithmetic of graphs and arrays. One of the conditions of the problem is that the final algorithm has to be in situ, but we will get to that in due course.
- Type
- Functional Pearls
- Information
- Copyright
- Copyright © Cambridge University Press 2013
References
Bird, R. S. (1998) Introduction to Functional Programming using Haskell. London: Prentice Hall.Google Scholar
Bird, R. S. (2010) Pearls of Functional Algorithm Design. Cambridge, UK: Cambridge University Press.CrossRefGoogle Scholar
Knuth, D. E. (2011) Solutions to a puzzling problem. Extract from A Companion to the Papers of Donald Knuth. Stanford, CA: California Centre for the Study of Languages and Information. Available at: http://www-cs-faculty.stanford.edu/knuth/shortcode.pdfGoogle Scholar
You have
Access
Discussions
No Discussions have been published for this article.