Executable Pseudocode for Graph Algorithms
2015
textabstract Algorithms are written in pseudocode. However the implementation of an
algorithm in a conventional, imperative programming language can often be
scattered over hundreds of lines of code thus obscuring its essence. This can
lead to difficulties in understanding or verifying the code. Adapting or
varying the original algorithm can be laborious.
We present a case study showing the use of Common Lisp macros to provide an
embedded, domain-specific language for graph algorithms. This allows these
algorithms to be presented in Lisp in a form directly comparable to their
pseudocode, allowing rapid prototyping at the algorithm level.
As a proof of concept, we implement Brandes' algorithm for computing the
betweenness centrality of a graph and see how our implementation compares
favourably with state-of-the-art implementations in imperative programming
languages, not only in terms of clarity and verisimilitude to the pseudocode,
but also execution speed.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
19
References
1
Citations
NaN
KQI