Source code
Any source code released here is publicly available, and licensed under a BSD-style license.
Network Simulator
An AS-level graph simulator, written in Scala, intended to be widely distributed across many commodity machines.
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
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.