SDS Tools - Simple Data Structures

A comprehensive and educational Python library of fundamental data structures — from linked lists to probabilistic graphical models — and of the classic algorithms that operate on them, implemented with object-oriented programming principles and extensive academic-style documentation.

Package name note: the PyPI/pip distribution is named pysds-tools (sds-tools collides with an existing, unrelated package once PyPI normalizes names). The importable module is unaffected — it's still sds (import sds.linear, import sds.probabilistic, ...).

Goals

• Educational: Clear, well-documented code for learning — not just working code, but code that explains why
• Comprehensive: Exhaustive coverage of classic and advanced data structures
• Typed: Full MyPy strict-mode support, pyright/basedpyright compatible
• Tested: 80–90%+ coverage target per module, enforced via pytest-cov
• Performant: __slots__ on every node and structure class

Installation

pip install pysds-tools

Quick Start

from sds.linear import Stack
from sds.graph import DirectedGraph, GraphNode, DirectedEdge
from sds.probabilistic import BayesianNetwork, Factor, RandomVariable

# Linear structures
stack = Stack()
stack.push(1)
stack.push(2)
stack.pop()  # 2

# Graphs
task_graph = DirectedGraph()
design, backend = GraphNode("Design"), GraphNode("Backend")
task_graph.add_node(design)
task_graph.add_node(backend)
task_graph.add_edge(DirectedEdge(design, backend))
task_graph.is_acyclic()  # True

# Probabilistic graphical models
rain = RandomVariable("Rain", ("true", "false"))
bn = BayesianNetwork()
bn.add_variable(rain)
bn.set_cpt(rain, Factor((rain,), {("true",): 0.2, ("false",): 0.8}))

# Algorithms: free functions that take the structure as argument
from sds.algorithms.graph_algorithms import bfs
from sds.algorithms.sorting import merge_sort

[node.data for node in bfs(task_graph, design)]  # ['Design', 'Backend']
merge_sort([3, 1, 2])  # [1, 2, 3]

Architecture

The project is organized into thematic modules, one per family of structures:

src/sds/
├── core/           # Foundations: AbstractNode, AbstractContainer, exceptions
├── linear/         # Linear structures (linked list, stack, queue)
├── tree/           # Tree structures (binary, AVL, heaps, B-tree, trie, segment tree)
├── graph/          # Graph structures (directed, weighted, adjacency representations)
├── advanced/       # Deterministic advanced structures (disjoint set, Bloom filter, ...)
├── probabilistic/  # Probabilistic graphical models (Bayesian networks, MRF, HMM)
├── algorithms/     # Sorting, tree and graph algorithms, probabilistic inference
└── utils/          # (planned) visualizer, extended exceptions

Available Structures

sds.core — Foundations

Base abstractions shared by every other module: AbstractNode, AbstractContainer, and the common exception hierarchy. Contains no concrete data structure by design — every other module imports from here, never the reverse.

sds.linear — Linear Structures

• LinkedList: doubly linked list — O(1) prepend/append
• Stack: LIFO — push(), pop(), peek(), all O(1)
• Queue: FIFO — enqueue(), dequeue(), all O(1)

sds.tree — Tree Structures

• BinaryTree, AVLTree (self-balancing, guaranteed O(log n)), GeneralTree (n-ary)
• MinHeap, MaxHeap
• BTree, Trie (prefix search), SegmentTree (range queries)

sds.graph — Graph Structures

• Graph, DirectedGraph, UndirectedGraph (strict wrapper — rejects directed edges explicitly rather than silently converting them)
• WeightedGraph, WeightedDirectedGraph
• AdjacencyListGraph (sparse, O(V+E) space), AdjacencyMatrixGraph (dense, O(1) edge lookup)

sds.advanced — Advanced Structures

Deterministic structures that don't fit cleanly into linear/tree/graph:

• DisjointSet (Union-Find, path compression + union-by-rank — O(α(n)) amortized)
• BloomFilter (probabilistic set membership), SkipList (probabilistic sorted structure)
• HashTableChaining, HashTableOpenAddressing
• LRUCache, FenwickTree (binary indexed tree), CountMinSketch (frequency estimation over streams)

sds.probabilistic — Probabilistic Graphical Models

Structures encoding probability distributions over discrete random variables. No inference logic (marginal queries, most-likely-explanation) is implemented here — inference lives in sds.algorithms.probabilistic_algorithms.

• RandomVariable, Factor: shared building blocks (a discrete variable and a potential/CPT table over a scope of variables)
• BayesianNetwork: directed acyclic graphical model with locally normalized CPTs, composes sds.graph.DirectedGraph for topology
• MarkovRandomField: undirected graphical model (cycles allowed) with unnormalized potentials, composes sds.graph.Graph
• HiddenMarkovModel: sequential model over a fixed states/observations pair, with initial/transition/emission components

