Crate outils

outils is a graph and tree data structure library. It provides utilities which at the time of writing were not available through other crates.

As of this version of outils, those utilities are:

Fully dynamic connectivity for general graphs: A dynamic graph data structure is able to answer queries as to whether two vertices are connected in a graph through a path of edges. In this context, fully dynamic means that the graph can be updated by insertions or deletions of edges between queries (see also Dynamic Connectivity).

• DynamicGraph: Deterministic dynamic connectivity with query cost O(log(n)) and update costs of O(log^2 (n)). The structure also supports vertex weights, dynamically maintaining the total weight of connected components.

Balanced binary search trees: A balanced binary search tree organizes search keys and their associated payload in a way such that the resulting binary tree has a minimal height, given the number of items stored, resulting in query and update costs of O(log(n)). This library uses AA trees, an abstraction of red-black trees, for balancing the trees after updates.

• AaTree: An iterative AA tree implementation using arena allocation. For most use cases, it is recommended to simply use the BTreeMap provided by the standard library, as it is considerably faster (appr. 50%). However, if information on parent and child relations between tree nodes, or custom traversal of the tree as such, are needed, AaTree has an advantage over BTreeMap.

• WeightedAaTree: This is similar to AaTree. However, in addition to the actual payload, node weights can be stored and tree subweights are maintained.

Balanced binary forests: A balanced binary forest is a forest of balanced binary trees. In contrast to the tree data structures above, the order of the payload is not determined by associated search keys but by the relations of the nodes to each other: the in-order traversal of a forest tree alone represents the order of its nodes. Forest trees can be concatenated or split in order to manage those sequences. Parent and child relations are available, facilitating analysis of the represented sequences.

• AaForest: A forest of trees balanced by the AA tree algorithm. Concatenation and separation do not require a reorganisation of the tree according to search keys - only rebalancing will take place, the order of the sequence being the responsibility of the user. The implementation is based on arena allocation, and tree queries and updates are conducted iteratively, as in the corresponding AA tree structures above.

• WeightedAaForest: This is similar to AaForest. However, in addition to the actual payload, a node weight can be stored and tree subweights are maintained.

General purpose tree data structures:

• Forest: A generic forest of trees. The implementation is based on arena allocation and a first child/next sibling representation, thus storing the children of a node as a linked list headed by the first child of the parent node.

Modules

graph	Graph data structures and algorithms
prelude	Commonly used items.
tree	Tree data structures and algorithms
types	Types that are the basic building blocks of the types and algorithms provided by this library.