Previous Tutorial Next

Tutorial - Introduction

The ch.bfh.algo framework is extremely usefull for its simplicity to implement pseudo-code algorithms.
The main target of this tutorial is to show some examples of how one can use the framework to write Java programs that use algorithmic data structures, such as lists graphs and trees (or forests in our case).

Data Structures

We will first present the concept of Sequence that extends the java.util.List (of the java collection framework) in a way to implement insertion and removal in the middle of the list in time O(1). This is done using a specific interface Position that is used to mark a place in a list. There are two implementations of the Sequence interface: ArraySequence where the underlying data structure is an array, and LinkedSequence where the underlying data structure is a doubly linked list.
Sequence is fully compatible with the java collection framework java.util.List interface, that means it is generic and iterable (very practicle for writing loops).

The framework contains a support for Graphs. We provide the Graph interface with one implementation DefaultGraph. This data stucture contains two types of elements: edges and vertices. In order to use it, one can simply consider they are both Positions. Graph is also a generic data strucutre, both edges and vertices can receive a different type. We also provide a way to extend the capabilities of the edges and vertices. One can write extensions of the two classes (adding new functionalities). The graph can be created using a specific factory for edges and vertices. So without touching to the graph classes, it is possible to extend the possibilities of the edges and vertices.

The support provided for trees (resp. binary trees) is using the interface Forest (resp. BinaryForest). The implementation allwos to insert nodes (creating a new root in the forest), link two nodes (such that a node becomes the child of another one), cut a branch (which is afterward a new tree). The two data structures make it easy to implement all the algorithms of the literature. All methods are implemented in time O(1), which can hardly be done using a simple tree datastructure.

Previous Tutorial Next