Available Algorithms

Algorithms are kept out of the structure classes: each one is a free function of sds.algorithms that receives the structure it works on, typed against the broadest abstract interface that provides what it needs.

sds.algorithms.sorting

• merge_sort (stable, returns a new list), quick_sort (in place, not stable) — both with sorted()-style key and reverse

sds.algorithms.tree_algorithms

• inorder, preorder, postorder, level_order: iterative traversals of any binary tree
• is_balanced, rebalance (rebuilds a BinarySearchTree to minimum height)

sds.algorithms.graph_algorithms

• bfs, dfs: traversals of any graph, in reproducible order
• dijkstra: shortest distances and paths, non-negative weights
• kruskal: minimum spanning forest of an undirected weighted graph

sds.algorithms.probabilistic_algorithms

• variable_elimination: exact posterior of query variables
• belief_propagation: every marginal at once (exact on tree-shaped models)
• forward, viterbi: likelihood, filtering and decoding for hidden Markov models

Deprecation (0.7.0): the inorder_traversal(), preorder_traversal(), postorder_traversal() and level_order_traversal() methods of binary trees are deprecated and will be removed in 1.0.0 — use sds.algorithms.tree_algorithms instead, e.g. inorder(tree).

Documentation

Full API reference and user guide, including mathematical foundations, Mermaid diagrams, complexity tables, and real-world examples for every module:

https://pysds-tools.readthedocs.io

Testing

# Run all tests
pytest

# Run with coverage
pytest --cov=sds --cov-report=html

# Run tests for a specific module
pytest tests/06_Probabilistic/

# Run in verbose mode
pytest -v

Test suite layout (mirrors the source tree, one directory per module):

tests/
├── 01_Core/
├── 02_Linear/
├── 03_Tree/
├── 04_Graph/
├── 05_Advanced/
└── 06_Probabilistic/

Static Analysis

The project is fully typed and verified with mypy, flake8, and bandit:

mypy src/sds/
flake8 src/sds/
bandit -r src/sds/

Or, via tox:

tox -e mypy,flake8,bandit

Contributing

Contributions are welcome!

1. Fork the project
2. Create a branch for your feature (git checkout -b feature/AmazingFeature)
3. Commit your changes following Conventional Commits
4. Push to the branch (git push origin feature/AmazingFeature)
5. Open a Pull Request

Full project conventions (labels, issue templates, commit format, versioning, releases) are documented in CONVENTIONS.md in the shared .github repository.

Quality Standards

• ✅ Type-checked with mypy (strict mode)
• ✅ Style-compliant with flake8
• ✅ Security-checked with bandit
• ✅ Tests with pytest (80–90%+ coverage target)
• ✅ NumPy-style docstrings
• ✅ __slots__ on all node and structure classes

Roadmap

v0.1.0–v0.5.0 — Foundations through Advanced Structures ✅ Completed

• sds.core, sds.linear, sds.tree, sds.graph, sds.advanced — fully implemented, tested, and documented

v0.6.0 — Probabilistic Structures ✅ Completed

• sds.probabilistic: BayesianNetwork, MarkovRandomField, HiddenMarkovModel

v0.7.0 — Algorithms ✅ Completed (this release)

• sds.algorithms: sorting (MergeSort, QuickSort), tree traversals and rebalancing, graph algorithms (BFS, DFS, Dijkstra, Kruskal), probabilistic inference (Variable Elimination, Belief Propagation, Forward, Viterbi)

v0.8.0 — Utilities Planned

• Shared visualizer, extended exception hierarchy

v0.9.0–v1.0.0 — Quality Consolidation & Stable Release Planned

• Full coverage/mypy sweep, documentation polish, first stable API

v1.1.0–v1.2.0 — French Translation Planned

• Bilingual documentation via a dedicated ReadTheDocs project

License

This project is licensed under the Apache License 2.0 — see the LICENSE file for details. Documentation is licensed separately under CC BY-NC 4.0 — see docs/source/license.rst.

Acknowledgments

• Inspired by classic data structures and algorithms courses
• Designed for learning
• Thanks to the Python community for exceptional tools (pytest, mypy, flake8, bandit, Sphinx, Furo)

Resources

• Python Documentation
• Type Hints — PEP 484
• NumPy Docstring Guide
• Probabilistic Graphical Models — Stanford CS228 notes (open-access reference for sds.probabilistic)

---

GitLab mirror: https://gitlab.com/open-works/sds