**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

Implements useful data-structures and algorithms

`{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)}`

`{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.

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