# Algorithms and Data-structures

provides
x-ozlib://duchier/algorithm/DictionaryMatrix.ozf
x-ozlib://duchier/algorithm/Queue.ozf
x-ozlib://duchier/algorithm/Stack.ozf
x-ozlib://duchier/algorithm/graph/AllShortestPaths.ozf
x-ozlib://duchier/algorithm/graph/Edge.ozf
x-ozlib://duchier/algorithm/graph/Node.ozf
x-ozlib://duchier/algorithm/graph/StronglyConnectedComponents.ozf
x-ozlib://duchier/algorithm/graph/TopologicalSort.ozf

## Purpose

Implements useful data-structures and algorithms

### General Data-structures

`{DictionaryMatrix.new Dimensions Default ?D}`
`Dimensions` is a list of lists of keys, where each sublist describes one dimension of the matrix. `Default` is the default value to give to each entry in the matrix.
`{Queue.new ?Q}`
creates a new queue object `Q` which responds to the following methods:
`{Q reset}`
`{Q enqueue(X)}`
`{Q enq(X)`
`{Q dequeue(?X)}`
`{Q deq(?X)}`
`{Q condDequeue(Default ?X)}`
`{Q condDeq(Default ?X)}`
`{Q isEmpty(?B)}`
`{Stack.new ?S}`
creates a stack object `S` which responds to the following methods:
`{S reset}`
`{S push(X)}`
`{S pop(?X)}`
`{S condPop(Default ?X)}`
`{S top(?X)}`
`{S isEmpty(?B)}`

### Graph Data-structures and Algorithms

`{Node.new ?N}`
a node has a feature `id` which uniquely identifies it.
`{Node.getId N ?Id}`
`{Edge.new ?Src ?Dst}`
an edge is created by supplying a source node `Src` and a destination node `Dst`, and has a feature `id` which uniquely identifies it.
`{Edge.getId E ?Id}`
`{Edge.getSrc E ?N}`
`{Edge.getDst E ?N}`
`{AllShortestPaths.compute Graph ?Matrix}`
a graph has a feature `nodes` which is a list of all its nodes, and a feature `edges` which is a list of all its edges. Additionally, it may here have a feature `edge2value` mapping edge ids to numbers and representing the length of the edge. If feature `edge2value` is missing or does not contain an entry for some edge id, then the number 1 is used as a default. The returned value `Matrix` is a 2 dimensional matrix giving for every pairs of node ids the shortest paths between them: this path is a list of nodes. If there is no path (traversing at least 1 edge) between 2 nodes, then the corresponding entry is `unit`. If `Matrix.I.I` is not unit, then it contains the node with id `I` twice: once as the starting point of the loop and once as its end point.
`{StronglyConnectedComponents Graph1 ?Graph2}`
Given a graph `Graph1`, return a new graph `Graph2` where the nodes are actually the strongly connected components of `Graph1`. The nodes of `Graph2` are called components. `Graph2` has a feature `node2value` which maps each component id to a list of nodes of `Graph1` which form a strongly connected component.
`{TopologicalSort.compute Graph1 ?Graph2}`
`Graph1` is expected to be a DAG. `Graph2` is identical to `Graph1` except that the nodes have been topologically sorted according to the precedence induced by the edges. There may be several possible topological orderings: one is chosen arbitrarily.

## Installation

This package can be installed by following the usual configure, build, install procedure, i.e. by executing a the shell: ```./configure make install``` By default, all files of the package are installed in the user's ~/.oz directory tree. In particular, all modules are installed in the user's private cache.

Denys Duchier