Algorithms and Data-structures

Denys Duchier

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.