Source code
Any source code released here is publicly available, and licensed under a BSD-style license. The source code itself is all available from http://svn.sdstrowes.co.uk/.
Orta
The overlay for real-time applications. A stand-alone peer-to-peer library written in C, and designed primarily for use with the Robust Audio Tool, a work of the UCL Network and Multimedia Research Group.
- SVN repository
- Technical report describing the performance of the overlay, written August 2005.
Scala fragments: Dijkstra's shortest-paths algorithm
Dijkstra's algorithm is reasonably easy to implement, but it requires a priority queue with priorities which can be modified efficiently. This is best represented as a priority map, where the ordering of the elements is based on priority, but indexing is based on the data stored.
PriorityMap stores keys of any type, and orders them against an integer priority. The interface is simple: items may be pushed into the queue, or popped off the end of the queue. Pushing a key which is already contained within the structure will reassign its priority. Lower numbers indicate higher priority. These semantics are based on those used by a very similar priority dictionary for Python.
- PriorityMap.scala: The PriorityMap provides efficient (O(log n)) insertions, removals, and reassignments. This may be useful stand-alone, but is required by this implementation of Dijkstra's algorithm.
- Dijkstra.scala:
An implementation of Dijkstra's algorithm, and a test harness to load a
graph and perform the algorithm from an arbitrary starting
point. Integers are used as node identifiers, and so are stored as keys
in the PriorityMap. Input is read from stdin, and the first two
fields of each line must be integers. Other fields in each line are
ignored. Usage is of the form:
- cat Dijkstra.input | scala com.sdstrowes.DijkstraTest
- AllPairs.scala As an example of
how simple it is to parallelise some Scala code, Dijkstra's algorithm
works extremely well. AllPairs accepts a graph in the
same format as above, and computes Dijkstra from every location,
storing the results in a triangular array of distances (since the
distances are symmetric). AllPairs will spawn as many threads as
the operating system reports cores. Usage is of the form:
- cat Dijkstra.input | scala com.sdstrowes.AllPairs